## A Monkey and a Typewriter

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

silverhammermba
Posts: 178
Joined: Fri Oct 13, 2006 1:16 am UTC

### A Monkey and a Typewriter

A relatively simple problem:

You have a monkey and a typewriter. The monkey hits one key of the typewriter at random with each letter (a-z) having an equal probability of being hit. Now, on average, would the word "abracadabra" appear before, after, or at the same time as "abcdefghijk"?

Anti-pedantist Edit:
What I mean is, if you performed a very large amount of trials, stopping each time when either abracadabra or abcdefghijk appeared, which one, statistically, would have taken less time to appear on average? (Or would they both take just as long)
Last edited by silverhammermba on Mon Oct 30, 2006 6:47 am UTC, edited 2 times in total.

Verysillyman
"Do me! Do me!"
Posts: 1442
Joined: Sat Aug 19, 2006 11:25 am UTC
Location: Drinks Cabinet.
Contact:
Is this worth an answer thread? I'll just wait a while before i say anything.

GreedyAlgorithm
Posts: 286
Joined: Tue Aug 22, 2006 10:35 pm UTC
Contact:

### Re: A Monkey and a Typewriter

silverhammermba wrote:A relatively simple problem:

You have a monkey and a typewriter. The monkey hits one key of the typewriter at random with each letter (a-z) having an equal probability of being hit. Now, on average, would the word "abracadabra" appear before, after, or at the same time as "abcdefghijk"?

Pedantic mode activate! It's not possible that abracadabra ever appears at the same time as abcdefghijk since we have only 1 monkey. Rephrased: is the expected number of keys hit before "abracadabra" is typed less than, greater than, or the same as the expected number of keys hit before "abcdefghijk" is hit?
GENERATION 1-i: The first time you see this, copy it into your sig on any forum. Square it, and then add i to the generation.

svk1325
Posts: 139
Joined: Mon Jul 17, 2006 9:10 am UTC
Location: Take a guess...
Contact:

### Re: A Monkey and a Typewriter

possible spoilers? wrote:If it is truly random, both have an equal chance of appearing after some amount of time. Probability doesn't care about the past. You can flip a coin 100 times and get all heads. The chances are still going to be 1/2 heads, 1/2 tails on the next flip.

The problem is similiar to continously flipping a coin and asking "Which will come first, 10 heads in a row, or 10 tails in a row?" Now replace "continously flipping a coin" with "randomly typing letters from a-z" and "10 heads in a row, or 10 tails in a row?" with "abcdefghijk, or abracadabra?" We have the same thing, but just with different amounts of time needed and different possibilities. The outcomes are still random compared to each other.

1/26 chance the first letter is "a"
1/26 chance the next will be "b"

1) "abcdefghijk"
1/26 chance the third will be "c"
1/26 chance the fourth will be "d"
....
1/(26^11) chance "abcdefghijk" will be spelled out

1/26 chance the third will be "c"
1/26 chance the fourth will be "d"
....
1/(26^11) chance "abracadabra" will be spelled out

You can't say anything about when they will appear relative to each other. That will also be completely random. We can, however predict on average how often they will appear. Random compared to random is something we can't.

If our chances of seeing either of them is 1 in 1.8*10^15 and the monkey hits, say 10 keys per second, why should we wait the average of 40 million years to see the truth?
Last edited by svk1325 on Mon Oct 30, 2006 7:37 am UTC, edited 1 time in total.
"Insanity in a measured dose is a good thing - the difficulty lies in the measurement."

phlip
Restorer of Worlds
Posts: 7572
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:
Spoilers wrote:But consider if I flip a coin a bunch of times, and ask "Which pattern came first... HH or TH"? The only way that HH can come before TH is if the first two flips were both heads... if one of the first two flips are tails, then you will certainly get TH before you get HH. So TH will come before HH 3 times in 4.

Code: Select all

`enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}`
[he/him/his]

Gelsamel
Lame and emo
Posts: 8237
Joined: Thu Oct 05, 2006 10:49 am UTC
Location: Melbourne, Victoria, Australia

### Re: A Monkey and a Typewriter

svk1325 wrote:
possible spoilers? wrote: We can, however predict on average how often they will appear.

Fixed.

Edit:

phlip wrote:
Spoilers wrote:But consider if I flip a coin a bunch of times, and ask "Which pattern came first... HH or TH"? The only way that HH can come before TH is if the first two flips were both heads... if one of the first two flips are tails, then you will certainly get TH before you get HH. So TH will come before HH 3 times in 4.

Dun dun duuuuuuuun!

I guess that extends past 2?

svk1325
Posts: 139
Joined: Mon Jul 17, 2006 9:10 am UTC
Location: Take a guess...
Contact:

### Re: A Monkey and a Typewriter

Gelsamel wrote:
svk1325 wrote:
possible spoilers? wrote: We can, however predict on average how often they will appear.

Fixed.

Heh, oops. I edited it. My brain is in a jumble since it's 1:30 AM over here.

phlip wrote:
Spoilers wrote:But consider if I flip a coin a bunch of times, and ask "Which pattern came first... HH or TH"? The only way that HH can come before TH is if the first two flips were both heads... if one of the first two flips are tails, then you will certainly get TH before you get HH. So TH will come before HH 3 times in 4.

"Insanity in a measured dose is a good thing - the difficulty lies in the measurement."

phlip
Restorer of Worlds
Posts: 7572
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:
But "abracadabra" also contains an "ab" in the middle... so if "ab" has just been typed, it could be the start of "abcdefghijk", the start of "abracadabra", or the middle of "abracadabra"

spoiler wrote:Ok, so maybe that doesn't matter so much... the first "ab" typed has an equal chance of being the start of "abcdefghijk" as "abracadabra"... and if it's neither, then the second "ab" typed has an equal chance of being either... when you look at it this way, the chance that a particular "ab" is the middle of an "abracadabra" is 0...

I could, however, be wrong here... I'm not certain this is right...

Code: Select all

`enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}`
[he/him/his]

svk1325
Posts: 139
Joined: Mon Jul 17, 2006 9:10 am UTC
Location: Take a guess...
Contact:
spoilers wrote:Any string of "ab" in much more likely to be the start of one of the strings instead of the middle of "abracadabra." An "ab" in the middle of "abracadabra" needs "abracad" correctly typed out directly before it. The letter case is 1/(26^7) and the former is the complement to this probability. Otherwise, "ab" is 8,031,810,175 times more likely to be the start rather than the middle. Besides, there's still that 25/26 chance that, after all of that luck, the wrong letter will be typed next.
"Insanity in a measured dose is a good thing - the difficulty lies in the measurement."

yy2bggggs
Posts: 1261
Joined: Tue Oct 17, 2006 6:42 am UTC

### Re: A Monkey and a Typewriter

The spoiler fairy wrote:Expect to see abracadabra first before abcdefghijk, due to the fact that finite "misses" in the latter require you to start over from scratch to get a hit ("abcd abcd...") whereas finite "misses" in the former don't always do the same ("abr a brac...", "a' is common with the miss "abrab" and the start of a potential hit "abrac")... this leads to sequences that produce abracadabra being slightly shorter on average.

The "ab" part in the middle is irrelevant, as a "hit" leading into a "miss" in this case, which starts you out into the next "hit", doesn't save you characters (once you have "abracadab", to get the first part of "abracadabra" again requires "abra", which means you already have the word spelled out.)
Last edited by yy2bggggs on Mon Oct 30, 2006 5:08 pm UTC, edited 1 time in total.

phlip
Restorer of Worlds
Posts: 7572
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:
z0mgspoiler wrote:But if you do miss like that and end up with "abrab", surely you'd be just as likely to get "abrabcdefghijk" at this point as "abrabracadabra"?

Code: Select all

`enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}`
[he/him/his]

yy2bggggs
Posts: 1261
Joined: Tue Oct 17, 2006 6:42 am UTC
Doesn't matter. abrabcd is no shorter than xxxabcd, so with the abcd sequence, the "abra" is just as good as random letters and a single occurrence of "a"--the "abr" part is irrelevant.

What is relevant is that "abrabracadabra" is shorter than "abraabracadabra"--the "mistaken" abra form doesn't require a do-over.

Another way to say it: Given that "ABRA" occurs, you can possibly get "ABRACADABRA" without starting over in 2 ways--by getting a "B" next, or getting a "C" next. Given that "ABRA" occurs, you can only get "ABCDEFGHIJK" without starting over 1 way--"B" has to occur next. Other than this type of thing occurring, every other required letter, be it patterned or "random", is just 1/26.

