Suppose we have a random $DAG(n, p)$. Here is how it's generated:

  • Put n distinct nodes on a line, and connect each node in the $i$th order to any node after that; This would form a complete directed graph with $n$ nodes.

  • Sample each edge with probability $p$.

The resulting graph will be directed, and acyclic.

The question is: what is the number of paths of length $\ell$ in a random $DAG(n, p)$?

Note: I know the answer for an undirected graph.

  • $\begingroup$ Well, as is directed to the right, then the paths are just how to pick $l +1$ vertices from the $n$ vertices and each edge has prob $p$ so is not $\binom{n}{l +1}p^{l}$? Am i missing something? $\endgroup$ – Phicar May 23 '18 at 21:59
  • $\begingroup$ @Phicar: I answered without looking at the comments, but yes, it's that simple (and my answer is essentially the same as your comment). $\endgroup$ – quasi May 23 '18 at 23:30
  • $\begingroup$ @quasi : No worries, thanks :) i thought i had misunderstood the question. $\endgroup$ – Phicar May 23 '18 at 23:39

Based on the specified graph construction scheme, a path of length $k$ requires $k+1$ vertices, in ascending vertex number order.

It follows that there are exactly ${\large{\binom{n}{k+1}}}$ potential paths of length $k$.

For each such potential path, the probability that it's an actual path is $p^k$.

Therefore, the expected number of paths of length $k$ is ${\large{\binom{n}{k+1}}}p^k$.


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.