[bonanova]

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.

[Guest]

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

lol, with hindsight I suppose I could have simplified things a bit before plunging into the infinite series manipulation, but, you know, I couldn't wait.

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

Oh, I didn't do a simulation, but it's ever so easy to throw together a table of event probabilities, A_n, B_n and S_n for n upto about 100. A very simple approach if you want a quick and dirty answer.

[Guest]

It goes like this ...

To get 1 Head = 2 Tosses

To get 2 Head in a row = (2 * 2) = 4 Tosses

To get 3 Heads in a row = (4 * 2) = 8 Tosses

To get 4 Heads in a row = (8 * 2) = 16 Tosses

To get 5 Heads in a row = (16 * 2) = 32 Tosses

Now we add a Tail to it ... That makes it one more Toss required, Does not matter if it is Heads or Tails you choose ;P

To get 1 Head = 2 Tosses

To get 1 Head, 1 Tail = 2 * 2 = 4 Tosses

To get 3 Heads in a row = (4 * 2) = 8 Tosses

To get 3 Heads, 1 Tail in a row = (8 * 2) = 16 Tosses

Anything Simpler than this ???

[Guest]

It goes like this ...

To get 1 Head = 2 Tosses

To get 2 Head in a row = (2 * 2) = 4 Tosses

To get 3 Heads in a row = (4 * 2) = 8 Tosses

To get 4 Heads in a row = (8 * 2) = 16 Tosses

To get 5 Heads in a row = (16 * 2) = 32 Tosses

Now we add a Tail to it ... That makes it one more Toss required, Does not matter if it is Heads or Tails you choose ;P

To get 1 Head = 2 Tosses

To get 1 Head, 1 Tail = 2 * 2 = 4 Tosses

To get 3 Heads in a row = (4 * 2) = 8 Tosses

To get 3 Heads, 1 Tail in a row = (8 * 2) = 16 Tosses

Anything Simpler than this ???

That doesn't cover all the bases. You can still "win" on the nth toss without having tossed n-1 heads previously. For example when n=5, THHHT, HHTHT and TTTHT all win.

Anyway, you'll have to beat Prime to get any kudos (see post #25). I don't think anybody will top that...

[Guest]

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.

The probably of flipping an odd number of heads followed by tails is

HT

HHHT

HHHHHT

it is a fair coin so H = T = 1/2

so

HT = 1/4 chance

HHHT = 1/16 chance or 1/4^2

HHHHHT = 1/64 chance or 1/4^3

...

so Probably of this ocuring is = 1/4 + 1/16 + 1/64

This can be represented by sum to infinity serries

S = a/( 1-r)

where

a= 1/4

r=1/4

S= 0.333333333

The probablity of this ocuring is 1/0.3333 = 3

Because I reduced 2 flips into 1 we multiply this by 2

So 6 Coin throws we will expect the outcome.

Edited October 10, 2008 by taliesin

[EventHorizon]

You can answer this one using a method quite similar to that of my answer for "circular dice." In fact, it is similar to prime's simple answer.

Let x be the average number of flips of a coin until the goal when in state 1 ((a) just starting, (b) just flipped a tails, or ©just flipped an even number of heads).

Let y be the average number of flips of a coin until the goal when in state 2 (you have flipped an odd number of heads consecutively).

y = 1 + (.5*x + .5*0) = 1+x/2

after 1 flip when starting at state 2, you will either be at state 1 (50%) or in the goal state.

x = 1+ x/2 + y/2 => y = x-2

after 1 flip when starting at state 1, you will either be at state 1 (50%) or at state 2 (50%).

So, 1+x/2 = x-2

3 = x/2

6 = x

[Yoruichi-san]

You can answer this one using a method quite similar to that of my answer for "circular dice." In fact, it is similar to prime's simple answer.

Let x be the average number of flips of a coin until the goal when in state 1 ((a) just starting, (b) just flipped a tails, or ©just flipped an even number of heads).

Let y be the average number of flips of a coin until the goal when in state 2 (you have flipped an odd number of heads consecutively).

y = 1 + (.5*x + .5*0) = 1+x/2

after 1 flip when starting at state 2, you will either be at state 1 (50%) or in the goal state.

x = 1+ x/2 + y/2 => y = x-2

after 1 flip when starting at state 1, you will either be at state 1 (50%) or at state 2 (50%).

So, 1+x/2 = x-2

3 = x/2

6 = x

Nice!

[bonanova]

That would be the easy way.

Nice going all.

[Guest]

Fist I don't know the math on this. And I know that humans are bad at guessing probability. But 6? How can that possibly be true when the pattern is 5 tosses long in a sequence. (THHHT)

The problem set is not well defined. I assume "run" means more than one. The smallest odd run then is three. That run of three has to be sandwiched by tails, so the full length of the solution is five tosses. UNLESS you start out with a run of three heads and a tail, in that one special instance, you can get a min of 4 tosses. Either way, it seems highly unlikely that you will average this pattern in six tosses.

The probability of a fair coin being either side is 50%, 1/2. The probablity of getting the shortest sequence is 1/2^5 or .03125. But you could get other patterns:

.5^5 = THHHT = .03125 Requires 5 flips min

.5^7 = THHHHHT = .0078125 Requires 7 flips min

.5^9 = THHHHHHHT = .001953125 Requires 9 flips min

So as you keep flipping more, you not only have more chances, you have more patterns you can match.

I don't know the formulas to use, so I did spreadsheet math. Flips is the total number of flips. Single adding the probability of single patterns that fit into the number of tosses. In other words, the chance that on that flip, you will have ended a pattern successfully. Sequence is adding up all the singles that have come before to get the probability that by this time, you reach your pattern.

