Question

Question: 36. The following method can be used to generate a random permutation of a sequence of \(n\)terms. First, interchange the \(n\)the term and the \(r(n)\)the term where \(r(n)\)is a randomly selected integer with \(1 \le r(n) \le n\). Next, interchange the \((n - 1){\rm{st}}\)term of the resulting sequence with its \(r(n - 1)\)st term where \(r(n - 1)\)is a randomly selected integer with \(1 \le r(n - 1) \le n - 1\). Continue this process until \(j = n\), where at the \(j\)the step you interchange the \((n - j + 1)\)st term of the resulting sequence with its \(r(n - j + 1)\)st term, where \(r(n - j + 1)\)is a randomly selected integer with \(1 \le r(n - j + 1) \le n - j + 1\). Show that when this method is followed, each of the \(n\)! different permutations of the terms of the sequence is equally likely to be generated. (Hint: Use mathematical induction, assuming that the probability that each of the permutations of \(n - 1\)terms produced by this procedure for a sequence of \(n - 1\)terms is \({\bf{1}}{\rm{ }}/\left( {{\bf{n}} - {\bf{1}}} \right)\).)

Short answer

Answer

The probability that each of the permutations of \(n - 1\) terms is produced by this procedure for a sequence of \(n - 1\) terms is \(\frac{1}{{(n - 1)!}}\).

Step-by-step solution

Definition of Permutation 

Permutation (order is important):

No repetition allowed:\(P(n,r) = \frac{{n!}}{{(n - r)!}}\)

Repetition allowed: \({{\bf{n}}^r}\)

Use Permutation

PROOF BY INDUCTION

Let\(P(n)\)be "The probability that each of the permutations of\(n - 1\)terms are produced by this procedure for a sequence of\(n - 1\)terms are\(\frac{1}{{(n - 1)!}}\)".

Basis step\(n = 1\).

Use the algorithm on a permutation of 1 term. The algorithm then contains only 1 step, which is interchange the first element with the first element and thus we obtain the only permutation of the 1 term.

Since the event of the one permutation is certain to occur:\(P\left( {{P_1}} \right) = 1\),

\(\begin{aligned}{}\frac{1}{{(n - 1)}} &= \frac{1}{{(1 - 1)}}\\ &= \frac{1}{0}\\ &= \frac{1}{1}\\ &= 1\end{aligned}\)

Thus\(P(1)\)is true.

Induction step Let \(P(k)\) be true. The probability that each of the permutations of \(k\) terms is produced by this procedure for a sequence of \(k\) terms is \(\frac{1}{k}\) it needs to proof that \(P(k + 1)\) is true.

Execute the algorithm

It first executes the algorithm for the\(k + 1\)integer (step 1). Since we randomly select an integer between 1 and\(k + 1\), each of the integers is equally likely and thus each integer\(r(k + 1)\)has 1 chance in\(k + 1\)to be selected.

\(P(r(k + 1)) = \frac{1}{{k + 1}}\)

In the next step, it ignores the\(k + 1\)integer and thus it then has a permutation of\(k\)terms remaining and it knows that each permutation of\(k\)terms has a probability of\(\frac{1}{k}\)(since\(P(k)\)is true).

\(P\left( {{P_k}} \right) = \frac{1}{{k!}}\)

Multiply the Probabilities

Multiply the corresponding probabilities:

\(\begin{aligned}{c}P\left( {{P_{k + 1}}} \right) = P(r(k + 1)) \cdot P\left( {{P_k}} \right)\\ = \frac{1}{{k + 1}} \cdot \frac{1}{{k!}} = \frac{1}{{(k + 1)!}}\end{aligned}\)

Thus\(P(k + 1)\)is true.

Conclusion By the principle of mathematical induction, \(P(n)\) is true for all positive integers \(n\) with \(n \ge 2\).