More Coin Filps

[irchans]

BruceZ solved the following coin toss question in this forum, "If you flip a coin until two heads occur in a row, what is the probability that you will flip the coin N times." His ingenious answer involves summing Fibonacci numbers.

I came across a very similar question on "google answers".

Consider a game where you flip a coin until you get two heads in a row.

1. How many tails on average will you flip before getting two heads in a row?

2. Let X be a random variable that counts the # of tails.
What is the distribution of X?


I was very surprised to find that this problem has a rather simple solution having nothing to do with Fibonacci numbers. I will post my "simple" solution in a couple of days if anyone is interested.

[crockpot]

for x tails, each solution is of the form:

_T_T...T_THH, where there are x tails, and each _ represents either a head or no flip.

the probability of getting each of these distributions is 2^(x+2+# of heads), and there are (x nCr n) ways to get the number of distributions for n heads.

the probability of getting x tails is thus a binomial distribution:

1/2^(x+2) + (x nCr 1)/2^(x+3) + (x nCr 2)/2^(x+4)...+1/2^(2x+2).

This simplifies to:

1/2^2 * (1/2 + 1/2^2)^x

or 1/4 * (3/4)^x.

i'm too tired to work out the expected value for this right now.

[irchans]

Excellent solution crocksucker! That was much much shorter and better than my first solution. Your solution hinges on the observation that the length of the coin toss sequence is between 2 + #tails and 2 + 2*(#tails). [img]/images/graemlins/ooo.gif[/img] I never thought of that.


There still is a slightly simpler solution which does not use the binomial theorem or combinations.

[Copernicus]

What does (x nCr n) represent?

[crockpot]

number of combinations picking n items from x (aka x choose n, or (x!)/(x-n)!(n!))

i picked this notation because texas instruments uses it.

[crockpot]

hmm, let me take a shot...

the ratio between the probability of (x+1) tails and x tails should remain constant for all x. therefore, since the probability of getting 0 tails is 1/4, the ratio must be 3/4 in order to make the sum of the infinite series equal to 1.

[Copernicus]

[ QUOTE ]
number of combinations picking n items from x (aka x choose n, or (x!)/(x-n)!(n!))

i picked this notation because texas instruments uses it.

[/ QUOTE ]

I thought it must be something more complex than C(x,n), since I'm not sure the solution is right then. I'll have to think about it more but off the top of my head that gives too much freedom to the Heads, allowing HH to be selected.

[Copernicus]

[ QUOTE ]
hmm, let me take a shot...

the ratio between the probability of (x+1) tails and x tails should remain constant for all x. therefore, since the probability of getting 0 tails is 1/4, the ratio must be 3/4 in order to make the sum of the infinite series equal to 1.

[/ QUOTE ]

Good observation I think, and knowing that carries you to the answer of the original question.

The ratio of the terms in the probability distribution of getting to each flip is 3/4, but the expected number of Tails has each term in that sum weighted by the number of Tails . Ie E(T)=(0*1/4 + 1 * (1/4 * 3/4) + (2 * 1/4 * (3/4)^2)....

Using the methodology in the dice thread the answer to the expected number of Ts is 3. Is that reasonable?

P(0)=1/4
P(1)=3/16
P(2)=9/64
P(3)=27/256
P(4)=81/1024
P(5)=and so on

Weighting the probabilities by that number of Ts till T=10 gets to 2.4 o 2.5 (I did the math fast and got 2 different answers) so taking it to infinity looks close to 3 to me.

[irchans]

[ QUOTE ]

the ratio between the probability of (x+1) tails and x tails should remain constant for all x. therefore, since the probability of getting 0 tails is 1/4, the ratio must be 3/4 in order to make the sum of the infinite series equal to 1


[/ QUOTE ]

That is a great, short answer using just one observation and one simple infinite sum. How would you prove the observation "the ratio between the probability of (x+1) tails and x tails should remain constant"?

[crockpot]

it helps to think of the sequences with (x+1) tails as all sequences of x tails, with HT or T added before them. conveniently this also gives you the ratio of 3/4 if you work it out, since the T... will occur with 1/2 the probability of the x tails, and the HT.... with 1/4 the probability.