Odd Streak of Heads
On average, how many times do you need to flip a fair coin before you have seen a run of an odd number of heads, followed by a tail?
Labels: Probability, SharedPuzzle
posted by Zaux at
5:43 AM
Tuesday, January 5, 2010
Links
Search
Share
- Tom Chrome Extension
- ToM @ Twitter
- MeeT ToM
- Daily Tricks Widget
- Vista Gadget 1.5
- iPhone Widget
- Windows XP Widget
- Google Toolbar Button
- Suggestions
Favorite Links
- Vista Sidebar Gadgets
- Widgets for Web 2.0
- C Sharp Tricks
- Interview Information
- Illustrator - Elar Alexander
Bookmark Us
Previous Posts
- The Lost Boarding Pass
- Losing at Dice
- A Poorly Designed Clock
- Summing to 15
- Lottery
- First Odd Number in an Alphabetical list
- Uses of Fuses
- Rolling All the Numbers
- Sequencing the Digits
- The Gambler's Ruin
8 Comments:
2, flip it once a get a heads, one is an odd number, flip it again and it will be followed by a tail
But you might instead have got HH, TH or TT in those two flips.
Went to bed, then this came into my head.
Rather than jumping in straight for the final equation, I'll consider a simpler problem. But it may still make your head hurt.
Let H[n] be the average number of flips needed to get n heads in a row. Now consider ourselves to have just got n-1 heads in a row. That has on average taken H[n-1] flips. Let p be the probability of throwing a head. I'll substitute p = 1/2 at the end. On the next flip, there is a 1-p probability of throwing a tails; then the run is broken and we've used H[n-1]+1 throws and we've got H[n] throws to go to finish, on average. There is a probability p that we throw a heads; then we'll have got our n heads in a row and it will have taken H[n-1]+1 throws to achieve that. So that gives us
H[n] = (1-p)*(H[n-1]+1+H[n]) + p*(H[n-1]+1). Solving for H[n],
H[n](1-(1-p)) = H[n-1]((1-p) + p)) + (1-p) + p =>
H[n] = (H[n-1]+1))/p. To get this into closed form, start at n=1.
H[0] = 0 and hence H[1] = 1/p (which should be obvious as for a fair coin p=1/2, so would expect to take two flips on average to get a head). Then H[2] = (1/p + 1)/p = (1+p)/p^2.
H[3] = ((1+p)/p^2 + 1)/p = (1 + p + p^2)/p^3.
If continue get H[n] = (1 + p + p^2 +...+ p^(n-1))/p^n.
Luckily, I spot a well known series.
Let Sn = 1 + x + x^2 + x^3 + x^(n-1) {n terms altogether}
The x*Sn = x + x^2 + x^3 +...+ x^(n-1) + x^n
= 1 + x + x^2 + x^3 +...+ x^(n-1) + x^n - 1
= Sn + x^n - 1
Solving for Sn => Sn = (1-x^n)/(1-x)
So H[n] = ((1-p^n)/(1-p))/p^n = (p^(-n)-1)/(1-p)
Substitute p = 1/2 => H[n] = 2^(n+1) - 2 = 2(2^n - 1)
I read the question as meaning throwing a sequence of n HT pairs, but I don't really understand what it's asking. Assuming a fair coin, the average number of flips needed to get n HT in a row is HT[n] = H[2n] = 2(4^n-1) = 2(2^n-1)(2^n+1). (I've not sure if that's right as I think I've assumed a head was thrown first).
Does the question mean what is the average number of flips needed to get one of HT, HHHT, HHHHHT, ... ? At the moment, I can't think of how to calculate that. Maybe after another coffee!
I hope my reasoning about using averages in the way I have isn't flawed. All other approaches I've thought up are nightmarish in complexity. This approach seems to me to be pretty clean. Even if it's all wrong, it was quite good "fun" anyway.
Zaux, this is a very hard problem (for me).
Lets assume we start right out flipping an odd number of heads, then followed by a tail.
The probability of that happening is:
Pr(HT)+Pr(HHHT)+ Pr(HHHHHT)+ ... = (1/2)^2 + (1/2)^4 + (1/2)^6 + ... = 1/3.
If a tail is flipped after an even number of heads, then you have to start over. So, on average, it will require three such attempts; however, we want to count flips, not attempts.
This will help:
If there is a random number n of items whose average size is s, then the average total size of the items is s times the average value of n. Each attempt ends when the first tail pops up; thus the average number of flips per attempt is 1/(1/2)= 2.
Therefore 2 x 3 = 6 flips.
2 (avg. number of flips per attempt) x 3 (avg. number of attemps) = 6 flips.
Hi Zaux, I haven't fully got my head around your answer. I suspect that you are right though. Thanks for posting.
Strangely, I note that H[2] (from above) = 6 also. This is what I'd expect for throwing the HT sequence. If find it curious that the two averages are the same.
i.e. H[HT] = H[HT¦HHHT¦HHHHHT¦..] = 6
where ¦ is logical exclusive or
By performing mental gymnastics, I can diretly see that that is quite possibly correct.
Still not got there yet. But am pretty sure that my equations above are correct. Take for example the case of throwing 4 heads in a row. There are 16 equally likely outcomes. So it is obvious (to me) that on average you would need to have 16 trials of throwing 4 coins to get the 4 heads. But if you really did that, you'd stop flipping the moment a tail came up, and start the next trial immmeditely. The possible results (all equally likely, along with the number of flips you would have taken) are:
HHHH 4
HHHT 4
HHTH 3
HHTT 3
HTHH 2
HTHT 2
HTTH 2
HTTT 2
Txxx 1 (8 lots for the xxx)
So overall you would have taken:
4+4+3+3+2+2+2+2+8 = 30 flips on average to get 4 heads in a row.
My formula give H[HHHH] = H[4] = 2(2^4-1) = 30.
In fact if you do this on a piece of paper, after a while you'll spot the patterns, and derive the formula. In fact it's easier to do it that way, than the way I originally presented (but not as satisfying). In fact you'd get the following for n heads:
n*2 + (n-1)*2 + (n-2)*4 + ... + (n-m)*2^m + ... + 2*2^(n-2) + 1*2^(n-1)
There are several ways you can go with this. But you end up with
H[n] = 2(2^n - 1) as I deduced previously.
Post a Comment
Links to this post:
Create a Link
<< Home