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.

  • $\begingroup$ What did you have for $N$ in your simulation? About $1700$? $\endgroup$ – Henry Apr 25 '12 at 20:44
  • $\begingroup$ I assume a self loop counts as a directed cycle. $\endgroup$ – Henry Apr 25 '12 at 20:45
  • $\begingroup$ N was 1000. A self loop counts as a directed cycle. $\endgroup$ – Erel Segal-Halevi Apr 26 '12 at 6:24
  • 1
    $\begingroup$ BTW, I see there are many questions about random graphs, why not add a "random-graph" tag? $\endgroup$ – Erel Segal-Halevi Apr 26 '12 at 6:27
  • $\begingroup$ For $N=1000$, the probability is closer to 3.9% $\endgroup$ – Henry Apr 26 '12 at 6:34

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}$$

  • $\begingroup$ That is probably the answer and certainly looks $O\left(\frac{1}{\sqrt{N}}\right)$. OEIS A001865 does not give a closed formula. $\endgroup$ – Henry Apr 25 '12 at 21:01
  • $\begingroup$ Fantastic! How can I quote your answer in a paper? $\endgroup$ – Erel Segal-Halevi Apr 26 '12 at 6:26
  • 1
    $\begingroup$ Empirically I suspect that something like $P_N \approx \sqrt{\frac{\pi}{2N}} - \frac{1}{3N}$ may be closer $\endgroup$ – Henry Apr 26 '12 at 7:04
  • $\begingroup$ What happens if every vertex has an outgoing edge with a probability of q<1 (instead of 1 as in the original problem)? In this case, we get additional q factor in each edge, so $$P_N = \sum_{a=0}^{N-1} \frac{(N-1)!}{a!N^{N-a}} = \frac{(N-1)!q^N}{N^N} \sum_{a=0}^{N-1} \frac{N^a}{a!q^a}$$. How can this be approximated? $\endgroup$ – Erel Segal-Halevi Apr 26 '12 at 9:59
  • 1
    $\begingroup$ @Erel: I don't think you can cite an MSE answer for truth in a paper, so you will have to reproduce the argument there and credit MSE informally in a footnote or acknowledgments section. As for the $q$ version, I have no good ideas. What I could think of on short notice was too crude to even give a better upper bound than the $q=1$ limit. $\endgroup$ – Henning Makholm Apr 26 '12 at 11:05

This problem can also be solved using recursion. First we see that, the edge selected randomly to be a part of a cycle iff the starting point of the edge is a part of a cycle

Let $p_n$ be the probability that the starting point of the edge is a part of some cycle hence we can say that,

$p_n = \frac{1}{n}(1) + \frac{n-1}{n}p_{n-2} $

This can be solved easily to get the closed form expression of $p_n$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.