pith. sign in

arxiv: 2606.30475 · v1 · pith:VAPNTDO4new · submitted 2026-06-29 · 🧮 math.PR · math.CO

Ancestries in random d-DAGs

Fabian Burghart This is my paper

Pith reviewed 2026-06-30 04:47 UTC · model grok-4.3

classification 🧮 math.PR math.CO
keywords random DAGancestry processPólya urndescendantsrecursive graphslimit theoremsJanson questions
0
0 comments X

The pith

Ancestry processes modeled as Pólya urns determine descendant properties in random d-DAGs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proposes ancestry processes to study the descendants in a random recursive DAG where each vertex has fixed out-degree d. These processes count the ancestors of a vertex and evolve according to multi-draw Pólya urn rules. Asymptotics of these processes translate into results on the number of descendants, allowing answers to two specific open questions from Janson on joint descendants of the last two vertices and the earliest non-descendant. The method also yields limit theorems for the ancestry counts and the position of the earliest source node.

Core claim

By defining the ancestor process a_i(n) as the number of ancestors of vertex i in the graph G_n on [n], and noting its equivalence to multi-draw Pólya urn evolution, the paper obtains technical integral expressions for descendant functionals that resolve the size of the joint descendants of vertices n and n+1 and the location of the earliest non-descendant of n.

What carries the argument

The ancestry process a_i(n), which tracks ancestor counts and mirrors multi-draw Pólya urn dynamics to convert urn limit laws into descendant statistics.

If this is right

  • The joint descendant count for n and n+1 admits an asymptotic description via integrals derived from urn convergence.
  • The position of the earliest non-descendant follows a limiting distribution obtained from the ancestry process.
  • Limit theorems hold for a_i(n) as n tends to infinity, for fixed or growing i.
  • The earliest source node has a determined location distribution.
  • An alternative proof is given for the first-moment result on the number of descendants of n.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • This urn linkage suggests that computational simulation of ancestry could approximate descendant structures for large n.
  • Similar ancestry tracking might apply to other recursive random structures like trees or preferential attachment graphs.
  • The integral expressions could be simplified or numerically evaluated for specific d values to yield explicit constants.

Load-bearing premise

The ancestor process evolves precisely as the multi-draw Pólya urn model.

What would settle it

Numerical simulation for moderate n and d comparing the empirical distribution of joint descendant sizes against the predicted integral expressions.

read the original abstract

We consider a random recursive DAG $G_n$ on the vertex set $[n]$ where every vertex $i\geq 2$ has out-degree $d$, with the targets chosen uniformly at random among the earlier $i-1$ vertices. For this model, we propose a novel way to investigate the descendants of $n$ (which have recently been studied in a paper by Janson) through what we call ancestry processes. The ancestor process $a_i(n)$ of a vertex $i$ is defined as the number of ancestors of $i$ in $G_n$, and is closely related to the evolutions of multi-draw P\'olya urns. Results on the descendants can then be obtained via asymptotic results on functionals of the ancestry processes, generally leading to technical integral expressions. This method yields the answer to two questions posed by Janson, the first on the size of the joint descendants of vertices $n$ and $n+1$, and the other on the location of the earliest non-descendant. We further prove limit theorems for the ancestry processes $a_i(n)$ depending on $i$, determine the location of the earliest source node, and provide an alternative proof of a first-moment result contained in Janson's work.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper studies random recursive d-DAGs on [n] with out-degree d, introduces ancestry processes a_i(n) linked exactly to multi-draw Pólya urns via time-reversal, and transfers urn asymptotics (beta-integral representations and dominated convergence) to obtain explicit results on descendant counts. It resolves two questions of Janson on the joint descendant size of n and n+1 and the earliest non-descendant location, proves limit theorems for a_i(n), locates the earliest source, and gives an alternative proof of Janson's first-moment result.

Significance. If the exact finite-n equivalence and passage to the limit hold, the work supplies a systematic urn-based method for descendant functionals in recursive DAGs, yielding technical integral expressions that directly answer open questions. The explicit connection to beta integrals and standard convergence arguments constitute a clear technical advance over direct combinatorial approaches.

minor comments (2)
  1. The abstract states that results 'generally leading to technical integral expressions'; the manuscript should include at least one fully worked example of such an integral (with the beta density and the functional) to illustrate the method.
  2. Notation for the ancestry process a_i(n) is introduced in the abstract but the precise recursive definition and the exact mapping to the urn composition vector should be stated in a dedicated preliminary section before the asymptotic arguments.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript on ancestry processes in random d-DAGs, the recognition of the Pólya urn connection, and the recommendation to accept. No major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity; external urn equivalence supplies independent structure

full rationale

The derivation defines ancestry counts a_i(n) directly from the random recursive DAG and invokes their exact equivalence to multi-draw Pólya urn composition vectors, a relation that rests on the standard embedding of recursive trees/DAGs into urn models rather than on any fitted parameter or self-citation. Asymptotics for descendant functionals are obtained by passing limits inside beta-integral representations already known for the urns; the passage is justified by dominated convergence once moments are controlled, without re-using the target quantities. The alternative proof of Janson's first-moment result is likewise obtained from the same urn representation and does not reduce to a renaming or self-referential fit. No load-bearing step collapses to a definition or to a prior result by the same author.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

