Interviewstreet had their second CodeSprint in January that included the question below. The programmatic answer is posted but doesn't include a statistical explanation.
(You can see the original problem and posted solution by signing in to the Interviewstreet website with Google creds and then going to the Coin Tosses problem from this page.)
Coin Tosses
You have an unbiased coin which you want to keep tossing until you get N consecutive heads. You've tossed the coin M times and surprisingly, all tosses resulted in heads.
What is the expected number of additional tosses needed until you get N consecutive heads?
Input:
The first line contains the number of cases T. Each of the next T lines contains two numbers N and M.
Output:
Output T lines containing the answer for the corresponding test case. Print the answer rounded to exactly 2 decimal places.
Sample Input:
4
2 0
2 1
3 3
3 2
Sample Output:
6.00
4.00
0.00
8.00
Sample Explanations:
If N = 2 and M = 0, you need to keep tossing the coin until you get 2 consecutive heads. It is not hard to show that on average, 6 coin tosses are needed.
If N = 2 and M = 1, you need 2 consecutive heads and have already have 1. You need to toss once more no matter what. In that first toss, if you get heads, you are done. Otherwise, you need to start over, as the consecutive counter resets, and you need to keep tossing the coin until you get N=2 consecutive heads. The expected number of coin tosses is thus 1 + (0.5 * 0 + 0.5 * 6) = 4.0
If N = 3 and M = 3, you already have got 3 heads, so you do not need any more tosses.
All of the mathematical equations I came up with had the right answers for the sample input data listed above, but was wrong for all of their other input sets (which are not known). Their programmatic solution appears to solve the problem far differently from my try-to-come-up-with-an-equation method. Can someone please explain how to come up with an equation that would solve this?
Best Answer
This is a computational exercise, so think recursively. The current state of coin flipping is determined by the ordered pair $(N,M)$ with $N\ge M\ge 0$. Let the expected number of flips to reach $N$ consecutive heads be $e(N,M)$:
(1) There is a 50% chance the next flip will be heads, taking you to the state $(N,M+1)$, and a 50% chance the next flip will be tails, taking you to the state $(N,0)$. This costs one flip. Therefore the expectation (recursively) is given by
$$e(N,M) = \frac{1}{2} e(N,M+1) + \frac{1}{2} e(N,0) + 1.$$
(2) Base conditions: you have already stipulated that
$$e(N,0) = 2^{N+1}-2$$
and obviously
$$e(N,N) = 0$$
(no more flips are needed).
Here's the corresponding Mathematica program (including caching of intermediate results to speed up the recursion, which effectively makes it a dynamic programming solution):
The program would look similar in other programming languages that support recursion. Mathematically, we can verify that $e(N,M) = 2^{N+1} - 2^{M+1}$ simply by checking the recursion, because it obviously holds for the base cases:
$$2^{N+1} - 2^{M+1} = 1 + (2^{N+1} - 2^{M+2} + 2^{N+1} - 2)/2,$$
which is true for any $M$ and $N$, QED.
More generally, the same approach will establish that $e(N,M) = \frac{p^{-N} - p^{-M}}{1-p}$ when the coin has probability $p$ of heads. The hard part is working out the base condition $e(N,0)$. That is done by chasing the recursion out $N$ steps until finally $e(N,0)$ is expressed in terms of itself and solving:
$$\eqalign{ e(N,0) &= 1 + p e(N,1) + (1-p) e(n,0) \\ &= 1 + p\left(1 + p e(N,2) + (1-p) e(N,0)\right) + (1-p) e(N,0) \\ \cdots \\ &= 1 + p + p^2 + \cdots + p^{N-1} + (1-p)[1 + p + \cdots + p^{N-1}]e(N,0);\\ e(N,0) &= \frac{1-p^N}{1-p} + (1-p^N)e(N,0); \\ e(N,0) &= \frac{p^{-N}-1}{1-p}. }$$