TAOCP 5.1.1 Exercise 23

We have \(n\) men numbered \(1,2,\dots,n\) sitting in a circle in increasing order clockwise.

taocpmathematicsalgorithmsvolume-3math-hard

Section 5.1.1: Inversions

Exercise 23. ▶ [M27] (Russian roulette.) A group of $n$ condemned men who prefer probability theory to number theory might choose to commit suicide by sitting in a circle and modifying Josephus's method (exercise 2) as follows. The first prisoner holds a gun and aims it at his head; with probability $p$ he dies and leaves the circle. Then the second man takes the gun and proceeds in the same way. Play continues cyclically, with constant probability $p > 0$, until everyone is dead.

Let $a_j = j$ if man $j$ is the $j$th to die. Prove that the death order $a_1 a_2 \ldots a_n$ occurs with a probability that is a function only of $n$, $p$, and the index of the dual permutation $(n+1-a_n) \ldots (n+1-a_2)(n+1-a_1)$. What death order is least likely?

Verified: yes
Solve time: 57m13s

Setup

We have (n) men numbered (1,2,\dots,n) sitting in a circle in increasing order clockwise. The gun starts with man (1). At each step the current holder either dies (probability (p)) or survives (probability (q=1-p)); in either case the gun passes to the next alive man in clockwise order. The process continues until everyone is dead. The death order is the permutation (a_1a_2\dots a_n) of ({1,\dots,n}) where (a_j) is the (j)-th man to die.

The dual permutation of (a_1a_2\dots a_n) is ((n+1-a_n)(n+1-a_{n-1})\dots(n+1-a_1)). Its index is the sum of all positions (j) ((1\le j<n)) where the (j)-th element exceeds the ((j+1))-st element.

We will prove that the probability of a given death order depends only on (n), (p) and the index of the dual permutation. In fact the exact probability is [ P(a_1a_2\dots a_n)=\frac{q^{\operatorname{ind}(\text{dual})}}{[n]_q!}, \qquad [n]q!=\prod{i=1}^{n}(1+q+\cdots+q^{i-1}). ]

Solution

1. Index of the dual permutation

Let (d_1d_2\dots d_n) be the dual permutation, i.e. (d_i=n+1-a_{n+1-i}). A descent in the dual at position (i) means (d_i>d_{i+1}), i.e. [ n+1-a_{n+1-i} > n+1-a_{n-i};\Longleftrightarrow; a_{n+1-i} < a_{n-i}. ] Setting (k=n-i) this is exactly (a_{k+1}<a_k), which is a descent in the original permutation at position (k). The weight contributed by this descent in the index of the dual is (i=n-k). Hence [ \operatorname{ind}(\text{dual})=\sum_{k=1}^{n-1}(n-k),[a_k>a_{k+1}]. \tag{1} ]

2. Recurrence for the probability

The first death occurs when the gun makes some number of full cycles (each cycle survives with probability (q^n)) and then man (k) dies on his turn. Thus [ \Pr(\text{first death}=k)=\frac{p,q^{k-1}}{1-q^n} =\frac{q^{k-1}}{1+q+\cdots+q^{n-1}}. \tag{2} ] After man (k) dies the gun is passed to the next alive man. The remaining men form the set (S={1,\dots,n}\setminus{k}) in the cyclic order [ C_k=(k+1,k+2,\dots,n,1,2,\dots,k-1) ] (starting at (1) if (k=n)). The subsequent death order (\tau) is a permutation of (S).

