Asymptotic normality for general subtree counts in conditioned Galton--Watson trees

Each language version is independently generated for its own context, not a direct translation.

这篇论文探讨了一个关于随机树（Random Trees）的有趣数学问题。为了让你轻松理解，我们可以把这篇论文的内容想象成在研究“森林里的树木生长规律”。

1. 故事背景：什么是“随机树”？

想象你有一片神奇的森林，这里的每一棵树（我们叫它 $T_n$ ）都是由一种特殊的规则长出来的。

生长规则（Galton-Watson 过程）： 每一棵树都有一个“种子”（根），这个种子会生出一些树枝（子节点），每个树枝又会继续生出新的树枝，直到它们决定停止生长。
临界状态（Critical）： 这篇论文研究的是一种特殊的树，它们的平均生长速度刚好是“不增不减”的（平均每个节点生出 1 个后代）。这种树既不会无限疯长，也不会立刻灭绝，而是像一片茂密的森林，大小各不相同。
条件限制（Conditioned）： 我们只观察那些恰好有 $n$ 个节点（叶子或树枝的总数）的树。这就好比我们只挑选那些“身高刚好 10 米”的树来研究。

2. 核心问题：数一数“小树苗”

在这篇论文里，作者们想解决一个计数问题：

在一棵巨大的、有 $n$ 个节点的随机树中，某种特定形状的小树（比如一个“丫”字形，或者一个“三叉戟”形）会出现多少次？

他们把这个计数叫做 $N_t(T_n)$ 。

普通计数（Fringe-subtree）： 以前大家主要研究“挂在树梢末端”的小树（就像树叶）。
广义计数（General subtree）： 这篇论文研究的是任何位置的小树。只要大树的某个部分长得像那个小形状，就算一次。这就像在森林里找特定的“树洞”或“分叉”，不管它长在树顶还是树腰。

3. 主要发现：大数定律与“正态分布”

作者们发现了一个惊人的规律，可以用一个**“人群身高”**的比喻来解释：

平均身高（均值）： 如果你种了无数棵 $n$ 个节点的树，算出每棵树里那个“小形状”出现的次数，你会发现这个次数和树的总大小 $n$ 是成正比的。树越大，小形状越多。
身高的波动（方差）： 虽然平均数很好算，但每棵树的具体数量会有波动。作者证明了，当树变得非常大（ $n \to \infty$ ）时，这些波动的分布会呈现出一种非常完美的形状——钟形曲线（正态分布/高斯分布）。

通俗地说：
如果你画一个图表，横轴是“小形状出现的次数”，纵轴是“有多少棵树是这个次数”，你会得到一座完美的钟形山。这意味着，虽然每棵树都不一样，但它们的统计规律是高度可预测的。

4. 关键条件：树木的“脾气”（矩条件）

这是论文最精彩的部分。作者发现，要让这个“钟形曲线”完美出现，树木的生长规则（也就是那个“种子生几个后代”的概率分布 $\xi$ ）必须满足一个**“脾气温和”**的条件。

比喻： 想象树木的后代数量。大多数时候，一个节点生 1 或 2 个孩子。但如果偶尔有一个节点生了几百万个孩子（虽然概率极低），这种“极端事件”会破坏整个森林的统计规律。
数学条件： 论文要求这种“极端事件”发生的概率必须衰减得足够快（数学上叫 $E(\xi^{2\Delta+1}) < \infty$ $E (ξ^{2Δ + 1}) < \infty$ ）。
- 如果树木的“脾气”太暴躁（偶尔生出巨量后代），那么“小形状”的数量波动就会失控，不再遵循钟形曲线，甚至可能变得无法预测。
- 作者通过例子证明，如果这个条件不满足，结论就会失效。这就像如果森林里偶尔会长出“哥斯拉”级别的巨树，那么关于普通树木的统计规律就全乱套了。

5. 什么时候规律会失效？（非退化情况）

论文还讨论了什么时候这个规律会“失效”（即方差为 0 或有限，而不是随树变大而变大）。

