What's the probability that a sequence of coin flips never has twice as many heads as tails?

I gave my friend this problem as a brainteaser; while her attempted solution didn't work, it raised an interesting question.

I flip a fair coin repeatedly and record the results. I stop as soon as the number of heads is equal to twice the number of tails (for example, I will stop after seeing HHT or THTHHH or TTTHHHHHH). What's the probability that I never stop?

I've tried to just compute the answer directly, but the terms got ugly pretty quickly. I'm hoping for a hint towards a slick solution, but I will keep trying to brute force an answer in the meantime.

-
Hopefully whatever method resolves this applies to other ratios than $2$. –  anon Aug 27 '11 at 3:32
@anon, good idea... See my answer. –  Did Aug 27 '11 at 13:53
@anon: I've generalized my answer up to an infinite series expression as well. –  Mike Spivey Aug 27 '11 at 21:00
See "a coin toss question" for the similar problem of flipping until achieving the same number of heads as tails. –  Mike Spivey Aug 31 '11 at 20:55
@Elliot I'd like you remind you that this question doesn't currently have an accepted answer. –  Git Gud Jun 16 '13 at 9:36

The game stops with probability $u=\frac34(3-\sqrt5)=0.572949017$.

See the end of the post for generalizations of this result, first to every asymmetric heads-or-tails games (Edit 1), and then to every integer ratio (Edit 2).

To prove this, consider the random walk which goes two steps to the right each time a tail occurs and one step to the left each time a head occurs. Then the number of tails is the double of the number of heads each time the walk is back at its starting point (and only then). In other words, the probability that the game never stops is $1-u$ where $u=P_0(\text{hits}\ 0)$ for the random walk with equiprobable steps $+2$ and $-1$.

The classical one-step analysis of hitting times for Markov chains yields $2u=v_1+w_2$ where, for every positive $k$, $v_k=P_{-k}(\text{hits}\ 0)$ and $w_k=P_{k}(\text{hits}\ 0)$. We first evaluate $w_2$ then $v_1$.

The $(w_k)$ part is easy: the only steps to the left are $-1$ steps hence to hit $0$ starting from $k\ge1$, the walk must first hit $k-1$ starting from $k$, then hit $k-2$ starting from $k-1$, and so on. These $k$ events are equiprobable hence $w_k=(w_1)^k$. Another one-step analysis, this time for the walk starting from $1$, yields $$2w_1=1+w_3=1+(w_1)^3$$ hence $w_k=w^k$ where $w$ solves $w^3-2w+1=0$. Since $w\ne1$, $w^2+w=1$ and since $w<1$, $w=\frac12(\sqrt5-1)$.

Let us consider the $(v_k)$ part. The random walk has a drift to the right hence its position converges to $+\infty$ almost surely. Let $k+R$ denote the first position visited on the right of the starting point $k$. Then $R\in\{1,2\}$ almost surely, the distribution of $R$ does not depend on $k$ because the dynamics is invariant by translations, and $$v_1=r+(1-r)w_1\quad\text{where}\ r=P_{-1}(R=1).$$ Now, starting from $0$, $R=1$ implies that the first step is $-1$ hence $2r=P_{-1}(A)$ with $A=[\text{hits}\ 1 \text{before}\ 2]$. Consider $R'$ for the random walk starting at $-1$. If $R'=2$, $A$ occurs. If $R'=1$, the walk is back at position $0$ hence $A$ occurs with probability $r$. In other words, $2r=(1-r)+r^2$, that is, $r^2-3r+1=0$. Since $r<1$, $r=\frac12(3-\sqrt5)$ (hence $r=1-w$).

Plugging these values of $w$ and $r$ into $v_1$ and $w_2$ yields the value of $u$.

Edit 1 Every asymmetric random walk which performs elementary steps $+2$ with probability $p$ and $-1$ with probability $1-p$ is transient to $+\infty$ as long as $p>\frac13$ (and naturally, for every $p\le\frac13$ the walk hits $0$ with full probability). In this regime, one can compute the probability $u(p)$ to hit $0$. The result is the following.

For every $p$ in $(0,\frac13)$, $u(p)=\frac32\left(2-p-\sqrt{p(4-3p)}\right).$

Note that $u(p)\to1$ when $p\to\frac13$ and $u(p)\to0$ when $p\to1$, as was to be expected.

Edit 2 Coming back to symmetric heads-or-tails games, note that, for any fixed integer $N\ge2$, the same techniques apply to compute the probability $u_N$ to reach $N$ times more tails than heads.

