Long and short paths in uniform random recursive dags

Luc Devroye, Svante Janson

In a uniform random recursive k-dag, there is a root, 0, and each node in turn, from 1 to n, chooses k uniform random parents from among the nodes of smaller index. If S_n is the s…