Chapter 10, Problem 10.1P

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\left(i\right)$ can be interpreted as the element in position i.

Step 1. Set $k=1$

Step 2. Set $P\left(1\right)=1$.

Step 3. If $k=n$, stop otherwise, let $k=k+1$.

Step 4. Generate a random number U and let $\begin{array}{l}P\left(k\right)=P\left(\left[kU\right]+1\right)\\ P\left(\left[kU\right]÷1\right)=k\end{array}$

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.

Hint: Use induction and argue that $\begin{array}{l}{P}_k\left\{i_1,i_2\mathrm{...},i_{j-1},k,i_j,\mathrm{...},i_{k-2},i\right\}\\ =P_{k-1}\left\{i_1,i_2\mathrm{...},i_{j-1},k,i_j,\mathrm{...},i_{k-2}\right\}\frac{1}{k}\\ =\frac{1}{k!}\text{ by the induction hypothesis}\end{array}$

To determine

To find: the explanation that the algorithm is doing.

Explanation of Solution

Given:

Some steps of algorithm are given.

The algorithm starts by initially putting k=1 thus it sets $\mathrm{p}\left(1\right)=1$ .

Then, until $\mathrm{K}=\mathrm{M}$ it increases the value of K by one after each iteration. It generates a random number U and replaces $\mathrm{p}\left(\mathrm{k}\right)$ by $\mathrm{p}\left(\left[\mathrm{k}\mathrm{u}\right]+1\right)$ . Then, it puts $\mathrm{p}\left(\left[\mathrm{k}\mathrm{u}\right]+1\right)=\mathrm{k}$ . Then, it goes again to step 3.

This algorithm start by putting $\mathrm{p}\left(1\right)=1$ , but it does not exclude this value in next interation the value of $\mathrm{p}\left(1\right)$ can change in any subsequent iteration. Thus, no position is fixed until the algorithm ends.

Therefore, therequired explanation is shown above.

To determine

To prove:that the set $\mathrm{p}\left(1\right),\mathrm{p}\left(2\right),\mathrm{.....},\mathrm{p}\left(\mathrm{k}\right)$ which is a random permutation of $1,2,\mathrm{....},\mathrm{k}$ .

Explanation of Solution

Given:

It is given that ${\mathrm{p}}_{\mathrm{k}}\left\{{\mathrm{i}}_1,{\mathrm{i}}_2,\mathrm{......},{\mathrm{i}}_{\mathrm{k}}\right\}={\mathrm{p}}_{\mathrm{k}-1}\left\{{\mathrm{i}}_1,{\mathrm{i}}_2,\mathrm{.....},{\mathrm{i}}_{\mathrm{k}-1}\right\}\times \mathrm{p}\left\{{\mathrm{i}}_{\mathrm{k}}\right\}$ .

As it is given that the condition ${\mathrm{p}}_{\mathrm{k}}\left\{{\mathrm{i}}_1,{\mathrm{i}}_2,\mathrm{......},{\mathrm{i}}_{\mathrm{k}}\right\}={\mathrm{p}}_{\mathrm{k}-1}\left\{{\mathrm{i}}_1,{\mathrm{i}}_2,\mathrm{.....},{\mathrm{i}}_{\mathrm{k}-1}\right\}\times \mathrm{p}\left\{{\mathrm{i}}_{\mathrm{k}}\right\}$ .

It is known that;

  $\begin{array}{c}\mathrm{p}\left\{{\mathrm{i}}_{\mathrm{k}}\right\}=\frac{1}{\text{total sample space}}\\ =\frac{1}{\mathrm{k}}\end{array}$

Then, the given condition becomes;

  ${\mathrm{p}}_{\mathrm{k}}\left\{{\mathrm{i}}_1,{\mathrm{i}}_2,\mathrm{......},{\mathrm{i}}_{\mathrm{k}}\right\}={\mathrm{p}}_{\mathrm{k}-1}\left\{{\mathrm{i}}_1,{\mathrm{i}}_2,\mathrm{.....},{\mathrm{i}}_{\mathrm{k}-1}\right\}\times \frac{1}{\mathrm{k}}$

Similarly,

  $\begin{array}{c}{\mathrm{p}}_{\mathrm{k}}\left\{{\mathrm{i}}_1,{\mathrm{i}}_2,\mathrm{......},{\mathrm{i}}_{\mathrm{k}}\right\}=\frac{1}{\mathrm{k}}\times \frac{1}{\mathrm{k}-1}\times \mathrm{.....}\frac{1}{1}\\ =\frac{1}{\mathrm{k}!}\end{array}$

This proves that at iteration k can be defined as $\mathrm{p}\left(1\right),\mathrm{p}\left(2\right),\mathrm{.....},\mathrm{p}\left(\mathrm{k}\right)$ which is a random permutation of $1,2,\mathrm{....},\mathrm{k}$ .

Therefore, the required identity has been proved.