Entertaining puzzle

[drmwc]

There are n people in a circle, all with guns. When the clock strikes, they all shoot someone else dead. they choose their victim at random, with equal probability assigned to any potential victim.

After the first round of killings, the clock strikes again. The survivors repeat the exercise. This continues until wither only 1 person is left; or until 0 people are left.

Let P(n) be the probability that 0 people are left.

What is the asymptotic distribution of P(n) as n gets large?

[EdLee]

drmwc, Thanks for the puzzle. Do you also know about Ponder This ?

[Fedya]

1/e

I don't know why, but am guessing that because it's the answer to a lot of questions that involve calculus.

[mitsun]

Does a numerical simulation count as a valid answer?

psim.png (29.44 KiB) Viewed 11829 times

[EdLee]

Hi drmwc, this sounds like a nice puzzle.
Did you invent it ? If so, you may consider to send it to Ponder This .
So that many others can enjoy it.

When the clock strikes, they all shoot someone ELSE dead.

I didn't get very far at all.
Just the first few baby steps.

Let Q(x->y) be the probability to get from (n==x) to (n==y).

If n == 2, both die, ending with n == 0. Q(2->0) = 1.
If n == 3, it's impossible to get down to 2. Q(3->2) = 0. Q(3->1) = 3/4. Q(3->0) = 1/4.

If you have never seen The Good, the Bad, and the Ugly, spoiler alert:

I hate spoilers; I've already said too much.

Drew some pretty graphs for n == 3 case.

Need a bigger piece of paper for the (n == 4) graphs.

Obviously, for each poor fellow in the circle, the probability this person survives this round is:
[ (n-2)/(n-1) ]^(n-1)

Thanks, drmwc.

mitsun, I hope there's an elegant algebraic solution.
But from your graph, it looks like 0.5 doesn't it.

[drmwc]

Ed

Thanks for pointing out ponder this - it looks interesting. I didn't make this puzzle up - I found it in this book:
http://www.amazon.co.uk/Mathematical-Puzzles-A-Connoisseurs-Collection/dp/1568812019

I wholeheartedly recommend the book.

Here is a mild hint:

The problem is highly non-trivial,and the solution is counter-intuitive.

[DrStraw]

Ed's statement (hidden below) for one person's chances of survival can be multiplied by n and produces a value which is remarkably close to 1/e as n increases. Fedya must have remarkable intuition.

Obviously, for each poor fellow in the circle, the probability this person survives this round is:
[ (n-2)/(n-1) ]^(n-1)

[mitsun]

I should have made the plot using the natural logarithm of the starting population The probability oscillates about 50% and looks like it might not ever converge. Each oscillation period appears to be a factor e longer than the previous period -- the spacing is one unit along the log(e) axis in the plot. Weird.

psim.png (28.08 KiB) Viewed 11686 times

[skydyr]

The question is really asking whether you'll end up with an odd or even number of people at the end, since 2 == 0 for the purposes of this question. If the selection process is random, you can do all sorts of calculation to determine exactly how many people will be killed on average given a number of starting people, but you should end up with 50/50 odds that one person will survive in a very large group, because while having an odd or even number of people to start may bias it in one direction or the other, you are taking both into account, and the more people there are, the more likely fluky selection of targets will randomize the odd/even count of the group.

[mitsun]

As Ed and DrStraw noted, the probability of any one person's survival into the next round is [(n-2)/(n-1)]^(n-1). For large n, this is also the fraction of people who survive into the next round, which we might call the culling factor. This can be simplified to approximately Fcull ~= [(n-1)/n]^(n-1) for large n. Taking the logarithm, ln(Fcull) ~= (n-1) ln[1-1/n] ~= (n-1)(-1/n) ~= -1, so Fcull ~= 1/e. This explains at least the periodicity of the results.

[perceval]

This does not really answer the OP question: the crazy duellist repeat the process until 1 or 0 are left!


each time, they have a proba of (1/e)^n of all dying, very small

but the proba of 1 survivor is n* (1/e)^(n-1) (1-1/e)

so P(1 left after this round)/P(0 left after this round ) is of order n * (e-1) (possible because both proba are very very small)

We will retry until there is either 1 or 0 left, so

so if n is very large, P (1 survivor) is about 1! all result other than 0 or 1 is meaningless even if they are by far the most probable each time!

The exact law is trickier to extract , though, because it might take a lot of rounds to reduce from N duellist to either 0 or 1.
if we start with N duellists, proba of 0 or 1 left after 1 round is given above,
but the actual number of rounds before it happens, and the number of remaining duellists at that time is hard to compute from N

i ll go with P(n = proba that 0 are left in the end after starting with n duelists) in O(1/n) anyway

[perceval]

attempt at more rigorous computation.

lets assume that we throw a weighted coin wich falls on tail with proba p, on head with proba q=p*r, and on the edge with proba
1-p-q
We will throw the coin until it falls on either head or tail.

what is the proba that it ends up on head ?

lets compute the proba that it end on head after N throws:
P(Head,N)= (1-p-q)^N-1q
if we sum over all N:

P(Head/End of game )=q* sum over N((1-p-q)^N-1)

now, we could compute the geometric sum but there is no need:

by symmetry,
P(Tail/End of game )=p* sum over N((1-p-q))^N-1)
so P(Head/End of game )/ P(Tail/End of game ) =q/p = r

in the end; the result is either Head or tail:
so P(Head/End of game )+ P(Tail/End of game ) = 1
We have

P(Head/End of game ) *(1+r)=1
=> P (Head at end of game) =1/(1+r)

back to first problem, p and q changes with the number duelist left, but IF we assume that the game will finish before N as been reduced enough that the law changes a bit,
(its reasonable, but not proved)

we have P(n)=P (0 is left at the end when starting with n duelists) = 1/ (1+n*(e-1))

so of order P(n)=1/n(e-1)

(unless there is some horrible error, its late)

EDIT: F- for me for not noticing that by beautiful theory contradicts the experiments (mitsun's graph)

[perceval]

The question is really asking whether you'll end up with an odd or even number of people at the end, since 2 == 0 for the purposes of this question. If the selection process is random, you can do all sorts of calculation to determine exactly how many people will be killed on average given a number of starting people, but you should end up with 50/50 odds that one person will survive in a very large group, because while having an odd or even number of people to start may bias it in one direction or the other, you are taking both into account, and the more people there are, the more likely fluky selection of targets will randomize the odd/even count of the group.

mm i missed the fact that if we are left with 2 then 0 will be left at the end, which changes my result above ...

in fact I know believe that my assumption above "lets assume that N does not goes down too fast before end of game" is wrong:

whatever the big N you start with, you will very probably ends up with a small number of duellist at the end, a number where the law above applies badly
The exact number you end up with at the last round probably introduce the weird oscillation on mitsun graph, or something.

i am not 100% convinced by skydir argument above, but 1/2 seems to fit mitsuns graph (butthere is still the issue of the weird oscillation)
probabilities are hard

[mitsun]

Perceval, you seem to be trying to solve a different game, in which the entire population is reduced to zero or one in a single round (with lots of repetitions from the full starting population until that very unlikely outcome actually occurs). In this scenario, the odds favor one survivor over zero survivors by a factor of N. This is quite different from the actual game.

The question of how many rounds it takes to resolve the actual game is easy to answer. Since the population is reduced by a factor of e each round, it ln(N) rounds to end the game. This approximation is derived for large N, but actually comes pretty close even for N=3.

[zorq]

What is the asymptotic distribution of P(n) as n gets large?

See arXiv:1507.03805