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

View Solution:


Sale on SolutionInn
Sales0
Views41
Comments
  • CreatedOctober 22, 2015
  • Files Included
Post your question
5000