svk1325
Posts: 139
Joined: Mon Jul 17, 2006 9:10 am UTC
Location: Take a guess...
Contact:
you know what this is... wrote:They are still equally as likely is the case of "abrabcdefghijk" or "abrabracadabra". It just so happens that the first 3 letters starts one of the strings. The mess-up nullifies any significance of this. Both of the above possibilities are just coincidences of probability. There was a 1/(26^3) of you seeing it like that, and it just so happens that you did see it this time. This case has the same probability of "dfeabcdefghijk" or "dfeabracadabra," it's just that the "abr" pops out to our eyes more that the "dfe" since it's part of a string. Because of the mess-up, this case is the same as "???abcdefghijk" or "???abracadabra," which has basically no significance whatsoever.
"Insanity in a measured dose is a good thing - the difficulty lies in the measurement."

ly_yng
Posts: 14
Joined: Wed Oct 25, 2006 5:36 am UTC
I think I've got it.

Phlip had the right idea with (1) TH vs (2) HH. The next step is allowing something like a third side to the coin, which you can call Q. Getting a Q is like resetting the order and starting from scratch. Even with the Q in there, a (1) TH is more likely to come up than a (2) HH, always.

This is because there is a non-Q route from H to T, but a non-Q route from T to H would truncate the series. Getting a Q just starts things over, but doesn't change this fact. We can jump from a (2) path to a (1) path, but not from a (1) path to a (2) path, and this means that (1) is more likely.

So now lets look at (1) ABRACADABRA vs. (2) ABCDEFGHIJK. The big difference between this and the last case is that there are many, many more Qs available. The monkey will type random letters, and eventually we'll get our first AB. What can happen now?

We've got an even chance of getting an RA or a CD. There are also a lot of Qs that will just reset the pattern. We have a path to (1) with RA, and a path to (2) with CD. From CD, we have a small chance of getting EFGHIJK, or we might get a Q. There is definetly no way to jump to (1), however.

From RA, we can get either CADAB, or one of many Qs. This is really the key juncture. From here, we have an even chance of getting an RA or a CD. We also might get one of many Qs. If we get an RA, we finish path (1). If we get a Q, we start from scratch. But if we get a CD, we essentially jump to the QABCD junction. That is, we jump from path (1) to path (2). Just like before, the ability to jump from (1) to (2), but not from (2) to (1), means that path (2) is more likely.

Thus, abcdefghijk is more likely than abracadabra.

Oh, and this is all dependent on the strings having the same number of characters.

[/code]

ly_yng
Posts: 14
Joined: Wed Oct 25, 2006 5:36 am UTC
Umm...

On second thought

I seem not to have answered the question.

abcdefghijk is more likely than abracadabra. I stand by that one. However, that doesn't answer the question of which one takes less time, on average.

Going back to HH vs. TH again. HH can happen only one way, with two consecutive heads. TH can happen many ways, like HTH, or HTTH, or TTH or TTTTTH, etc. Thus, on average, though more likely, the average # of letters for TH will take longer.

Now looking at abracadabra vs abcdefghijk, I think that this same reasoning will show that abracadabra will, on average, take fewer letters to appear than abcdefghijk, although it will come up more often. That's because, from ABRACADAB, an RA will terminate the string, while a CD will allow a longer string with ABCD through.

So I stand by my original claim, although now, I'm actually answering the question.

abracadabra is generally the end of a shorter string than abcdefghijk.

svk1325
Posts: 139
Joined: Mon Jul 17, 2006 9:10 am UTC
Location: Take a guess...
Contact:
******* wrote:I know this is almost completely changing my mind about this, but we need to realize that the second string, "abracadabra" contains part of itself. We can think of the alternative between "abcdefghij" and "abracad" 1 1/2 times (technically 11/7 times, but it gets the point across). I dunno how this changes the probability, but it would seem that it should remain the same. I'll try to figure it out later on.

