BrainDen.com - Brain Teasers
• 0

## Question

Here's a simple question about probability and expectation.

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?

This puzzle was submitted, but not used, in the International

Mathematical Olympiad twenty-five years ago. What makes it

appealing for use as a test question [where time can be of the

essence] is that it has an easy answer as well as a difficult answer.

That is it tests for insight.

As such it qualifies as a puzzle as well as a math question.

Extra bragging rights go to the solver who solves it both ways.

## 35 answers to this question

• 0
Here's a simple question about probability and expectation.

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?

This puzzle was submitted, but not used, in the International

Mathematical Olympiad twenty-five years ago. What makes it

appealing for use as a test question [where time can be of the

essence] is that it has an easy answer as well as a difficult answer.

That is it tests for insight.

As such it qualifies as a puzzle as well as a math question.

Extra bragging rights go to the solver who solves it both ways.

Must the tail also in odd number? :huh

##### Share on other sites
• 0

My suggestion is : two times is enough, tough it seemed me rather low. My solution: Sigma(n) (sum of) from 2 to inf. (1/2)^n = 1/2 then you need 2 toss.

##### Share on other sites
• 0

could it be like 3 real heads followed by a dogs tail

or something like that??

##### Share on other sites
• 0
My suggestion is : two times is enough, tough it seemed me rather low. My solution: Sigma(n) (sum of) from 2 to inf. (1/2)^n = 1/2 then you need 2 toss.

that you need n to be even (using your notation), since you need n-1 to be odd, so the probability should be 1/2*1/2=1/4, so the expected number should be 4.

In the spirit of the Math Olympiad, doing it quickly, what I *think* is the "easy way" (plus I need to get to sleep ;P)

The probability of having a string n-1 of heads is (1/2)^(n-1). The probability of the next one being tails is 1/2. So the probability of having a string n-1 of heads and then a tails is (1/2)^n. Start from n=2 b/c you need at least one heads and one tails, and summing up the geometric series gives 1/2. Since you need n-1 to be odd, divide again by two (alternatively you could have considered an odd series of heads (1/2)^(2n-1)), and you get 1/4 probability of an odd string of heads followed by a tails. Using the result we proved in a different thread , the expected number of tosses is 4.

