Flajolet & Sedgewick: How to compute the variance of the number of cycles in a random permutation

analytic-combinatoricscombinatoricspermutationsprobabilityvariance

I am reading the book Analytic Combinatorics 4ed by Sedgewick and Flajolet. On page 160 at Example III.4 the authors derive the variance of the number of cycles in a random permutation. I can follow the authors up to the part where the write

$$\sigma_n^2 = \biggl(\sum_{k=1}^n \frac{1}{k} \biggr) – \biggl(\sum_{k=1}^n \frac{1}{k^2} \biggr). $$

I do not understand how they arrive at that. If I understand the above part correctly the authors state that $\mathbb{E}_n[\chi] = H_n$, where $H_n$ is the $n$-th Harmonic Number, and $\mathbb{E}_n[\chi(\chi-1)] = \sum_{k=1}^n \frac{1}{k^2}$.

I think that it would now suffice to compute

$$\mathbb{E}_n[\chi^2] – \mathbb{E}_n[\chi]^2$$

by somehow utilising the above. However, I do not understand how to do that. Could you please help me?

Could you please explain this to me?

Best Answer

Probably not exactly what you were looking for, but the calculations are a bit easier:

  • Law of total variance with $Y=C_n$, the number of cycles in a uniform permutation on $n$ elements and $X=\mathbf 1\{n\text{ is a fixed point}\}$ gives $$\text{Var}(C_n)=\text{Var}(\mathbb E[C_n\mid X])+\mathbb E[\text{Var}(C_n\mid X)].$$
  • By the Chinese restaurant construction, $\mathbb E[C_n\mid X]$ is just $\mathbb E C_{n-1}$ with probability $1-{1\over n}$ and $1+\mathbb E C_{n-1}$ with probability $1\over n$; thus its variance is that of a Bernoulli random variable with success rate $1\over n$, i.e.: $$\text{Var}(\mathbb E[C_n\mid X])={1\over n}-{1\over n^2}.$$
  • Analogously: $$\mathbb E[\text{Var}(C_n\mid X)]={1\over n}\text{Var}(1+C_{n-1})+\left(1-{1\over n}\right)\text{Var}(C_{n-1})=\text{Var}(C_{n-1}).$$
  • Combining the above, we get $$\text{Var}(C_n)=\text{Var}(C_{n-1})+{1\over n}-{1\over n^2}=\dots=\sum_{k=1}^n\left({1\over k}-{1\over k^2}\right),$$ as desired.

While this might not look as general/reusable as the above, the law of total variance comes in handy whenever you have a way of recursively generating a random object (e.g. random permutations via the Chinese restaurant process here, or fractals) and want to know the variance of some observable.

Related Question