The following algorithm will generate a random permutation of the elements 1, 2, . . . , n. It is somewhat faster than the one presented in Example 1a but is such that no position is fixed until the algorithm ends. In this algorithm, P(i) can be interpreted as the element in position i.
Step 1. Set k = 1.
Step 2. Set P(1) = 1.
Step 3. If k = n, stop. Otherwise, let k = k + 1.
Step 4. Generate a random number U and let
P(k) = P([kU] + 1)
P([kU] + 1) = k
Go to step 3.
(a) Explain in words what the algorithm is doing.
(b) Show that at iteration k—that is, when the value of P(k) is initially set—P(1), P(2), . . . , P(k) is a random permutation of 1, 2, . . . , k.
Use induction and argue that
Pk{i1, i2, . . . , ij−1, k, ij, . . . , ik−2, i}
= Pk−1{i1, i2, . . . , ij−1, i, ij, . . . , ik−2} 1/k
= 1/k! by the induction hypothesis