6

100 coins in a circle, clockwise labeled 1-100. Starting at coin 1, you flip each one moving clockwise. If a coin lands tails, you keep it, if it lands heads, you remove it. After a long time, only one coin will remain. What would you expect its label is

The problem sounds pretty tricky but my initiation is that since each coin has an equal chance to become a tail or head, this would really become a uniform distribution so with that said the expected value for uniform distribution would be (100 + 1) /2 = 50.5

is this correct ?

szd116
  • 667
  • No, I think that your intuition is not correct, because we start tossing from 1 to 100 (in a specific order) and not at random. I think that if we just picked a coin at random each time then your intuition would be correct. In other words if there are say, two coins remaining it must be (to me at least) more likely that we will remove the first coin than the second. – Jimmy R. Feb 18 '16 at 19:52
  • can I do it this way: reduce 100 coins to 10 coins so we have: start with: 1,2,3,4,5,6,7,8,9,10 1st round: 1,3,5,7,9 these landed tails, assuming that it takes 2 flips to get a tail 2nd round 1,5,9 left 3rd round 1,9 left 4th round 1 left ? – szd116 Feb 18 '16 at 19:55
  • 1
    What is the first coin that have a real chance to survive to all the others? – Masacroso Feb 18 '16 at 20:37
  • @Masacroso - All the coins have a "real chance to survive". 1 has the least chance, but it is still > 0. 100 has the best chance. But that observation is still far from helpful in determining what the expected number of the survivor will be. – Paul Sinclair Feb 18 '16 at 23:18
  • For just two coins, the probability that the survivor is coin $2$ is $2/3$, so the expected value of the survivor is $5/3$, not $3/2$. It will be biased high because you flip the small numbers first. I suspect that with $100$ coins the bias will be small so your $50.5$ is not far wrong. – Ross Millikan Feb 19 '16 at 04:49
  • @Ross $N/2$ is asymptotically off since the distribution of the last survivor is not uniform with $p_N=2p_1$ precisely. The limiting distributions is approximately $p_i\propto \frac 1 {2N-1-i}$ and the expected finishing position is $\approx (2-\frac 1{\log 2})N\approx 0.557N$. – A.S. Feb 19 '16 at 08:19

1 Answers1

1

Break the flippings into rounds around the table. Further, to make things easier mathematically, pretend that we flip every coin, including the eliminated ones, every time around. We just ignore the result. Further, we keep going until all coins have flipped a head. The "winner" is the final coin to flip a head. (We may know it will be the winner much earlier, but we will still stubbornly flip it until it finally shows a head.)

Every coin has an equal chance of surviving a round. The probability of any particular coin surviving $n$ rounds is $(1/2)^n$. the probability of not surviving $n$ rounds is therefore $$1 - (1/2)^n = \frac {2^n - 1}{2^n}$$

In order for coin $i$ to be the winner in round $n$, three conditions must hold:

  • Coin $i$ survives $n-1$ flips.
  • Every coin greater than $i$ does not survive $n-1$ flips.
  • No coin survives $n$ flips.

The probability of $i$ surviving $n-1$ flips but not $n$ is $(1/2)^{n}$. The probability of every coin greater than $i$ not surviving $n-1$ flips is $$\left(\frac {2^{n-1} - 1}{2^{n-1}}\right)^{100 - i} = \left(\frac {2^n - 2}{2^n}\right)^{100 - i}$$ The probability of every coin less than $i$ not surviving $n$ flips is: $$\left(\frac {2^{n} - 1}{2^{n}}\right)^{i-1}$$ So the total probability of $i$ winning in round $n$ is: $$\left(\frac 1{2^n}\right)\left(\frac {2^{n} - 1}{2^{n}}\right)^{i-1}\left(\frac {2^n - 2}{2^n}\right)^{100 - i} = \frac{(2^n-1)^{i-1}(2^n - 2)^{100-i}}{2^{100n}}$$

Which means that the total probability of $i$ winning is $$\sum_{n=1}^\infty \frac{(2^n-1)^{i-1}(2^n - 2)^{100-i}}{2^{100n}}$$ and of course the expected index is $$\sum_{i=1}^{100}\sum_{n=1}^\infty \frac{i(2^n-1)^{i-1}(2^n - 2)^{100-i}}{2^{100n}}$$

Since it is very late, I'll leave it there.

Paul Sinclair
  • 43,643
  • Very neat. From here we get (approximately) $p_i\propto \frac 1 {2N-1-i}$ (satisfies true $p_N=2p_1$) and hence $$EX_N\approx (2-\frac 1{\log 2})N\approx 0.557N$$. – A.S. Feb 19 '16 at 06:54