Question

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.

Short answer

Answer for each part is

(a)The explanation for this part is given below.

(b)The statement is proved below.

Step-by-step solution

Part (a) Step 1: Given Information

We need to explain what the algorithm is doing.

Part (a) Step 2: Explanation

The algorithm goes from position$k=1$to the position$k=n-1$and in every iteration, it chooses one number from set$\left\{1,...,n\right\}$and replaces values at positionlocalid="1648185462421" $k$and that randomly chosen position.

Part (b) Step 1: Given Information

We have to prove that when the value of $P\left(k\right)$is initially set—$P\left(1\right),P\left(2\right),...,P\left(k\right)$is a random permutation of $1,2,...,k$.

Part (b) Step 2: Explanation

Using mathematical induction. For basis $k=1,$the claim trivally holds. Suppose now that the claim is true for $k-1.$What is for $k$?

Since the value at position $k$in $kth$iteration is swapped with the value at random position, we have

$P_k\left\{i_1,i_2,...,i_{j-1},k,i_j,...,i_{k-2},i\right\}=P_{k-1}\left\{i_1,i_2,...,i_{j-1},i,i_j,...,j_{k-2}\right\}\frac{1}{k}$

Now, using the hypothesis of induction

$P_{k-1}\left\{i_1,i_2,...,i_{j-1},i,i_j,...i_{k-2}\right\}=\frac{1}{\left(k-1\right)!}$

So, we have

$P_k\left\{i_1,i_2,..,i_{j-1},k,i_j,...,i_{k-2},i\right\}=\frac{1}{k!}$

Hence, the statement is proved.