6
$\begingroup$

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?

$\endgroup$
  • 4
    $\begingroup$ Not sure this helps, but it is clear that $P(k,n)=2P(k,1)$: look at the first toss. If it is $H$ then coin 1 is gone, if it is $T$ then the game starts over only now the first coin is last. Hence $$P(k,1)=\frac 12 0+\frac 12 P(k,n)$$ $\endgroup$ – lulu Sep 19 '15 at 1:12
  • 1
    $\begingroup$ Unless I botched it (definitely possible) for $k=3$ I get the probabilities $\{\frac 5{21},\frac 6{21},\frac {10}{21}\}$. The pattern has yet to leap out at me. $\endgroup$ – lulu Sep 19 '15 at 1:17
  • $\begingroup$ When you remove a coin, you start then flipping from the next coin? or from the beginning? $\endgroup$ – nickchalkida Sep 19 '15 at 1:56
  • 1
    $\begingroup$ For $k=4$, I get $\{\frac{19}{105},\frac{22}{105},\frac{26}{105},\frac{38}{105}\}$. The denominator would be $(2^2-1)(2^3-1)(2^4-1)$, but in this case the numerators were multiples of 3 $\endgroup$ – Empy2 Sep 19 '15 at 3:28
  • $\begingroup$ I get the same for $n=3,4$ as lulu and Michael, respectively, and $(471,530,606,706,942)/(31\cdot105)$ for $n=5$. $\endgroup$ – joriki Sep 19 '15 at 4:06
5
$\begingroup$

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}

$\endgroup$
  • $\begingroup$ I find the gaps fascinating. I expected linearity or close...yet the gap from penultimate to final is persistently outsized. $\endgroup$ – lulu Sep 19 '15 at 11:47
  • $\begingroup$ @lulu: I also had this expectation of linearity (as opposed to linearity of expectation :-). But it's not quite as surprising if you consider that the last coin outlives the penultimate coin (in fact each of the other coins) with probability $2/3$. It's the only coin that can "win" by merely surviving the same number of flips as all the others; all others have to survive one flip more than the ones after them to "win". $\endgroup$ – joriki Sep 20 '15 at 18:54
  • $\begingroup$ I ran a simulation for $n=5$ with 10 million experiments and I'm getting probabilities of $0.1446$, $0.1630$, $0.1862$, $0.2168$ and $0.2894$ for $k=1,\dots,5$, which matches your exact numbers. Here's a graph for $n=100$, 1 million experiments: imgur.com/OVBjL6U $\endgroup$ – wj32 Jan 20 '16 at 11:46
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Unfortunately I don't understand many of your sentences, including, unfortunately, the first one, which seems crucial to understanding the rest. What do you mean by "Assume for $n$ coin, the expected label coin is $T_n$."? What's "the expected label coin"? $\endgroup$ – joriki Oct 9 '15 at 17:00
  • $\begingroup$ The question is which coin is the most likely to be last coin remaining. I just assume the exception of last coin's label is $T_n$. Since the last coin remaining could be any of $(1,2,\cdots, n)$, I am not trying to know the distribution of it but the exception of the distribution of the last coin. $\endgroup$ – Jingyu Bao Oct 10 '15 at 2:12
  • $\begingroup$ @joriki Sorry to make you confuse. I supposed to answer the other question instead of this one since I first looked at that one. math.stackexchange.com/questions/1457464/… $\endgroup$ – Jingyu Bao Oct 10 '15 at 2:25
  • $\begingroup$ I don't understand what you mean by "the exception of last coin's label" -- do you mean the expectation? I also don't understand your second comment. Are you saying you were answering a different question? If so, you should delete the answer and post it under the other question. $\endgroup$ – joriki Oct 10 '15 at 2:57
  • $\begingroup$ Yes I mean the expectation. To my understanding, the question is also about expectations. Anyway, an expression of $P(n,n)$ was given to improve the question. $\endgroup$ – Jingyu Bao Oct 10 '15 at 3:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.