arXiv:2610.38586 · v1

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

首次提交 2026-10-28 18:15

版本更新 2026-10-28 18:15

雷达观测 2026-10-30 10:22

摘要

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.

作者备注：28 pages, 5 figures, 10 tables, 4 appendices