Source-linked AI summary
Gaussian approximation for rooted edges in a random minimal directed spanning tree
Chinmoy Bhattacharjee
TL;DR
For rooted edges in a Poisson MDST, the Gaussian limit in dimensions d ≥ 3 was previously established only for α = 1, while dimension two has a Dickman limit. This paper uses stabilization theory and Stein’s method to prove a Gaussian limit for every α > 0 and provide presumably optimal quantitative bounds.
Problem
In dimensions d ≥ 3, a Gaussian limit for rooted-edge length was known for α = 1, but the general-α case remained unresolved, unlike the Dickman limit established in dimension two.
Source: §1 · p. 2Method
The paper uses stabilization theory and Stein’s method to obtain a quantitative central limit theorem for rooted-edge length in a Poisson MDST.
Source: §1 · p. 2Results
For d ≥ 3 and every α > 0, suitably normalized rooted-edge length has a Gaussian limit with presumably optimal quantitative convergence rates.
Source: §1 · p. 2, §1.2 · p. 4Takeaways & Limitations
The Gaussian limit for rooted-edge length extends across all positive α in dimensions d ≥ 3, with convergence rates described as presumably optimal.
Source: §1 · p. 2The stated results concern Poisson processes; the paper notes that extension to Binomial processes may be possible.
Source: §1.2 · p. 5
Abstract
from arXiv · showhide
We study the total $\alpha$-powered length of the rooted edges in a random minimal directed spanning tree - first introduced in Bhatt and Roy (2004) - on a Poisson process with intensity $s \ge 1$ on the unit cube $[0,1]^d$ for $d \ge 3$. While a Dickman limit was proved in Penrose and Wade (2004) in the case of $d=2$, in dimensions three and higher, Bai, Lee and Penrose (2006) showed a Gaussian central limit theorem when $\alpha=1$, with a rate of convergence of the order $(\log s)^{-(d-2)/4} (\log \log s)^{(d+1)/2}$. In this paper, we extend these results and prove a central limit theorem in any dimension $d \ge 3$ for any $\alpha>0$. Moreover, making use of recent results in Stein's method for region-stabilizing functionals, we provide presumably optimal non-asymptotic bounds of the order $(\log s)^{-(d-2)/2}$ on the Wasserstein and the Kolmogorov distances between the distribution of the total $\alpha$-powered length of rooted edges, suitably normalized, and that of a standard Gaussian random variable.
1. Introduction and main results
The paper studies the α-powered length of rooted edges in a Poisson minimal directed spanning tree (MDST), extending Gaussian-limit results from α = 1 to every α > 0 in dimensions d ≥ 3. It also gives quantitative Gaussian-approximation bounds and develops mean and variance estimates for the statistic.
1. Introduction and main results
- The general-α Gaussian limit fills a gap left by the earlier d ≥ 3 result, which covered only α = 1; in d = 2, the rooted-edge statistic has a Dickman limit.The earlier two-dimensional result applied for α > 0, while the higher-dimensional general-α case remained open.Source: §1 · p. 2, §1.2 · p. 5
- For d ≥ 3 and every α > 0, the suitably normalized rooted-edge length has a Gaussian limit, with presumably optimal quantitative convergence rates.The approach combines stabilization theory and Stein’s method.Source: §1 · p. 2, §1.2 · p. 4
1.2. Model and main results.
- An MDST minimizes total Euclidean edge length among directed graphs connecting every vertex to the origin by a path; rooted edges have one endpoint at the origin.The statistic sums the α-powered lengths of these rooted edges, whose endpoints are the minimal points.Source: §1.2 · pp. 2–3
- For d ≥ 3, the variance of the rooted-edge statistic is exactly of order log^(d−2) s, supporting the claim that the Gaussian-approximation rate is presumably optimal.The paper also establishes the mean’s asymptotic behavior to obtain the variance estimate.Source: §1.2 · pp. 3, 5
- For minimal-point weights formed from powers of k coordinates, the expected sum is of order log^(d−k−1) s for k ∈ [d−1].The paper identifies this weighted-sum estimate as a key ingredient in analyzing the mean and variance.Source: §1.2 · p. 6
2. Bounds for sums of region-stabilizing functionals
The section presents a Gaussian-approximation bound for sums of region-stabilizing functionals, whose local dependence is better captured by a stabilization region than by a ball. The bound applies under score-function assumptions including monotonicity, stabilization, and an L4+p norm condition.
2. Bounds for sums of region-stabilizing functionals
- Region-stabilizing functionals express the statistic as a sum of local scores, and a stabilization region is used because a ball is vastly suboptimal here.The section recalls a bound for these functionals to prove Theorem 1.2.Source: §2 · p. 6
- For a Gaussian approximation result for Hs, the assumptions include (A0) monotonicity, (A1) a stabilization-region map Rs for every s ≥ 1, and an L4+p norm condition.The norm condition posits some p ∈ (0, 1] and applies to measures µ with µ(X) ≤ 7.Source: §2 · pp. 6–7
- The Gaussian-approximation framework represents Hs as a sum of score functions over a Poisson process with intensity measure sQ.The theorem assumes conditions (A0)–(A2).Source: §2 · pp. 6, 8
- Under conditions (A0)–(A2), Theorem 2.1 gives a Gaussian-approximation bound for Hs for all s ≥ 1, with a constant depending only on p.The excerpt states θ := p/(32 + 4p) and identifies the constant's dependence, but does not include the bound's full expression.Source: §2 · p. 8
3. Estimating the mean and variance
This section estimates the mean and variance of the total α-powered rooted-edge length for α > 0, including a leading-order variance estimate and establishing that w(d, α) is finite and positive for d ≥ 2.
3.1. Mean.
- The mean is estimated for any α > 0, with an exact leading-order estimate obtained to support the variance analysis.An auxiliary expectation involving (x1x2)^α is stated to have order log^(d−3) s for d ≥ 3.Source: §3.1 · pp. 8, 11, 13
3.2. Variance.
- The variance estimate gives its leading-order term for any α > 0, extending the α = 1 result of.Source: §3.2 · p. 13
- The variance analysis establishes asymptotic behavior for the auxiliary functions cδ,τ,s and c(k), which are used in deriving the variance estimate.Source: §3.2 · p. 13
- For d ≥ 2 and s > 1, the preceding estimates are collected with (3.16) and (3.15) to obtain the variance result.The displayed bound is not present in the supplied passage.Source: §3.2 · p. 20
- For d ≥ 2, the function w given by (1.2) has a finite supremum over α > 0.Source: §3.2 · p. 20
- The proof of Theorem 1.1(b) follows from (3.25) and Lemma 3.10.Source: §3.2 · p. 21
4. Proof of Theorem 1.2
The proof establishes integral estimates for the rooted-edge functional and verifies the conditions needed to apply the quantitative theorem.
4. Proof of Theorem 1.2
- The proof checks stabilization condition (A0) using preservation of minimal-point status under intermediate configurations, then establishes (A1) and (A2).Source: §4 · p. 22
- For ξ_s, the proof takes p = 1 and uses r_s(x,y) = s|x| when y ≺ x, and infinity otherwise.Source: §4 · p. 22
- Adding a nontrivial α-powered norm to c_{α,δ,τ,s} reduces the integral's order by one logarithmic factor.Source: §4 · p. 22
- Var(L^α_0(P_s)) is bounded below by C1 log^(d-2) s, and Lemmas 4.4–4.6 yield Theorem 1.2.The variance lower bound is stated for all s > 1.Source: §4 · p. 28