One gets $2u_N=E(w^{R_N-1})+w^N$ where $w$ is the unique solution in $(0,1)$ of the polynomial equation $2w=1+w^{1+N}$, and the random variable $R_N$ is almost surely in $\{1,2,\ldots,N\}$. The distribution of $R_N$ is characterized by its generating function, which solves $$(1-(2-r_N)s)E(s^{R_N})=r_Ns-s^{N+1}\quad\text{with}\quad r_N=P(R_N=1).$$ This is equivalent to a system of $N$ equations with unknowns the probabilities $P(R_N=k)$ for $k$ in $\{1,2,\ldots,N\}$. One can deduce from this system that $r_N$ is the unique root $r<1$ of the polynomial $(2-r)^Nr=1$. One can then note that $r_N=w^N$ and that $E(w^{R_N})=\dfrac{Nr_N}{2-r_N}$ hence some further simplifications yield finally the following general result.

For every $N\ge2$, $u_N=\frac12(N+1)r_N$ where $r_N<1$ solves the equation $(2-r)^Nr=1$.

-
+1: Nice work, Didier! (And for the side effect of showing me that the answer I got is correct, too.) –  Mike Spivey Aug 27 '11 at 14:56
@Mike, thanks. To tell the truth, I DID compute the numerical value of my answer as soon as I got a formula, to check whether it coincided with the numerical value of your mysterious formula and I WAS relieved to see these coincided... –  Did Aug 27 '11 at 16:28
+1, I had a feeling a Markov approach would pop up. Nice to see such a simple polynomial's root solve the general form. –  anon Aug 27 '11 at 21:24
@anon, yes. This is no accident that the computations go through and that the algebra is nice, there is an underlying structure to all this, sometimes called cycles-and-weights Markov chains, which is a nifty extension of +/-1 random walks (I might add some references one day). –  Did Aug 27 '11 at 21:51

(Update: The answer to the original question is that the probability of stopping is $\frac{3}{4} \left(3 - \sqrt{5}\right)$. See end of post for an infinite series expression in the general case.)

Let $S(n)$ denote the number of ways to stop after seeing $n$ tails. Seeing $n$ tails means seeing $2n$ heads, so this would be stopping after $3n$ flips. Since there are $2^{3n}$ possible sequences in $3n$ flips, the probability of stopping is $\sum_{n=1}^{\infty} S(n)/8^n$.

To determine $S(n)$, we see that there are $\binom{3n}{n}$ ways to choose which $n$ of $3n$ flips will be tails. However, this overcounts for $n > 1$, as we could have seen twice as many heads as tails for some $k < n$. Of these $\binom{3n}{n}$ sequences, there are $S(k) \binom{3n-3k}{n-k}$ sequences of $3n$ flips in which there are $k$ tails the first time we would see twice as many heads as tails, as any of the $S(k)$ sequences of $3k$ flips could be completed by choosing $n-k$ of the remaining $3n-3k$ flips to be tails. Thus $S(n)$ satisfies the recurrence $S(n) = \binom{3n}{n} - \sum_{k=1}^{n-1} \binom{3n-3k}{n-k}S(k)$, with $S(1) = 3$.

The solution to this recurrence is $S(n) = \frac{2}{3n-1} \binom{3n}{n}.$ This can be verified easily, as substituting this expression into the recurrence yields a slight variation on Identity 5.62 in Concrete Mathematics (p. 202, 2nd ed.), namely, $$\sum_k \binom{tk+r}{k} \binom{tn-tk+s}{n-k} \frac{r}{tk+r} = \binom{tn+r+s}{n},$$ with $t = 3$, $r = -1$, $s=0$.

So the probability of stopping is $$\sum_{n=1}^{\infty} \binom{3n}{n} \frac{2}{3n-1} \frac{1}{8^n}.$$

Mathematica gives the closed form for this probability of stopping to be $$2 \left(1 - \cos\left(\frac{2}{3} \arcsin \frac{3 \sqrt{3/2}}{4}\right) \right) \approx 0.572949.$$

Added: The sum is hypergeometric and has a simpler representation. See Sasha's comments for why the sum yields this closed form solution and also why the answer is $$\frac{3}{4} \left(3 - \sqrt{5}\right) \approx 0.572949.$$

