Section 1.3.3: Applications to Permutations

Exercise 22. [HM34] (The following approach, due to L. Shepp and S. P. Lloyd, gives a convenient and powerful method for solving problems related to the cycle structure of random permutations.) Instead of regarding the number, $n$, of objects as fixed, and the permutation variable, let us assume instead that we independently choose the quantities $\alpha_1, \alpha_2, \alpha_3, \ldots$ appearing in exercises 20 and 21 according to some probability distribution. Let $w$ be any real number between 0 and 1.

a) Suppose that we choose the random variables $\alpha_1, \alpha_2, \alpha_3, \ldots$ according to the rule that "the probability that $\alpha_m = k$ is $f(w, m, k)$," for some function $f(w, m, k)$. Determine the value of $f(w, m, k)$ so that the following two conditions hold:

1. $\sum_{k \ge 0} f(w, m, k) = 1$, for $0 < w < 1$ and $m \ge 1$;
2. the probability that $\alpha_1 + 2\alpha_2 + 3\alpha_3 + \cdots = n$ and that $\alpha_1 = k_1$, $\alpha_2 = k_2$, $\alpha_3 = k_3$, ... equals $(1 - w)w^n P(n; k_1, k_2, k_3, \ldots)$, where $P(n; k_1, k_2, k_3, \ldots)$ is defined in exercise 21.

b) A permutation whose cycle structure is $\alpha_1, \alpha_2, \alpha_3, \ldots$ clearly permutes exactly $\alpha_1 + 2\alpha_2 + 3\alpha_3 + \cdots$ objects. Show that if the $\alpha$'s are randomly chosen according to the probability distribution in part (a), the probability that $\alpha_1 + 2\alpha_2 + 3\alpha_3 + \cdots = n$ is $(1 - w)w^n$; the probability that $\alpha_1 + 2\alpha_2 + 3\alpha_3 + \cdots$ is infinite is zero.

c) Let $\phi(\alpha_1, \alpha_2, \ldots)$ be any function of the infinitely many numbers $\alpha_1, \alpha_2, \ldots$. Show that if the $\alpha$'s are chosen according to the probability distribution in (a), the average value of $\phi$ is $(1 - w)\sum_{n \ge 0} w^n \phi_n$; here $\phi_n$ denotes the average value of $\phi$ taken over all permutations of $n$ objects, where the variable $\alpha_j$ represents the number of $j$-cycles of a permutation. [For example, if $\phi(\alpha_1, \alpha_2, \ldots) = \alpha_1$, the value of $\phi_n$ is the average number of singleton cycles in a random permutation of $n$ objects; we showed in (28) that $\phi_n = 1$ for all $n$.]

d) Use this method to find the average number of cycles of even length in a random permutation of $n$ objects.

e) Use this method to solve exercise 18.

Verified: yes
Solve time: 11m55s

---

We start by using the standard cycle enumeration formula.

From Exercise 21, the number of permutations of $n$ objects with cycle counts $(k_1,k_2,\dots)$ satisfying $\sum m k_m=n$ is

$$ \frac{n!}{\prod_{m\ge 1} m^{k_m} k_m!}, $$

hence the probability for a uniform random permutation of $n$ objects is

$$ P(n;k_1,k_2,\dots)=\frac{1}{\prod_{m\ge 1} m^{k_m} k_m!}. $$

(a) Determination of $f(w,m,k)$

We want independent random variables $\alpha_m$ such that

$$ \Pr(\alpha_m=k)=f(w,m,k), $$

and such that for every $(k_1,k_2,\dots)$,

$$ \Pr\Big(\alpha_m=k_m\ \forall m,\ \sum m\alpha_m=n\Big)=(1-w)w^n P(n;k_1,k_2,\dots). $$

Step 1: guess a factorized form

We try Poisson distributions:

$$ f(w,m,k)=e^{-\lambda_m}\frac{\lambda_m^k}{k!} $$

with parameters $\lambda_m$ to be determined.

Then the joint probability is

$$ \prod_{m\ge 1} e^{-\lambda_m}\frac{\lambda_m^{k_m}}{k_m!} = \exp\Big(-\sum_{m\ge 1}\lambda_m\Big)\prod_{m\ge 1}\frac{\lambda_m^{k_m}}{k_m!}. $$

Step 2: match the cycle structure term

We want the factor

$$ \prod_{m\ge 1}\frac{1}{m^{k_m}k_m!} $$

to appear. Hence we set

$$ \lambda_m=\frac{w^m}{m}. $$

Then

