Probability of unique winner in a coin flipping game (limit of a recursive sequence)

Question

Suppose we have a coin flipping game involving $n$ players. In each round everyone still playing flips a fair coin, and the players whose coin comes up tails are eliminated. The game continues until at most one player is still alive, and they are declared the winner.

Now, it is possible that the game does not end with a winner (e.g. if $n=2$ and both players get tails on their first flip). Let $f(n)$ denote the probability that a game with $n$ players has a winner. We have $f(0)=0$ and $f(1)=1$. For $n>1$ it follows from considering the binomial distribution that $$f(n) = \sum_{k=0}^{n}\frac{\binom{n}{k}}{2^{n}} f(k) $$ (Here $\binom{n}{k}/(2^n)$ represents the probability $k$ players survive the current round), which can be rearranged as $$f(n) = \sum_{k=0}^{n-1} \frac{\binom{n}{k}}{2^n-1} f(k)$$ Using this formula we can compute $f(n)$ recursively.
$$\begin{array}{cc} n & f(n) \\ 0 & 0 \\ 1 & 1 \\ 2 & 2/3 \\ 3 & 5/7 \\ 4 & 76/105 \\ 5 & 157/217 \\ \vdots & \vdots \\ 20 & 0.7213 \end{array}$$ The sequence of numerators doesn't seem to be in OEIS, nor does the sequence $a_n=f(n)(2^n-1)(2^{n-1}-1)\dots(3)(1)$ from clearing all the denominators in the recursion.

Is there a way of analytically determine the limit (if it exists) of $f(n)$ as $n$ goes to infinity? It seems from calculation to be about $0.7213$, though I'm not confident in digits beyond that due to error propagation as the recursion continues.

Answer 1

The limit of $f(n)$ as $n$ goes to infinity does not exist.

Suppose that $n$ is large. Then we can choose an integer $k$ such that $n = 2^k x$ with $1 \leq x < 2$. What is the probability of winning starting at $n$?

Let us say that we win at step $k+m$ if at step $k+m$ there is only one player, but their next coin flip is tails. That is half the probability that at step $k+m$ there is only one player left. But if $k$ is large, the odds of there being one player left is approximated by the Poisson Distribution with $\lambda = 2^m x$. Therefore the probability of winning is approximately $\sum_{m = -\infty}^{\infty} 0.5 * (2^m x) * e^{- 2^m x}$.

It isn't too hard to see that this sum converges, and it is easy to calculate it with a short program. If we calculate this for $x = 1.0$ we get $0.721352103337$. For $x = 1.5$ we get $0.721346354574$. The difference is around $0.00000574876$ and is far larger than calculation error. And therefore the probability keeps bouncing around in a range that includes these values and so can't converge.