2

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.

Daniel
  • 2,630
  • 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? – Phicar May 23 '18 at 21:59
  • @Phicar: I answered without looking at the comments, but yes, it's that simple (and my answer is essentially the same as your comment). – quasi May 23 '18 at 23:30
  • @quasi : No worries, thanks :) i thought i had misunderstood the question. – Phicar May 23 '18 at 23:39

1 Answers1

4

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

quasi
  • 58,772