Probability of winning game whereby $T+1$ heads in a row of a coin flip is required to win where $T$ is the number of cumulative tails flipped

Question

I have a weird question which probably seems out of place here but it has proven more difficult than anticipated. I am going to describe the game without showing work toward a solution. Numerically, the solution is easy - it is about $71\%.$ A simple Python script to determine this is included at the end of the question.

Say I flip a coin. If I get heads, then I win the game I am describing. However, if I get tails, then I need two heads in a row to win the game. If instead I flip a tails while trying to get the necessary number of heads in a row, then I then need three heads in a row. That is, to win, I need to flip $T + 1$ heads consecutively, where $T$ is the cumulative number of tails flipped. I hope this is clear. If not, the script below is very explicit.

I want to find the overall probability of winning. Obviously, there is no losing condition, but the game quickly devolves into infinite flips as the probability of winning decreases rapidly. What is the overall probability of winning before the first coin flip? I want to derive an expression for this number.

I know this is weird and particularly 'unacademic', but any help would be appreciated to infinity and beyond.

Thank you.

import random
# number of games to play (should be infinity)
g = 100000
def game():
    # number of heads needed in a row before we give up (should also be infinity)
    N = 100
    # cumulative sum of tails
    T = 0
    # heads needed to win
    H = 1
    while H < N:
        # simulate flip
        flip = random.randint(0, 1)
        # 1 for h, 0 for t
        if flip == 1:
            H -= 1
        if flip == 0:
            T += 1
            H = T + 1
        # won
        if H == 0:
            return 1
    # not yet won
    return 0
outcomes = [game() for a in range(g)]
print(sum(outcomes)/len(outcomes))

Answer 1

The probability of not winning is $$ \prod_{T=1}^\infty \left(1 - \frac1{2^T} \right) = \frac12 \frac34 \frac78 \frac{15}{16} \cdots = 0.28878809508660 \ldots ; $$ that's a well-known constant (equal to the probability that a large square matrix of integers has odd determinant), and is not expected to have a "closed form", though it does have the shockingly good approximation $$ 2^{1/24} \sqrt{\frac{2\pi}{\log 2}} \exp \left(-\frac{\pi^2}{6\log 2}\right) $$ (good to about one part in $e^{4\pi^2/\log 2} \approx 5 \cdot 10^{24}$). This the win probability is $1 - \prod_{T=1}^\infty (1 - 2^{-T})$ which is numerically about 71.12%, consistent with your experimental 71%.

To get the product formula for the probability of losing: to lose, you must get tails on the first flip, then get the next tails during the next two flips, then (counting from that second tails) get the next tails during the next three, then (counting from that third tails) get the next tails during the next four, etc. The first tails happens with probability 1/2; the next, with probability 3/4, independently of the first; the third, independently 7/8, etc., and in general the $T$-th with probability $1 - 2^{-T}$, independently of the rest.

Answer 2

The game can be modeled by the following Markov chain with infinitely many states, the state $\bbox[yellow]{\boxed 0} $ is final, entering this state means winning. The other states are $\boxed 1, \boxed 2, \boxed 3, \boxed 4, \boxed 5, \dots$ - and the game starts in $\bbox[lightblue]{\boxed 1}$:

$$\require{AMScd} \begin{CD} \bbox[yellow]{\boxed 0} @= \bbox[yellow]{\boxed 0} @= \bbox[yellow]{\boxed 0} @= \bbox[yellow]{\boxed 0} @= \bbox[yellow]{\boxed 0} @= \dots\\ @A {\bbox[lightgreen]{\frac12}}A 1 A @A {\bbox[lightgreen]{\frac14}}A 11 A @A {\bbox[lightgreen]{\frac18}}A 111 A @A {\bbox[lightgreen]{\frac1{16}}}A 1111 A @A {\bbox[lightgreen]{\frac1{32}}}A 11111 A \\ \bbox[lightblue]{\boxed 1} @>\frac 12>{0}> \boxed 2 @>\frac 34>\substack{0\\10}> \boxed 3 @>\frac 78>\substack{0\\10\\110}> \boxed 4 @>\frac {15}{16}>\substack{0\\10\\110\\1110}> \boxed 5 @>\frac {31}{32}>\substack{0\\10\\110\\1110\\11110}> \dots \end{CD}$$

The probability of winning is $$ P = {\bbox[lightgreen]{\frac12}} \ +\ \frac12\cdot{\bbox[lightgreen]{\frac14}} \ +\ \frac12\cdot\frac34\cdot{\bbox[lightgreen]{\frac18}} \ +\ \frac12\cdot\frac34\cdot\frac78\cdot{\bbox[lightgreen]{\frac1{16}}} \ +\ \frac12\cdot\frac34\cdot\frac78\cdot\frac{15}{16}\cdot{\bbox[lightgreen]{\frac1{32}}} \ +\ \dots $$ and the term number $k$ in the sum corresponds to reaching the final state $\bbox[yellow]{\boxed 0}$ after being in the states $\boxed k$ at the last step. It is easier to compute the complementary probability $q=1-p$, which corresponds to moving on the horizontal line from $\bbox[lightblue]{\boxed 1}$ to infinity: $$ \begin{aligned} Q&= \frac 12\cdot \frac 34\cdot \frac 78\cdot \frac {15}{16}\cdot \frac {31}{16}\cdot \dots =\prod_{n\ge 1}\left(1-\frac 1{2^n}\right) =\prod_{n\ge 1}\left(1-q^n\right)_{\text{ in }q=1/2} \\ & =\left(\frac{\tau(q=1/2)}{1/2}\right)^{1/24} =\left(\frac{\tau\left(z=\frac{-\log 2}{2\pi i}\right)}{1/2}\right)^{1/24} \end{aligned} $$ where $\tau$ stays (with abuse) for the Ramanujan tau function in both "worlds", as a function of the nome $q$, and as a function of $z$, with the connection $q=\exp(2\pi i\; z)$.

Page 358 of

Constants Associated with Enumerating of Discrete Structures

gives (references and) the formulas for $Q$. (See also page 318.) $$ \begin{aligned} Q&= \frac 13 -\frac 13\cdot\frac 17 +\frac 13\cdot\frac 17\cdot\frac 1{15} -\frac 13\cdot\frac 17\cdot\frac 1{15}\cdot\frac 1{31} +\frac 13\cdot\frac 17\cdot\frac 1{15}\cdot\frac 1{31}\cdot\frac 1{63} \pm\dots \\ &=\exp-\sum_{n\ge 1}\frac 1{n(2^n-1)} \\ &=\sqrt{\frac {2\pi}{\log 2}}\exp\left(\frac {\log 2}{24}-\frac{\pi^2}{6\log 2}\right)\prod_{n\ge 1}\left(1-\exp\left(-\frac{4\pi^2n}{\log 2}\right)\right)\ . \end{aligned} $$

---

Numerically, $Q\approx 0.28878809508660242127889972192923078008891190484\dots$ which leads to the numerical value for $P\approx 0.71121190\dots$, matching OP's experiment.