(I'm not sure if this works, but)is the real "easy way" to say:

When you get your first tails, there is an equal 1/2 chance of the string of heads before being even or odd. And the probability of the first coin tossed not being a tails is 1/2, giving 1/2*1/2=1/4, and using the same result, the expected number of coin tosses is 4?

Edited by Yoruichi-san

##### Share on other sites
• 0

first flip a head second flip a tail will make the eqution true. But that is only one solution.

##### Share on other sites
• 0

(I'm not sure if this works, but)is the real "easy way" to say:

When you get your first tails, there is an equal 1/2 chance of the string of heads before being even or odd. And the probability of the first coin tossed not being a tails is 1/2, giving 1/2*1/2=1/4, and using the same result, the expected number of coin tosses is 4?

that you need n to be even (using your notation), since you need n-1 to be odd, so the probability should be 1/2*1/2=1/4, so the expected number should be 4.

In the spirit of the Math Olympiad, doing it quickly, what I *think* is the "easy way" (plus I need to get to sleep ;P)

The probability of having a string n-1 of heads is (1/2)^(n-1). The probability of the next one being tails is 1/2. So the probability of having a string n-1 of heads and then a tails is (1/2)^n. Start from n=2 b/c you need at least one heads and one tails, and summing up the geometric series gives 1/2. Since you need n-1 to be odd, divide again by two (alternatively you could have considered an odd series of heads (1/2)^(2n-1)), and you get 1/4 probability of an odd string of heads followed by a tails. Using the result we proved in a different thread , the expected number of tosses is 4.

You're right Yourichi-san, I calculated the probability of getting a tail before an odd number of heads. But it was not the question

##### Share on other sites
• 0
Must the tail also in odd number? :huh

Here are some examples of what you want to have happen.

It should clear up what the OP asks:

Here the dots represent H or T but with the caveat that

the dots don't contain the string of results you want.

. . . . H H H T [8 tosses]

. . . . . . . H H H H H T [13 tosses]

H T [2 tosses]

##### Share on other sites
• 0
Here are some examples of what you want to have happen.

It should clear up what the OP asks:

Here the dots represent H or T but with the caveat that

the dots don't contain the string of results you want.

. . . . H H H T [8 tosses]

. . . . . . . H H H H H T [13 tosses]

H T [2 tosses]

I'm confused. What if you tossed:

T H H T

Would that count as a success? That includes the string "H T" but is preceded by another head. Technically it meets the criteria but I suspect that wasn't what you meant...

##### Share on other sites
• 0
Here are some examples of what you want to have happen.

It should clear up what the OP asks:

Here the dots represent H or T but with the caveat that

the dots don't contain the string of results you want.

. . . . H H H T [8 tosses]

. . . . . . . H H H H H T [13 tosses]

H T [2 tosses]

for "H T" will be (1/2)2

for "H H H T" will be (1/2)4

for "H H H H H T" will be (1/2)6

for (2n-1) odd number of head followed by a tail, the probability = (1/2)2n

hence the average expectation should be x * p(x) which is 1*(1/2)2+3*(1/2)4+5*(1/2)2+.....+ (2n-1)*(1/2)2n+.....

well, am I on the right track? :huh

##### Share on other sites
• 0
You're right Yourichi-san, I calculated the probability of getting a tail before an odd number of heads. But it was not the question

Lol, and you're right! I forgot about the tail before the string of heads! The string needs to be bound on both sides by tails, so the probability is actually

1/8 -> average of 8 tosses. Basically the probability of having an odd string of heads*probability of tails on both sides = (1/2)^3

Lol...didn't I say I was going to bed?

Edited by Yoruichi-san

##### Share on other sites
• 0
I'm confused. What if you tossed:

T H H T

Would that count as a success? That includes the string "H T" but is preceded by another head. Technically it meets the criteria but I suspect that wasn't what you meant...

That's what I was thinking too, and i think that's the trick. All you need to flip is an "H T" string, nothing else matters. Which means all you need is H...HT or TH...HT. To calculate the expected value

HT: 1/4*2

HHT: 1/8*3

THT: 1/8*3

HHHT: 1/16*4

THHT: 1/16*4

HHHHT: 1/32*5

THHHT: 1/32*5

=1/2+sum(n=3,inf)[1/2n-1*n),

Which comes out to 2.5 expected flips.

##### Share on other sites
• 0
That's what I was thinking too, and i think that's the trick. All you need to flip is an "H T" string, nothing else matters. Which means all you need is H...HT or TH...HT. To calculate the expected value

HT: 1/4*2

HHT: 1/8*3

THT: 1/8*3

HHHT: 1/16*4

THHT: 1/16*4

HHHHT: 1/32*5

THHHT: 1/32*5

=1/2+sum(n=3,inf)[1/2n-1*n),

Which comes out to 2.5 expected flips.

Too late to edit, but I clearly forgot about the T...TH...HT solutions, which changes the calculations.

That's why I shouldn't do math this early in the morning.

##### Share on other sites
• 0

Generally we will be in one of two conditions:

A) We have just tossed an even run of heads, or a tail

B) We have just tossed an odd run of heads

A followed by head moves us to B

B followed by head moves us to A

A followed by tail keeps us on A

B followed by tail finishes the sequence

So if An is probability of A on nth trial, Bn probability of B, and Sn probability of success,

An=(An-1+Bn-1)/2

Bn=An-1/2

Sn=Bn-1/2

A0=1, A1=1/2, A2=1/2...

B0=0, B1=1/2, B2=1/4...

S0=0, S1=0, S2=1/4...

Expected trials = sum {n>=1} (n*Sn) = S1+2*S2+C = 0.5+C, where