Only the abstract is available, so the ledger is necessarily incomplete. The central modeling choice and the urn connection are the main unverified inputs.

axioms (1)
  • domain assumption The ancestor process a_i(n) is closely related to the evolutions of multi-draw Pólya urns
    Explicitly invoked in the abstract as the route to asymptotic results on functionals of the ancestry processes.
invented entities (1)
  • ancestry process a_i(n) no independent evidence
    purpose: Number of ancestors of vertex i in G_n, used to study descendants via urn asymptotics
    Newly defined object proposed in the paper; no independent evidence supplied in abstract.

pith-pipeline@v0.9.1-grok · 5744 in / 1346 out tokens · 39320 ms · 2026-06-30T04:47:28.145672+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

20 extracted references · 2 canonical work pages

  1. [1]

    Arya, M.J

    S. Arya, M.J. Golin, and K. Mehlhorn. On the expected depth of random circuits.Combinatorics, Probability, and Computing, 8(3):209–227, 1999

    1999

  2. [2]

    Björklund, C

    J. Björklund, C. Holmgren, S. Janson, and T.Y.Y. Lo. Approximation of subgraph counts in the uniform attachment model.Combinatorics, Probability, and Computing, 34(1):90–114, 2025

    2025

  3. [3]

    N.BroutinandO.Fawzi.Longestpathdistanceinrandomcircuits.Combinatorics, Probability, and Computing, 21(6):856–881, 2012

    2012

  4. [4]

    Devroye and S

    L. Devroye and S. Janson. Long and short paths in uniform random recursive dags.Arkiv för Matematik, 49:61–77, 2011

    2011

  5. [5]

    Devroye and J

    L. Devroye and J. Lu. The strong convergence of maximal degrees in uniform random recursive trees and dags.Random Structures and Algorithms, 7(1):1–14, 1995

    1995

  6. [6]

    Drmota.Random Trees

    M. Drmota.Random Trees. Springer, 2009

    2009

  7. [7]

    S. Janson. The number of descendants in a random directed acyclic graph.Random Structures and Algorithms, 64(3):768–803, 2023

    2023

  8. [8]

    Janson and T.Y.Y

    S. Janson and T.Y.Y. Lo. The number of descendants in a preferential attachment graph. arxiv:2412.13975, 2024

    work page arXiv 2024

  9. [9]

    Janson, T

    S. Janson, T. Łuczak, and A. Ruciński.Random Graphs. John Wiley & Sons, 2000. 20 F. BURGHART

    2000

  10. [10]

    Kallenberg.Foundations of Modern Probability

    O. Kallenberg.Foundations of Modern Probability. Springer, 2nd edition, 2002

    2002

  11. [11]

    Knuth.The Art of Computer Programming

    D.E. Knuth.The Art of Computer Programming. Section 7.2.2.3 (Preliminary draft), 2024

    2024

  12. [12]

    Kuba and H.M

    M. Kuba and H.M. Mahmoud. Two-color balanced affine urn models with multiple drawings.Advances in Applied Mathematics, 90:1–26, 2017

    2017

  13. [13]

    Kuba and H

    M. Kuba and H. Sulzbach. On martingale tail sums in affine two-color urn models with multiple drawings. Journal of Applied Probability, 54(1):96–117, 2017

    2017

  14. [14]

    Kuba and S

    M. Kuba and S. Wagner. On the distribution of depths in increasing trees.Electronic Journal of Combinatorics, 17:R137, 2010

    2010

  15. [15]

    Lasmar, C

    N. Lasmar, C. Mailler, and O. Selmi. Multiple drawing multi-colour urns by stochastic approximation.Journal of Applied Probability, 55(1):254–281, 2018

    2018

  16. [16]

    Mahmoud and T

    H. Mahmoud and T. Tsukiji. On the internal structure of random recursive circuits.Journal of Computational and Applied Mathematics, 142(1):155–171, 2002

    2002

  17. [17]

    Mailler and R

    C. Mailler and R. Steiner. Multi-drawing Pólya urns via labelled random DAGs. arxiv:2508.20592, 2025

    work page arXiv 2025

  18. [18]

    Moler, F

    J.A. Moler, F. Plo, M. San Miguel, and H. Urmeneta. Asymptotics in random recursive circuits.Journal of Mathematical Sciences, 196:70–74, 2014

    2014

  19. [19]

    Tsukiji and H

    T. Tsukiji and H. Mahmoud. A limit law for outputs in random recursive circuits.Algorithmica, 31(2):403–412, 2001

    2001

  20. [20]

    Tsukiji and F

    T. Tsukiji and F. Xhafa. On the depth of randomly generated circuits. InAlgorithms – ESA ’96, volume 1136 ofLecture Notes in Computer Science, pages 208–220. Springer, 1996. Institute for Discrete Mathematics, TU Graz, 8010 Graz, Austria Email address:fabian.burghart@tugraz.at

    1996