Added 2: This answer is generalizable to other ratios $r$ up to the infinite series expression. For the general $r \geq 2$ case, the argument above is easily adapted to produce the recurrence $S(n) = \binom{(r+1)n}{n} - \sum_{k=1}^{n-1} \binom{(r+1)n-(r+1)k}{n-k}S(k)$, with $S(1) = r+1$. The solution to the recurrence is $S(n) = \frac{r}{(r+1) n - 1} \binom{(r+1) n}{n}$ and can be verified easily by using the binomial convolution formula given above. Thus, for the ratio $r$, the probability of stopping has the infinite series expression $$\sum_{n=1}^{\infty} \binom{(r+1)n}{n} \frac{r}{(r+1)n-1} \frac{1}{2^{(r+1)n}}.$$ This can be expressed as a hypergeometric function, but I am not sure how to simplify it any further for general $r$ (and neither does Mathematica). It can also be expressed using the generalized binomial series discussed in Concrete Mathematics (p. 200, 2nd ed.), but I don't see how to simplify it further in that direction, either.

Added 3: In case anyone is interested, I found a combinatorial proof of the formula for $S(n)$. It works in the general $r$ case, too.

-
It's late here, and I'm going to bed. Any comments, corrections, etc., will be dealt with in the morning. And if someone has an explanation for Mathematica's output I would love to see it! –  Mike Spivey Aug 27 '11 at 6:50
Wow, incredible (both the write up and the result itself)! However, I have a slight point of confusion--why is S(1) = 1, rather than 3? –  Elliott Aug 27 '11 at 7:48
Does anyone know (or perhaps have a useful reference book to find out from) the generating function of $a_n = \binom{3n}{n}$? That should help in finding the closed form of this series. –  Ragib Zaman Aug 27 '11 at 9:17
Let $u$ be you answer, then $\cos(\frac{2}{3}\arcsin \frac{3}{4}\sqrt{\frac{3}{2}}) = 1-\frac{u}{2}$. Using $\cos(3 x) = -3 \cos(x) + 4 \cos(x)^3$, and $\cos( 2 \arcsin \frac{3}{4}\sqrt{\frac{3}{2}}) = -\frac{11}{16}$, it follows $u$ satisfy a cubic with rots $u_1=\frac{3}{2}$, $u_2 = \frac{3}{4}( 3- \sqrt{5})$ and $u_3 = \frac{3}{4}(3+ \sqrt{5})$. Root $u_2$ is the one corresponding to the original expression, by numerical comparison. –  Sasha Aug 27 '11 at 13:47
@Ragib $\sum_{k\ge 0} \binom{3 k}{k} z^k$ is a hypergeometric sum with answer $\frac{3}{4 \pi} F(\frac{1}{3}, \frac{2}{3} ; \frac{1}{2} ; \frac{9 z}{4} )$. This Gauss hypergeometric function admits simpler representation. –  Sasha Aug 27 '11 at 13:57

Here's another solution, following Ross Millikan's hint:

Let $n=H−2T$ (H=heads, T=tails). At each step, $n := n+1$ or $n := n-2$ with probability 1/2. The game starts with $n=0$ and stops when $n=0$.

For any iteration (after the initial), let $P(n)$ be the probability that the game eventually stops, given the current value of $n$ (and given that the event has not yet occurred). It's clear that $P(n)$ does not depend on time. Then the following recurrence holds:

$$P(n)= \frac{P(n+1)+P(n-2)}{2} \;, \;\; n\ne 0$$

