Author 
Topic: Expected number of throws before n heads in a row (Read 33245 times) 

NickH
Senior Riddler
Gender:
Posts: 341


Expected number of throws before n heads in a row
« on: May 30^{th}, 2004, 1:40pm » 
Quote Modify

What is the expected number of times you would have to toss a fair coin in order to obtain n consecutive heads? For example, you could obtain two consecutive heads as follows: HH (2 tosses) THH (3 tosses) HTHH (4 tosses) ... and so on.


IP Logged 
Nick's Mathematical Puzzles



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Expected number of throws before n heads in a
« Reply #1 on: May 30^{th}, 2004, 2:35pm » 
Quote Modify

N + the expected length of a sequence [e](which doesn't end on a H)[/e] with less than N consecutive heads ..

« Last Edit: May 30^{th}, 2004, 2:40pm by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7527


Re: Expected number of throws before n heads in a
« Reply #2 on: May 30^{th}, 2004, 2:49pm » 
Quote Modify

It's 1+(expected throws to get heads). Because after 1 throw, the probability of getting the same side again is the same as the probability of getting heads. So my answer is: 3.


IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Expected number of throws before n heads in a
« Reply #3 on: May 30^{th}, 2004, 10:59pm » 
Quote Modify

Let E(k) be the expected number of tosses required immediately after a string of k heads: E(k) = 1/2 [ 1+E(k+1) ] + 1/2 [ 1+E(0) ], for k<n, E(n) = 0. We may write E(k+1) = 2E(k)  2  E(0), and easily convince ourselves that E(k) = E(0)  2^{k+1} + 2, and since E(n) = E(0)  2^{n+1}+2 = 0, E(0) = 2^{n+1}  2. ::


IP Logged 



ThudnBlunder
wu::riddles Moderator Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489


Re: Expected number of throws before n heads in a
« Reply #4 on: May 31^{st}, 2004, 1:10am » 
Quote Modify

Quote: LOL!

« Last Edit: May 31^{st}, 2004, 2:52am by ThudnBlunder » 
IP Logged 
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.



Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7527


Re: Expected number of throws before n heads in a
« Reply #5 on: May 31^{st}, 2004, 8:32am » 
Quote Modify

Oops. Right answer to the wrong question. What I solved is the expected number of throws to get 2 times the same side. If we want only HH, then it is twice that value. And if I develop for the general case, I find like Eigenray.

« Last Edit: May 31^{st}, 2004, 9:36am by Grimbal » 
IP Logged 



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: Expected number of throws before n heads in a
« Reply #6 on: May 31^{st}, 2004, 7:55pm » 
Quote Modify

T&B  Thanks for the link! I have often heard of this bill, but never before seen the actual thing. As the accompanying article points out, the bill itself does not appear to assign "3" as the value of [pi], even though apparently the author claimed it did. But instead, it assigns 4 other values to [pi] (none even good approximations) at various times. I also note that contrary to common claim, it appears that the Indiana legislature did not think they could decide mathematical truth by legislative fiat. Rather, being not so educated as to be able to cut through the heavy b.s. in this bill (I found it extremely taxing, and was unable to determine the meaning of some phrases), they thought that they were being given the chance to adopt proven new discoveries into their education curriculum without inccuring added costs. They were hoodwinked into thinking that these results were proven by false claims of peer review (at least, I find it highly doubtful that the American Mathematical Monthly ever accepted this load of bunk). It would appear that much of the ridicule of the Indiana Legislature induced by this action was undeserved (much, but not all  they still should have checked with real mathematicians before voting  but this sort of mistake is made by legislatures all the time).


IP Logged 
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? "  Anonymous



ThudnBlunder
wu::riddles Moderator Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489


Re: Expected number of throws before n heads in a
« Reply #7 on: May 31^{st}, 2004, 9:05pm » 
Quote Modify

Quote:...but this sort of mistake is made by legislatures all the time). 
 There was also an extremely successful April Fool's Day hoax.

