# A coin game and a crazy recurrence

Consider the following game between two people. You start with a large stack of $$n$$ fair coins and flip all of them. For all coins that come up heads, toss those coins out the window and pass the remaining coins to the other player. Repeat this process until some player flips no heads. If a player fails to flip any heads, that player loses.

Question: Given a (large) value of $$n$$, determine which player is more likely to win this game.

Let $$P_n$$ be the probability of losing this game when you go first and start with $$n$$ coins. Then $$P_0=1$$ (you can’t flip heads if there aren’t any coins) and $$P_n$$ satisfies the following recurrence: $$P_n=1-\frac{1}{2^n}\sum_{k=1}^n \binom{n}{k}P_{n-k}$$ While analyzing this, I found out pretty quickly that $$P_n$$ converges to $$1/2$$, so I let $$P_n=1/2+Q_n$$ and found the following recurrence for $$Q_n$$: $$Q_n=-\frac{1}{2^n}\sum_{k=1}^n \binom{n}{k}Q_{n-k}$$ Some initial values of $$Q_n$$, starting with $$Q_0=1/2$$, are $$\frac{1}{2},\space 0,\space -\frac{1}{4},\space \frac{1}{64},\space \frac{5}{256},\space ....$$ Of course, the sign of $$Q_n$$ determines which player the game favors. Running a Python script, I determined that $$Q_n$$ changes signs after $$n=8,17,35,72,145,291,583$$ (at which point the numbers got too big for my program to handle, since it was dealing with binomial coefficients). I know that these values at which sign changes occur are $$\sim c\cdot 2^k$$ for some constant $$c$$.

What I need help with: Can anyone calculate the value of $$c$$, or come up with a clever way to calculate the sign of $$Q_n$$ for arbitrary large $$n$$?

What I know already: If it helps, I’ve found out that the EGF (exponential generating function) of $$Q_n$$, denoted $$f$$, satisfies the following functional equation: $$f(2x)=(1-e^x)f(x)$$ However, I’m not sure how to use this fact. Also, I know that the expected duration of the game (that is, the number of turns before someone loses) is asymptotically $$\log_2(n)$$ for large $$n$$. However, this fact is almost trivial because we expect half of the coins to come up heads (and be thrown out) after each turn.

• I am not sure what went wrong, but the numbers are wrong. To not lose, you must flip some Head, i.e. you must discard some coin, right? (And because of this rule, the game must terminate in $\le n$ turns.) Then $P_1 = 1/2$ because if you flip Head and discard, your opponent loses. So $Q_1 = 0$, but you are saying $Q_1 = -1/4$...??? Nov 9, 2019 at 1:58
• @antkam My bad, I made a miscalculation/typo somewhere. All of the numbers are now updated. Thanks for noticing. :) Nov 9, 2019 at 2:07
• Is the first recurrence correct? I don't see where it takes into account that you lose if you throw no heads. It seems to me that you should subtract $2^{-n}$ from the right-hand side. Nov 9, 2019 at 2:16
• @saulspatz Actually, that recurrence is an algebraic simplification of this original recurrence: $$P_n=\frac{1}{2^n}+\frac{1}{2^n}\sum_{k=1}^n \binom{n}{k}(1-P_{n-k})$$ which is a bit easier to intuit. Nov 9, 2019 at 2:22
• This doesn't look right to me, either. The first term says I win if I throw $n$ heads. The second term says that I win I throw $k$ heads, and my opponent loses, for $k=1,2,\dots,n$ so that the case where I throw $n$ heads is counted twice. What am I missing? Nov 9, 2019 at 2:29

I'm sorry to tell you that you made a mistake with the $$Q$$ recurrence...

Just to be clear, the game rule is that you discard any Heads, and if you flip no Heads (equivalent: discard no coins) then you lose.

Claim: $$\forall n \ge 1: P_n = 1/2$$

Proof by induction: With $$n$$ coins, you can win immediately if you throw $$n$$ Heads (discarding all coins to force your opponent to lose). You can also lose immediately if you throw $$n$$ Tails. These two results are equally likely.

With any other result, i.e. you throw at least one but not all Heads, the game reduces to some $$P_m$$ faced by your opponent, where $$1 \le m < n$$. By induction hypothesis, this number $$P_m = 1/2$$. Therefore:

$$P_n = 0 \times P(\text{all Heads}) + 1 \times P(\text{all Tails}) + \frac12 \times P(\text{at least one but not all Heads}) = \frac12$$

QED

Lets try to "debug" your recurrences. Your $$P$$ recurrence is:

$$P_n=1-\frac{1}{2^n}\sum_{k=1}^n \binom{n}{k}P_{n-k}$$

This looks fine to me. You lose by not winning, and you win by flipping $$k\ge 1$$ Heads, and then your opponent losing from $$n-k$$ coins. And this recurrence agrees with my claim:

• $$P_0 = 1$$ by definition

• $$P_1 = 1 - \frac12 {1 \choose 1} P_0 = 1 - \frac12 = \frac12$$

• $$P_2 = 1 - \frac14 ( {2 \choose 1} P_1 + {2 \choose 2} P_0 ) = 1 - \frac14 (2 \times \frac12 + 1 \times 1) = \frac12$$

• $$P_3 = 1 - \frac18 ( {3 \choose 1} P_2 + {3 \choose 2} P_1 + {3 \choose 3} P_0 ) = 1 - \frac18 ( 3\times \frac12 + 3 \times \frac12 + 1 \times 1) = \frac12$$

etc. However, when you convert it to the $$Q$$ recurrence, you made a mistake:

$$\begin{array}{rrcl} &\frac12 + Q_n &=& 1-\frac{1}{2^n}\sum_{k=1}^n \binom{n}{k}(\frac12 + Q_{n-k})\\ &Q_n &=& \frac12-\frac{1}{2^n}\sum_{k=1}^n \binom{n}{k}(\frac12)-\frac{1}{2^n}\sum_{k=1}^n \binom{n}{k}Q_{n-k}\\ &&=& \frac12 ( 1 - \frac{1}{2^n}\sum_{k=1}^n \binom{n}{k} ) - \frac{1}{2^n}\sum_{k=1}^n \binom{n}{k}Q_{n-k}\\ \end{array}$$

Sadly for you, $$\sum_{k=\color{red}{1}}^n \binom{n}{k} = 2^n - \color{red}{{n \choose 0}} = 2^n -1$$. So the correct $$Q$$ recurrence is:

$$Q_n = \frac{1}{2^{n+1}} - \frac{1}{2^n}\sum_{k=1}^n \binom{n}{k}Q_{n-k}$$

• Woah, that’s wack... that would imply that $Q_n=0$ for all $n>0$! Nov 9, 2019 at 12:13
• sure, you can prove inductively that the correct $Q$ recurrence, starting with $Q_0 = 1/2$, leads to all other $Q_n = 0$. By induction assumption, most terms in the summation vanish, so you are left with $Q_n = 2^{-(n+1)} - 2^{-n} {n \choose n} Q_0 = 0$. The sad thing is that your original (wrong) $Q$ recurrence is the one with interesting dynamics! Nov 9, 2019 at 13:00
• Well, if you replace the fair coins with biased coins, it gets interesting again. :) Nov 9, 2019 at 13:34
• Of course, but that's a different question (and with different sequence $Q_n$). Off the top of my head, I cannot think of a similar game where $Q_n$ change signs often... good luck inventing it! Nov 9, 2019 at 14:47