6
$\begingroup$

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))
$\endgroup$
2
  • $\begingroup$ Thank you so much for your generous solutions. $\endgroup$
    – user504691
    Commented May 14, 2023 at 22:49
  • $\begingroup$ Also asked at math.stackexchange.com/questions/4698675/… $\endgroup$
    – Henry
    Commented May 15, 2023 at 11:49

2 Answers 2

12
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Does the shockingly good approximation come from some nice reasoning? $\endgroup$ Commented May 14, 2023 at 5:06
  • 1
    $\begingroup$ @SridharRamesh yes, as I expect to note in the next edit: $\eta(q) = q^{1/24} \prod_{n=1}^\infty (1 - q^n)$ is a modular form of weight $1/2$, so $\eta(e^{-2\pi/t}) = t^{1/2} \eta(e^{-2\pi t})$, and if $q=1/2$ then $2\pi t = \log 2$ makes $t$ small and $e^{-2\pi/t}$ tiny. $\endgroup$ Commented May 14, 2023 at 5:25
5
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ The cited book is S. R. Finch, Mathematical Constants (2003), Chapter 5. The constant also appears in Kolchin V. F. Random Graphs (1998). $\endgroup$
    – dan_fulea
    Commented May 14, 2023 at 6:00
  • $\begingroup$ I like this derivation since I started it and then didn't have time. It was actually not obvious to me that the final product would result. $\endgroup$
    – kodlu
    Commented May 14, 2023 at 18:25
  • 2
    $\begingroup$ @kodlu This is the same as in Elkies' solution, posted it alternatively only for the diagram with the states, that is in fact the solution by picture. (At the beginning i had a lot of H's and T's inside, it became clearly laid out by using $1$ instead of $H$, and $0$ instead of $T$. Also the state-$k$-notation is more intuitive, we successfully quit in $\boxed k$ iff there come consecutively the "word" $1^k$.) Initially i wanted to "generalize" the situation, e.g. so that a $T$ adds e.g. $2$ (or $r$) to the "Hs needed to win". The essence is kept. Instead of $\tau(q)$ in $1/2$ it's in $1/3$. $\endgroup$
    – dan_fulea
    Commented May 14, 2023 at 18:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.