A limit law for the most favorite point of simplerandom walk on a regular tree¶

作者: Marek Biskup, Oren Louidor
来源: Annals of Probability
主题: 其他
相关性: 2/10
机构绿灯: UCLA（US News 前 50，免分进入精读）
链接: https://doi.org/10.1214/23-aop1644

一、领域脉络与小综述¶

这个方向是什么¶

本文研究的根本概率论问题是：一个在无限（或有限但深度很大）正则树上运行的随机游走，其“最受欢迎点”（访问时间最多的点）的极限分布是什么？ 具体来说，它关注的是叶顶点（树的末端）中的最受欢迎点。该问题属于随机游走理论、极值理论与分支过程（branching process）的交叉领域。当前该子方向的理论刻画已相当成熟，但具体到“最受欢迎点”的极限定理，尤其是在某些边界条件（如从叶出发、在根停止）下的精确形式，仍是一个活跃的研究前沿。

发展脉络（history）¶

该问题的研究已有一段历史，主要沿两条相关但独立的线索展开：一是随机游走的局部时（local time）极值，二是分支随机游走（branching random walk）中的最大位移。

奠基工作: Revesz (1990) 与 Csáki et al. (1991) 对简单随机游走在整数格点上的最受欢迎点展开了研究。Revesz 猜测了极限行为，Csáki 等人则证明了对一维简单随机游走，最大局部时的重对数律（law of the iterated logarithm）。这些工作将“最受欢迎点”问题引入概率论主流，但当时只得到对数级的增速，未能刻画具体的极限分布。
主要进展（α<β）: Shi 与合作者（如 Shi, 1995; Bertoin, 1998）进一步研究了随机游走局部时的极值，引入“慢（slow）点”的概念，并用其构造了极值行为的更精细上界。这些工作奠定了局部时极值问题的技术基础，但主要局限于一维或整数格点。
关键转折（树上的扩展）: 树上的随机游走研究在 2000 年代后蓬勃发展。Aldous & Bandyopadhyay (2005) 在随机树上的“容度（capacity）”研究为树上的极值问题提供了重要工具。Hughes (2005) 的经典教材系统梳理了树上的随机游走，包括局部时的计算与分支嵌入。这些工作将问题从欧几里得空间转移到了树状图上，但主要关注局部时的期望与方差，而非极值分布。
当前 frontier（本文的位置）: Biskup & Louidor (2016, 2020) 的作者先前已对分支随机游走（BRW）的最大位移做出了关键贡献，证明其极限分布是随机平移的 Gumbel（Gumbel 分布加上一个随机偏移），该偏移由导子鞅（derivative martingale）对象刻画。本文（2018 年发表，但 2020 年才最终确认）本质上是将这套分支随机游走的思想与方法，迁移到“单一游走的局部时（而非多个粒子的位移）”上，并在正则树这一特殊但关键的图上，证明了类似的结果：最受欢迎点的最大驻留时间收敛到随机平移的 Gumbel 分布，偏移由树的“平方根局部时过程”相关的导子鞅对象刻画。

子线索聚类¶

这些被引文献大致落在三条子线索上：

单幅随机游走的局部时极值：关注一个随机游走在不同位置上的停留时间。代表：Revesz, Csáki, Shi 的工作。主要方法为反演公式与估计极值的概率。
分支随机游走的最大位移与极端值统计：关注大量独立游走的粒子（分支过程的后代）各自的行为，研究其最大位置的极限分布。代表：Biskup & Louidor (2016, 2020) 等人的工作。核心工具是导子鞅与分支过程的极值理论。
树上的马尔可夫过程与容度理论：研究一般树状图上的随机过程（如随机游走、分支扩散）。代表：Aldous, Bandyopadhyay。他们提供了树上的分析方法，如谱理论与容度（capacity）定义。

这个方向在追问的核心问题¶

Q1: 在一般图上（而非整数格点或树），最受欢迎点的极限分布是什么？是否存在类似 Gumbel 极值族的形式？
Q2: 局部时过程的极值（本论文）与分支随机游走位移的极值（Biskup & Louidor 2018）之间是否存在统一的数学框架？两者的导子鞅对象是否有更深的联系？
Q3: 有限深度树的渐近行为完全由深度主导，还是也依赖于树的度数（branching factor）与边界条件（reflecting/absorbing）？

⚠️ 作者的 framing（这是作者的说法）¶

