Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 32 min ago
PreprintarXiv licencearXiv

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

  • Günter Rote
Open at sourcePDFDOICite

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.

Related

  1. Existence and uniqueness of radial bound states with prescribed number of nodes for nonlinear dispersive equations on spherically symmetric manifolds
    Valentino Badalucco
    arXivPreprintarXiv licenceFull textAnalysis & PDEsGeometry & topologyarXiv
  2. Random nodes with positive weights: Richter-Tchakaloff rules and optimal positive quadrature
    Sebastian Neumayer, Martin Schäfer, Tino Ullrich
    arXivPreprintCC BY 4.0Full textNumerical analysis & scientific computingarXiv
  3. Random Clocks on Computation Paths]{Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?
    Farzad Didehvar, Saman Farhat
    arXivPreprintCC BY 4.0Full textProbabilityarXiv
  4. The Maximum Number of Shortest Paths in Graphs
    Jing Yu, Jie-Xiang Zhu
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. Random dynamical systems generated by rough differential equations driven by controlled rough paths
    Xing Gao, Jiaqi Liu
    arXivPreprintarXiv licenceFull textProbabilityarXiv

Cite

BibTeXRIS
BibTeX
@misc{rote2026estimating,
  title = {{Estimating the number of nodes and paths in a DAG by following a random path}},
  author = {Günter Rote},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.38586},
  eprint = {2610.38586},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.38586},
}
RIS
TY  - UNPB
TI  - Estimating the number of nodes and paths in a DAG by following a random path
AU  - Günter Rote
PY  - 2026
DA  - 2026/10/28
PB  - arXiv
DO  - 10.48550/arxiv.2610.38586
UR  - https://arxiv.org/abs/2610.38586
AB  - 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.
ER  -