Paperlane

no. 5 · Friday 30 October 2026

Estimating the number of nodes and paths in a DAG by following a random path

Günter Rote

math.CO · via cs.DS · 28 pp

Abstract

We investigate a simple method to compute an unbiased estimate of the number of nodes of a directed acyclic graph (DAG) by following a random directed path. This method is due to Leonard Pitt from 1987, and it generalizes a method of D. E. Knuth from the 1960s for estimating the size of a rooted tree. A slight variation makes it possible to estimate the number of source-sink paths. We extend the algorithm to use many "agents" that walk cooperatively through the graph. This extension unifies and generalizes several methods that have been proposed for approximately counting the nodes of a tree.

comments
28 pages, 5 figures, 10 tables, 4 appendices
fields
Combinatorics
pdf ↗ page arXiv:2610.38586 ↗