A Probability Question

[anarchy]

Lets say you flip a coin 10,000 times. Everytime it lands heads 3 times in a row you get a point and you start again. Therefore, if it lands heads 5 times in a row you don't get 3 points. If it landed
heads 6 times in a row you would get 2 points.
What is your expected value for points for flipping a coin 10,000
times?

This is just for my own curiosity, if anybody knows how to solve this problem without using some type of random number generator your input would be helpful.

[uuDevil]

Poster Izverg04 provided the link below a while ago. It might interest you:

Success Run.... (http://www.hicstatistics.org/2003StatsProceedings/Gregory%20Light.pdf)

[jason1990]

Let E_n be the expected number of points when flipping a coin n times. Then E_n solves the difference equation

(1) E_n = (1/2)E_{n-1} + (1/4)E_{n-2} + (1/8)E_{n-3} + (1/8)(1 + E_{n-3})
= (1/2)E_{n-1} + (1/4)E_{n-2} + (1/4)E_{n-3} + 1/8

with initial conditions

(2) E_1 = 0, E_2 = 0, E_3 = 1/8.

To solve (1), we first find a particular solution. If we look for a particular solution of the form cn, we find that c = 1/14.

Next, we find the general solution to the corresponding homogeneous difference equation

(3) E_n = (1/2)E_{n-1} + (1/4)E_{n-2} + (1/4)E_{n-3}

by solving the characteristic equation

r^3 = (1/2)r^2 + (1/4)r + (1/4).

By inspection, we see that r = 1 is a solution. Using polynomial division and the quadratic formula, we find that the other two roots are z = -(1/4) + (sqrt{3}/4)i and its complex conjugate, bar{z}. Therefore, the general solution to (3) is given by

c_1 + c_2 Re{z^n} + c_3 Im{z^n}.

Writing z in polar coordinates, we have

z = (1/2)e^{2pi i/3},

which, by Euler's formula, gives

z^n = (1/2^n)cos(2pi n/3) + i(1/2^n)sin(2pi n/3).

We can therefore write the general solution to (1) as

E_n = c_1 + c_2(1/2^n)cos(2pi n/3) + c_3(1/2^n)sin(2pi n/3) + n/14

and it only remains to use (2) to find the values of the constants c_j. This is a simple exercise in linear algebra, and the result is

c_1 = -5/49, c_2 = 5/49, c_3 = 11/(49sqrt{3}).

Putting it all together, we have

E_n = -5/49 + (5/49)(1/2^n)cos(2pi n/3) + (11/(49sqrt{3}))(1/2^n)sin(2pi n/3) + n/14.

If we take n = 10000, then we obtain the expected number of points when flipping a coin 10,000 times, which is

-5/49 + 6/(49*2^10001) + 10000/14.

The second term is negligible, so the expected value is approximately

-5/49 + 10000/14 = 714.1837.

[jason1990]

Another way to get very close to the true expected value is to reason as follows: Define a "round" of the game to be a sequence of flips that either ends with getting a point or ends with flipping a tail. So if your first flip is a tail, then the first round is over and the next round begins. But if your first flip is a head and the second flip is a tail, then the first round is over after the second flip and the next round begins. If your first two flips are heads, then the first round will be over after the third flip, no matter what happens.

It's easy to see that the expected length of each round is 1.75 flips. So you can expect to play 10000/1.75 rounds. In each round, you get a point with probability 1/8, so you expect to get (10000/1.75)*(1/8) = 10000/14 points.

Notice that this is not exactly the right answer, but it differs from the true expected value by less than than 1/50th of a percent. The discrepancy comes from the fact that you may not be able to complete the final round, since you are not allowed any more than 10000 flips.

[gaming_mouse]

Jason,

Could you explain how you got the initial difference equation?

Also, how do you move from that to the characteristic function? Do you have to assume that the formula for E_n is polynomial. I can see that it is, but is that the assumption? Which theorems/techniques are you using?

Thanks,
gm

[jason1990]

[ QUOTE ]
Could you explain how you got the initial difference equation?

[/ QUOTE ]

The initial difference equation comes from first step analysis. There are four disjoint events that could happen in the first steps: (1) the first flip is a tail, (2) the first two flips are HT, (3) the first three are HHT, and (4) the first three are HHH. These account for all possibilities and their probabilities are 1/2, 1/4, 1/8, and 1/8 respectively.

After event (1), you start over and your expectation is E_{n-1}. After event (2) it is E_{n-2}. After event (3), it is E_{n-3}. After event (4), however, you gain a point before starting over. So your expectation is 1 + E_{n-3}. Hence, your expectation at the start of the game is given by the first formula in my earlier post.

[ QUOTE ]
Also, how do you move from that to the characteristic function? Do you have to assume that the formula for E_n is polynomial.

[/ QUOTE ]

This technique is analogous to the technique used for solving homogeneous, linear differential equations with constant coefficients (there you look for solutions of the form e^{rt}).

With the difference equation, we are looking for solutions of the form r^n. Under this assumption, we are led to the characteristic equation. When this equation has distinct roots, it can be shown that the resulting solutions are linearly independent. Also, when the roots come in complex conjugate pairs, it can be shown that the two resulting solutions can be replaced by their real and imaginary parts, and still yield a full set of linear independent solutions.

The theorems for difference equations are so similar to those for differential equations (and so much easier to prove) that I would recommend, if you're interested, just reviewing the differential equation stuff and working out the difference equation stuff on your own. But if you really want a reference, I'm sure you can find a good one just by googling for it. If you can't, ask me again later and I'll see what I can dig up.