Large Sample Properties of Higher Order Markov Models¶
作者: Tuhin Majumder, Donald E. K. Martin, Soumendra N. Lahiri
主题: 数理统计 / 假设检验
相关性: 6/10
链接: https://arxiv.org/abs/2608.20321
一、领域脉络与小综述¶
这个方向是什么¶
本文所处的子方向是高阶马尔可夫链(higher-order Markov chains)的渐近理论,其根本的统计问题是:当观测到一条长度为 \(n\) 的有限字母表序列,且当前状态对过去 \(m\) 个状态的依赖(阶数 \(m\))本身随样本量增长(\(m = m_n \to \infty\))时,如何建立加性泛函 \(\sum_{t} g_n(Y_t^{(n)})\) 的中心极限定理(CLT),从而为推断(估计、检验、模型选择)提供渐近基础。这个方向的成熟度属于"经典对象的新设定"——一阶马尔可夫链的 CLT 是教科书内容,但阶数随样本量增长的三角阵列设定,使得状态空间大小 \(|\Sigma|^{m_n}\) 指数膨胀,经典遍历性条件无法直接套用,需要新的技术工具。
发展脉络¶
奠基工作:高阶马尔可夫链的建模与降维。 本文的起点是 Raftery [1985] 提出的混合模型(Mixture Transition Distribution, MTD),它将高阶转移概率建模为各阶滞后项的加权组合,参数数量从 \(O(d^m)\) 降到 \(O(dm)\)。这是对"阶数增长导致参数爆炸"这一核心困难的最早系统性回应。随后 Rissanen [1983] 提出变长马尔可夫链(VLMC),其思想是:不同历史(context)可以有不同的记忆长度,用一棵 context tree 刻画哪些后缀是"相关的"。Bühlmann and Wyner [1999] 和 Bühlmann [2000] 为 VLMC 建立了模型选择方法和渐近理论——这是本文直接对话的对象,因为 VLMC 是本文第三节具体例子的载体。
主要进展:稀疏马尔可夫模型(SMM)的兴起。 García et al. [2011] 提出 Minimal Markov Models(即 SMM 的雏形),其核心思想比 VLMC 更一般:将 \(\Sigma^m\) 中的所有 \(m\)-元组划分成若干等价类,同一类内的转移概率相同。这比 VLMC 的"context tree"结构更灵活,因为划分不必由后缀树诱导。Jääskinen et al. [2014] 在贝叶斯框架下扩展了 SMM,Xiong et al. [2016] 引入递归划分算法,Bennett et al. [2023] 用 collapsed Gibbs sampler 做后验估计。这些工作解决了"如何拟合"的问题,但渐近理论(CLT、相合性、收敛速度)基本缺席——这正是本文要填补的口子。
当前 frontier:贝叶斯与精确推断。 Kontoyiannis et al. [2020] 的 Bayesian Context Trees(BCT)框架提供了后验推断和预测分布的精确算法(context tree weighting 的变体),Papageorgiou and Kontoyiannis [2022] 进一步给出了后验的收敛性质。这些工作把"推断"推到了精确计算的前沿,但它们的渐近结果主要针对固定阶数或后验一致性,而非本文关注的"阶数随 \(n\) 增长时的频率学派 CLT"。
本文的位置。 本文是第一个(据作者所述)在 \(m_n \to \infty\) 且 \(m_n/n \to 0\) 的三角阵列设定下,为高阶马尔可夫链建立 CLT 的工作。它把经典的一阶链 CLT 推广到状态空间维度随样本量增长的场景,并给出了一个可验证的充分条件(\(m_n \log m_n / n \to 0\),在二元 VLMC 特例下)。
子线索聚类¶
被引文献大致落在三条子线索上:
- 降维建模:Raftery [1985] 的 MTD、García et al. [2011] 的 SMM、Jääskinen et al. [2014] 的贝叶斯 SMM。这条线关心"如何用更少的参数刻画高阶依赖"。
- 变长记忆与树结构:Rissanen [1983] 的 VLMC、Bühlmann and Wyner [1999] 的渐近理论、Bühlmann [2000] 的模型选择、Kontoyiannis et al. [2020] 和 Papageorgiou and Kontoyiannis [2022] 的 BCT。这条线关心"如何让记忆长度自适应于数据"。
- 计算与推断算法:Xiong et al. [2016] 的递归学习、Bennett et al. [2023] 的 Gibbs 采样、Majumder et al. [2026] 的凸聚类。这条线关心"如何高效地拟合这些模型"。
本文属于第 2 条线的理论延伸,但它的结果(CLT)对第 1 条和第 3 条线的推断问题(如 SMM 的模型选择、参数估计的置信区间)提供了基础。
这个方向在追问的核心问题¶
- 阶数增长时,CLT 是否仍然成立? 经典一阶链的 CLT 依赖状态空间的固定性和遍历性。当 \(m_n \to \infty\) 时,状态空间指数膨胀,每个状态的出现次数可能很少甚至为 0,经典正则条件(如一致遍历性)无法满足。本文的核心问题是:在什么条件下,加性泛函的 CLT 依然成立?
- 归一化常数是什么? 经典 CLT 的归一化是 \(\sqrt{n}\),但高阶链的方差结构可能随 \(m_n\) 变化。本文的归一化涉及 \(\sqrt{n \pi_n(\alpha_n)}\),其中 \(\pi_n(\alpha_n)\) 是某个"好状态"的平稳概率——这反映了状态空间膨胀带来的新现象。
- 稀疏性如何量化? 本文的假设 (iii) 和 (iv) 本质上是要求存在一个平稳概率不太小的状态 \(\alpha_n\),且返回时间的波动可控。这等价于要求模型"足够稀疏"——大多数概率质量集中在少数状态上。这个条件在 VLMC 和 SMM 中如何验证?本文第三节给出了一个特例。
⚠️ 作者的 framing¶
这是作者的说法:作者把缺口 frame 成"高阶马尔可夫链的渐近理论在 \(m_n \to \infty\) 时完全空白"。引言中明确说:"Proving CLTs in this setup is considerably more challenging",并声称本文是第一个处理该设定 CLT 的工作。作者淡化的竞争路线包括:(a) Bühlmann and Wyner [1999] 的 VLMC 渐近理论——作者暗示那是在固定阶数或更慢增长下的结果,但并未详细对比;(b) BCT 的贝叶斯后验一致性——作者承认其存在,但认为频率学派的 CLT 仍是缺失的。值得研究者去查的问题:Bühlmann and Wyner [1999] 是否真的只处理了固定阶数?如果它已经允许 \(m_n\) 缓慢增长,那么本文的 novelty 就打了折扣——需要去读原文确认。
张力¶
未见明显对立引用。被引文献之间是互补关系(建模 vs. 推断 vs. 计算),而非竞争关系。唯一的潜在张力是:BCT 的贝叶斯框架强调"精确后验推断",而本文的频率学派 CLT 强调"渐近正态性"——两者对不确定性的量化方式不同,但作者没有正面讨论这种张力。
二、最核心、最简单的例子 / 数学问题¶
第一步:符号、模型、可观测数据¶
符号清单(逐个点名):
| 记号 | 含义 | 类型 |
|---|---|---|
| \(\Sigma\) | 有限字母表,( | \Sigma |
| \(X_t^{(n)}\) | 第 \(n\) 条链在时刻 \(t\) 的取值,\(X_t^{(n)} \in \Sigma\) | 可观测的随机变量 |
| \(m_n\) | 第 \(n\) 条链的阶数(记忆长度) | 随 \(n\) 增长的参数(非随机) |
| \(Y_t^{(n)}\) | \(Y_t^{(n)} = (X_{t+m_n-1}^{(n)}, \ldots, X_t^{(n)}) \in \Sigma^{m_n}\) | 由可观测序列构造的 \(m_n\)-元组状态 |
| \(\Phi'_n = \{Y_t^{(n)}\}\) | 嵌入后的一阶马尔可夫链,状态空间 \(S_n = \Sigma^{m_n}\) | 可观测的(由 \(X\) 构造) |
| \(\pi_n\) | \(\Phi'_n\) 的平稳分布,\(\pi_n \in \Delta(\Sigma^{m_n})\) | 未知参数(要估计的对象) |
| \(g_n: \Sigma^{m_n} \to \mathbb{R}\) | 加性泛函的核函数 | 已知的(由研究者指定) |
| \(\alpha_n \in \Sigma^{m_n}\) | 选定的"好状态"(平稳概率不太小) | 辅助量(存在性由假设保证) |
| \(\tau_{\alpha_n}\) | 从状态 \(\alpha_n\) 出发首次回到 \(\alpha_n\) 的返回时间 | 随机变量(潜在量,不可直接观测) |
| \(\ell_{n,\alpha_n}\) | 到时刻 \(n\) 为止访问 \(\alpha_n\) 的次数 | 可观测的计数统计量 |
| \(\sigma_{\alpha_n}(k)\) | 第 \(k\) 次访问 \(\alpha_n\) 的时刻 | 可观测的停时 |
模型:对每个 \(n\),\(\Phi_n = \{X_0^{(n)}, \ldots, X_n^{(n)}\}\) 是一条长度为 \(n\) 的、取值于 \(\Sigma\) 的 \(m_n\) 阶马尔可夫链。等价地,\(\Phi'_n = \{Y_t^{(n)}\}\) 是状态空间 \(S_n = \Sigma^{m_n}\) 上的一阶马尔可夫链,转移矩阵记为 \(P_n\)(维度 \(d^{m_n} \times d^{m_n}\),每行至多 \(d\) 个非零元)。可观测数据:只有原始序列 \(X_0^{(n)}, \ldots, X_n^{(n)}\)(或等价地 \(Y_0^{(n)}, \ldots, Y_{n-m_n+1}^{(n)}\))。不可观测 / 潜在量:平稳分布 \(\pi_n\)、返回时间 \(\tau_{\alpha_n}\)、以及"好状态" \(\alpha_n\) 本身——它们的存在性由假设保证,但具体值未知。
关键区分:这里的"参数"是平稳分布 \(\pi_n\) 和转移概率 \(P_n\)(随 \(n\) 变化,属于三角阵列设定);"estimand"是 \(\mathbb{E}_{\pi_n}[g_n]\) 或加性泛函的均值;"随机变量"是 \(Y_t^{(n)}\) 和返回时间;"潜在量"是 \(\tau_{\alpha_n}\)(虽然由链的轨迹决定,但在观测到完整轨迹前不可知)。
第二步:最小内核¶
剥掉所有一般性设定后,本文的核心数学问题可以归结为:
最小问题:设 \(\{Z_j\}_{j \ge 0}\) 是一条不可约、非周期的马尔可夫链,状态空间为 \(S_n\)(大小随 \(n\) 增长),平稳分布为 \(\pi_n\)。对某个状态 \(\alpha_n \in S_n\),定义返回时间 \(\tau_{\alpha_n} = \inf\{j \ge 1 : Z_j = \alpha_n\}\)(从 \(\alpha_n\) 出发)。若 \(\mathbb{E}_{\alpha_n}[\tau_{\alpha_n}] = 1/\pi_n(\alpha_n)\) 且 \(\mathrm{Var}_{\pi_n}(\tau_{\alpha_n}) / (n \pi_n(\alpha_n)) \to 0\),则加性泛函的 CLT 成立。
为什么这是最小内核:本文的证明策略是"再生结构"(regenerative structure)——把链的轨迹在每次访问 \(\alpha_n\) 时切成独立的"块"(block),每个块是从 \(\alpha_n\) 出发到下次回到 \(\alpha_n\) 的一段路径。这些块是独立同分布的(由强马尔可夫性),因此加性泛函可以写成独立随机变量之和,CLT 退化为经典的独立同分布情形。
在这个最小设定下,命题退化为:
其中 \(\bar{g}_n = g_n - \mathbb{E}_{\pi_n}[g_n]\),且 \(\sigma^2 = \mathbb{E}_{\alpha_n}\left[\left(\sum_{j=1}^{\tau_{\alpha_n}} \bar{g}_n(Y_j^{(n)})\right)^2\right] / \mathbb{E}_{\alpha_n}[\tau_{\alpha_n}]\)。
证明怎么走(在最小设定下):
- 块分解:把轨迹分成 \(\ell_n\) 个完整的块(每次访问 \(\alpha_n\) 到下次访问之间),加上首尾两个不完整的块。完整块上的泛函和是 i.i.d. 的。
- 归一化:块的个数 \(\ell_n \approx n \pi_n(\alpha_n)\)(由遍历性),每个块的贡献是 \(O(1/\sqrt{\pi_n(\alpha_n)})\),所以总归一化是 \(\sqrt{n \pi_n(\alpha_n)}\)。
- 尾部处理:首尾不完整块的贡献是 \(o_p(\sqrt{n})\),需要假设 (iv) 来控制返回时间的波动。
- CLT:对 i.i.d. 块和用经典 Lindeberg-Lévy CLT,再结合 Slutsky 引理处理归一化常数的估计。
为什么难:难点不在 CLT 本身,而在验证假设 (iii) 和 (iv)。当 \(m_n \to \infty\) 时,状态空间指数膨胀,\(\pi_n(\alpha_n)\) 可能指数小,导致 \(n \pi_n(\alpha_n) \to 0\)(即"好状态"几乎不被访问)。本文的贡献在于给出了一个非平凡的例子(二元 VLMC),在其中可以显式计算 \(\pi_n(\alpha_n)\) 的下界,从而得到 \(m_n \log m_n / n \to 0\) 这个具体的充分条件。
读者读完这一节应掌握:本文在数学上干的事是——把"高阶马尔可夫链的 CLT"转化为"对返回时间块的 i.i.d. CLT",而核心困难在于找到平稳概率不太小的状态 \(\alpha_n\) 并控制返回时间的波动。第三节的 VLMC 例子就是为验证这些条件服务的。
三、这篇论文做了什么¶
三句话¶
- 研究了什么问题:在阶数 \(m_n\) 随样本量 \(n\) 增长(\(m_n \to \infty\),\(m_n/n \to 0\))的三角阵列设定下,建立了有限字母表上高阶马尔可夫链加性泛函的中心极限定理。
- 核心工具 / 方法:将高阶链嵌入到 \(\Sigma^{m_n}\) 上的一阶链,利用返回时间分解(regenerative block decomposition)把加性泛函转化为 i.i.d. 块的和,再对块和施加经典 CLT。
- 主要结论:在自然遍历性(假设 i-ii)、存在平稳概率不太小的状态(假设 iii)、以及返回时间波动可控(假设 iv)的条件下,归一化的加性泛函依分布收敛到标准正态分布。在二元 VLMC 特例下,给出了保证 CLT 的显式增长条件 \(m_n \log m_n / n \to 0\)。
关键设定与假设¶
设定:三角阵列 \(\{\Phi_n\}_{n \ge 1}\),其中 \(\Phi_n\) 是长度为 \(n\)、阶数为 \(m_n\) 的马尔可夫链,字母表 \(\Sigma\) 有限(\(|\Sigma| = d\))。嵌入后的一阶链 \(\Phi'_n\) 的状态空间为 \(S_n = \Sigma^{m_n}\),转移矩阵 \(P_n\) 每行至多 \(d\) 个非零元(因为从 \(m\)-元组只能转移到 \((m-1)\)-元组加一个新符号)。
假设(逐条解读):
- (i) 不可约 + 非周期:对每个 \(n\),\(\Phi'_n\) 不可约且非周期。这是保证平稳分布存在唯一、且返回时间有限的前提。相比固定阶数情形,这里要求对每个 \(n\) 都成立,而非只对某个固定的 \(m\)。
- (ii) \(m_n \to \infty\),\(m_n/n \to 0\):阶数增长但远慢于样本量。这是本文的核心新设定。\(m_n/n \to 0\) 保证状态空间 \(\Sigma^{m_n}\) 的膨胀速度不至于让每个状态几乎不被访问。
- (iii) 存在 \(\alpha_n \in \Sigma^{m_n}\) 使得 \(n \pi_n(\alpha_n) \to \infty\):这是"稀疏性"的量化——存在一个状态,其平稳概率衰减得不太快。注意 \(\pi_n(\alpha_n) \ge 1/d^{m_n}\) 总是成立,所以 \(n/d^{m_n} \to \infty\) 是充分条件,但本文第三节给出了更紧的条件。
- (iv) \(\mathrm{Var}_{\pi_n}(\ell_{n,\alpha_n} / (n \pi_n(\alpha_n))) \to 0\):访问次数的波动可控。这等价于返回时间的二阶矩条件,是块分解中尾部项可忽略的关键。
相比已有文献的放宽/强化:相比固定阶数(\(m_n = m\))的经典结果,本文允许 \(m_n \to \infty\),这是放宽;但假设 (iii)-(iv) 是新的、非标准的条件,在固定阶数情形下自动满足(因为 \(\pi_n(\alpha_n)\) 有正下界),在本文设定下需要额外验证。相比 Bühlmann and Wyner [1999] 的 VLMC 渐近理论,本文的假设更抽象(不依赖于具体的 context tree 结构),但代价是需要为具体模型验证 (iii)-(iv)。
主要结果¶
定理 2.1(核心定理):在假设 (i)-(iv) 下,
解读: - 归一化因子是 \(\sqrt{n}\) 乘以一个涉及返回时间的比值。这个比值是渐近方差的倒数平方根。 - 定理的证明分三步:(1) 用强马尔可夫性把轨迹分成 i.i.d. 块;(2) 证明首尾不完整块的贡献可忽略(用到假设 iv);(3) 对 i.i.d. 块和施加经典 CLT。 - 关键技巧是归一化因子的选择:不是用 \(\sqrt{n}\) 直接归一化,而是用 \(\sqrt{n \pi_n(\alpha_n)}\) 再乘以一个块内泛函的方差项。这反映了状态空间膨胀下方差结构的改变。
推论 3.1.1(VLMC 特例):对二元字母表 \(\Sigma = \{0,1\}\),考虑 context 为 \(\{0, 10, 110, \ldots, 1^{m-1}0, 1^m\}\) 的 VLMC,转移概率满足 \(P(0|1^j 0) = 1 - p_j\),\(P(1|1^j 0) = p_j\)。若 \(p_j = (j+1)/(j+2)\),则 \(n \pi_n(1^{m_n-1}0) \to \infty\) 当且仅当 \(m_n \log m_n / n \to 0\)。
解读: - 这个例子展示了如何验证假设 (iii)。关键在于显式计算 \(\pi_n(1^{m_n-1}0)\) 的下界,得到 \(q(p, m_n) = O(m_n \log m_n)\)。 - 条件 \(m_n \log m_n / n \to 0\) 比朴素的 \(m_n / n \to 0\) 更严格(多了一个 \(\log m_n\) 因子),这是因为状态空间膨胀导致每个状态的平稳概率衰减更快。 - 这个例子的技术价值在于:它给出了一个非平凡的、可验证的充分条件,而不是仅仅停留在抽象假设层面。
真实例子与应用¶
本文没有真实数据应用。第三节的 VLMC 例子是理论示例,用于说明假设 (iii) 如何验证。作者在结论中明确说,将条件推广到 SMM 是未来工作。因此,本文属于纯理论贡献,其应用价值在于为后续的推断方法(如 SMM 的模型选择、参数估计的置信区间)提供渐近基础。
🔎 结论是否比证明窄¶
是的,存在明显的不匹配:
- 定理 2.1 的证明依赖假设 (iv),但作者没有给出任何验证 (iv) 的例子。第三节的 VLMC 例子只验证了 (iii)(平稳概率下界),没有验证 (iv)(方差条件)。这意味着定理的适用范围实际上比作者声称的要窄——目前只有一个例子同时满足 (i)-(iii),但 (iv) 是否满足未知。
- 定理 2.1 的陈述是"存在 \(\alpha_n\)",但如何找到这个 \(\alpha_n\) 没有一般性指导。在 VLMC 例子中,作者选择了 \(1^{m_n-1}0\) 这个特定状态,但没有解释为什么这个状态是好的,也没有给出一般性的选择准则。
- 作者在结论中说"Similar reductions may be possible for SMMs",但这只是推测,没有证明。SMM 的划分结构比 VLMC 的 context tree 更复杂,验证 (iii)-(iv) 的难度可能更大。
- 定理 2.1 只处理了加性泛函,没有处理更一般的统计量(如经验分布函数、U-统计量)。对于假设检验问题,通常需要的是泛函的 CLT 在某种度量下的一致版本(如 Kolmogorov-Smirnov 型统计量),本文没有涉及。
四、开放问题¶
以下问题均扎根于本文的具体语句,只罗列、不判断可行性:
-
SMM 的显式条件(扎根于结论段:"Similar reductions may be possible for Sparse Markov Models (SMMs) by exploiting their underlying partition structure")。要证明什么:对一般的 SMM,能否利用其划分结构推导出类似 \(q(p, m_n) = o(n)\) 的显式条件?SMM 的划分比 VLMC 的 context tree 更灵活,验证 (iii)-(iv) 的难度在哪里?
-
假设 (iv) 的验证(扎根于定理 2.1 的假设 (iv),但全文没有给出任何验证例子)。要证明什么:在第三节的 VLMC 例子中,\(\mathrm{Var}_{\pi_n}(\ell_{n,\alpha_n} / (n \pi_n(\alpha_n))) \to 0\) 是否成立?如果成立,需要什么额外的条件(如对 \(p_j\) 的矩条件)?
-
CLT 的收敛速度(扎根于定理 2.1 的陈述,但作者没有给出 Berry-Esseen 型界)。要证明什么:在 \(m_n \log m_n / n \to 0\) 的条件下,CLT 的收敛速度是 \(O(1/\sqrt{n})\) 还是更慢?状态空间膨胀是否会导致收敛速度退化?
-
泛函类的推广(扎根于定理 2.1 只处理单个 \(g_n\),没有处理函数类)。要证明什么:如果 \(g_n\) 属于某个函数类(如指示函数族),CLT 是否能一致地成立?这是构造 Kolmogorov-Smirnov 型检验统计量的前提。
-
假设 (iii) 的必要性(扎根于假设 (iii) 的陈述,但作者没有讨论如果 \(n \pi_n(\alpha_n) \to c < \infty\) 会发生什么)。要证明什么:当 \(n \pi_n(\alpha_n)\) 收敛到有限常数时,加性泛函的极限分布是什么?是否会出现非高斯极限(如 Poisson 型)?
提醒:要确认上述问题是否是真 gap,建议去读近 5 年关于 VLCM/SMM 渐近理论的论文(如 Bühlmann 后续工作、Kontoyiannis 团队的 BCT 理论分析)的引言——如果它们都指向"高阶渐近理论缺失"这个共识,那么问题 1-2 就是真 gap;如果它们各自给出了不同的处理方式,那么问题 3-4 可能更有价值。
Maintained by 陈星宇 · Homepage · Source on GitHub