with $P(0)=1$. We also know (do we?) that $P(-\infty)=0$ (but we don't yet know $P(+\infty)$)

The solution to this difference equation (I'll spare you the details, just the usual linear difference equation procedure, in the two regions, with the above boundary conditions) is given by:

$$P(n)= \left\{ \begin{array}{ll} \phi^{-n} & \mbox{if } n \le 0 \\ 1 + B \, [(-\phi)^n -1] & \mbox{if } n \ge 0 \end{array} \right.$$

with $B= \phi^2 (1-\phi)$, $\phi = (\sqrt{5}-1)/2$

Now, after the first step we have $n=1$ or $n=-2$ with equal probability, then the probability that the game eventually stops is

$$\frac{P(1)+P(-2)}{2}=\frac{2 \phi^2 -\phi +1}{2} = 0.572949$$

The form of $P(n)$ is interesting:

This, for example, shows that the probability of stop is strongly dependent on the first coin toss (less than 40% if tail, more than 75% if head).

This procedure also seems directly generalizable, either to asymmetric coins or other integer ratios.

Added: Here goes the details for solving the recursion:

We postulate a solution of the form $P(n)= r^n$ and replacing in the recursion $2 P(n) - P(n+1) - P(n-2) = 0$ we get $$2 \; r^2 - r^3 - 1 = 0$$ The root $r_1=1$ comes immediately, and then the others: $r_2 = - \phi$, $r_3 = 1/\phi$. Then the general solution is given by $A + B (-\phi)^n + C \phi^{-n}$, for some $A,B,C$, in each zone.

In the zone $n \le 0$: we have $P(0)=1$ and $P(-\infty)=0$. As $\phi \approx 0.618 < 1$, this implies $A=0$, $B=0$,$C=1$ Hence

$$P(n) = \phi^{-n} \hspace{10px} n \le 0$$

In the zone $n \ge 0$: we have $P(0)=1$, but we don't know $P(\infty)$. We do know it's bounded, so $C=0$, and $A=1-B$, so

$$P(n) = 1 + B \, [(-\phi)^n -1] \hspace{10px} n \ge 0$$

To get rid of the remaining degree of freedom, we write the recursion for $n=1$, and replace the value of $P(-1)$ for the previous solution:

$$2 \, P(1) = P(2) + P(-1)$$ $$2 \, (1 + B \, [-\phi -1]) = 1 + B \, [(-\phi)^2 -1] + \phi$$

From this, we obtain $B= \phi^2 (1-\phi)$.

-
This solution is beautiful! One thing I don't understand is, how did you set boundary conditions for the region n >= 0? –  Elliott Aug 29 '11 at 16:34
@Elliot: You first solve for $n \le 0$, then plugging it in the recursion for $n=1$ you resolve the remaining degree of freedom. Tell me if this is not clear, and I'll write the details. –  leonbloy Aug 29 '11 at 17:44
So... in the end, you know that P(-infty)=0? –  Did Aug 31 '11 at 21:01
Well, we "knew" (actually assumed) that from the beginning, it was $P(+\infty)$ the unknown. It's true (are you pointing to this?) that $P(-\infty)=0$ is intuitive and true but a rigorous proof is lacking here. –  leonbloy Aug 31 '11 at 21:19
Just pointing to the fact that, when P(-infty) first appear, you feel necessary to signal that the relation P(-infty)=0 might need a proof. But when you need the value of P(-infty) later on, you state it without further ado. Hence, reading your post, I was wondering if I had missed, somewhere inbetween these two appearances, a proof that P(-infty)=0. (Please use @.) –  Did Sep 1 '11 at 13:22

I would suggest $1-\phi=1-\frac{\sqrt{5}-1}{2}$. If define $P(n)$ as the probability that if we have an excess of tails of $n$ we will eventually have twice the heads as tails, the recurrence is $$P(n)=\frac{P(n+1)+P(n-2)}{2}$$ with boundary conditions $$P(n)=\begin {cases}1 &n\gt 0 \\ 0 &n=-\infty \end {cases}$$ The recurrence has solution $P(n)=\phi ^n$

-
Sorry, I'm not sure I follow. Can you please explain what P(n) represents in slightly more detail? –  Elliott Aug 27 '11 at 6:18
+1 Nice answer, though cryptic (and slightly incorrect). To clarify: Let $n(t)=H-2T$ (H=heads, T=tails), say we are interest in the event $n(t)>0$ for some $t$. Let $P(n)$ (for $n\le0$) be the probability of that event, given the value $n$ that at that time, and that the event has not ocurred before; further, let $P(1)=1$. Then, the recursion is correct, and so is the solution (actually I think its $p(n)=\phi^{1-n}$, but anyway $P(0)= 0.618033989$). But... (continued) –  leonbloy Aug 27 '11 at 15:17
The problem is that the original game stops when $H=2T$ exactly, and this event is not equivalent to $H>2T$ (for example, the sequence $HHHTHHHTHHT...$ does not make the game stop. I wonder if this can be corrected, I liked this approach. –  leonbloy Aug 27 '11 at 15:22
@leonbloy: Good elaboration. Thanks. I was thinking that if we have excess heads then with probability 1 we get back to a 2:1 ratio. But you are right we can skip over it. A more telling (to me) sequence that fails is $HHHTTTHTHTHTHT...$ –  Ross Millikan Aug 27 '11 at 15:28
The approach was indeed fixable, I posted the derivation in my own answer - I hope this it's ok. –  leonbloy Aug 29 '11 at 0:15