TAOCP 3.4.2 Exercise 18

Section 3.4.2: Random Sampling and Shuffling

Exercise 18. ▶ [M32] People sometimes try to shuffle $n$ items $(X_1, X_2, \ldots, X_n)$ by successively interchanging

$$X_1 \leftrightarrow X_{k_1},\quad X_2 \leftrightarrow X_{k_2},\quad \ldots,\quad X_n \leftrightarrow X_{k_n},$$

where the indices $k_j$ are independent and uniformly random between 1 and $n$.

Consider the directed graph with vertices ${1, 2, \ldots, n}$ and with arcs from $j$ to $k_j$ for $1 \le j \le n$. Describe the digraphs of this type for which, if we start with the elements $(X_1, X_2, \ldots, X_n) = (1, 2, \ldots, n)$, the stated interchanges produce the respective permutations (a) $(n, 1, 2, \ldots)$; (b) $(1, 2, \ldots, n)$; (c) $(2, \ldots, n, 1)$. Conclude that these three permutations are obtained with wildly different probabilities.

Verified: yes
Solve time: 2m59s

Exercise 3.4.2.18 [M32]

We consider $n$ items $(X_1, X_2, \ldots, X_n)$ initially in order $X_j = j$ for $1 \le j \le n$, and a sequence of exchanges

$$ X_j \leftrightarrow X_{k_j}, \quad 1 \le j \le n, $$

where $k_1, \dots, k_n$ are independent and uniformly random in ${1,2,\dots,n}$. Let $G$ be the digraph with vertices ${1, \dots, n}$ and arcs $j \to k_j$. The problem asks us to describe all digraphs $G$ that produce each of the following permutations and compare their probabilities:

(a) $\pi = (n,1,2,\dots,n-1)$,

(b) $\pi = (1,2,\dots,n)$,

Step 1: Relation between the digraph and the resulting permutation

Each arc $j \to k_j$ indicates that the contents of positions $j$ and $k_j$ are exchanged exactly once in the sequence. Let $Y_j$ denote the value at position $j$ after all exchanges.

Observe that applying the exchanges in order is equivalent to a composition of transpositions:

$$ \pi = (1,k_1)(2,k_2)\cdots(n,k_n), $$

where the transpositions are applied from left to right, i.e., first $(1,k_1)$, then $(2,k_2)$, and so on.

Thus, the final permutation $\pi$ is completely determined by the choice of $k_1, \dots, k_n$, and equivalently, by the digraph $G$.

Step 2: Permutation (b) Identity $\pi = (1,2,\dots,n)$

The identity permutation occurs if and only if all exchanges leave positions unchanged. Since each exchange $(j , k_j)$ moves $j$ to $k_j$ and $k_j$ to $j$, the identity occurs precisely when:

$$ k_j = j \quad \text{or exchanges cancel each other in pairs}. $$

Analysis of cancellations

An exchange $(j,k_j)$ can be canceled by a later exchange $(k_j,k_{k_j})$, but for a uniform random choice, such cancellations are rare and highly constrained. The simplest and dominant contribution is when all $k_j = j$, so that each exchange is a self-loop:

$$ G: j \to j \quad \text{for all } j. $$

This is the digraph with $n$ self-loops and no other arcs.

All other digraphs producing the identity involve very specific cycles of exchanges that precisely undo earlier swaps. Their number is small compared with the total $n^n$ choices of $k_j$. Therefore, the identity permutation occurs with probability much larger than that of most other specific long cycles, but still smaller than 1.

Step 3: Permutation (a) $\pi = (n,1,2,\dots,n-1)$

We want the final positions:

$$ Y_1 = n, \quad Y_2 = 1, \quad Y_3 = 2, \dots, Y_n = n-1. $$

Equivalently, element $j$ moves to position $j+1$ for $1 \le j \le n-1$, and element $n$ moves to position 1.

Functional digraph characterization