« Last Edit: May 31^{st}, 2004, 9:44pm by ThudnBlunder » 
IP Logged 
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.



william wu
wu::riddles Administrator
Gender:
Posts: 1291


Re: Expected number of throws before n heads in a
« Reply #8 on: Jul 27^{th}, 2004, 5:10am » 
Quote Modify

I know a sweet way to do this problem, from martingale theory. This approach may at first seem unnecessarily complicated, but it has the advantage of being robust enough to easily solve more difficult questions, such as In drawing lowercase English letters a through z uniformly at random, the expected time till you see willywilly is 26^10 + 26^5. In drawing numerals over 09 uniformly at random, the expected time till you see 1231231 is 10^7 + 10^4 + 10. In flipping a fair coin, the expected time till you see HTHTTHT is 2^7 + 2^2. This is a worthwhile technique to know for analyzing the time till certain patterns occur in random processes. Here's the argument; hopefully after reading it you'll feel it was worth your time ... First imagine a casino which contains only one game  the game of betting on whether a fair sided coin comes up heads or tails. The odds are fair, meaning that if you bet $X on a guess and you are correct, you get $2X back as reward; otherwise you lose $X. Now for the gamblers. At every time step, a new gambler enters the casino, to join the existing pool of gamblers inside. Now, all the gamblers use the same policy. Each comes in with only $1, and they progressively bet all their monies on the sequence H^{n} = HHHH ... H. So for example, at time 1, gambler #1 appears; we will denote him by G_{1}. He bets $1 on H. If he wins, he gets $2 back  all of which he bets on H in the next time step. And so forth. If he ever loses, he goes broke and leaves the casino. However, if he's lucky enough to get a straight of n heads, then he'll get $2^{n} back, in which case the casino managers get seriously discouraged and the casino immediately shuts down. Thus the casino shuts down exactly when the first occurrence of n consecutive heads is completed. Let this time be T. Now we need three crucial observations: 1) Eventually the casino will shut down, since eventually the sequence of n consecutive heads will rear its "head" . When it's all over, the ONLY gamblers who will have made any money in this casino are the final n gamblers, G_{Tn+1} through G_{T}. These n gamblers cause a monetary loss of 2_{n+1}  2  n for the casino. "Proof:" G_{Tn+1} is the "shutdown" gambler who was lucky enough to complete the entire heads sequence. But while that sequence is being completed, new gamblers G_{Tn+2} through G_{T} are coming in at each new time step, successfully betting on partial sequences. Thus the last guy to come in gets $2, the guy before him gets $4 (for HH), and the guy before him gets $8 dollars ... etc. until G_{Tn+1}, who gets $2^{n}. Thus their total worth is 2 + 4 + 8 + ... + 2^{n} = 2_{n+1}  2. Finally, to compute how much the casino has to pay out, note that each of the n gamblers pays $1 to play. Thus we subtract $n from their total worth. Now you ask, what about all the gamblers before G_{Tn+1}, who won a couple coin flips? Well, since the n consecutive heads have never occurred yet, all those gamblers had to have lost all their monies, since they always bet everything they have. 2) For the stretch of time between n and Tn inclusive, the casino earns money at an amortized rate of $1 per time unit. "Proof:" Remember, all the gamblers with entry times prior to Tn+1 end up losing all their money. Since they came in with only $1, the casino gets $1 from each of those gamblers. And exactly one new gambler enters at each time step. Note that this $1 will be in the casino's possession after at most n units of time have elapsed since the losing gambler's entry. Thus, starting at time n, we can say that the casino is earning money at a rate of $1 per time unit. 3) Since the odds are fair, the expected amount of money which leaves the casino is equal to the expected amount of money that enters the casino. "Proof": Obvious; this is what we mean by fair odds. Finally, we combine these three facts. From (1), we know that the money going out is 2^{n+1}  2  n., and all the gamblers prior to the shutdown gambler have lost their money. From (2), we know that the money going into the casino comes in at a amortized rate of exactly $1 per each time step, prior to the shutdown gambler's time of entry. From (3), since expected money going out = expected money going in, then, the expected money coming in must also be 2^{n+1}  2  n. Finally, since the money comes in at an amoritzed rate of $1 per time unit, the expected time till the string of n consecutive heads BEGINS is 2^{n+1}  2  n. Finally we add n to this time, to get the expected time till the string finishes: 2^{n+1}  2. One can easily extend the above argument to other kinds of patterns over different alphabets. Footnote: An strange consequence of this I noticed is that the more "selfsimilarity" your pattern has when reading it from left to right, the longer it will take for the string to be seen. My amusing interpretation of this is that history is less likely to repeat itself!

