Group Russian Roulette

Question

This problem is from "Mathematical Puzzles: A Connoisseur's Collection" (P. Winkler, AK Peters, 2005) as the opening puzzle in the chapter "Probability".

There are N armed people. At each chime of a clock everyone spins around and shoots a random other person. That person falls dead. AT THE NEXT CHIME, The survivors shoot again. Eventually either everyone is dead, or there is a single survivor. Given N, what is the chance that this game ends with a single survivor?

Winkler's problem asks " What is the probability of there being a survivor as N increases to infinity. The answer says "Amazingly, this probability does not tend to a limit as N grows. ... ".

The seeming simplicity of this problem made me think it would be easy to find an expression for the probability of a survivor as a function of N. I got nowhere, so i put it out here to see if anyone could provide some insight. I thought it should be pretty straightforward, but it already gets bogged down to compute the probability of there being a survivor even when N is as low as 4 or 5.

So, here's my question- What is the probability, that with N shooters, one will be left standing??

Answer 1

The probabilities are calculated to a high degree of accuracy in "The Asymptotics of Group Russian Roulette," by Tim Van De Brug, Wouter Kager, and Ronald Meester. If you download the paper, you also get the Mathematica notebook that produced the calculations, and the results. Also, there's a PDF file which I take to be a transcription of the notebook, so you can follow it even if you don't have Mathematica.

The paper shows that the probabilities are, in the limit, periodic with period one, on the log scale, that is, they depend only on the fractional part of the natural logarithm of $n$. The authors calculate the probabilities up to $n=6,000$ to a high degree of accuracy. These are needed for the analysis of the asymptotic behavior, but here I'll only discuss the calculation of the probabilities.

Let $P(n,k)$ be the probability that there are exactly $k$ survivors after one round of shooting, starting with $n$ shooters. Then by the principle of inclusion and exclusion, $$P(n,k)=\binom{n}{k}(n-1)^{-n} \Sigma_{0 \le r \le n-k-2}(-1)^r\binom{n-k}{r}(n-k-r)^{k+r}(n-k-r-1)^{n-k-r}$$

