2
$\begingroup$

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.

$\endgroup$
3
  • $\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
    Commented May 23, 2018 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
    Commented May 23, 2018 at 23:30
  • $\begingroup$ @quasi : No worries, thanks :) i thought i had misunderstood the question. $\endgroup$
    – Phicar
    Commented May 23, 2018 at 23:39

1 Answer 1

4
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .