TAOCP 1.3.3 Exercise 14

Let $A$ denote the total number of executions of the assignment j\leftarrow i in Algorithm $J$.

taocpmathematicsalgorithmsvolume-1math-hard

Section 1.3.3: Applications to Permutations

Exercise 14. [M34] Find the average value of the quantity $A$ in the timing of Algorithm $J$.

Verified: yes
Solve time: 24m50s

Let $A$ denote the total number of executions of the assignment

$$ j\leftarrow i $$

in Algorithm $J$. We compute the average of $A$ over all $n!$ permutations.

1. Contribution of a single cycle

Let the permutation $\pi$ contain a cycle

$$ C=(a_1,a_2,\ldots,a_r), $$

and let

$$ M=\max{a_1,\ldots,a_r}. $$

Algorithm $J$ processes values of $m$ in the order

$$ n,n-1,\ldots,1. $$

Hence, among the elements of $C$, the element $M$ is encountered first.

When $m=M$, no element of the cycle has yet been restored. The cycle is reconstructed starting from $M$. During this first encounter with the cycle, the assignment $j\leftarrow i$ is not executed.

Now consider any other element $x\in C$, $x\neq M$. Since $x<M$, the cycle has already been partially restored when $m=x$ is reached. At that stage, the entry corresponding to $x$ points by a positive link to the next element of the cycle. Step $J3$ follows that positive link once and executes

$$ j\leftarrow i. $$

Immediately afterward a negative entry is reached and the traversal terminates.

Thus every nonmaximum element of the cycle causes exactly one execution of

$$ j\leftarrow i, $$

and the maximum element causes none.

Therefore a cycle of length $r$ contributes exactly

$$ r-1 $$

to $A$.

If the cycle lengths of $\pi$ are

$$ r_1,r_2,\ldots,r_t, \qquad r_1+\cdots+r_t=n, $$

then

$$ A=\sum_{j=1}^{t}(r_j-1) =\sum_{j=1}^{t}r_j-t =n-t. $$

Since $t=c(\pi)$, the number of cycles of $\pi$,

$$ A=n-c(\pi). $$

Thus

$$ E[A]=n-E[c(\pi)]. $$

It remains to compute the average number of cycles.

2. Average number of cycles

For $1\le k\le n$, let $I_k$ be the indicator variable of the event

$$ I_k= \begin{cases} 1,&\text{if }k\text{ is the largest element in its cycle},\[4pt] 0,&\text{otherwise}. \end{cases} $$

Every cycle contains exactly one largest element, so

$$ c(\pi)=\sum_{k=1}^{n} I_k. $$

Hence

$$ E[c(\pi)] =\sum_{k=1}^{n}E[I_k] =\sum_{k=1}^{n}\Pr(I_k=1). $$

We now compute $\Pr(I_k=1)$.

The event $I_k=1$ means that every other element in the cycle containing $k$ is chosen from

$$ {1,2,\ldots,k-1}. $$

For a random permutation, the cycle containing $k$ is equally likely to contain any subset $S\subseteq{1,\ldots,k-1}$. Equivalently, among the elements of that cycle, each element is equally likely to be the largest. Since the possible largest elements are precisely the elements of ${1,\ldots,k}$, symmetry gives

$$ \Pr(I_k=1)=\frac1k. $$

Therefore

$$ E[c(\pi)] =\sum_{k=1}^{n}\frac1k =H_n, $$

where

$$ H_n=1+\frac12+\cdots+\frac1n $$

is the $n$th harmonic number.

3. Average value of $A$

Using

$$ A=n-c(\pi), $$

we obtain

$$ E[A] =n-E[c(\pi)] =n-H_n. $$

Hence the average value of the quantity $A$ is

$$ \boxed{,n-H_n,}. $$

$\square$