10
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ See also here where also we find the $2^{N+1}-2^{M+1}$ result given by Daniel Johnson below. $\endgroup$ – Dilip Sarwate Feb 16 '12 at 19:46
8
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Perhaps working iteratively rather than recursively might be better? You have $$e(N,M)=\frac{1}{2}e(N,M+1)+\frac{1}{2}e(N,0)+1$$ which gives $$e(N,M+1)=2e(N,M)-2^{N+1}$$ and so $$\begin{align*}e(N,1)&=2e(N,0)-2^{N+1}=2(2^{N+1}-2)-2^{N+1}=2^{N+1}-4\\e(N,2)&=2e(N,1)-2^{N+1}=2(2^{N+1}-4)-2^{N+1}=2^{N+1}-8\end{align*}$$ and so on giving $$e(N,M)=2^{N+1}-2^{M+1}.$$ Or the difference equation could be solved "theoretically" instead of by iteration. $\endgroup$ – Dilip Sarwate Feb 16 '12 at 22:59
  • $\begingroup$ @Dilip The inferences you draw both at "which gives" and "and so on" are recursive. What solution method do you have in mind by "solved theoretically"? $\endgroup$ – whuber Mar 24 '13 at 13:25
  • $\begingroup$ To my mind, the difference between recursive and iterative is the method of working. For the relation $$x(n)=2x(n-1),~~ x(0)=1,$$ recursion calculates $x(n)$ as $$x(n)=2x(n-1)=2(2x(n-2))=2(2(2x(n-3)))=\cdots=2(2(\cdots 2x(0)\cdots)=2^n$$ while iteration says $$x(0)=1\Rightarrow x(1)=2x(0)=2\Rightarrow x(2)=2x(1)=2^2\Rightarrow \cdots x(n)=2x(n-1)=2\cdot 2^{n-1}=2^n.$$ "theoretically" meant solving a difference equation by finding the characteristic polynomial, determining its roots, and then fitting the general solution to the initial conditions, instead of simple calculation as above. $\endgroup$ – Dilip Sarwate Mar 24 '13 at 14:51
  • $\begingroup$ From a programming viewpoint, a program find_x(n) is recursive if it says something like if n=0 return 1 else return 2*find_x(n-1) in which find_x calls itself $n$ times, whereas an iterative program would say something like y = 1; while n > 0 do begin y=2*y; n=n-1 end; return y $\endgroup$ – Dilip Sarwate Mar 24 '13 at 23:25
  • $\begingroup$ If you look at how those programs are actually implemented on the computer, @Dilip, in many environments (such as R) they scarcely differ at all. (In one case you create and then process a vector 1:n and in the other you will discover that n:1 has been placed on the stack and processed in reverse.) But part of my point was conceptual: your initial comment spoke of "working iteratively." That referred to the analysis and not to any computer program. But these are trivial, tangential points whose discussion doesn't warrant extending this comment thread. $\endgroup$ – whuber Mar 24 '13 at 23:43
5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ This is a harder way to solve it than the recursive idea listed above, but it's extremely useful to see both approaches laid out together. Most people don't appreciate the way that stopping time methods can be used for small, practical problems too. $\endgroup$ – ely Feb 16 '12 at 23:53
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.