Problems / probability-statistics

probability-statistics / Markov decision processes

Optimal Strategies in the All-Heads Coin Game

In the all-heads coin game a player starts with $n$ coins, each showing heads with probability $p$; each round all remaining coins are flipped, the player must set aside at least one head (losing if none shows), and wins once all coins are set aside. Determine optimal strategies and the winning probability $w_{n,p}$. Resolved: for $p=\tfrac12$ every strategy achieves $w_{n,1/2}=\tfrac12$; for $p>\tfrac12$ the single-head strategy One is optimal, $n\mapsto w_{n,p}$ is strictly increasing, and $W(p)=\lim_n w_{n,p}$ has an explicit series representation. In the regime $p<\tfrac12$, explicitly left open by van Doorn, a first-order perturbation in $\delta=\tfrac12-p$ gives a closed-form description: the deficit satisfies $\tfrac12-w_{n,1/2-\delta}\approx\delta c_n$, where $c_n$ obeys a linear recursion for $n\ge7$ with limit $L\approx1.7035$, and to first order the optimal-value sequence has a strict local minimum at $n=5$ and no local maximum.