This Riddler puzzle involves a particular coin-flipping game. Here is the problem:
I flip a coin. If it’s heads, I’ve won the game. If it’s tails, then I have to flip again, now needing to get two heads in a row to win. If, on my second toss, I get another tails instead of a heads, then I now need three heads in a row to win. If, instead, I get a heads on my second toss (having flipped a tails on the first toss) then I still need to get a second heads to have two heads in a row and win, but if my next toss is a tails (having thus tossed tails-heads-tails), I now need to flip three heads in a row to win, and so on. The more tails you’ve tossed, the more heads in a row you’ll need to win this game.
I may flip a potentially infinite number of times, always needing to flip a series of N heads in a row to win, where N is T + 1 and T is the number of cumulative tails tossed. I win when I flip the required number of heads in a row.
What are my chances of winning this game? (A computer program could calculate the probability to any degree of precision, but is there a more elegant mathematical expression for the probability of winning?)
Here is my solution:
[Show Solution]
The solution is short but sweet. It turns out it’s easier to think about the probability of losing rather than the probability of winning. Let’s define:
\[
P(t) = \text{Probability of losing given we have just flipped the }t^\text{th}\text{ Tail}.
\]If we have just flipped our $t^\text{th}$ Tail, then we’ll win if we flip $t+1$ Heads in a row (probability $\frac{1}{2^{t+1}}$). Otherwise, we’ll flip our $(t+1)^\text{st}$ Tail and we’ll have a chance $P(t+1)$ of losing from that point forward. Mathematically,
\[
P(t) = \left(1-\frac{1}{2^{t+1}}\right) P(t+1)
\]Our goal is to find the initial probability of winning, which is $1-P(0)$. It’s clear that $\lim_{t\to\infty}P(t) = 1$, because it becomes progressively less likely we’ll win as the number of Tails flipped accrues. Iterating the above recursion, we have
$\displaystyle
\text{Probability of winning} = 1-\prod_{t=1}^\infty \left(1-\frac{1}{2^t}\right)
$
This expression occurs often enough that it was given its own name! It’s a special case of the Euler function (just one of many things named after Euler), which is itself a special case of the q-Pochhammer symbol.
There is no way to further simplify the infinite product, unfortunately, but it’s rather easy to approximate it. The probability of winning is approximately $0.711211904913…$, so about $71\%$.
Very elegant! I’m sure I’m not the only one who tried to solve the problem by calculating the probability, P(N), of winning the game after N flips, and then summing P(N) from N=1 to infinity. But I couldn’t come up with an analytic expression of P(N). I wish I had thought of your approach.
I solved it your way, but with N = the number of tails flipped so far. Then
P(N) = 2^(-N-1) Product_{k=0}^{N-1} [1-2^(-k-1)].
The kth factor in the product is the probability of NOT winning after the kth tail and before the (k+1)th, and the prefactor is the probability of winning after the Nth tail and before the (N+1)th. Numerically, Sum_{N=0}^infinity P(N) equals Laurent’s number. I presume this can be shown analytically, but I have not done so.
Right, my mistake was that I set N to be the number of flips instead of the number of tails so far.
This is actually a pretty standard chain for recurrent events. The (row stochastic) transition matrix for this countable state markov chain is:
$P = \begin{bmatrix}
p & (1-p) & 0 & 0 & 0 & 0 & \dots \\
p^2 & 0 & (1-p^2) &0 & 0 & 0 & \dots\\
p^3 & 0 & 0 & (1-p^3) & 0& 0& \dots \\
p^4 & 0 & 0 & 0 & (1-p^4)& 0 & \dots \\
p^5 & 0 & 0 & 0 & 0& (1-p^5)&\dots\\
\vdots & \vdots & \vdots & \vdots & \vdots &\vdots & \ddots
\end{bmatrix}$
It’s fairly immediate that if we start at the top left (State 1), the only way to avoid returning to state 1 (i.e. avoiding a renewal) is to hit each and every item above the diagonal.
There’s a standard analytic fact that $(1-p)(1-p^2)(1-p^3)(1-p^4)…$ converges if and only if $p + p^2 + p^3 + p^4 +…$ converges, which of course it does for any $p\in (0,1)$ — it equals $\frac{p}{1-p}$, hence the chain is transient.
Too bad we can’t get $\sum_{k=1}^\infty \log(1-p^k)$ in closed form.
“It’s clear that $\lim_{t\rightarrow \infty}P(t)=1$, because it becomes progressively less likely we’ll win as the number of Tails flipped accrues.” Could we be more mathematical on this?