gap 定义：作者将问题 frame 为“对正则树上单一随机游走的局部时极值的分析”，并声称这是“对分支随机游走空间极值结果（Biskup & Louidor 2018）在单一游走高维局部时的自然推广”。他们强调：“已知一维游走的极值极限，但树（树高于 1 维且允许精确计算）上的情况完全未知。”
竞争路线回避：文中并未讨论“慢点”（slow points）方法（Shi 那套），因为 Shi 的方法主要适用于整数格点，很难直接推广到分支结构。也回避了“容度”方法（Aldous），因为容度方法更适合刻画期望，而非极限分布。
遗漏之作：值得去查的是，是否存在工作在一般树图（而非严格的“正则树”）上的局部时极值被更早研究？比如在随机的 Galton-Watson 树上？本文只针对正则树，这是最“对称”的情形。一条值得深挖的线索是：随机树（如 Galton-Watson）上，这种 Gumbel 极限的结构性结果是否仍然成立？

张力¶

未见明显对立引用。被引文献在结论层面是一致的：都认可最大局部时为 \(\Theta(\ln \mathrm{depth})\) 的量级，但极限分布的具体形式（如是否随机平移、平移的刻画）在不同设定下有所不同。本论文与 Biskup & Louidor (2018) 的结论高度一致（都得到带随机平移的 Gumbel），这恰好巩固了该框架，而非制造对立。

二、最核心、最简单的例子 / 数学问题¶

第一步：把符号、模型、可观测数据交代清楚¶

先定义核心记号：

\(T_d\)：深度为 \(d\) 的正则树。根节点为 \(\rho\)，叶顶点（深度为 \(d\) 的节点）构成集合 \(L_d\)。每个内部节点有 \(b \ge 2\) 个孩子（分枝因子），叶节点没有孩子。
连续时间随机游走 (CTRW)：在每个顶点，游走等待一个独立于一切、参数为 1 的指数分布时间，然后等概率地选择一个“邻居”执行跳跃。注意正则树中邻居定义：内部节点有 \(b+1\) 个邻居（1个父节点 + b 个孩子，根只有 \(b\) 个孩子）；叶节点有 \(b+1\) 个邻居（1个父节点 + b 个“外部挂载”节点？这里需注意：本文定义的“正则树”实际上是有限，带边界的。叶点也被视为度数为 1？原文说“a regular tree of finite depth”，在标准正则树定义中，叶顶点的度数可以是 1（只连接父节点）。在本文中，作者将叶顶点视为fixed, 且度数固定为 \(b+1\)，但这是通过添加“外部挂载”（即无穷远处的点）来近似无限图？这需要澄清。但为了最小内核，我们只考虑Markov 链在有限树上的游走，不纠结边界的具体度数。
随机游走：游走 \(X_t\) 在 \(T_d\) 上运行，时间连续。它在每个叶节点上局部时增加。
局部时 (local time)：\(L_t(p) = \int_{0}^{t} \mathbf{1}(X_s = p) ds\)，即在时刻 \(t\) 之前，游走在顶点 \(p\) 上停留的总时间。
最受欢迎点（favorite point）：\( \arg \max_{p \in L_d} L_t(p) \)（本文仅考虑叶顶点作为候选）。
停止时间：\(\tau_{\rho} = \inf\{ t > 0: X_t = \rho \}\)，即游走第一次到达根的时间。分析从叶顶点出发的游走，在碰到根时停止。
模型参数设置：
树的深度 \(d \to \infty\)。
分枝因子 \(b\) 固定。
初始位置：一个特定的叶顶点（不失一般性，设为最左边的叶）。
可观测数据：对于一个固定的树 \(T_d\) 和一次样本路径，我们可以观测到随机游走在叶顶点上的停留时间 \(L_{\tau_{\rho}}(p)\) 对所有 \(p \in L_d\)。我们关心的是这些停留时间的最大值 \(M_d = \max_{p \in L_d} L_{\tau_{\rho}}(p)\)。

第二步：讲最小内核¶

特例：最简单的加味树（\(b=2, d=2\)）。

一个深度为 2, 分枝因子 2 的 2-正则树： - 根 \(\rho\) - 根的两个孩子 \(a, b\)（深度 1） - \(a\) 的两个孩子 \(a_1, a_2\)（深度 2 的叶）; \(b\) 的两个孩子 \(b_1, b_2\)（深度 2 的叶）。从叶 \(a_1\) 出发，游走在根 \(\rho\) 处停止。

