Flipping $n$ coins in a circle until they are all gone

Question

You have $n$ coins arranged in a circle, labeled $1$ to $n$. You start at the first coin and go around. At each coin you flip it - if it lands heads you keep it, if it lands tails you remove it. Which coin is most likely to be the last coin remaining?

---

The answer is the coin labeled $n$ is the most likely. Indeed, the last coin is twice as likely than the first and the probabilities are strictly increasing from $1$ to $n$.

This is an interview question I had and I came up with a couple intuitive ways to explain it. The clearest one is that when you reach coin $k$ for the $m$th time, $k-1$ coins have had $m$ chances to disappear and $n-k+1$ coins have had $m-1$ chances to disappear (including coin $k$). When $k$ is the last coin, then every other coin has had one more chance to be removed than that coin and when $k$ is the first coin, then every other coin has had the same amount of chances to be removed than it (which is why the last coin is twice as likely).

---

What other ways, intuitive or rigorous, can you use to explain this phenomenon?

Also, can you find exact evaluations for $P(k, n)$, i.e. the probability that the $k$th coin in a circle of $n$ coins is the last remaining coin?

Answer 1

If the first coin is removed, the $k$-th coin will be removed with probability $P (k-1,n-1)$. If it isn't, the $k$-th coin will be removed with probability $P(k-1,n)$. Thus we have the recurrence relation

$$ P(k,n)=\frac12(P(k-1,n-1)+P(k-1,n))\;. $$

This expresses every entry in the triangle of probabilities as the average of two of its neighbours. There are no given initial values, but here are two ways to calculate $P(1,n)$.

To calculate $P(1,n)$ from $P(k,n-1)$, we can use the fact (proved by lulu in a comment) that $P(1,n)=\frac12P(n,n)$, together with the contributions from $P(1,n)$ and the $P(k,n-1)$ to $P(n,n)$:

$$ 2^{-(n-1)}P(1,n)+\sum_{k=1}^{n-1}2^{-(n-k)}P(k,n-1)=P(n,n)=2P(1,n)\;,\\ P(1,n)=\frac1{1-2^{-n}}\sum_{k=1}^{n-1}2^{-(n-k+1)}P(k,n-1)\;. $$

Or, to calculate $P(1,n)$ from $P(1,m)$ for $m\lt n$, note that the $(k+1)$-th coin becomes the first coin after $k$ Bernoulli experiments with $p=\frac12$ have been performed to remove coins, so

$$ P(k+1,n)=2^{-k}\sum_{j=0}^k\binom kjP(1,n-j)\;. $$

The sum over $k$ is $1$, so

$$ \sum_{k=0}^{n-1}2^{-k}\sum_{j=0}^k\binom kjP(1,n-j)=1\;, $$

and reversing the order of summation yields

$$ \sum_{j=0}^{n-1}P(1,n-j)\sum_{k=j}^{n-1}2^{-k}\binom kj=1\;. $$

Then performing the sum for $j=0$ and solving for $P(1,n)$ yields

$$ P(1,n)=\frac{2^{n-1}}{2^n-1}\left(1-\sum_{j=1}^{n-1}P(1,n-j)\sum_{k=j}^{n-1}2^{-k}\binom kj\right)\;. $$

Unfortunately I don't see a way to obtain a closed form for $P(k,n)$ from any of these relations.

Here are the values of $P(k,n)$ up to $n=5$:

\begin{array}{l|cc} n\setminus k&1&2&3&4&5\\\hline 1&1\\ 2&\frac13&\frac23\\ 3&\frac5{21}&\frac6{21}&\frac{10}{21}\\ 4& \frac{19}{105}& \frac{22}{105}& \frac{26}{105}& \frac{38}{105}\\ 5& \frac{471}{3255}& \frac{530}{3255}& \frac{606}{3255}& \frac{706}{3255}& \frac{942}{3255} \end{array}

Answer 2

Assume for $n$ coin, the expected label coin is $T_n$.

For the first coin, if it is $H$, the circle become $(2, 3, \cdots, n, 1)$. If it is $T$, then the circle become $(2, 3, \cdots, n)$. For both cases, the probability is $1/2$.

Therefore, think about using $(2, 3, \cdots, n, n + 1)$ instead of $(2, 3, \cdots, n, 1)$,

$$T_n = \frac{1}{2}\big( T_{n} + 1 - nP(n, n)\big) + \frac{1}{2}\big(T_{n-1} + 1) $$

where $P(n, n)$ is the probability that the $k$th coin in a circle of $n$ coins. The formula holds because the circle label $+1$ (except label $1$) after the flip.

Then we can have

$$T_n = 2n - \sum_{j = 1}^n jP(j, j)$$

We only need to know $P(j, j)$.

Since for $P(j,j)$, $j$ is the last labelled coin, we can consider the number of flips it does to stay.

If it flips $0$ time, then other coins must all $T$, the probability is $(1 - \frac{1}{2})^{j-1}$. If it flips $k-1$ times and it must be all $H$ for the last coin, then other coins must flip at least one $T$ in $k$ times and the probability is $(1 - \frac{1}{2^k})^{j-1}$. Thus, we have

$$P(j, j) = \sum_{k=1}^{\infty} \frac{1}{2^{k}}(1 - \frac{1}{2^k})^{j-1}$$

So for $T_n$,

$$T_n = 2n - \sum_{j=1}^n \sum_{k=1}^{\infty} \frac{j}{2^{k}}(1 - \frac{1}{2^k})^{j-1}$$

Let $S_{n,k} = \sum_{j=1}^n j (1 - \frac{1}{2^k})^{j-1}$, then $$(1-x_k)S_{n, k} = \frac{1-x_k^n}{1-x_k} - nx_k^n,$$ where $x_k = 1-\frac{1}{2^k}$, then $$T_n = 2n - \sum_{k=1}^{\infty} (1-x_k)S_{n,k} = 2n - \sum_{k=1}^{\infty} \Big( \frac{1-x_k^n}{1-x_k} - nx_k^n \Big)$$