« Last Edit: Jul 27^{th}, 2004, 6:30am by william wu » 
IP Logged 
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Expected number of throws before n heads in a
« Reply #9 on: Jul 27^{th}, 2004, 6:19am » 
Quote Modify

on Jul 27^{th}, 2004, 5:10am, william wu wrote:Footnote: An strange consequence of this I noticed is that the more "selfsimilarity" your pattern has when reading it from left to right, the longer it will take for the string to be seen. 
 You mean it would take longer to get 123123 than 132213 ? It seems to me that can't be the case, seeing as independence makes both strings equally likely..


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



william wu
wu::riddles Administrator
Gender:
Posts: 1291


Re: Expected number of throws before n heads in a
« Reply #10 on: Jul 27^{th}, 2004, 6:27am » 
Quote Modify

Yes, according to the argument, the expected time to see your first string is longer than the time to see the second. I didn't believe it either, but I did some simulations a while back on strings to that effect, and I think I confirmed it. Although I still find it disturbing myself. You have to be careful though  a lot of simulations are necessary in order to get estimates accurate enough to see the tiny differences in expected time. Namely, the standard errors of the sample means should be significantly less than the difference. This difference is only a constant term, where as the expected times themselves are on the order of n^(alphabet size), where n is the length of the pattern. (For instance, in your example, assuming alphabet = {1,2,3,}, the difference is only (3^6 + 3^3)  (3^6  3^2) = 27  9 = 18.) When simulating, try to choose strings that maximize the ratio of this difference to the expected time till the patterns occur, within the computational limits of available resources.

« Last Edit: Jul 27^{th}, 2004, 6:43am by william wu » 
IP Logged 
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Expected number of throws before n heads in a
« Reply #11 on: Jul 27^{th}, 2004, 8:14am » 
Quote Modify

In both cases you can define (the same) matrix A_{i} := [2/3, 1/3, 1/3, 2/3, 1/3, 1/3, 0; 1/3, 1/3, 1/3, 0, 1/3, 1/3, 0; 0, 1/3, 0, 0, 0, 0, 0; 0, 0, 1/3, 0, 0, 0, 0; 0, 0, 0, 1/3, 0, 0, 0; 0, 0, 0, 0, 1/3, 0, 0; 0, 0, 0, 0, 0, i/3, 1] which gives the statetransition at step i and [prod]_{i=1}[supinfty]A_{i} [times][1,0,0,0,0,0,0] gives the end state of the system. And considering the transition matrices are the same in both cases, the end result is the same, with the last element of the vector (which holds the expected waiting time) being 756.. 132312 on the other hand really would take less time. It's intuitive to see why, because if you at some point have the first 5 numbers, you can either get the number 2, in which case you're done get the number 1, in which case you're back at only having the first number of the sequence or you get a 3, in which case you have the first 2 numbers of the sequence. With 123123 if you have the first 5 numbers, you either get a 3 and finish get a 1, and start again with only the first number or get a 2 and you'll have to start over completely So on average you have to repeat more of the sequence there..

« Last Edit: Jul 27^{th}, 2004, 8:32am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



william wu
wu::riddles Administrator
Gender:
Posts: 1291


Re: Expected number of throws before n heads in a
« Reply #12 on: Jul 28^{th}, 2004, 4:19am » 
Quote Modify

