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.
