Expected number of coin tosses to get N consecutive, given M consecutive

Question

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?

Answer 1

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):

e[n_, m_] /; n > m > 0 := e[n, m] = 1 + (e[n, m + 1] + e[n, 0])/2 // Simplify
e[n_, 0] := 2^(n + 1) - 2
e[n_, n_] := 0

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}. }$$

Answer 2

To solve this problem, I will use stochastic processes, stopping times, and dynamic programming.

First, some definitions:

$$X_n \doteq \#\text{(of consecutive heads after the nth flip)}$$ We also allow a value for $X_0$ to mean the number of consecutive heads before we start. So, for $X_0 = 0$ and the sequence of flips HHTHHHTHTTHH, the corresponding values of $X$ are 120123010012. If we had $X_0 = M$, the values of X would be (M+1)(M+2)0123010012.

Then define the following stopping times: $$\tau_N \doteq \min\{k: X_k = N\} \text{ and } \tau_0 \doteq \min\{k > 1: X_k = 0\} $$

The value we are looking for is the expected value of $\tau_N$, the number of flips it takes to observe N consecutive flips $(X_{\tau_N} = N)$, given that we have already observed M consecutive flips $(X_0 = M)$. Assume $M \leq N$ as the answer is trivially 0 otherwise. We compute:

$$E[\tau_N|X_0 =M] = E[\tau_N\boldsymbol{1}_{\{\tau_N < \tau_0\}} + \tau_N\boldsymbol{1}_{\{\tau_N > \tau_0\}}|X_0 =M] $$ $$ = (N-M)(\frac{1}{2})^{N-M} + E[\tau_0|\tau_N > \tau_0,X_0 =M] + (1 - (\frac{1}{2})^{N-M})E[\tau_N|X_0 = 0]$$ This leaves us to compute the last two conditional expectations.

The first corresponds to the expected number of flips before getting a tail assuming a tail is flipped before N consecutive heads are observed assuming we start with M consecutive heads. It is not too difficult to see that

$$E[\tau_0|\tau_N > \tau_0,X_0 =M] = \sum^{N-M}_{j=1}(j)(\frac{1}{2})^j = 2 - (N-M+2)(\frac{1}{2})^{N-M}$$

Now all we have to do is compute the second conditional expectation which corresponds to the expected number of flips it takes to observe N consecutive heads starting from 0. With a similar calculations, we see that

$$E[\tau_N|X_0 = 0] = E[\tau_N\boldsymbol{1}_{\{\tau_N < \tau_0\}} + \tau_N\boldsymbol{1}_{\{\tau_N > \tau_0\}}|X_0 =0]$$ $$ = N(\frac{1}{2})^{N} + E[\tau_0|\tau_N > \tau_0,X_0 =0] + (1 - (\frac{1}{2})^N)E[\tau_N|X_0 = 0]$$ $$= 2^N\lbrace N(\frac{1}{2})^{N} + (2 - (N+2)(\frac{1}{2})^{N})\rbrace$$ $$ = 2^{N+1} - 2$$

This gives a final answer of:

$$E[\tau_N|X_0 =M] = (N-M)(\frac{1}{2})^{N-M} + 2 - (N-M+2)(\frac{1}{2})^{N-M} + (1 - (\frac{1}{2})^{N-M})(2^{N+1} - 2)$$ $$ = 2^{N+1}-2^{M+1}$$

This agrees with the four test cases you've listed. With such a simple answer, there may be an easier way to compute this.

Answer 3

Warning: the following may not be considered as a proper answer in that it does not provide a closed form solution to the question, esp. when compared with the previous answers. I however found the approach sufficiently interesting to work out the conditional distribution.

Consider the preliminary question of getting a sequence of $N$ heads out of $k$ throws, with probability $1-p(N,k)$. This is given by the recurrence formula $$ p(N,k) = \begin{cases} 1 &\text{if } k<N\\ \sum_{m=1}^{N} \frac{1}{2^m}p(N,k-m) &\text{else}\\ \end{cases} $$ Indeed, my reasoning is that no consecutive $N$ heads out of $k$ draws can be decomposed according to the first occurrence of a tail out of the first $N$ throws. Conditioning on whether this first tail occurs at the first, second, ..., $N$th draw leads to this recurrence relation.

Next, the probability of getting the first consecutive N heads in $m\ge N$ throws is $$ q(N,m) =\begin{cases} \dfrac{1}{2^N} &\text{if }m=N\

     p(N,m-N-1) \dfrac{1}{2^{N+1}} &\text{if } N<m<2N+1
     \end{cases}

$$ The first case is self-explanatory. the second case corresponds to a tail occuring at the $m-N-1$th draw, followed by $N$ heads, and the last case prohibits $N$ consecutive heads prior to the $m-N-1$th draw. (The two last cases could be condensed into one, granted!)

Now, the probability to get $M$ heads first and the first consecutive $N$ heads in exactly $m\ge N$ throws (and no less) is $$ r(M,N,m) = \begin{cases} 1/2^N &\text{if }m=N\

     0 &\text{if } N<m\le N+M\\

      \dfrac{1}{2^{M}}\sum_{r=M+1}^{N}\dfrac{1}{2^{r-M}}q(N,m-r)&\text{if } N+M<m

\end{cases} $$ Hence the conditional probability of waiting $m$ steps to get $N$ consecutive heads given the first $M$ consecutive heads is $$ s(M,N,m) = \begin{cases} 1/{2^{N-M}} &\text{if }m=N\ 0 &\text{if } N \sum_{r=M+1}^{N}\dfrac{q(N,m-r)}{2^{r-M}}&\text{if } N+M

\end{cases} $$ The expected number of draws can then be derived by $$ \mathfrak{E}(M,N)= \sum_{m=N}^\infty m\, s(M,N,m) $$ or $\mathfrak{E}(M,N)-M$ for the number of additional steps...