Let (\varphi) be the unique order‑preserving bijection from the cyclic order (C_k) to the standard order (1,2,\dots,n-1): [ \varphi(x)= \begin{cases} x-k & \text{if }x>k,\[2pt] x+n-k & \text{if }x<k. \end{cases} ] Then (\tau'=\varphi(\tau)) is a permutation of ({1,\dots,n-1}). The sub‑game on (S) with start at the first element of (C_k) is exactly the original game of size (n-1) on the relabelled men. By induction (see below) its probability is [ \Pr(\tau\mid\text{first}=k)=\frac{q^{\operatorname{ind}{n-1}(\text{dual}(\tau'))}}{[n-1]q!} ] where (\operatorname{ind}{m}) denotes the index of the dual for permutations of ({1,\dots,m}). Using formula (1) for size (m=n-1) we have [ \operatorname{ind}{n-1}(\text{dual}(\tau')) =\sum_{i=1}^{n-2}\bigl((n-1)-i\bigr),[\tau'i>\tau'{i+1}]. \tag{3} ]

3. Induction

We prove by induction on (n) that [ P(a_1\dots a_n)=\frac{q^{\operatorname{ind}(\text{dual})}}{[n]_q!}. ] For (n=1) the only permutation is (1); its dual is (1) with index (0) and ([1]_q!=1), so the formula holds.

Assume the formula holds for all sizes (<n). For a permutation (a) of ({1,\dots,n}) write (a_1=k) and (\tau=(a_2,\dots,a_n)). Using (2) and the induction hypothesis, [ P(a)=\frac{q^{k-1}}{1+q+\cdots+q^{n-1}}; \frac{q^{\sum_{i=1}^{n-2}((n-1)-i)[\tau'i>\tau'{i+1}]}}{[n-1]q!} =\frac{q^{,k-1+\sum{i=1}^{n-2}((n-1)-i)[\tau'i>\tau'{i+1}]}}{[n]q!}. ] We must show that the exponent equals (\operatorname{ind}(\text{dual}(a))). By (1) this is [ (n-1)[\tau_1<k]+\sum{i=1}^{n-2}\bigl((n-1)-i\bigr)[\tau_i>\tau_{i+1}]. \tag{4} ] Thus we need the identity [ k-1+\sum_{i=1}^{n-2}\bigl((n-1)-i\bigr)[\tau'i>\tau'{i+1}] =(n-1)[\tau_1<k]+\sum_{i=1}^{n-2}\bigl((n-1)-i\bigr)[\tau_i>\tau_{i+1}]. \tag{5} ]

4. Proof of the identity (5)

For (i=1,\dots,n-2) let [ D_i=[\tau_i>\tau_{i+1}]-[\tau'i>\tau'{i+1}]. ] We analyse (D_i) by comparing the standard integer order on (S) with the order induced by (\varphi).
Let (H={k+1,\dots,n}) (elements (>k)) and (L={1,\dots,k-1}) (elements (<k)). For (a,b\in S):

  • If (a,b\in H) or (a,b\in L) then (\varphi) preserves order, so (D_i=0).
  • If (a\in H,;b\in L) then (a>b) is true, but (\varphi(a)\le n-k < n-k+1\le\varphi(b)), so (\varphi(a)>\varphi(b)) is false; hence (D_i=1).
  • If (a\in L,;b\in H) then (a>b) is false while (\varphi(a)>\varphi(b)) is true; hence (D_i=-1).

Thus (D_i = X_i - X_{i+1}) where (X_i=1) if (\tau_i\in H) and (X_i=0) if (\tau_i\in L).
Now compute the weighted sum: [ \sum_{i=1}^{n-2}\bigl((n-1)-i\bigr)D_i = \sum_{i=1}^{n-2}\bigl((n-1)-i\bigr)(X_i-X_{i+1}). ] This telescopes: [ \begin{aligned} \sum_{i=1}^{m-1}(m-i)(X_i-X_{i+1}) &= \sum_{i=1}^{m-1}(m-i)X_i - \sum_{j=2}^{m}(m-j+1)X_j \ &= (m-1)X_1 + \sum_{i=2}^{m-1}\bigl((m-i)-(m-i+1)\bigr)X_i - 1\cdot X_m \ &= mX_1 - \sum_{i=1}^{m}X_i, \end{aligned} ] where (m=n-1). Since (X_1=[\tau_1>k]=1-[\tau_1<k]) and (\sum_{i=1}^m X_i = |H| = n-k = m-(k-1)), [ mX_1 - \sum_{i=1}^m X_i = m(1-[\tau_1<k]) - (m-(k-1)) = (k-1) - m[\tau_1<k]. ] Therefore [ \sum_{i=1}^{n-2}\bigl((n-1)-i\bigr)D_i = (k-1) - (n-1)[\tau_1<k]. ] Substituting (D_i) gives exactly identity (5). This completes the induction.

Hence the probability of the death order (a_1\dots a_n) is [ P(a_1\dots a_n)=\frac{q^{\operatorname{ind}(\text{dual})}}{[n]_q!}, ] which is a function of (n), (p) and the index of the dual permutation.

5. Least likely death order

Since (0<q<1), the probability is strictly decreasing in the index of the dual. The maximum possible index of any permutation of (n) elements is (1+2+\cdots+(n-1)=n(n-1)/2), attained exactly by the decreasing permutation (n,n-1,\dots,1). Its dual is also (n,n-1,\dots,1) (the decreasing permutation is self‑dual), and its index is (n(n-1)/2). Therefore the least likely death order is [ \boxed{n,;n-1,;\dots,;1}. ]

Verification

  1. Small cases.
    For (n=2): death orders are (12) (probability (1/(2-p))) and (21) (probability ((1-p)/(2-p))). The duals are (12) (index (0)) and (21) (index (1)). Formula gives (q^0/(1+q)) and (q^1/(1+q)), matching the direct computation.

    For (n=3): the six death orders and their duals have indices (0,1,2,1,2,3). The probabilities are (q^0, q^1, q^2, q^1, q^2, q^3) divided by ((1+q)(1+q+q^2)), which agree with the recurrence in Section 2.

  2. Telescoping identity.
    The key identity (5) was verified by rewriting the difference of the two statistics as a telescoping sum. The steps are algebraically exact and independent of the probabilistic interpretation, providing a solid check on the induction.

  3. Boundary cases.
    (n=1): probability (1), index (0), formula holds.
    (p\to 0) ((q\to 1)): all death orders become equally likely ((1/n!)), and the formula gives (1/[n]_1! = 1/n!).
    (p\to 1) ((q\to 0)): only the identity permutation (1,2,\dots,n) (index (0)) survives, probability (1).

∎