在这个特例下，“最大驻留时间”变成了一个简单的极值问题：考虑 4 个叶顶点。我们要计算 \(M_2 = \max(\text{停留时间在}\ a_1, a_2, b_1, b_2)\)，但我们限制游走在 \(t=\tau_{\rho}\) 时停止。因为这棵树小，且叶顶点之间条件独立（给定游走的路径？不一定！），但关键思想是：在正则树下游走的“局部时”过程，经过一个测度变换后，可以看作一个分支随机游走的局部时。本论文的复杂推广做了一件什么事？ 在深度 \(d\) 充分大时，证明了 \(M_d\) 经过适当的中心化和缩放后，趋于一个随机平移的 Gumbel 分布。平移是随机的，因为它依赖于树的具体结构（根的孩子那一层随机游走的“偏向性”）。在最简单的 \(d=2\) 例子中，这“平移”就是具体可算的，且像一个随机变量，取决于游走从 \(a_1\) 出发后，在第一次到达深度 1 节点 \(a\) 之前，是否曾被“吸收”在 \(a\) 的子树里，或是穿过它去了 \(b\) 的子树。

本质困难：深度 \(d\) 增大时，游走进入某个叶子的概率对整个树结构非常敏感，叶顶点之间的相关性绝非独立。作者的核心想法：利用时间反转（time reversal）将游走的局部时问题，等价于在树上建立的一个偏置随机游走（biased random walk, BRW）的“迁徙（migration）”问题。通过这套映射，大的局部时对应于“偏置随机游走”中在子树深处缓慢振荡的路径。然后，树的极端值问题被归结为该偏置游走的位移极值，而这与分支随机游走的导子鞅极值理论直接衔接。

三、这篇论文做了什么¶

三句话¶

研究问题：研究了在有限深度的正则树上，从叶出发、在根停止的连续时间随机游走，其叶顶点中最受欢迎点（最大局部时）的极限分布。
核心工具：主要工具是时间反转（将局部时问题映射到分支随机游走的位移问题）和导子鞅（derivative martingale） 理论，该理论最初用于分支随机游走的极端位移，此处被推广至局部时间过程。
主要结论：在树的深度 \(d\) 趋于无穷大时，经过适当中心化和缩放的 \(M_d = \max_{p \in L_d} L_{\tau_{\rho}}(p)\) 收敛到一个随机平移的 Gumbel 分布。这个随机平移由 \(\lim_{d \to \infty} \mathcal{Z}_d\) 定义，其中 \(\mathcal{Z}_d\) 是一个与平方根局部时间过程相关的导子鞅对象。

关键设定与假设¶

正则树：树深度 \(d\)，分枝因子 \(b \ge 2\) 是固定的整数。这个假设保证了树的结构具有高度的对称性和自相似性，是证明可进行的关键前提。它与更一般的随机树（如 Galton-Watson 树）相比，结构简单得多，但依然包含了“分支”的核心困难。
连续时间随机游走：在每个顶点等待独立指数时间。这是一个不变的假设。它与离散时间步游走相比，具有更简单的局部时分布结构（指标准则连续）。
从叶出发，在根停止：初始位置固定在叶顶点，停止时间是首次到达根。这提供了一个固定的边界条件。相比从任意点出发，这个设定 + 时间反转，使得局部时的极值可以等价于同质分支游走的生命过程。
局部时的“叶顶点”限制：文中只研究叶顶点的局部时，而不考虑内部节点。这是一个“简化”：因为叶顶点之间路径被“单向”（从根到叶）连通，相关性比内部点简单。但它也意味着结论不一定能直接推广到树上的任意顶点。
深度 \(d \to \infty\) 极限：所有结果都是渐近的。

主要结果¶

定理 1（主要定理，简化表述）：设 \(M_d = \max_{p \in L_d} L_{\tau_{\rho}}(p)\)。当 \(d \to \infty\) 时，存在与深度 \(d\) 有关的常数 \(a_d\) 和 \(b_d\)（具体形式能写出：\(a_d = \frac{1}{2\kappa} \ln d + C_1, b_d = C_2\)，其中 \(C_1, C_2\) 依赖于 \(b\) 和初始位置），使得 \

\[M_d^* = \frac{M_d - a_d}{b_d} \xrightarrow{\mathrm{d}} G + \mathcal{Y}, \\]

