Flipping $n$ coins in a circle until they are all gone 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?
 A: 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}
A: 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)$$