C = sum {n>=3} (n*Sn)

= sum (n*Bn-1)/2

= sum (n*An-2)/4

= sum (n*An-3+n*Bn-3))/8

= sum ((n+1)*An-2+(n+2)*Bn-1)/8 + (3*A0+3*B0+4*B1)/8

= sum (n*An-2+An-2+n*Bn-1+2Bn-1)/8 + 5/8

= C*1/4 + C*1/2 + sum(An-2) + 2*sum(Bn-1) + 5/8

C = 4*sum{n>2}(An-2) + 8*sum{n>2}(Bn-1) + 5/2

C = 4*sum{n>0}(An) + 8*sum{n>1}(Bn) + 5/2

sum(Sn) {n>2} = 1-S2 = 3/4

Bn-1=Sn*2, so sum(Bn) {n>1} = 3/2

An-1=Bn*2, so sum(An) {n>0} = 3

C = 4*3 + 8*3/2 + 2.5 = 26.5

So that would make expected trials 27

Only experimenting it in Excel gives me an answer of 6, which I think is more plausible

So much for maths, I'll have to try and find my mistake...

Oh, and if this is the easy way I don't want to know about the hard way

##### Share on other sites
• 0

Well I think that, on average, you have to toss the coin an infinite number of times to get the H followed by a T...

##### Share on other sites
• 0

Interpreting an odd number of H followed by a T:

H H T T H H T H T 9 flips

H T 2 flips

T T T H H T H H H H T T T H H H T 17 flips

H H H H H H H H H H H H H H H T 16 flips

T T T T T T T T H T 10 flips

T T H H T T H H T T H H T T H H T T H H H T 22 flips

At the point that you've "won" you have a T.

Preceding that is an odd number of H

Preceding that is either a T or nothing [you started with an odd number of H]

##### Share on other sites
• 0

Generally we will be in one of two conditions:

A) We have just tossed an even run of heads, or a tail

B) We have just tossed an odd run of heads

A followed by head moves us to B

B followed by head moves us to A

A followed by tail keeps us on A

B followed by tail finishes the sequence

So if An is probability of A on nth trial, Bn probability of B, and Sn probability of success,

An=(An-1+Bn-1)/2

Bn=An-1/2

Sn=Bn-1/2

A0=1, A1=1/2, A2=1/2...

B0=0, B1=1/2, B2=1/4...

S0=0, S1=0, S2=1/4...

Expected trials = sum {n>=1} (n*Sn) = S1+2*S2+C = 0.5+C, where

C = sum {n>=3} (n*Sn)

= sum (n*Bn-1)/2

= sum (n*An-2)/4

= sum (n*An-3+n*Bn-3))/8

= sum ((n+1)*An-2+(n+2)*Bn-1)/8 + (3*A0+3*B0+4*B1)/8

= sum (n*An-2+An-2+n*Bn-1+2Bn-1)/8 + 5/8

= C*1/4 + C*1/2 + sum(An-2) + 2*sum(Bn-1) + 5/8

C = 4*sum{n>2}(An-2) + 8*sum{n>2}(Bn-1) + 5/2

C = 4*sum{n>0}(An) + 8*sum{n>1}(Bn) + 5/2

sum(Sn) {n>2} = 1-S2 = 3/4

Bn-1=Sn*2, so sum(Bn) {n>1} = 3/2

An-1=Bn*2, so sum(An) {n>0} = 3

C = 4*3 + 8*3/2 + 2.5 = 26.5

So that would make expected trials 27

Only experimenting it in Excel gives me an answer of 6, which I think is more plausible

So much for maths, I'll have to try and find my mistake...

Oh, and if this is the easy way I don't want to know about the hard way

Impressive. Now lie down in a quiet place, put a cool washcloth on your forehead, and relax.

No worry - that is not even close to the easy way.

Or the hard way, for that matter.

That is, there are [at least] two ways, one very quick, that are less cumbersome.