Not sure what that matrix is about. States? If it's supposed to be a probability transition matrix, the rows don't add to one either. Anyways, your latter comments I think are a great way to see it. You can consider the minimal finite state machines which one can build to recognize these patterns. The expected time to get to the absorption state is then given by some markov chain analysis. But basically when trying to recognize patterns with high lefttoright repetitive substructure, you often pay the price of retracting to very early states when an sequence mismatch occurs.

« Last Edit: Jul 28^{th}, 2004, 4:20am by william wu » 
IP Logged 
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Expected number of throws before n heads in a
« Reply #13 on: Jul 28^{th}, 2004, 5:03am » 
Quote Modify

on Jul 28^{th}, 2004, 4:19am, william wu wrote:Not sure what that matrix is about. States? If it's supposed to be a probability transition matrix, the rows don't add to one either. 
 The columns add to one (except for the 5th, as that doesn't give a chance, but probability*time = (partial) expected time) You start without anything of the string, then either you get 1 with probability 1/3, or 2 or 3 (and thus are left with nothing of the string) with probability 2/3. If you have the first 1, then you can get a 2 with probability 1/3, or you get a 1 (in which case you still only have the first number of a string) with probability 1/3, or you get a 3 with probability 1/3 in which case you have to start over. etc Near the end you have 12312 and either get a 3 with probability 1/3 in which case you're done and it took i steps, so expected time get incremented by i/3 * (fraction in state 12312), other wise you return to 1, or nothing both with probability 1/3..

« Last Edit: Jul 28^{th}, 2004, 5:05am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



ThudnBlunder
wu::riddles Moderator Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489


Re: Expected number of throws before n heads in a
« Reply #14 on: Aug 22^{nd}, 2004, 9:56am » 
Quote Modify

Quote:It seems to me that can't be the case, seeing as independence makes both strings equally likely.. 
 See also Coin Triplets.


IP Logged 
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.



Porsche911
Newbie
Posts: 2


Re: Expected number of throws before n heads in a
« Reply #15 on: Dec 4^{th}, 2007, 10:06am » 
Quote Modify

With Markov Chains we get the same result! (10010010 for 1231231): Here is a nice introduction: http://www.dartmouth.edu/~chance/teaching_aids/books_articles/probabilit y_book/Chapter11.pdf We have 8 different states: {0,1,2,3,4,5,6,7} State 7: ...1231231 = Absorption State State 6: ...123123 State 5: ...12312 State 4: ...1231 State 3: ...123 State 2: ...12 State 1: ...1 State 0: ... In MathematicaCode: TransitionMatrix = { {9/10, 1/10, 0, 0, 0, 0, 0, 0}, {8/10, 1/10, 1/10, 0, 0, 0, 0, 0}, {8/10, 1/10, 0, 1/10, 0, 0, 0, 0}, {9/10, 0, 0, 0, 1/10, 0, 0, 0}, {8/10, 1/10, 0, 0, 0, 1/10, 0, 0}, {8/10, 1/10, 0, 0, 0, 0, 1/10, 0}, {9/10, 0, 0, 0, 0, 0, 0., 1/10}, {0, 0, 0, 0, 0, 0., 0, 1}}; Q = { {9/10, 1/10, 0, 0, 0, 0, 0}, {8/10, 1/10, 1/10, 0, 0, 0, 0}, {8/10, 1/10, 0, 1/10, 0, 0, 0}, {9/10, 0, 0, 0, 1/10, 0, 0}, {8/10, 1/10, 0, 0, 0, 1/10, 0}, {8/10, 1/10, 0, 0, 0, 0, 1/10}, {9/10, 0, 0, 0, 0, 0, 0}}; (*Q = TransitionMatrix without absorption states*) ExpectedTimeToAbsorption = Inverse[(IdentityMatrix[7]  Q)].{1,1,1,1,1,1,1} TimeTill1231231={1, 0, 0, 0, 0, 0, 0}.T (*TimeTill1231231=10010010*)


IP Logged 



Hippo
Uberpuzzler
Gender:
Posts: 919


Re: Expected number of throws before n heads in a
« Reply #16 on: Dec 5^{th}, 2007, 5:58am » 
Quote Modify

on Dec 4^{th}, 2007, 10:06am, Porsche911 wrote:With Markov Chains we get the same result! (10010010 for 1231231) 
 They were probably interested on 123123 (resp. 123312 only. ... I have no time to study the link yet. The problem with towr analysis was the wrong calculation for restarting ... I hope the link solves it well on Dec 5^{th}, 2007, 6:21am, towr wrote: ?! Which analysis are you referring to here? 
 The last one. But let me think about it a little more ... this was just the first impression and sorry if the analysis was Ok and my impression wrong.

« Last Edit: Dec 5^{th}, 2007, 7:37am by Hippo » 
IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Expected number of throws before n heads in a
« Reply #17 on: Dec 5^{th}, 2007, 6:21am » 
Quote Modify

on Dec 5^{th}, 2007, 5:58am, Hippo wrote:The problem with towr analysis was the wrong calculation for restarting ... 
 ?! Which analysis are you referring to here?


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



Porsche911
Newbie
Posts: 2


Re: Expected number of throws before n heads in a
« Reply #18 on: Dec 13^{th}, 2007, 2:39am » 
Quote Modify

Hey Hippo, no we are interested in 1231231.


IP Logged 



fiziwig
Junior Member
Posts: 78


Re: Expected number of throws before n heads in a
« Reply #19 on: Dec 20^{th}, 2007, 10:15am » 
Quote Modify

Quote:Footnote: An strange consequence of this I noticed is that the more "selfsimilarity" your pattern has when reading it from left to right, the longer it will take for the string to be seen. 
 I really had to convince myself that this counterintuitive result was true. Here's how I proved it to myself: Rather than playing the game until someone wins, we continue to play the game for an infinite length of time. We know that any given string will occur with equal frequency as any other given string. In other words, we expect the interval between occurrences of a given string to be, on average, the same regardless of the string in question. However, given that "123123" has just been encountered for the first time, we already have 3 out of the 6 digits matching as we look for the second occurrence, thus giving a slight edge to a second consecutive occurrence. Since the likelihood of a second consecutive occurrence is higher than average, which would give a very much shorter interval, in order for the longterm average interval to be correct, the interval before the first occurrence must be larger. Quote: 132312 on the other hand really would take less time. It's intuitive to see why, because if you at some point have the first 5 numbers, you can either get the number 2, in which case you're done get the number 1, in which case you're back at only having the first number of the sequence or you get a 3, in which case you have the first 2 numbers of the sequence. With 123123 if you have the first 5 numbers, you either get a 3 and finish get a 1, and start again with only the first number or get a 2 and you'll have to start over completely So on average you have to repeat more of the sequence there.. 
 I wonder about this reasoning. We are "given" that 5 digits have already matched, but consider the two 5digit precursor strings themselves: 132312 is claimed to be favored to show up earlier. If you have the first 4 digits you can either get 1 and finish get 2 and start again with NO digits correct get 3 and start again with NO digits correct 123123 is claimed to be favored to show up later. If you get the first 4 digits you can either get 2 and be finished get 1 and start over with only 1 digit correct get 3 and start over with NO digits correct. Therefore, the precursor to the favored string is disfavored, and the precursor to the disfavored string is favored. Is the advantage of a certain string always balanced by the disadvantage of its precursor strings? Apparently not, since in the final analysis, some strings are more or less favored to occur (for the first time) sooner than expected. gary


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Expected number of throws before n heads in a
« Reply #20 on: Dec 20^{th}, 2007, 11:13am » 
Quote Modify

Possibly the last step always outweighs all possible previous steps; but I'm not really good at picking up a thought 3 years on..

« Last Edit: Dec 20^{th}, 2007, 11:13am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