Flips Single Sequence

1 0.00% 0.00%

2 0.00% 0.00%

3 0.00% 0.00%

4 0.00% 0.00%

5 3.13% 3.13%

6 3.13% 6.25%

7 3.91% 10.16%

8 3.91% 14.06%

9 4.10% 18.16%

10 4.10% 22.27%

11 4.15% 26.42%

12 4.15% 30.57%

13 4.16% 34.73%

14 4.16% 38.89%

15 4.17% 43.06%

16 4.17% 47.22%

17 4.17% 51.39%

At 5 tosses, you have the first chance of victory, and thats only 3%. Only when I get to 17 flips is my probablity over 50%. So my answer would be 17 flips on average to get a run of odd heads followed by a tail.

[bonanova]

Fist I don't know the math on this. And I know that humans are bad at guessing probability. But 6? How can that possibly be true when the pattern is 5 tosses long in a sequence. (THHHT)

The problem set is not well defined. I assume "run" means more than one. The smallest odd run then is three. That run of three has to be sandwiched by tails, so the full length of the solution is five tosses. UNLESS you start out with a run of three heads and a tail, in that one special instance, you can get a min of 4 tosses. Either way, it seems highly unlikely that you will average this pattern in six tosses.

The probability of a fair coin being either side is 50%, 1/2. The probablity of getting the shortest sequence is 1/2^5 or .03125. But you could get other patterns:

.5^5 = THHHT = .03125 Requires 5 flips min

.5^7 = THHHHHT = .0078125 Requires 7 flips min

.5^9 = THHHHHHHT = .001953125 Requires 9 flips min

So as you keep flipping more, you not only have more chances, you have more patterns you can match.

I don't know the formulas to use, so I did spreadsheet math. Flips is the total number of flips. Single adding the probability of single patterns that fit into the number of tosses. In other words, the chance that on that flip, you will have ended a pattern successfully. Sequence is adding up all the singles that have come before to get the probability that by this time, you reach your pattern.

Flips Single Sequence

1 0.00% 0.00%

2 0.00% 0.00%

3 0.00% 0.00%

4 0.00% 0.00%

5 3.13% 3.13%

6 3.13% 6.25%

7 3.91% 10.16%

8 3.91% 14.06%

9 4.10% 18.16%

10 4.10% 22.27%

11 4.15% 26.42%

12 4.15% 30.57%

13 4.16% 34.73%

14 4.16% 38.89%

15 4.17% 43.06%

16 4.17% 47.22%

17 4.17% 51.39%

At 5 tosses, you have the first chance of victory, and thats only 3%. Only when I get to 17 flips is my probablity over 50%. So my answer would be 17 flips on average to get a run of odd heads followed by a tail.

A run can be any length, including 0.

Since the run is odd, it's 1, 3, 5, etc.

[Prime]

Fist I don't know the math on this. And I know that humans are bad at guessing probability. But 6? How can that possibly be true when the pattern is 5 tosses long in a sequence. (THHHT)

The problem set is not well defined. I assume "run" means more than one. The smallest odd run then is three. That run of three has to be sandwiched by tails, so the full length of the solution is five tosses. UNLESS you start out with a run of three heads and a tail, in that one special instance, you can get a min of 4 tosses. Either way, it seems highly unlikely that you will average this pattern in six tosses.

The probability of a fair coin being either side is 50%, 1/2. The probablity of getting the shortest sequence is 1/2^5 or .03125. But you could get other patterns:

.5^5 = THHHT = .03125 Requires 5 flips min

.5^7 = THHHHHT = .0078125 Requires 7 flips min

.5^9 = THHHHHHHT = .001953125 Requires 9 flips min

So as you keep flipping more, you not only have more chances, you have more patterns you can match.

I don't know the formulas to use, so I did spreadsheet math. Flips is the total number of flips. Single adding the probability of single patterns that fit into the number of tosses. In other words, the chance that on that flip, you will have ended a pattern successfully. Sequence is adding up all the singles that have come before to get the probability that by this time, you reach your pattern.

Flips Single Sequence

1 0.00% 0.00%

2 0.00% 0.00%

3 0.00% 0.00%

4 0.00% 0.00%

5 3.13% 3.13%

6 3.13% 6.25%

7 3.91% 10.16%

8 3.91% 14.06%

9 4.10% 18.16%

10 4.10% 22.27%

11 4.15% 26.42%

12 4.15% 30.57%

13 4.16% 34.73%

14 4.16% 38.89%

15 4.17% 43.06%

16 4.17% 47.22%

17 4.17% 51.39%

At 5 tosses, you have the first chance of victory, and thats only 3%. Only when I get to 17 flips is my probablity over 50%. So my answer would be 17 flips on average to get a run of odd heads followed by a tail.

The OP asks to find average number of tosses to get odd number of heads followed by tail.

The shortest such sequence is HT, which is only two tosses. The probability of that sequence is (1/2)*(1/2) = (1/4). Which means in one case out of each four you'll get the sequence after just 2 tosses.

In all cases the number of tosses is the length of the required sequence of heads followed by one tail plus all the tosses that preceded that sequence.

The number of tosses in all possible cases ranges from 2 to infinity. The longer the sequence, the lower is its probability (it is less likely to happen). Your own calculations show that.

The formula for the average is simple. It is the sum of probability for each case times its weight. In this case it is the probability of a sequence times length of the sequence (counting from the very first toss.)

So it is an infinite series:

2*p₂ + 3*p₃ + 4*p₄ + ... and so on to infinity. Where each p_n is the probability of making n tosses before the conditions are satisfied.