Total Path Length in Power-Weight Recursive Trees: Martingale Limits and Global Fluctuations
Abstract
We study total path length in recursive trees with positive deterministic attachment weights. Writing W_n = w_1 + ... + w_n and p_n = w_n/W_n, we obtain exact martingale-innovation identities and a variance recurrence. Under the condition p_n = O(1/n), centered total path length divided by n converges almost surely and in L² to a nondegenerate random variable, and its variance is asymptotic to a positive constant times n². No polynomial asymptotic for W_n is required. For power weights w_i = i^α, the same argument applies to every real α, including the critical and summable regimes beyond the positive-power cumulative-weight assumptions of existing profile theory. The expected average depth is logarithmic for α > -1, iterated logarithmic for α = -1, and bounded for α < -1, while the global fluctuation scale remains linear throughout. In the summable regime we identify the random limit through the weighted depths of the infinite tree. The uniform case recovers the classical variance coefficient 2 - π²/6. For linear weights we evaluate the coefficient as 8 - 2π²/3. Although this tree and a random binary search tree have identical insertion-depth marginals and expected total path length, their asymptotic variance coefficients differ by one. This gives an explicit comparison of global dependence that is invisible in individual depth distributions.
Related
- Fluctuations of additive martingale limits of branching Brownian motion
- Determination of weight enumerators of binary extremal self-dual codes of length 60
- The weight enumerators of irreducible cyclic codes of length 2ℓ
- Gaussian and non-Gaussian limits for the total edge-length of random directional nearest-neighbour graphs
- Limits of Weight-Bounded Redundant Checks for Peeling Decoding of Random Regular LDPC Codes
BibTeX
@misc{galazka2026total,
title = {{Total Path Length in Power-Weight Recursive Trees: Martingale Limits and Global Fluctuations}},
author = {Marek Gałązka and Hanna Wdowicka},
howpublished = {HAL},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2610.00614},
eprint = {2610.00614},
archivePrefix = {arXiv},
url = {https://hal.science/hal-05741587v1},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Total Path Length in Power-Weight Recursive Trees: Martingale Limits and Global Fluctuations
AU - Marek Gałązka
AU - Hanna Wdowicka
PY - 2026
DA - 2026/09/07
PB - HAL
DO - 10.48550/arxiv.2610.00614
UR - https://hal.science/hal-05741587v1
AB - We study total path length in recursive trees with positive deterministic attachment weights. Writing W_n = w_1 + ... + w_n and p_n = w_n/W_n, we obtain exact martingale-innovation identities and a variance recurrence. Under the condition p_n = O(1/n), centered total path length divided by n converges almost surely and in L² to a nondegenerate random variable, and its variance is asymptotic to a positive constant times n². No polynomial asymptotic for W_n is required. For power weights w_i = i^α, the same argument applies to every real α, including the critical and summable regimes beyond the positive-power cumulative-weight assumptions of existing profile theory. The expected average depth is logarithmic for α > -1, iterated logarithmic for α = -1, and bounded for α < -1, while the global fluctuation scale remains linear throughout. In the summable regime we identify the random limit through the weighted depths of the infinite tree. The uniform case recovers the classical variance coefficient 2 - π²/6. For linear weights we evaluate the coefficient as 8 - 2π²/3. Although this tree and a random binary search tree have identical insertion-depth marginals and expected total path length, their asymptotic variance coefficients differ by one. This gives an explicit comparison of global dependence that is invisible in individual depth distributions.
ER -