TAOCP 1.3.3 Exercise 24

Section 1.3.3: Applications to Permutations

Exercise 24. [M41] Find the variance of the quantity $A$ that enters into the timing of Algorithm $J$. (See exercise 14.)

Verified: yes
Solve time: 4m38s

---

Let the permutation be decomposed into cycles, and let $\alpha_k$ denote the number of cycles of length $k$.

In the timing analysis of Algorithm $J$ from Exercise 14, the quantity $A$ is the total number of repetitions of step $J3$ caused by following already-established links inside a cycle.

Consider a cycle of length $k$. Let its elements be

$$ a_1<a_2<\cdots<a_k . $$

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

• When $m=a_k$, step $J3$ stops immediately.
• When $m=a_{k-1}$, one previously established link is followed.
• When $m=a_{k-2}$, two links are followed.
• $\dots$
• When $m=a_1$, $k-1$ links are followed.

Hence a $k$-cycle contributes

$$ 0+1+\cdots +(k-1) = \binom{k}{2} $$

to $A$. Therefore

$$ A=\sum_{k\ge1}\binom{k}{2}\alpha_k . $$

To compute the variance, it is convenient to reinterpret $A$.

A cycle of length $k$ contains exactly $\binom{k}{2}$ unordered pairs of elements belonging to the same cycle. Therefore

$$ A = \sum_{1\le i<j\le n} I_{ij}, $$

where

$$ I_{ij} = \begin{cases} 1,&\text{if } i \text{ and } j \text{ lie in the same cycle},\ 0,&\text{otherwise}. \end{cases} $$

Thus $A$ counts the number of unordered pairs of elements that belong to the same cycle.

For a random permutation,

$$ P(I_{ij}=1)=\frac12, $$

so

$$ E(I_{ij})=\frac12, \qquad \operatorname{Var}(I_{ij})=\frac14. $$

There are

$$ N=\binom{n}{2} $$

such pairs.

Covariances

Let $I_{ab}$ and $I_{cd}$ be distinct indicators.

1. Pairs sharing one element

For three distinct elements $a,b,c$,

$$ P(I_{ab}=1,\ I_{ac}=1) = P(a,b,c \text{ are in the same cycle}) = \frac13. $$

Hence

$$ \operatorname{Cov}(I_{ab},I_{ac}) = \frac13-\frac14 = \frac1{12}. $$

The number of unordered indicator-pairs of this type is

$$ 3\binom{n}{3}. $$

2. Disjoint pairs

For four distinct elements $a,b,c,d$,

$$ P(I_{ab}=1,\ I_{cd}=1) = \frac{7}{24}. $$

Indeed, among the four distinguished elements the admissible cycle partitions are

$$ {a,b,c,d} $$

with probability $1/4$, and

$$ {a,b}{c,d} $$

with probability $1/24$. Thus

$$ P(I_{ab}=1,\ I_{cd}=1) = \frac14+\frac1{24} = \frac7{24}. $$

Therefore

$$ \operatorname{Cov}(I_{ab},I_{cd}) = \frac7{24}-\frac14 = \frac1{24}. $$

The number of unordered indicator-pairs of this type is

$$ 3\binom{n}{4}. $$

Variance

Using

$$ \operatorname{Var}(A) = \sum \operatorname{Var}(I_{ij}) + 2!!\sum_{p<q}!!\operatorname{Cov}(I_p,I_q), $$

we obtain

$$ \operatorname{Var}(A) = \binom{n}{2}\frac14 + 2!\left( 3\binom{n}{3}\frac1{12} + 3\binom{n}{4}\frac1{24} \right). $$

Hence

$$ \operatorname{Var}(A) = \frac14\binom{n}{2} +\frac12\binom{n}{3} +\frac14\binom{n}{4}. $$

After simplification,

$$ \boxed{ \operatorname{Var}(A) = \frac{n(n-1)(n+1)(n+2)}{96} }. $$

This is the variance of the quantity $A$ appearing in the timing analysis of Algorithm $J$.