# Long and short paths in uniform random recursive dags - Mathematics > Probability

Long and short paths in uniform random recursive dags - Mathematics > Probability - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: In a uniform random recursive k-dag, there is a root, 0, and each node inturn, from 1 to n, chooses k uniform random parents from among the nodes ofsmaller index. If S n is the shortest path distance from node n to the root,then we determine the constant \sigma such that S n-logn tends to \sigma inprobability as n tends to infinity. We also show that max {1 \le i \le n}S i-logn tends to \sigma in probability.

Autor: Luc Devroye, Svante Janson

Fuente: https://arxiv.org/