I attempted this on my own and got a fairly simple solution. However, after reading proofs here and here, I feel like I have massively over simplified the problem. I understand the other solutions, but does my shorter one work?

Proposition. The expected number of cycles of length $k$ in an Erdős–Rényi random graph $G_{n,p}$ is $$\binom nk(k-1)!p^k/2.$$

Proof. A cycle of length $k$ requires $k$ vertices of which there are $\binom nk$ choices. There are $k!$ different cycles/paths we could potentially follow in a cycle on these $k$ vertices. Since the starting point is irrelivant, we can divide by $k$, as is the direction/orientation, giving $(k-1)!/2$ different cycles. For each cycle, we require the $k$ edges between them to be included in the graph, which happens with probability $p^k$. Conclude that the expected number of such cycles is as stated.

Edit: I am only interested in cycles of length $k$, sorry!

  • $\begingroup$ Apologies for my erroneous answer. Your solution is basically the same as this one here. $\endgroup$
    – angryavian
    May 24, 2016 at 4:20
  • 2
    $\begingroup$ @angryavian I had seen that but was worried about independence, to be honest. Was your answer incorrect because $E(Y+Z)=E(Y)+E(Z)$ for any RVs $Y$, $Z$ (i.e. independence is not necessary for the final step in my proof)? $\endgroup$
    – Szmagpie
    May 24, 2016 at 4:29
  • 3
    $\begingroup$ Yes, basically. That is the advantage of using indicators. $\endgroup$
    – angryavian
    May 24, 2016 at 4:30
  • $\begingroup$ The solution above makes sense to me, but I'd like to ask some further questions, since I usually get confused when analyzing similar situations. In particular, why is it not enough to just stop at ${n \choose k}$ (and multiplying it by the probability term of course), but we have to go on with the analysis of $k!$ ways the elements are arranged? I don't see the train of thoughts here. $\endgroup$
    – ensbana
    Feb 15, 2020 at 14:41


You must log in to answer this question.

Browse other questions tagged .