# Question: The following algorithm will generate a random permutation of the

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

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

**View Solution:**## Answer to relevant Questions

Consider the grid of points shown at the top of the next column. Suppose that, starting at the point labeled A, you can go one step up or one step to the right at each move. This procedure is continued until the point ...How many different letter arrangements can be made from the letters (a) Fluke? (b) Propose? (c) Mississippi? (d) Arrange? Prove the multinomial theorem. In Example 2c we simulated the absolute value of a unit normal by using the rejection procedure on exponential random variables with rate 1. This raises the question of whether we could obtain a more efficient algorithm by ...Present a method for simulating a random variable having distribution functionPost your question