We describe 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. It generalizes in a straightforward way a method of D. E. Knuth from the 1960s for estimating the size of a rooted tree. A slight variation allows 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.
Last update: April 26, 2026.