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.

Answer

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.

Attribution
Source : Link , Question Author : Elliott , Answer Author : Did

Leave a Comment