(I'm not much good at MathJax, and I hope someone will format this equation better.) Anyway, to explain it, we get the same probability for any $k$ survivors we choose, and each probability is a fraction with denominator $n-1$, which explains the two factors outside the sum. Now if there are $k$ survivors, there are $n-k$ "targets," or persons who may be shot at. So at first glance we have $(n-k)^k(n-k-1)^{n-k}$ possibilities, since the survivors can shoot at any of the targets, and and each target can shoot at any target but himself. This gives the $r=0$ term in the sum.

But just because a person is a potential target, he doesn't necessarily get shot. If no one shoots at a particular target, we would have $k+1$ survivors, not $k$, and we must subtract those possibilities. That accounts for the $r=1$ term. However, suppose two targets aren't shot at. Then we have subtracted that event twice, once for each of them, and we only want to subtract it once, so we must add it back in. This gives the $r=2$ term, and so on. It isn't possible to have $n-1$ survivors (if everyone shoots the same person, who does he shoot?) which accounts for the upper limit on $r$.

By the Bonferroni inequalities, the partial sums in the inclusion-exclusion formula alternately overstate and understate the answer, and the error has the same sign as the first omitted term, and does not exceed it in magnitude. Since the authors are looking for a lower bound on $S(n,k)$, they quit computing after an even number of terms, once the next term is small enough. (Of course, "small enough" must take into account the factors outside the sum.)

Now let $p_n$ be the probability that we end with one survivor, if we start with $n$ persons. Then $$p_n=\Sigma_{0 \le k \le n-2}P(n,k)p_k$$ and $p_0=0, p_1=1, p_2 = 0$. Of course, we would get an exactly analogous formula if $p'_n$ were defined as the probability of ending with no survivors, but the initial values would be different. In that case, we would have $p'_0=1, p'_1=0, p'_2 = 1$. The authors compute lower bounds for both cases. Then complementing the lower bound on $p'_n$ gives an upper bound on $p_n$.

It seems odd to compute two lower bounds, since the Bonferroni inequalities seem to give upper bounds with little additional work, but here we get to the most interesting part of the calculation. Let $$k1 = max(0, \frac{n}{e} - \sqrt{5n}),$$ $$k2 = min(n-2, \frac{n}{e} + \sqrt{5n})$$ Then the authors show that $$\Sigma_{k_1 \le k \le k_2}P(n,k)p_k$$ is a very good approximation to $p_n$ and it is certainly a lower bound, provided that the computed $P(n,k)$ values are lower bounds on the true values.

Of course, the proof of the pudding is in the results. Comparing the upper and lower bounds computed up to $n=6,000$ shows that they agree to seven decimal places in all cases.

A Hint at the Theory

To arrive at the tail bound above, the authors first use a coupling to show that the distribution of the number of survivors after one round of shooting is closely approximated by the number of boxes remaining empty after $n-1$ balls are randomly thrown into $n-1$ boxes. The latter random variable is much simpler to analyze. (It's like group Russian roulette, but each shooter may shoot at himself.) By an ingenious argument, they show that it can be written as the sum of $n-2$ independent (but not identically distributed) Bernoulli random variables. Then they use a sort of generalization of the Chernoff bound to get a tail bound.

This isn't the place to expand on this outline, and it would severely test my MathJax skills to try, but if the sketch above makes sense to you, I think you'd enjoy the paper.

Practical Details of Computation

In order to get accurate answers all the authors' computations are done in integer arithmetic in Mathematica. The terms in the sum for $P(n,k)$, which are all integers, are computed with full precision. The probabilities are all multiplied by $10^{10}$ and truncated to the next lower integer.

I don't have access to Mathematica, so I tried to verify the computations in python. I was able to do so up to $n=2,000$ but even after all the optimizations I could find, it's clear that $n=6,000$ is beyond my reach.

It is not possible, so far as I can see, to duplicate the calculations in C without using an extended precision library like GMP, because the numbers involved in the calculations are so huge. Even if you could somehow avoid the problems of exponent overflow and underflow, and I don't see how you can, you have the problem of subtracting the huge terms in the sum to produce a number between 0 and 1, so that you are essentially ending up with a rounding error. My experiments in C++ failed badly; I started getting garbage long before I reached $n=100.$

Answer 2

$\textbf{Caution: Long calculation ahead.}$

We assume that each player shoots only once at each chime. We also assume that a player does not shoot himself and that there are no misses, i.e. each player shoots at least one other player at each chime. This in particular implies that if only two players are playing the game then both of them are certain to die. We also assume that there are at least 2 players at the beginning of the game.

At the beginning of the game let the players be labeled by numbers from $1$ to $N$. Consider the propositions: \begin{align} A_{ij}&\equiv\textrm{Person $i$ is shot by person $j$}\\ B_i & \equiv\textrm{Person $i$ survives} \end{align} Assuming there is no preference to shoot one rather than another, the probability that person $i$ shoots person $j$, given that there are $N$ people is: $P(A_{ij}|N)=1/(N-1)$. Probability that person $i$ survives is equal to the probability that he is not shot at by other people: \begin{align} P(B_i|N)=P(\prod_{j=1 \\ j\neq i}^N\overline{A}_{ij}|N) \end{align} where $\overline{()}$ indicates logical negation and product of propositions indicates logical AND between them. Assuming that they shoot independently of each other, we have \begin{align} P(B_i|N)=\prod_{j=1 \\ j\neq i}^NP(\overline{A}_{ij}|N)=\left(1-\frac{1}{N-1}\right)^{(N-1)},\quad N\geq 2 \end{align} For $N=2$ above probability becomes zero, as it should. We also have an interesting result in that as the initial number of players grows indefinitely, i.e. $N\to\infty$, the probability that any particular player survives the first round is $1/e$, which is less than even chance.

Next consider the proposition: \begin{align} E_m\equiv\textrm{$m$ number of people survive the shootout} \end{align} Obviously, given that there are $N$ players, $P(E_m|N)=0$ for $m\geq N$ (recall we have assumed that at least one person dies at each round). So let us consider the case $m<N$. For $m\geq 1$, there are $C_m^N$ ways of selecting $m$ players out of $N$. Therefore, as per our assumption that people shoot independently of each other, we have a Binomial distribution: \begin{align} P(E_m|N) & =C_m^N\left( P(B_i|N) \right)^m\left(1-P(B_i|N) \right)^{N-m},\quad 0\leq m<N,~N\geq 2 \end{align}

Now finally for the sought for proposition: \begin{align} G & \equiv\textrm{1 player survives.}\\ Q_{m,k} & \equiv\textrm{$m$ players survive at the end of round number $k$ (equal to number of chimes).} \end{align} $k=0$ corresponds to the initial state before the game begins; therefore $N$ players at the beginning of the game corresponds to the proposition $Q_{N,0}$. Probability that $m'$ players survive round $k+1$ given that $m$ players survived round $k$ is simply \begin{align} P(Q_{m',k+1}|Q_{m,k})=P(E_{m'}|m),\quad 0\leq m'<m \end{align} and zero otherwise. Above equation also says that the probability of survival depends only on the present number of players and not on any prior history. Such a process is called a Markov process. Further if only one player survives round $k$ then since the game does not proceed to round $k+1$ we have formally \begin{align} P(Q_{m,k+1}|Q_{1,k})=0,\quad m\geq 1 \end{align}

If we begin with $N$ players, since at least one player must die at each round, there cannot be greater than $N-1$ rounds until the game ends. Also if at the end of any round there are only two players left, then both of them are certain to die in the next round, i.e. $P(Q_{m'=0,k+1}|Q_{m=2,k})=1$.

Now after any particular round $k$, $\{Q_{0,k},Q_{1,k},Q_{2,k},...\}$ forms a set of mutually exclusive and exhaustive set of propositions. Now 1 person may be left standing at the end of round $k\in\{1,2,...,N-1\}$. This also forms a mutually exclusive and exhaustive set of propositions. Therefore \begin{align} P(G|Q_{N,0})=\sum_{k=1}^{N-1}P(Q_{1,k}|Q_{N,0}) \end{align}

Employing Bayes' theorem we have our final answer \begin{align} P(G|Q_{N,0})& =\sum_{k=1}^{N-1}P(Q_{1,k}|Q_{N,0})\\ & = P(Q_{1,1}|Q_{N,0})+P(Q_{1,2}|Q_{N,0})+P(Q_{1,3}|Q_{N,0})+...+P(Q_{1,N-1}|Q_{N,0}) \end{align} in which each term is evaluated as \begin{align} P(Q_{1,1}|Q_{N,0}) & = P(E_1|N)\\ \\ P(Q_{1,2}|Q_{N,0}) & =\sum_{m=3}^{N-1}P(Q_{1,2}|Q_{m,1})P(Q_{m,1}|Q_{N,0}),\quad\textrm{(Markov property)} \\ &=\sum_{m=3}^{N-1}P(E_1|m)P(E_m|N)\\ \\ P(Q_{1,3}|Q_{N,0}) & = \sum_{m_1,m_2=3}^{N-1}P(Q_{1,3}|Q_{m_2,2})P(Q_{m_2,2}|Q_{m_1,1})P(Q_{m_1,1}|Q_{N,0}),\quad\textrm{(Markov property)} \\ & = \sum_{m_1,m_2,m_3=3}^{N-1}P(E_{1}|m_2)P(E_{m_2}|m_1)P(E_{m_1}|N)\\ \vdots \end{align}

P.S. I shall leave it you to do the limit $N\to\infty$ of $P(G|Q_{N,0})$ :-)