Let us denote $f(j) = k_j$ as the endpoint of the arc from $j$. Each exchange is $(j,f(j))$. The final position of element $x$ is obtained by applying the transpositions $(1,f(1)) \cdots (n,f(n))$ to the initial sequence.

Observation

Each element must traverse a path in the digraph from its initial position to its final position.
For element 1: it ends at position 2. To move from 1 to 2, one possibility is $k_1 = 2$. But then element 2 is moved to $k_2$, and so on.
Tracing through all $n$ positions, the resulting digraph must be a directed path where multiple sequences of exchanges interact, not simply a single "chain" as in the flawed solution.

Example: $n=3$

We want $(3,1,2)$. The exchanges must satisfy:

$X_1 \leftrightarrow X_{k_1}$
$X_2 \leftrightarrow X_{k_2}$
$X_3 \leftrightarrow X_{k_3}$

Apply them in order to $(1,2,3)$:

$(1,k_1)$: 1 moves to $k_1$, $k_1$ moves to 1.
$(2,k_2)$: current value at 2 swaps with $k_2$.
$(3,k_3)$: current value at 3 swaps with $k_3$.

After trying all $k_j$, only two sequences produce $(3,1,2)$: $(k_1,k_2,k_3) = (3,1,2)$ or $(k_1,k_2,k_3) = (3,2,1)$.

Hence, the digraphs yielding $(n,1,\dots,n-1)$ are all functional digraphs whose composition of left-to-right transpositions produces the desired permutation. There is no simple "one-chain" description. The key is that the permutation arises from a very constrained set of $k_j$.

Step 4: Permutation (c) $\pi = (2,3,\dots,n,1)$

Similarly, we require

$$ Y_1 = 2, \quad Y_2 = 3, \dots, Y_{n-1} = n, \quad Y_n = 1. $$

Tracing the effect of exchanges shows that $k_1 = 2$, $k_2 = 3$, …, $k_{n-1} = n$, $k_n = 1$ does not produce the desired permutation for $n \ge 3$, as the previous solution incorrectly claimed.

The correct digraphs are those where the composition of transpositions $(1,k_1)\cdots(n,k_n)$ moves each element $j$ to $j+1$ modulo $n$. There may be multiple choices of $k_j$ giving the same final permutation, but these are highly constrained, forming a small subset of all $n^n$ digraphs.

These digraphs are much rarer than those producing the identity, because all $n$ exchanges must "cooperate" to move elements around the cycle.

Step 5: Probability comparison

Let $P_\pi$ denote the probability that the sequence of random $k_j$ produces permutation $\pi$.

Identity $(1,2,\dots,n)$: occurs whenever exchanges cancel or are self-loops. Many $k_j$ sequences satisfy this. Probability is relatively large.
Long cycles $(n,1,\dots,n-1)$ and $(2,3,\dots,n,1)$: require a very specific coordination of $k_j$. Probability is very small, on the order of $1/n^n$ for the main contributing sequences.

Hence, the three permutations occur with wildly different probabilities, as the problem statement anticipates.

Step 6: Conclusion

The digraphs producing each permutation are those whose corresponding left-to-right transpositions $(1,k_1)\cdots(n,k_n)$ yield the permutation.
For the identity, many digraphs, especially those with self-loops or cancellations, work.
For the long-cycle permutations, only a few very constrained digraphs work.
Therefore, although the exchanges $k_j$ are chosen uniformly at random, the resulting permutation distribution is highly nonuniform: the identity is much more probable than the long cycles.

This confirms that the probabilities are wildly different.

∎

Remarks

Attempting to describe the digraphs explicitly as chains or cycles (as in the original solution) is incorrect.
The correct approach is to characterize digraphs functionally via the composition of transpositions.
This shows why naive uniform swaps do not produce uniform permutations, motivating the correct shuffling algorithms (e.g., Knuth shuffle / Algorithm P).