Total Path Length in Power-Weight Recursive Trees: Martingale Limits and Global Fluctuations

Source abstract

We study total path length in recursive trees with positive deterministic attachment weights. Writing $W_n=\sum_{i=1}^n w_i$ and $p_n=w_n/W_n$, we obtain exact martingale-innovation identities and a variance recurrence. Under the condition $p_n=O(n^{-1})$, centered total path length divided by $n$ converges almost surely and in $L^2$ to a nondegenerate random variable, and its variance is asymptotic to a positive constant times $n^2$. 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-π^2/6$. For linear weights we evaluate the coefficient as $8-2π^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.