比喻： 想象一种极其特殊的树，它的结构被锁死了。比如，如果你数的形状是“一条直线”，而在某种特定的树结构里，直线的数量完全由树的总大小决定，没有任何随机性。这时候，无论树多大，直线的数量都是固定的，没有波动，也就没有“钟形曲线”了。
作者证明了，除了这些极其特殊的“死板”情况外，只要树木的生长规则稍微有点随机性，那个完美的钟形曲线就会出现。

6. 总结：这篇论文有什么用？

这篇论文就像是为随机树世界制定了一条**“交通法规”**：

确认了规律： 只要树木的生长规则不是太疯狂（满足矩条件），那么树中任何固定形状的出现次数，在大树中都会遵循正态分布。
解决了猜想： 之前有一位叫 Janson 的数学家猜到了这个结论，但这篇论文给出了严格的证明，并且指出了这个结论成立的边界条件（即那个“脾气温和”的要求）。
警示作用： 它告诉我们，如果树木的生长规则太“极端”（方差太大），那么任何基于平均值的预测都会失效。

一句话概括：
这篇论文证明了，只要树木的生长规则不过分“狂野”，在大森林里寻找特定形状的小树，其数量分布就像抛硬币一样，最终会呈现出完美的钟形曲线，这是自然界中一种美妙的统计秩序。

Each language version is independently generated for its own context, not a direct translation.

1. 研究问题 (Problem)

本文研究的是临界 Galton-Watson 树（Critical Galton-Watson trees）中，固定根有序树 $t$ 作为一般子树（general subtree）出现的次数 $N_t(T_n)$ 的渐近分布性质。

背景设定：
- $T$ 是一个具有后代分布 $\xi$ 的 Galton-Watson 树，满足 $E(\xi)=1$ （临界条件）。
- $T_n$ 是 $T$ 在节点总数恰好为 $n$ 条件下的条件分布（Conditioned Galton-Watson tree）。
- 一般子树定义： $t$ 是 $T$ 的一般子树，如果存在从 $t$ 到 $T$ 的嵌入，使得 $t$ 的根映射到 $T$ 中某个节点，且该节点在 $T$ 中的度数大于等于 $t$ 中对应节点的度数（即允许 $T$ 中有额外的分支）。这与“边缘子树”（fringe subtree，要求完全匹配）不同。
核心问题：
- 当 $n \to \infty$ 时，随机变量 $N_t(T_n)$ 是否服从渐近正态分布？
- 其均值和方差是否随 $n$ 线性增长？
- 在什么矩条件（moment condition）下该结论成立？
- 是否存在退化的特殊情况（即方差有界或为 0）？

2. 方法论 (Methodology)

作者采用了一套结合截断论证（truncation argument）、方差估计和加性泛函理论的方法。

加性泛函分解：
- 利用 $N_t(T)$ 的加性性质： $N_t(T) = \sum N_t(T_k) + n_t(T)$ ，其中 $n_t(T)$ 是附着在根上的 $t$ 的出现次数（toll function）。
- 将 $N_t(T_n)$ 分解为中心化的加性泛函和仅依赖于树大小的部分。
截断技术 (Truncation Argument)：
- 这是证明中心极限定理（CLT）的核心。作者定义了一个截断版本的加性泛函 $F_{p,q}$ ，仅考虑大小在 $[p, q)$ 范围内的子树。
- 利用 Lemma 7（基于 $L^2$ 收敛的经典概率论结果），通过证明截断部分收敛到正态分布，且剩余部分的方差随截断参数 $p \to \infty$ 而趋于 0，从而推导原变量的渐近正态性。
矩条件与引理构建：
- 引入**大小偏置树（Size-biased tree, Kesten tree, $\hat{T}$ ）**作为分析工具。
- 建立了一系列引理（Lemma 2-6），在假设 $E(\xi^{2\Delta+1}) < \infty$ $E (ξ^{2Δ + 1}) < \infty$ 的条件下，证明了：
  - 条件期望的有界性。
  - 截断误差的阶数（ $O(n^{-1/2})$ ）。
  - 方差的上界估计（线性增长 $O(n)$ ）。
  - 截断后剩余项的协方差控制。
