[Math] Probability of cycle in random graph

graph theoryprobability

I create a random directed graph, with N vertices and N edges, in the following process:

A. Each vertex has a single outgoing edge.

B. The target of that edge is selected at random from all N vertices (self loops are possible).

What is the probability that a certain edge, selected at random, will be a part of a directed cycle?


FYI: This problem comes from the following model of land trade: http://ccl.northwestern.edu/netlogo/models/community/land-random . The meaning of an edge "being a part of a cycle" is that the relevant land-plot will not be returned to its original owner. My simulations show that this probability is quite low – about 3.9% in average. I would like to understand why, so I am looking for a theoretic solution.

Best Answer

Select a starting vertex and follow the edges, choosing the endpoint of each point randomly as you go along. Sooner or later you will end at a vertex you have been at before. If that vertex is the starting vertex, then your initial edge was part of a cycle, otherwise it wasn't.

Using this procedure, let's derive the probability that the initial edge was part of a cycle containing $N-a$ vertices for $0\le a< N$ (I'm parameterizing by the number of vertices not in the cycle, which happens to make the following formulas come out nicer). For this to happen, we first have to select a yet unused vertex $N-a-1$ times, which happens with probability $$ \frac{N-1}{N} \frac{N-2}{N}\cdots \frac{a+1}{N} = \frac{(N-1)!}{a! N^{N-a-1}}$$ -- and then we have to select the initial vertex, for an additional factor of $\frac 1N$.

Summing over all cycle lengths, the probability for the initial edge to be part of any cycle is $$P_N = \sum_{a=0}^{N-1} \frac{(N-1)!}{a!N^{N-a}} = \frac{(N-1)!}{N^N} \sum_{a=0}^{N-1} \frac{N^a}{a!}$$

Recognizing the sum in the final expression as a partial sum of the series for $e^N$, and using Stirling's approximation for the factorial, we can bound this probability from above as $$P_N < \frac{(N-1)!}{N^N} e^N = N!\frac{e^N}{N^{N+1}} \approx \sqrt{2\pi N}\frac{N^N}{e^N}\frac{e^N}{N^{N+1}} = \sqrt{\frac{2\pi}{N}} $$ but this is at least a factor of $2$ too high, because the exponential series was cut off right at its largest term (and the terms of the full series fall off slower after the apex than they increases to begin with).

Edit: I am now informed that $\sum_{n=0}^{k} \frac{k^n}{n!} \sim \frac{e^k}{2}$, which allows us to refine the estimate to an actual approximation: $$ P_N \approx \sqrt{\frac{\pi}{2N}} - \frac{1}{N}$$

Related Question