edit wrote:Ok, I've got it. I also took into consideration of the "path cross". If there's a flaw in this, please tell me.
(# = "none of the above")

1st letter
A (1/26)
# (25/26)
2nd letter
B (1/26)
# (25/26)
3rd letter
C (1/26) -> "abcdefghijk"
# (24/26)
-----
"abcdefghijk"
4th letter
D (1/26)
# (25/26)
5th letter
E (1/26)
# (25/26)
6th letter
F (1/26)
# (25/26)
7th letter
G (1/26)
# (25/26)
8th letter
H (1/26)
# (25/26)
9th letter
I (1/26)
# (25/26)
10th letter
J (1/26)
# (25/26)
11th letter
K (1/26)
# (25/26)
~~~~~
4th letter
R ( 1/26)
# (25/26)
5th letter
C (1/26)
# (25/26)
6th letter
A (1/26)
# (25/26)
7th letter
D (1/26)
# (25/26)
8th letter
A (1/26)
# (25/26)
9th letter
B (1/26)
# (25/26)
10th letter
R (1/26)
C (1/26) -> "abcdefghijk"
# (24/26)
11th letter
A (1/26)
# (25/26)
~~~~~
Probabilities:
"abcdefghijk"
1/26^11 (single pass)
Total: 2.724539899918760 * 10^-16

1/26^11 (single pass)
Total: 2.724539899579542 * 10^-16

So there you go, "abcdefghijk" in slightly (1 part per 10^10) more likely to appear than "abracadabra." Yeah... that's practically zero difference. Then again, 2.724 * 10^-16 is practically zero also...

Okay... much longer than I thought. Sorry.
"Insanity in a measured dose is a good thing - the difficulty lies in the measurement."

Torn Apart By Dingos
Posts: 817
Joined: Thu Aug 03, 2006 2:27 am UTC
Man, these spoiler boxes are really annoying.

silverhammermba
Posts: 178
Joined: Fri Oct 13, 2006 1:16 am UTC
The answer! Don't read this if you want to figure out the problem for yourself!!!

The person who knows the answer wrote:abcdefghijk is statistically more likely to appear than abracadabra. This can be verified very simply and without any tricky math at all.
Let's assume that right from the beginning by some freak chance, the monkey has typed 10 of the 11 letters of one of the sequences. Kind of like svk1325 first said, up to this point both strings of letters are equally likely to appear since each key press is independent of the others.
If the monkey has typed abracadabr then he has only two options for his next key press: he types A or not A. If he types A (1/26 chance) he finishes the word and we're done, otherwise (25/26) he has to start the entire thing over again.
If, however, the monkey has typed abcdefghij, then he actually has three options. Obviously one is that he could type K with a 1/26 chance of completing the string. The big difference here is that there is also a 1/26 chance that the monkey could type an A. In that case he wouldn't complete the string but he would already have a one letter head start on trying to type it again. And then of course there's the 12/13 chance that he totally screws up and has to start over entirely.

So, it can be seen that they key difference between the two words is that one starts and ends with the same letter, while the other does not thus allowing a very slight advantage.

svk1325
Posts: 139
Joined: Mon Jul 17, 2006 9:10 am UTC
Location: Take a guess...
Contact:
Dang it, that was much simpler that I thought. And I wind up making a huge quote box (spoiler box, if you will) to state the wrong reason. Well, I got the problem right... that's 1/2 right
"Insanity in a measured dose is a good thing - the difficulty lies in the measurement."

umbrae
Posts: 336
Joined: Sat Sep 09, 2006 2:44 pm UTC
Contact:
But that doesn't make sense either, because the same chance to start over can be found at 'abraca', where he could either get a 'd' and keep going, or get a 'b' and have a 1-letter head start. It seems that would lead to a similar situation.

Although I guess thinking in general, since there are so many 'a's in abracadabra, the 2-letter reset doesn't occur as often in abracadabra. Alright, I think I've wrapped my head around this one. Interesting puzzle!

planck
Posts: 8
Joined: Thu Nov 16, 2006 9:45 am UTC
silverhammermba wrote:The answer! Don't read this if you want to figure out the problem for yourself!!!

A dissenting opinion wrote:That's answering a slightly different question: "If you ran a bunch of trials stopping at the first abcdefghijkl, and you ran a bunch of trials stopping at the first abracadabra, which would be shorter on average?" The question specified stopping when either sequence came out, and dividing these sequences up.

To more clearly see the subtle difference, consider a much simpler scenario. There are only two letters (a,b) and shorter strings (aa,ab).

Suppose we stop at the first "aa": The sequences will match the pattern (b*a)+a and have a mean length of 5.
Suppose we stop at the first "ab": The sequences will match the pattern b*a+b with a mean length of 4.
This is in agreement with your argument: the mismatch between the last and first letter of the latter string gives a greater probability (in this case 1) of being a step ahead for the next possibility of matching.

But suppose we stop at the first aa or ab, analogously to the original question. Now the sequences will match (b*)a(a|b), with a mean length of 3 regardless of whether the last letter is a or b. Changing the termination condition changes the mean lengths of the sequences in both cases. The argument no longer holds.

AllTooHuman
Posts: 26
Joined: Thu Nov 09, 2006 9:58 pm UTC
Location: 127.0.0.1
I agree with planck/svk1325 (and I had to edit)...

Let's call "ABCDEFGHIJK" Series-2

My answer and why I agree with planck/svk1325 wrote:When Series-2 expects a 'K', but instead gets an 'A', neither series is at an advantage: because both series start with 'A'. It is just as likely that this bad 'A' will start off Series-1 as it would Series-2.

Again, we need a sequence of 11 correct keys to win. This 'A' is the required key to start both series, so neither series is at an advantage here.

Neither series has an advantage when the other series breaks on the last letter.

However, Series-2 has an advantage when Series-1 breaks here:

An R here continues Series-1, but a C here gives us the first three letters of Series-2, putting it at an advantage. Doesn't it?

Edit: Just realized this is pretty much what svk1325 said...

Sorry for the edits..

Twasbrillig
Tawsbirlig
Posts: 1942
Joined: Mon Nov 20, 2006 5:50 am UTC
you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you you
Last edited by Twasbrillig on Fri Jun 22, 2007 5:19 am UTC, edited 9 times in total.

phlip
Restorer of Worlds
Posts: 7572
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:
Spoilers wrote:No, the statements about TH vs HH are true. The answer to the question "If I was to flick a coin twice, would TH be more or less likely than HH?" is of course "They're both the same", but the answer to the question "If I was to continually flick a coin until I recieved either a TH or an HH at some point in the sequence, which is more likely to happen first?" is TH, by a 3:1 factor. And the answer to the question "Of the coin sequences that end in HH before TH is reached, and the sequences that end in TH before HH is reached, which is shorter on average" is HH, since a sequence that ends HH before a TH is reached is always exactly 2 flips long, but a sequence that ends TH is an average of 3 1/3 flips long (I think... I haven't checked my working on the 3 1/3 figure... but it's certainly more than 2).

The three are very different questions, and it's fallacious to apply reasoning designed for one to any of the others.

Code: Select all

`enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}`
[he/him/his]

nuggetmonkey
Posts: 45
Joined: Wed Nov 15, 2006 2:52 am UTC

### almost

The important thing is the string "abra" comes both at the beginning and the end of "abracadabra".

There is a 1 in 26^11 chance of the monkey typing either "abracadabra" or "abcdefghijk".

However, once he spells "abracadabra," there is a 1 in 26^7 chance that the next letters will be "cadabra", which would count as spelling abracadabra twice. This is MUCH more likely than spelling either "abracadabra" or "abcdefghijk".

nuggetmonkey
Posts: 45
Joined: Wed Nov 15, 2006 2:52 am UTC
by the way, how do I get the white text box?

no-genius
Seemed like a good idea at the time
Posts: 4221
Joined: Wed May 17, 2006 6:32 pm UTC
Location: UK
Contact:
nuggetmonkey wrote:by the way, how do I get the white text box?

Use white text inside quotes
I don't sing, I just shout. All. On. One. Note.
Official ironmen you are free, champions officially

The Mighty Thesaurus wrote:Why? It does nothing to address dance music's core problem: the fact that it sucks.

Twasbrillig
Tawsbirlig
Posts: 1942
Joined: Mon Nov 20, 2006 5:50 am UTC

### Re: almost

nuggetmonkey wrote:

The important thing is the string "abra" comes both at the beginning and the end of "abracadabra".

There is a 1 in 26^11 chance of the monkey typing either "abracadabra" or "abcdefghijk".

However, once he spells "abracadabra," there is a 1 in 26^7 chance that the next letters will be "cadabra", which would count as spelling abracadabra twice. This is MUCH more likely than spelling either "abracadabra" or "abcdefghijk".

That doesn't work because once he's typed it, that's it. If it were typing it twice, then yes, but that doesn't affect the problem.

Twasbrillig
Tawsbirlig
Posts: 1942
Joined: Mon Nov 20, 2006 5:50 am UTC
phlip wrote:
Spoilers wrote:No, the statements about TH vs HH are true. The answer to the question "If I was to flick a coin twice, would TH be more or less likely than HH?" is of course "They're both the same", but the answer to the question "If I was to continually flick a coin until I recieved either a TH or an HH at some point in the sequence, which is more likely to happen first?" is TH, by a 3:1 factor. And the answer to the question "Of the coin sequences that end in HH before TH is reached, and the sequences that end in TH before HH is reached, which is shorter on average" is HH, since a sequence that ends HH before a TH is reached is always exactly 2 flips long, but a sequence that ends TH is an average of 3 1/3 flips long (I think... I haven't checked my working on the 3 1/3 figure... but it's certainly more than 2).

The three are very different questions, and it's fallacious to apply reasoning designed for one to any of the others.

Mathematically, TH is equally likely to HH. Empirically (as in if you were to actually do it) the odds are 3:1.

TH, mathematically, does not = HT.

So you can get:

HH
TT
HT
TH.

1/4 chance of any of them.

nuggetmonkey
Posts: 45
Joined: Wed Nov 15, 2006 2:52 am UTC
That doesn't work because once he's typed it, that's it. If it were typing it twice, then yes, but that doesn't affect the problem.

Yes, you are right.

Dang.

FiddleMath
Posts: 245
Joined: Wed Oct 11, 2006 7:46 am UTC
Contact:
I... actually, I just had almost exactly this on a problem set I turned in just this morning. (It started "An immortal monkey, with a typewriter with two keys . . .") The analysis is actually pretty neat. Let's see if anyone can figure this out:

Say the monkey is generating 0 and 1, with a 50% chance of each. What is the precise expected time until she generates a given binary word w of length n? As we've already seen, this time is dependent not only on the length of w, but also the structure of w.

(Yes, this is hairy, and you need a fair amount of probability. But it's really quite nifty.)

edit: silverhammermba: are you in that class? I mean, it's a somewhat wild coincidence, now that I think about it.

svk1325
Posts: 139
Joined: Mon Jul 17, 2006 9:10 am UTC
Location: Take a guess...
Contact:
You can't compare this case to the TH, HH case. The reason is because our analogy shows two strings where one contains of 50% of the other. The case presented here has neither string even close to containing 50% of the other. You can use some facts for comparison, but you can't base your entire theory and reasoning on it.
"Insanity in a measured dose is a good thing - the difficulty lies in the measurement."

Gelsamel
Lame and emo
Posts: 8237
Joined: Thu Oct 05, 2006 10:49 am UTC
Location: Melbourne, Victoria, Australia
Even 0.0001 percent is more chance..

phlip
Restorer of Worlds
Posts: 7572
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:
svk1325 wrote:
You can't compare this case to the TH, HH case. The reason is because our analogy shows two strings where one contains of 50% of the other. The case presented here has neither string even close to containing 50% of the other. You can use some facts for comparison, but you can't base your entire theory and reasoning on it.

sp0iler wrote:The TH/HH case is intended not as an analogy to solve the puzzle itself, but more to show that the puzzle's structure means that the standard "they're the same length so they have the same chance" rule doesn't apply, and you have to look deeper. TH will come before HH more often than vice-versa, so it's reasonable to think that one of abcdefghij and abracadabra will come before the other more often than vice-versa. The analogy doesn't say which way around it would go, but it says it's possible that they're not equally likely, as it would intuitively seem.

Twasbrillig wrote:Mathematically, TH is equally likely to HH. Empirically (as in if you were to actually do it) the odds are 3:1.

If your mathematical model says the chances are equal, and if the chances are actually 3:1, then the mathematical model is wrong, and the correct mathematical model will give a result of 3:1.

Code: Select all

`enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}`
[he/him/his]

Twasbrillig
Tawsbirlig
Posts: 1942
Joined: Mon Nov 20, 2006 5:50 am UTC
phlip wrote:
svk1325 wrote:
You can't compare this case to the TH, HH case. The reason is because our analogy shows two strings where one contains of 50% of the other. The case presented here has neither string even close to containing 50% of the other. You can use some facts for comparison, but you can't base your entire theory and reasoning on it.

sp0iler wrote:The TH/HH case is intended not as an analogy to solve the puzzle itself, but more to show that the puzzle's structure means that the standard "they're the same length so they have the same chance" rule doesn't apply, and you have to look deeper. TH will come before HH more often than vice-versa, so it's reasonable to think that one of abcdefghij and abracadabra will come before the other more often than vice-versa. The analogy doesn't say which way around it would go, but it says it's possible that they're not equally likely, as it would intuitively seem.

Twasbrillig wrote:Mathematically, TH is equally likely to HH. Empirically (as in if you were to actually do it) the odds are 3:1.

If your mathematical model says the chances are equal, and if the chances are actually 3:1, then the mathematical model is wrong, and the correct mathematical model will give a result of 3:1.

*sigh*...

I've had to explain this a lot.

When you flip 2 coins, there is 4 possible outcomes.

HH
HT
TH
TT.

So mathematically, there is a 1 in 4 chance to get any of them (and don't bother with that old "heads-is-heavier" argument). Were one to actually do it, the odds are 3:1. If you flip heads on the first flip (50% chance), the odds of flipping heads again are 50%, so the odds of getting HH is 25%. If you flip heads and then tails, and then tails or heads, the odds are increased that you'll get either HT or TH BEFORE the flip. AFTER the flip, the odds are 0%, unless you got them. Mathematically, you SHOULD have a 25% chance, but its really 3:1.

phlip
Restorer of Worlds
Posts: 7572
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:
That's the right answer, but to the wrong question.

It's not "if I flip 2 coins, what happens?", it's "if I keep flipping this coin until I get either HH or TH somewhere in the sequence, and then stop, which is more likely?"

Thus there are many possible outcomes:
HH
TH
HTH
TTH
HTTH
TTTH
HTTTH
TTTTH
HTTTTH
TTTTTH
etc
The first two are the possibilities where you start with HH or TH, the rest of the infinite list are the possibilities where you start with HT or TT. As they get longer, they of course get less likely... and if you do the math then you get a 1/4 chance that you get HH, and a 3/4 chance that you get one of the others, all of which end in TH.

I'll say it again - it's completely meaningless to say "The math says X but if you actually did it you'd get Y". If actually doing it would get you Y, then the math should say Y, and if it doesn't then you're doing it wrong, or using the wrong model. Indeed, how would you get the Y value in the first place, if not through a different angle of math?

Code: Select all

`enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}`
[he/him/his]

no-genius
Seemed like a good idea at the time
Posts: 4221
Joined: Wed May 17, 2006 6:32 pm UTC
Location: UK
Contact:
phlip wrote:It's not "if I flip 2 coins, what happens?", it's "if I keep flipping this coin until I get either HH or TH somewhere in the sequence, and then stop, which is more likely?"

Yeah, isn't that not a probability question? In fact, is the actual question even meaningful?
I don't sing, I just shout. All. On. One. Note.
Official ironmen you are free, champions officially

The Mighty Thesaurus wrote:Why? It does nothing to address dance music's core problem: the fact that it sucks.

phlip
Restorer of Worlds
Posts: 7572
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:
no-genius wrote:Yeah, isn't that not a probability question? In fact, is the actual question even meaningful?

How is it not a probability question? It's a test, the result could go either way, it's well-defined what each result is, and chance is the only determining factor...

Code: Select all

`enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}`
[he/him/his]

no-genius
Seemed like a good idea at the time
Posts: 4221
Joined: Wed May 17, 2006 6:32 pm UTC
Location: UK
Contact:

### Re: A Monkey and a Typewriter

silverhammermba wrote:A relatively simple problem:

You have a monkey and a typewriter. The monkey hits one key of the typewriter at random with each letter (a-z) having an equal probability of being hit. Now, on average, would the word "abracadabra" appear before, after, or at the same time as "abcdefghijk"?

before : 1/2
after: 1/2
same time: 0

That clear it up?
I don't sing, I just shout. All. On. One. Note.
Official ironmen you are free, champions officially

The Mighty Thesaurus wrote:Why? It does nothing to address dance music's core problem: the fact that it sucks.

phlip
Restorer of Worlds
Posts: 7572
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:
The whole point of the "TH/HH" example is that it's not necessarily that simple...

Code: Select all

`enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}`
[he/him/his]