# Expected Number of Cycles in Random Permutations with a Random Number of Symbols

It is known that for permutations sampled uniformly from $S_k$ that $\mathbb{E}[C] = H_k = O(\log k)$ (more precisely, $\Theta(\log k)$), where $C$ is the number of cycles in a random permutation.

If $k$ is itself a random variable, for instance if $k$ is Binomially distributed with parameters: $n$ trials and $p$ probability, may the expectation be composed? In the sense:

$$\mathbb{E}[C] = O(\log \mathbb{E}[k]) = O(\log np)$$

I have a feeling that this is true especially, but perhaps not necessarily, given that both expectations are monotonic in the relevant parameters.

EDIT: I believe the condition required is not monotonicity, but that the expectation with respect to the hyperparameter must be bounded above by a concave function. In this particular case:

$$\mathbb{E}[C] = \mathbb{E}_k[\mathbb{E}[C\mid k]] = \mathbb{E}_k[O(\log k)] \leq O(\mathbb{E}_k[\log k]) \leq O(\log \mathbb{E}_k[k]) = O(\log np)$$

Hence $\mathbb{E}[C] = O(\log np)$. This doesn't permit us to say that $\mathbb{E}[C] = \Omega(\log np)$ though.

• Linearity of expectation Commented Jan 27, 2016 at 22:52
• I'm not quite clear on how linearity of expectation gives you any more than the first equality in my edit, unless you are only addressing the case of a Binomial distribution. I think the use of Jensen's inequality in that line is necessary for the conclusion. Could you correct me if I am wrong? Commented Jan 27, 2016 at 23:32