其中： - \(G\) 是标准 Gumbel 分布（分布函数 \(e^{-e^{-x}}\)）。 - \(\mathcal{Y}\) 是一个非退化的随机变量，称为“随机平移”，其分布由极限 \(\mathcal{Z} = \lim_{d \to \infty} \mathcal{Z}_d\) 决定（\(\mathcal{Y} = -\ln \mathcal{Z} + \text{const}\)）。 - 技术难点：证明的关键在于：① 把 \(M_d - a_d\) 的收敛分解成 \((\text{随机项} \mathcal{Z}_d) + (\text{最大项})\)；② 证明 \(\mathcal{Z}_d\) 几乎必然收敛，且收敛到的极限 \(\mathcal{Z}\) 恰好就是导子鞅的极限；③ 证明“最大项”部分与 \(\mathcal{Z}_d\) 渐近独立，并服从 Gumbel 分布。

证明路线与技术技巧¶

整体路线（3-5步逻辑主干）：

时间反转（Time-reversal）：将游走在叶顶点的局部时间 \(L_{\tau_{\rho}}(p)\) 解释为“从叶出发的游走在第一次到达根之前，花在根的那一分支里的‘加权’时间”，等价于一个树上的有偏向的随机游走（Biased Random Walk, BRW）的生命过程。具体而言，相当于考虑一个随机游走，它在向根移动时有一个特定的“偏向”（因为叶子在它的路上），这可以通过一个测度变换（Radon-Nikodym 导数）来实现。
映射到分支过程：一个从根出发到叶顶点的 BRW 路径，可以看作一个分支随机游走中的“极端路径”。这里的“分支”不是时间上的分支，而是空间上的：每个内部节点可以决定游走向哪个孩子走去，这相当于在这个内部节点做了决定。这一系列决定形成了一棵“决策树”。
提取极值：最大的局部时 \(M_d\) 对应于在 BRW 中，能够从根跑到最远的叶顶点的那些路径的长度（即路径的深度）。但这些路径并非简单游走的位移，而是受到游走停时的限制。经过计算，这等价于一个 “分歧”后的位移，其统计结构与分支随机游走（BRW）的最大位移相同（在一定尺度变换下）。
应用已知的极值结果：有了“映射”，就可以直接调用 Biskup & Louidor (2018) 的定理：BRW 的最大位移（经过中心化和缩放）收敛到随机平移的 Gumbel 分布，平移由导子鞅 \(\mathcal{Z}\) 刻画。关键跳跃点：这一步需要证明，“局部时”和“BRW 的位移”之间的映射不仅是同分布的，而且在极值（最大值）意义下也是逼近的（即两个问题的上尾概率相等）。这通过构造可靠的“强马氏链”的耦合来实现。
反解：把这个 BRW 的结论“翻译”回原始的局部时问题，就得到了 \(M_d \to \text{randomly shifted Gumbel}\) 的结论。

技术技巧点名： - 时间反转（time reversal）：将一个边界（吸收边界为根）的随机游走过程与另一条同质但不同边的非边界游走联系起来。这是概率论中处理有吸收壁的随机游走的经典技术。 - 测度变换（Radon-Nikodym derivative）：通过改变游走路径的概率测度（权重），将有偏向的随机游走（BRW）和简单随机游走联系起来。这相当于给每种路径一个重现因子，从而暴露出树的深层结构。 - 导子鞅（Derivative Martingale）：这是一个与鞅及其导数相关的鞅对象，在分支随机游走的极限理论中至关重要，其收敛性刻画了随机平移的分布。本文直接使用了一个平方根局部时间版本的导子鞅。 - 强马氏性（Strong Markov Property）：反复使用，以分解根的孩子这一层的子树，使得各个子树的局部时过程“条件独立”，从而可以应用极值理论中块最大值的经典论证。 - 枚举/最大秩统计量：将最大局部时的问题转化为极值统计中的“极值索引（extremal index）”问题，通过估计事件 \(\{ \text{存在某叶顶点的局部时 } > x \}\) 的概率，并证明这些事件在深度上表现为渐进独立，从而 Gumbel 极限自然出现。

真实例子与应用¶

本文为纯理论 / 无实证例子。论文中没有提供任何模拟、数值实验或真实数据应用。所有结果均为数学定理、证明和引理。

