From The Riddler:

You are playing a coin flipping game. If you flip a head, you win. If you flip a tail, you now need to flip two heads in a row to win. In general, you keep track of the number of tails flipped, and you need to flip that many tails in a row plus one to win the game. What is the probability of winning the game?

Let \(p(T, H)\) denote the probability of winning if the current count of tails is \(T\), and the current number of heads in a row is \(H\). That is enough to uniquely specify all states, I think. Then, it should be possible to set up a recurrence relation with certain boundary terms, and at worst a computer could calculate the solution. But based on how The Riddler presents the problem, it seems that a closed for solution should exist.

At the start we have a probability \(p(0,0)\) of winning. We have seen no tails yet, and we have a total of zero heads in a row so far.

A win occurs when you get \(T+1\) heads when you have seen a total of \(T\) tails, which means the probability of winning is \(1\) when that condition is met. Thus we have:

\[ p(T, T+1) = 1 \]

Now, we consider the probability of winning starting from the state of having seen \(T\) tails and having \(H\) heads in a row, which is \(p(T, H)\). This is only defined for \(0 \leq H \leq T+1\). When the next flip comes, it is tails half the time, which will add one to our count of tails (\(T\) becomes \(T + 1\)), and it is heads half the time, which will reset our heads-in-a-row count (\(H\) becomes 0). Thus, we have:

\[ p(T, H) = \frac{1}{2}p(T+1, 0) + \frac{1}{2}p(T, H+1) \]

\[ p(T, T) = \frac{1}{2}p(T+1, 0) + \frac{1}{2}p(T, T+1) = \frac{1}{2}p(T+1, 0) + \frac{1}{2} \]

We can write expressions for lower and lower values of \(H\) and substitute:

\[ p(T, T-1) = \frac{1}{2}p(T+1, 0) + \frac{1}{2}p(T, T) = \frac{1}{2}p(T+1, 0) + \frac{1}{4}p(T+1, 0) + \frac{1}{4} \]

\[ p(T, T-k) = p(T+1,0) \sum_{i = 0}^{k}[(\frac{1}{2})^{i+1}] + (\frac{1}{2})^{k+1} \]

\[ p(T,0) = p(T+1,0) \sum_{j = 0}^{T}[(\frac{1}{2})^{j+1}] + (\frac{1}{2})^{T+1} \]

\[ p(T,0) = p(T+1,0)(1 - (\frac{1}{2})^{T+1}) + (\frac{1}{2})^{T+1} \]

At this point, I define a new notation to simply things a little:

\[ f(T) = p(T,0) \]

\[ a_{T+1} = (1 - (\frac{1}{2})^{T+1}) \]

\[ b_{T+1} = (\frac{1}{2})^{T+1} \]

And then, we can write our equation in our new notation:

\[ f(T) = a_{T+1}f(T+1) + b_{T+1} \]

Now, we want to find \(f(0)\) by substituting \(f(1), f(2)\), etc:

\[ f(0) = a_1f(1) + b_1 \]

\[ f(0) = a_1a_2f(2) + a_1b_2 + b_1 \]

\[ f(0) = a_1a_2a_3f(3) + a_1a_2b_3 + a_1b_2 + b_1 \]

After \(n\) such substitutions, we will have:

\[ f(0) = (\prod_{i=1}^{n}a_i)f(n) + \sum_{k=1}^{n}b_k\prod_{j=1}^{k-1}a_i \]

We see that if we take the limit of \(n\) going to infinity (which is to say we keep substituting until our hand falls off), we notice that \(f(n) = p(n, 0) \to 0\), and so we have:

\[ f(0) = \lim_{n\to\infty}\sum_{k=1}^{n}b_k\prod_{j=1}^{k-1}a_i \]

Here, I found it not immediately obvious how to continue. The sum is bounded above by \(1\), but I wanted to see if I could establish a bound that was less than \(1\). There are a lot of ways to do this. For example, if we write out the terms, we get:

\[ \frac{1}{2} + \frac{1}{4}(\frac{1}{2}) + \frac{1}{8}(\frac{1}{2}\cdot\frac{3}{4}) + \cdots \]

Then, we can notice that for the third term and on, if we drop any of the terms past \(a_1\), then we have something strictly greater (we don’t multiply by as many numbers less than one):

\[ \geq \frac{1}{2} + \frac{1}{4}\cdot\frac{1}{2} + \frac{1}{8}\cdot\frac{1}{2} \cdots \]

\[ = \frac{1}{2} + \frac{1}{8} + \frac{1}{16} + \cdots \]

\[ = \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \frac{1}{16} + \cdots - \frac{1}{4} \]

\[ = 1 - \frac{1}{4} = \frac{3}{4} \]

I had to leave during the middle of this, and I asked Jeff (and JZ) for help. Jeff then made a huge breakthrough (JZ also realized this, independently). I initially wrote \(b_i\) as separate from \(a_i\), but writing one in terms of the other, Jeff realized something incredible:

\[ b_i = (\frac{1}{2})^i = 1 - (1 - 1 - (\frac{1}{2})^i) = 1 - a_i \]

\[f(0) = \lim_{n\to\infty}\sum_{k=1}^{n}(1 - a_k)\prod_{j=1}^{k-1}a_i \]

\[ f(0) = \lim_{n\to\infty}\sum_{k=1}^{n}(\prod_{j=1}^{k-1} a_i - \prod_{j=1}^k a_i) \]

The sum telescopes! So then, we are left with:

\[ f(0) = \lim_{n\to\infty}(1 - \prod_{j=1}^na_i) \]

At first, we thought the product might go to zero, but that can’t be the case. It is bounded below by \(\frac{1}{4}\) due to what we proved earlier about the \(f(0)\), and above by \(\frac{1}{2}\) (or really by however many terms you want to multiply out together).

Jeff proved the identity that the infinite product can be simplified (?):

\[ \prod_{j=1}^{\infty}a_i= \frac{1}{3} - \frac{1}{3}\frac{1}{7} + \frac{1}{3}\frac{1}{7}\frac{1}{15} - \cdots \]

This is done by grouping the product after foiling:

\[ (1-a)(1-b)(1-c)(1-d) \cdots \]

\[ = 1 - (a + b + c + \cdots) + (ab + ac \dots + bc + bd + \cdots) - (abc + abd + \cdots) + \cdots \]

Into a bunch of sums that are either infinite series:

\[ 1 - (a + b + c + \cdots) + (a(b + c + \cdots) + b(c + d + \cdots) - (ab(c + d + \cdots) + bc(d + e + \cdots) - \cdots \]

Then, you just sum all the geometric series until you see the pattern (the \(1\) and the first sum cancel, and after that each level of nesting down essentially contributes a factor of \(\frac{1}{2}\) to \(r\), the ratio in the geometric series. Hard to explain, it is best if you do it out on paper). This also turns out to be hard to evaluate.