##### Share on other sites
• 0
Interpreting an odd number of H followed by a T:

H H T T H H T H T 9 flips

H T 2 flips

T T T H H T H H H H T T T H H H T 17 flips

H H H H H H H H H H H H H H H T 16 flips

T T T T T T T T H T 10 flips

T T H H T T H H T T H H T T H H T T H H H T 22 flips

At the point that you've "won" you have a T.

Preceding that is an odd number of H

Preceding that is either a T or nothing [you started with an odd number of H]

Thank you for the clarification, but this is not what u've explained in ur post before! In this case, my answer, infinite numbers, doesn't stand anymore!!!

##### Share on other sites
• 0
Impressive. Now lie down in a quiet place, put a cool washcloth on your forehead, and relax.

No worry - that is not even close to the easy way.

Or the hard way, for that matter.

That is, there are [at least] two ways, one very quick, that are less cumbersome.

I think its either 2 or 3.. If yes then i can explain the logic behind it..

##### Share on other sites
• 0

Generally we will be in one of two conditions:

A) We have just tossed an even run of heads, or a tail

B) We have just tossed an odd run of heads

A followed by head moves us to B

B followed by head moves us to A

A followed by tail keeps us on A

B followed by tail finishes the sequence

So if An is probability of A on nth trial, Bn probability of B, and Sn probability of success,

An=(An-1+Bn-1)/2

Bn=An-1/2

Sn=Bn-1/2

A0=1, A1=1/2, A2=1/2...

B0=0, B1=1/2, B2=1/4...

S0=0, S1=0, S2=1/4...

Expected trials = sum {n>=1} (n*Sn)

= sum {n>=1} ((n-2+2)*Sn)

= sum {n>=1} ((n-2)*Sn) + 2 * sum {n>=1} (Sn)

= sum {n>=-1} (n*Sn+2) + 2

= sum {n>=1} (n*Sn+2) + 2 - S1 +0*S2

= C + 2, where

C = sum {n>=1} (n*Sn+2)

= sum (n*Bn+1)/2

= sum (n*An)/4

= sum (n*An-1+n*Bn-1)/8

= sum ((n+1)*An+(n+2)*Bn+1)/8 + (1*A0+1*B0+2*B1)/8

= sum (n*An+An+n*Bn+1+2Bn+1)/8 + (1+0+1)/8

= sum (n*An)/8 + sum(n*Bn+1)/8+ sum(An)/8 + sum(2Bn+1)/8 + ¼

= C/2 + C/4 +sum(An)/8 + sum(Bn+1)/4 + ¼

[multiply both sides by 4 and subtract 3*C]

= sum(An/2) + sum(Bn+1) + 1

[use Bn = An-1/2]

= 2*sum(Bn+1) + 1

[use Sn = Bn-1/2]

= 4*(sum {n>=1} (Sn+2)) + 1

= 4*(sum {n>=1} (Sn) – (S1+S2)) + 1

= 4*(1 – ¼) + 1

= 4

Expected trials = C+2 = 6

Tell me that isn't the easy way!

I'm going to stick my head in a bucket of ice now

##### Share on other sites
• 0

25 times

The most basic element of this, is that there must be an odd 'run' (suggesting at least 3 flips) on heads, and then a tails side. So it would take four tosses to complete the prerequisite.

The odds of performing this particular action seems to be .5^4 (H, H, H, T) Yielding 0.0625

So, out of 100 4-toss runs, it would work about 16 times. Meaning that on average it would occur once in every 25 tosses.

I'm probably way off.

Edit: or it might be 6.25, and I took it a little too far. <_< but I'm leaning toward 25

Edited by Brandonb

##### Share on other sites
• 0
Thank you for the clarification, but this is not what u've explained in ur post before! In this case, my answer, infinite numbers, doesn't stand anymore!!!

The blue H and T are the dots in the previous post - flips that didn't contribute to odd H plus T.

##### Share on other sites
• 0
Generally we will be in one of two conditions:

A) We have just tossed an even run of heads, or a tail

B) We have just tossed an odd run of heads

A followed by head moves us to B

B followed by head moves us to A

A followed by tail keeps us on A

B followed by tail finishes the sequence

So if An is probability of A on nth trial, Bn probability of B, and Sn probability of success,

An=(An-1+Bn-1)/2

Bn=An-1/2

Sn=Bn-1/2

A0=1, A1=1/2, A2=1/2...

B0=0, B1=1/2, B2=1/4...

S0=0, S1=0, S2=1/4...

Expected trials = sum {n>=1} (n*Sn)

= sum {n>=1} ((n-2+2)*Sn)

= sum {n>=1} ((n-2)*Sn) + 2 * sum {n>=1} (Sn)

= sum {n>=-1} (n*Sn+2) + 2

= sum {n>=1} (n*Sn+2) + 2 - S1 + 0*S2

= C + 2, where

C = sum {n>=1} (n*Sn+2)

= sum (n*Bn+1)/2

= sum (n*An)/4

= sum (n*An-1+n*Bn-1)/8

= sum ((n+1)*An+(n+2)*Bn+1)/8 + (1*A0+1*B0+2*B1)/8

= sum (n*An+An+n*Bn+1+2Bn+1)/8 + (1+0+1)/8

= sum (n*An)/8 + sum(n*Bn+1)/8 + sum(An)/8 + sum(2Bn+1)/8 + ¼

= C/2 + C/4 + sum(An)/8 + sum(Bn+1)/4 + ¼

[multiply both sides by 4 and subtract 3*C]

= sum(An/2) + sum(Bn+1) + 1

[use Bn = An-1/2]

= 2*sum(Bn+1) + 1

[use Sn = Bn-1/2]

= 4*(sum {n>=1} (Sn+2)) + 1

= 4*(sum {n>=1} (Sn) – (S1+S2)) + 1

= 4*(1 – ¼) + 1

= 4

Expected trials = C+2 = 6

Tell me that isn't the easy way!

I'm going to stick my head in a bucket of ice now

shooting a rabbit with an elephant gun, but Bugs is quite taken care of, nonetheless.

Kudos.

Now for something simpler.

And disparagement of frequency analysis aside, those simulations do provide useful guidance don't they?

##### Share on other sites
• 0

I thought we laid quite a bit of groundwork in previous like-topics.

I'll designate head as 0 and tail as 1. Let's call the average number of tosses we seek -- x.

1) 00 -- this has a probability of 1/4, two tosses and we are back where we started. Thus 1/4(2+x)

2) 01 -- probability 1/4 and we are done in just two tosses. 1/4*2

3) 100 -- probability 1/8, 3 tosses, same position as from the start. 1/8(3+x)

4) 101 -- probability 1/8, 3 tosses, done. 1/8*3

5) 11 -- probability 1/4, 2 tosses, starting position. 1/4(2+x)

Adding them all up we get: x = 1/2 + x/4 + 1/2 + 3/8 + x/8 + 3/8 + 1/2 + x/4

Solving, we find x = 6

Using geometric series to solve is straight forward enough too. There we get probability of the required sequence is 1/3 and its average length is 8/3, whereas probability of other sequences is 2/3 and their average length 5/3. Calculating 2*5/3 + 8/3 = 6. Same result, I don't show the actual series here as we have discussed them at other topics.

Edited by Prime

##### Share on other sites
• 0

Or even simpler, yet:

If we tossed tails on the first try, we are at the starting position again, the averaage in that case is 1/2*(x+1).

When heads, we have probability 1/2 to finish on the next toss: 1/2*1/2*2, or get back to starting position: 1/2*1/2*(2+x).

Thus x = x/2 + 1/2 + 1/2 +1/2 + x/4 --> x = 6

##### Share on other sites
• 0

6 is exactly right.

I wonder what's the long way of solving. Once I got it easy way there's no stimulus looking for long one.

## Create an account

Register a new account