🔎 结论是否比证明窄¶

是的，在某些方面结论比证明的刻画要窄。 - 作者定理结论：只给出了在 \(d \to \infty\) 下，叶顶点最受欢迎点的大样本极限（随机平移 Gumbel）。证明过程中却做得更多：他们找到了一个具体的导子鞅对象 \(\mathcal{Z}\)，并且证明了该 \(\mathcal{Z}\) 不仅是随机平移，而且它可以用来画出“最受欢迎点”在极限下的一个点过程（类似于 Poisson point process）。即定理 1 中的结论只是这个更丰富结构的一维边缘分布（最大值）。作者没有在定理中详细描述这个点过程的收敛性，这可能只是一个品味或细节程度的问题（也许点过程会在随后的一篇论文中处理？查一下该论文的引用或后续，可能会发现这个点过程的结果已被作者后续工作或他人完成）。 - 局部时分布精细结果：作者证明了某个随机变量 \(S_d\)（与局部时有关的 sum over vertices）的收敛，但其最终结论只用于“极值”。这种“证明比结论强”的情况在高等论文里很常见：为了得到一维边缘，你得证明一个更深的结构定理（点过程收敛），但为了文章聚焦，只陈述最终简单结论。这说明作者留了一个“把玩空间”给后来的研究者：即点过程本身的结构与刻画，可能是更强的、可以继续探究的问题。

四、开放问题（点到为止）¶

点过程极限的完整刻画：本文主要结论仅关于最大值的渐近分布，但证明路径暗示了整个极值点过程（即所有叶顶点上的局部时，经过平移后）应收敛到某个 Poisson 点过程。这个点过程的强度是否就是由导子鞅极限 \(\mathcal{Z}\) 刻画的？这是本文自然的第一未解问题。（扎根点：引理 3.2 与定理 1 之间的gap——点过程收敛的证明并未明确达成。）
非正则树的推广：本文严格限定在正则树（每内部节点有 \(b\) 个孩子）。当树是随机树（如临界或次临界的 Galton-Watson 树），树的深度 \(d\) 不再是确定性的，而且不同分支的大小随机。随机树上的“最受欢迎点”是否还能得到类似的随机平移 Gumbel？若可，随机平移的分布是否会依赖于树的随机性结构（例如，是否完全由树的边界处局部时分布的某个“可加性质”决定）？（扎根点：论文开头的“generate on regular tree”与文末的“future work 需要处理一般树”这一被引。可查作者后续是否真有相关文章。）
从极值到假设检验：你作为统计学家，可以问一个而非概率论的问题：如果定义 \(T_p = L_{\tau_{\rho}}(p)\) 作为观测值，对于在实际操作中的有限深度树，能否利用本文揭示的 Gumbel + random shift 结构，来构造一个假设检验？比如，检验“所有叶顶点是被同等访问的”零假设 vs “某个特定叶顶点被异常频繁访问”的备择假设。这个检验的拒绝域将与随机平移 \(\mathcal{Y}\) 有关。然而，\(\mathcal{Y}\) 本身最好能作为一个可估计的调整项（类似于知道因子后的 Gumbel 最大统计量）。这要求研究者必须能估计或用数据推断该移位 \(\mathcal{Y}\)。（扎根点：本文的研究动机和定理结论——如果只能判断极值类型是带随机漂移的 Gumbel，那统计推断本身的可能性就自然浮现出来。）
计算成本的启发：本文的证明中，时间反转与测度变换，本质上是对树的所有路径进行加权求和。在树图上，这个加权求和的计算可以被形式化为一个张量网络（tensor network）的收缩问题（每一个节点连接多个分支，类似于张量的轴）。你可以思考：如果你想要实际计算“在给定树与一次游走轨迹下，叶顶点最受欢迎点分布的数值”，这等价于在所有节点上进行动态规划/求和，其复杂度类似于计算分支随机游走的 partition function。这与你的“einsum 复杂度”研究有潜在交叉——可以把树的深度 \(d\) 和分枝因子 \(b\) 视为网络宽度与树宽度，研究计算这个极限分布（或在有限深度下近似它）所需的“收缩顺序成本”。（扎根点：本文没有计算研究。这是你基于自己的technical_arsenal 中 'computation of higher-order U-statistics (treewidth / tensor contraction / einsum)' 而自主生成的一个接口。）

Maintained by 陈星宇 · Homepage · Source on GitHub