退化性分析：
- 通过构造特定的树对 $\tau_1, \tau_2$ 来证明方差非退化（ $\gamma > 0$ ）。
- 利用反证法分析 $\gamma=0$ 的情况，导出了 $N_t(T)$ 必须具有特定线性形式的结论。

3. 主要贡献与结果 (Key Contributions & Results)

A. 渐近正态性定理 (Theorem 1)

在后代分布 $\xi$ 满足矩条件 $E(\xi^{2\Delta(t)+1}) < \infty$ 的情况下（其中 $\Delta(t)$ 是 $t$ 的最大出度）：

均值与方差：
$E(N_t(T_n)) = \mu n + o(\sqrt{n})$
$\text{Var}(N_t(T_n)) = \gamma^2 n + o(n)$
其中 $\mu = E(n_t(\hat{T}))$ ， $\gamma \ge 0$ 为常数。
中心极限定理：
如果 $\limsup_{n \to \infty} \text{Var}(N_t(T_n)) = \infty$ （即 $\gamma \neq 0$ ），则：
$\frac{N_t(T_n) - \mu n}{\gamma \sqrt{n}} \xrightarrow{d} N(0, 1)$

B. 非退化性条件 (Non-degeneracy)

命题 8：给出了 $\gamma > 0$ 的充分条件（Assumption 1）。只要存在两棵大小相同、高度为 $M-1$ 的前缀相同的树 $\tau_1, \tau_2$ ，且它们作为 $T_n$ 的子树时 $N_t$ 的计数不同，则方差线性增长，分布非退化。
命题 9 与推论 10：如果 $\gamma = 0$ ，则 $N_t(T)$ 必须可以表示为树大小 $|T|$ 的函数加上边缘子树计数的线性组合。此时方差有界（ $O(1)$ ），不满足中心极限定理。

C. 矩条件的最优性探讨 (Section 5)

作者通过两个反例表明，矩条件 $E(\xi^{2\Delta+1}) < \infty$ $E (ξ^{2Δ + 1}) < \infty$ 几乎是必要的：
- 例 11（路径）：若 $t$ 是长度为 2 的路径（ $\Delta=1$ ），且 $E(\xi^3)=\infty$ 但 $E(\xi^{3-\epsilon})<\infty$ ，则方差 $\text{Var}(N_t(T_n))$ 的增长速度超过线性（superlinear），导致分布非高斯。
- 例 12（星形树）：若 $t$ 是星形树（ $\Delta \ge 3$ ），且 $E(\xi^{2\Delta}) = \infty$ ，则方差同样呈现超线性增长，破坏了 CLT 的结论。

4. 意义与影响 (Significance)

验证了 Janson 的猜想：
本文证实了 Janson 在 [9] 中提出的猜想：在适当的矩条件下，条件 Galton-Watson 树中一般子树的计数服从非退化的中心极限定理。此前该结论仅在 $\xi$ 有界（bounded）的情况下被证明。
推广了现有理论：
将结果从“边缘子树”（fringe subtrees）推广到了更广泛的“一般子树”（general subtrees，即允许度数松弛的嵌入）。这涵盖了更多类型的树模式匹配问题。
明确了矩条件的边界：
论文不仅给出了充分条件 $E(\xi^{2\Delta+1}) < \infty$ ，还通过构造反例表明该条件在指数上非常接近最优（optimal）。如果矩条件不满足，方差可能不再线性增长，从而破坏正态性。这为理解随机树统计量的稳定性提供了深刻的理论边界。
方法论的通用性：
文中使用的截断论证结合大小偏置树（Kesten tree）的分析技巧，为处理随机树上的加性泛函（additive functionals）提供了新的技术路径，特别是针对那些不满足传统局部性条件（locality condition）的泛函。

总结

该论文在随机图论和概率论领域做出了重要贡献，严格证明了在临界 Galton-Watson 树中，一般子树计数的渐近正态性，并精确刻画了保证该性质成立的矩条件边界以及方差退化的特殊情况。这不仅完善了 Janson 等人的理论框架，也为后续研究复杂树结构中的模式计数问题奠定了坚实基础。