A coin game and a crazy recurrence

Question

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.

Answer 1

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}$$