$$ \prod_{m\ge 1}\frac{\lambda_m^{k_m}}{k_m!} =\prod_{m\ge 1}\frac{w^{mk_m}}{m^{k_m}k_m!} =w^n \prod_{m\ge 1}\frac{1}{m^{k_m}k_m!}, $$

since $\sum m k_m=n$.

Thus the joint probability becomes

$$ \exp\Big(-\sum_{m\ge 1}\frac{w^m}{m}\Big), w^n, P(n;k_1,k_2,\dots). $$

Step 3: evaluate the normalizing constant

$$ \sum_{m\ge 1}\frac{w^m}{m}=-\log(1-w), $$

so

$$ \exp\Big(-\sum_{m\ge 1}\frac{w^m}{m}\Big)=1-w. $$

Conclusion

$$ \boxed{f(w,m,k)=e^{-w^m/m}\frac{(w^m/m)^k}{k!}}. $$

(b) Distribution of $\sum m\alpha_m$

Summing the joint probability over all $(k_m)$ with fixed total $n$,

$$ \Pr\Big(\sum_{m\ge 1} m\alpha_m=n\Big) =(1-w)w^n \sum_{\sum m k_m=n} P(n;k_1,k_2,\dots). $$

But the $P(n;\cdot)$ form a probability distribution over all cycle types of permutations of $n$, hence the sum equals $1$. Therefore

$$ \Pr\Big(\sum m\alpha_m=n\Big)=(1-w)w^n. $$

Hence $\sum m\alpha_m$ has geometric distribution on ${0,1,2,\dots}$, and

$$ \Pr\Big(\sum m\alpha_m=\infty\Big)=0 $$

since $\sum_{n\ge 0}(1-w)w^n=1$.

(c) Expectation identity

Let $\phi(\alpha_1,\alpha_2,\dots)$ be any function. Then

$$ \mathbb{E}[\phi] =\sum_{(k_m)} \phi(k_1,k_2,\dots)\Pr(\alpha_m=k_m\ \forall m). $$

Group terms by $n=\sum m k_m$:

$$ \mathbb{E}[\phi] =\sum_{n\ge 0}\sum_{\sum m k_m=n} \phi(k_1,k_2,\dots)(1-w)w^n P(n;k_1,k_2,\dots). $$

For fixed $n$, the conditional probability of cycle type is

$$ \Pr(\alpha_m=k_m\ \forall m\mid \sum m\alpha_m=n)=P(n;k_1,k_2,\dots), $$

because the factor $(1-w)w^n$ is constant over all configurations with the same $n$.

Thus the inner sum is exactly the expectation $\phi_n$ over permutations of $n$ objects:

$$ \mathbb{E}[\phi]=(1-w)\sum_{n\ge 0} w^n \phi_n. $$

(d) Expected number of even cycles in a permutation of $n$

Let

$$ \phi(\alpha)=\sum_{\substack{m\ge 1\ m\ \text{even}}}\alpha_m. $$

For a uniform random permutation of $n$, linearity of expectation gives

$$ \phi_n=\sum_{\substack{m\le n\ m\ \text{even}}}\mathbb{E}[\alpha_m]. $$

A standard result from cycle counting is:

$$ \mathbb{E}[\alpha_m]=\frac{1}{m}\quad (m\le n). $$

Therefore

$$ \boxed{\phi_n=\sum_{\substack{m\le n\ m\ \text{even}}}\frac{1}{m}} =\sum_{k=1}^{\lfloor n/2\rfloor}\frac{1}{2k} =\frac{1}{2}H_{\lfloor n/2\rfloor}. $$

This is an exact identity, not an asymptotic approximation.

(e) Solution of Exercise 18

Exercise 18 asks for the expected number of cycles whose length is divisible by $d$.

Let

$$ \phi(\alpha)=\sum_{\substack{m\ge 1\ d\mid m}}\alpha_m. $$

Again,

$$ \phi_n=\sum_{\substack{m\le n\ d\mid m}}\mathbb{E}[\alpha_m] =\sum_{\substack{m\le n\ d\mid m}}\frac{1}{m}. $$

Write $m=dk$. Then $k\le \lfloor n/d\rfloor$, so

$$ \phi_n=\sum_{k=1}^{\lfloor n/d\rfloor}\frac{1}{dk} =\frac{1}{d}H_{\lfloor n/d\rfloor}. $$

Thus

$$ \boxed{\text{Expected number of cycles with length divisible by }d =\frac{1}{d}H_{\lfloor n/d\rfloor}.} $$