[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.