Large Sample Properties of Higher Order Markov Models¶
作者: Tuhin Majumder, Donald E. K. Martin, Soumendra N. Lahiri
主题: 数理统计 / 假设检验
相关性: 7/10
链接: https://arxiv.org/abs/2608.20321
一、领域脉络与小综述¶
这个方向是什么¶
这个子方向研究的是高阶马尔可夫链(order m 随序列长度 n 增长)的渐近理论,特别是其加性泛函的中心极限定理(CLT)。核心统计问题是:当模型的有效维度(即状态空间大小 d^m_n)随样本量 n 增长时,传统的固定阶 CLT 是否仍然成立?若成立,需要什么样的条件(如 m_n 的增长速率、稀疏性结构)?这为高维时间序列的推断(如假设检验、置信区间)提供了理论基础。
发展脉络(history)¶
奠基工作:固定阶马尔可夫链的渐近理论 - Raftery [1985]:提出了一个线性混合模型(Mixture Transition Distribution, MTD),将高阶链的参数从 d^m(d-1) 压缩到 m(d-1) + d(d-1)。这是早期降维尝试,但模型结构是参数化的,且渐近理论仍基于固定阶。 - Rissanen [1983]:提出了变长马尔可夫链(VLMC) 的概念,通过上下文树(context tree)让记忆长度随过去状态自适应变化。这是第一个真正意义上的稀疏高阶模型,但当时缺乏严格的渐近理论。
主要进展:VLMC 与 SMM 的推断与渐近 - Bühlmann and Wyner [1999] 和 Bühlmann [2000]:为 VLMC 建立了模型选择方法和渐近性质,包括基于 bootstrap 的 CLT。这是第一个将 VLMC 的渐近理论系统化的成果,但他们的 CLT 仍假设阶数固定(或至少不随 n 增长)。 - García et al. [2011] 和 Jääskinen et al. [2014]:提出了稀疏马尔可夫模型(SMM),将状态空间 Σ^m 划分为等价类,同一类内的历史共享相同的转移概率。这比 VLMC 更一般(VLMC 是 SMM 的一种特例,其划分由上下文树决定)。Jääskinen et al. [2014] 给出了贝叶斯框架下的推断。 - Xiong et al. [2016]:为 SMM 开发了递归划分算法,用于快速近似后验模式。 - Kontoyiannis et al. [2020] 和 Papageorgiou and Kontoyiannis [2022]:提出了贝叶斯上下文树(BCT) 框架,给出了精确的后验推断和预测分布,并证明了后验一致性。这是当前 VLMC 推断的最先进方法之一。 - Majumder et al. [2026](本文作者之一):开发了基于凸聚类的 SMM 拟合方法,并证明了模型选择一致性。
当前 frontier:阶数随样本量增长的渐近理论 - 本文(Majumder, Martin, Lahiri [2026])是第一个系统研究 m_n → ∞ 时高阶马尔可夫链 CLT 的工作。它填补了上述所有工作的空白:无论是 VLMC、SMM 还是 BCT,其渐近理论都假设阶数固定或增长极慢(如 m_n = O(log n)),而本文允许 m_n 以更快的速率增长(如 m_n log m_n / n → 0)。
子线索聚类¶
- 参数化降维模型(Raftery [1985]):通过线性混合结构减少参数,但模型形式受限,渐近理论仍基于固定阶。
- 变长马尔可夫链(VLMC)(Rissanen [1983], Bühlmann and Wyner [1999], Bühlmann [2000], Kontoyiannis et al. [2020], Papageorgiou and Kontoyiannis [2022]):通过上下文树实现自适应记忆长度。渐近理论(CLT、后验一致性)在固定阶下已成熟,但 m_n 增长时未研究。
- 稀疏马尔可夫模型(SMM)(García et al. [2011], Jääskinen et al. [2014], Xiong et al. [2016], Bennett et al. [2023], Majumder et al. [2026]):通过状态空间划分实现更一般的稀疏性。模型选择一致性已建立,但渐近分布理论缺失。
- 本文:m_n 增长时的 CLT(Majumder, Martin, Lahiri [2026]):独立于上述所有工作,直接处理三角阵列设定,为 VLMC 和 SMM 的推断提供渐近基础。
这个方向在追问的核心问题¶
- CLT 成立的最小条件是什么? 即 m_n 可以多快增长?本文给出一个充分条件:存在一个状态 α_n 使得 nπ_n(α_n) → ∞,且方差条件 (iv) 成立。在二元 VLMC 例子中,这退化为 m_n log m_n / n → 0。
- 这个条件是否紧? 即是否存在反例表明 m_n log m_n / n → 0 是必要的?本文未讨论。
- 对于更一般的 SMM,条件如何简化? 本文仅给出了 VLMC 的例子,SMM 的类似结果留作未来工作。
- 加性泛函的 CLT 能否推广到更一般的统计量(如 M-估计量、U-统计量)? 本文仅处理了加性泛函。
⚠️ 作者的 framing¶
作者将缺口 frame 为:“当马尔可夫链阶数随序列长度增长时,CLT 尚未被研究”。他们通过嵌入一阶链和返回时间分解,将问题转化为 i.i.d. 块和 CLT,从而在自然遍历性和稀疏性条件下建立了结果。
被淡化或回避的竞争路线: - Bühlmann and Wyner [1999] 的 bootstrap CLT:作者在 intro 中仅提到“Bühlmann and Wyner [1999] derived large-sample properties of VLMC estimators, including bootstrap-based CLTs”,但未说明他们的 CLT 是否允许 m_n 增长。实际上,Bühlmann and Wyner 的 CLT 假设阶数固定,因此本文的结果是真正的推广。 - BCT 的后验一致性:Kontoyiannis et al. [2020] 和 Papageorgiou and Kontoyiannis [2022] 的后验一致性结果也假设模型空间固定或增长极慢,本文未与之对比。
什么明显该被引 / 该存在、却没出现在 intro 里? - 关于高阶马尔可夫链 minimax 估计率的工作:例如,对于 VLMC 或 SMM,是否存在 minimax 下界表明 m_n 不能超过某个速率?这类工作可能来自信息论或高维统计领域,但本文未引用。这可能是研究者值得去查的方向。 - 关于“有效维度增长”的渐近理论:例如,高维线性回归中 p_n → ∞ 时的 CLT(如 Portnoy [1985] 或 Mammen [1993] 的工作)。本文的设定(m_n → ∞)与高维统计中 p_n → ∞ 有平行性,但作者未建立这种联系。
张力¶
未见明显对立引用。所有被引工作都支持“固定阶渐近理论已成熟,增长阶渐近理论缺失”这一共识。
二、最核心、最简单的例子 / 数学问题¶
第一步:把符号、模型、可观测数据交代清楚¶
符号: - Σ:有限字母表,大小 |Σ| = d。例如,二元序列 Σ = {0, 1}。 - Φ_n = {X_t^(n) : t = 0, 1, ..., n}:第 n 个三角阵列中的高阶马尔可夫链,阶数为 m_n。X_t^(n) ∈ Σ。 - m_n:第 n 个阵列的阶数,随 n 增长(m_n → ∞),且 m_n / n → 0。 - Y_t^(n) = (X_{t+m_n-1}^(n), ..., X_t^(n)):将高阶链嵌入为一阶链后的状态,t = 0, 1, ..., n - m_n + 1。Y_t^(n) ∈ S_n = Σ^{m_n}。 - Φ'_n = {Y_t^(n)}:嵌入后的一阶马尔可夫链,状态空间大小为 d^{m_n}。 - π_n:Φ'n 的平稳分布,是长度为 d^{m_n} 的概率向量。 - α_n:一个精心选择的序列状态,α_n ∈ Σ^{m_n},满足 nπ_n(α_n) → ∞(即该状态的平稳概率足够大,使得期望返回次数发散)。 - τ_{α_n}:从状态 α_n 出发,首次返回 α_n 的时间(即返回时间)。 - ℓ_{n, α_n}:在 n - m_n + 1 个时间步内,Φ'_n 返回 α_n 的次数(减去首次命中)。即 ℓ{n, α_n} = Σ_{j=0}^{n-m_n+1} I(Y_j^(n) = α_n) - 1。 - g_n : Σ^{m_n} → ℝ:定义在嵌入状态上的函数。我们关心其加性泛函 Σ_{j=0}^{n-m_n+1} g_n(Y_j^(n))。 - \bar{g}n(x) = g_n(x) - E{π_n}[g_n]:中心化后的函数。 - s_j^(n)(f):第 j 个“块和”,即从第 j 次返回 α_n 到第 j+1 次返回之间,函数 f 的和。s_j^(n)(f) = Σ_{t = σ_{α_n}(j)+1}^{σ_{α_n}(j+1)} f(Y_t^(n))。
模型: - 数据生成机制:对于每个 n,Φ_n 是一个阶数为 m_n 的马尔可夫链,其转移概率由某个未知的(但满足遍历性条件的)规则决定。嵌入后的一阶链 Φ'_n 是不可约且非周期的(假设 (i))。 - 要估的对象:我们并不直接估计转移概率,而是研究加性泛函 Σ g_n(Y_t^(n)) 的渐近分布。这类似于“给定一个函数,其样本均值的 CLT”。
可观测数据: - 可观测:序列 X_0^(n), X_1^(n), ..., X_n^(n)(长度为 n+1 的离散时间序列)。由此可构造 Y_t^(n)(长度为 n - m_n + 2 的嵌入状态序列)。 - 不可观测 / 潜在:平稳分布 π_n、返回时间 τ_{α_n}、块和 s_j^(n)(g_n) 的分布。这些是理论分析的工具,不是直接可观测的。CLT 的归一化因子(如 √(E[τ_{α_n}] / E[s_0^(n)(\bar{g}_n)^2]))依赖于这些不可观测量,因此该 CLT 是非自归一化的(non-self-normalized),即它给出了一个渐近正态的统计量,但其方差需要估计才能用于实际推断。
第二步:讲最小内核¶
最简特例:考虑一个二元(d=2)VLMC,其上下文树只有 m_n + 1 个叶子,如 Example 3.1 所述。具体地,上下文为 {0, 10, 110, ..., 1^{m_n-1}0, 1^{m_n}}。转移概率为: - P(0 | 1^j 0) = 1 - p_j, P(1 | 1^j 0) = p_j, j = 0, 1, ..., m_n - 1 - P(0 | 1^{m_n}) = 1 - p_{m_n}, P(1 | 1^{m_n}) = p_{m_n}
在这个特例下,要证的命题退化成什么? - 定理 2.1 的条件 (iii) 要求存在一个状态 α_n 使得 nπ_n(α_n) → ∞。作者选择 α_n = 1^{m_n-1}0(即“连续 m_n-1 个 1 后跟一个 0”这个历史)。 - 他们推导出 π_n(1^{m_n-1}0) 的显式下界:1/π_n(1^{m_n-1}0) = q(p, m_n),其中 q(p, m_n) 是 p_j 的函数(见论文公式)。 - 进一步,若取 p_j = (j+1)/(j+2),则 q(p, m_n) = O(m_n log m_n)。因此,nπ_n(1^{m_n-1}0) → ∞ 当且仅当 m_n log m_n / n → 0。
核心思路: 1. 嵌入:将 m_n 阶链嵌入到 Σ^{m_n} 上的一阶链。这本身是标准技巧,但代价是状态空间大小 d^{m_n} 爆炸。 2. 返回时间分解:利用强马尔可夫性,将整个序列的加性泛函分解为“首次到达 α_n 之前的片段” + “一系列 i.i.d. 的块和(每次返回 α_n 之间的和)” + “最后一次返回后的片段”。关键点是:块和 s_j^(n)(\bar{g}_n) 是 i.i.d. 的(由强马尔可夫性保证)。 3. 用 i.i.d. CLT 逼近:如果 ℓ_n(返回次数)很大,则块和的和近似于 i.i.d. 随机变量的和,从而 CLT 成立。但 ℓ_n 本身是随机的,需要证明 ℓ_n / (nπ_n(α_n)) → 1(依概率),即返回次数与期望返回次数之比收敛到 1。这由条件 (iv)(方差趋于 0)保证。 4. 处理边界项:首次到达前的片段和最后一次返回后的片段是“边界项”,需要证明它们相对于主项可忽略。这通过假设 (ii)(矩条件)和 ℓ_n → ∞ 来证明。
为什么这个特例能体现核心困难? - 核心困难在于:当 m_n 增长时,状态空间 Σ^{m_n} 指数级膨胀,导致每个状态的平稳概率 π_n(α_n) 可能指数级小。条件 nπ_n(α_n) → ∞ 本质上要求 m_n 不能增长太快,否则即使 n 很大,期望返回次数也有限。在 VLMC 例子中,这个条件退化为 m_n log m_n / n → 0,给出了一个具体的、可验证的增长速率。 - 证明中的关键跳跃点在于:如何从 ℓ_n / (nπ_n(α_n)) → 1 推导出 ℓ_n → ∞ 且边界项可忽略。这需要精细的概率估计,特别是 Kolmogorov 不等式和切比雪夫不等式的组合使用。
三、这篇论文做了什么¶
三句话¶
- 研究了什么问题:当高阶马尔可夫链的阶数 m_n 随序列长度 n 增长时,其加性泛函的中心极限定理。
- 核心工具 / 方法:将高阶链嵌入 Σ^{m_n} 上的一阶链,利用返回时间分解将加性泛函分解为 i.i.d. 块和,再结合三角阵列的 CLT。
- 主要结论:在自然遍历性(不可约、非周期)和稀疏性(存在一个状态 α_n 使得 nπ_n(α_n) → ∞,且返回次数的方差趋于 0)条件下,归一化的加性泛函依分布收敛到标准正态分布。在二元 VLMC 特例中,给出了显式条件 m_n log m_n / n → 0。
关键设定与假设¶
完整设定(在第二节记号基础上补充): - 三角阵列:对于每个 n,有一个独立的马尔可夫链 Φ_n,其阶数为 m_n。不同 n 的链之间没有依赖关系。 - 函数 g_n:定义在 Σ^{m_n} 上的实值函数,可以随 n 变化。这是为了允许函数本身依赖于状态空间的大小(例如,g_n 可能是某个统计量的组成部分)。 - 归一化因子:CLT 的归一化因子是 √(E_{α_n}[τ_{α_n}] / E_{α_n}[s_0^(n)(\bar{g}_n)^2])。注意,这个因子依赖于不可观测的返回时间分布和块和方差,因此该 CLT 是非自归一化的——它给出了一个渐近正态的统计量,但实际应用时需要估计这个归一化因子。
假设逐条说明: - (i) 不可约且非周期:保证平稳分布 π_n 存在且唯一,且链是遍历的。这是马尔可夫链 CLT 的标准条件。 - (ii) m_n → ∞ 且 m_n / n → 0:阶数增长,但比样本量慢。这是三角阵列设定的核心——如果 m_n 与 n 同阶,则每个状态几乎只出现一次,CLT 不可能成立。 - (iii) nπ_n(α_n) → ∞:存在一个状态 α_n,其平稳概率足够大,使得期望返回次数发散。这是稀疏性条件——它要求链的“质量”集中在少数状态上,而不是均匀分布在 d^{m_n} 个状态上。如果链是均匀的(π_n(α_n) = 1/d^{m_n}),则此条件要求 n / d^{m_n} → ∞,即 m_n = o(log n)。但通过利用稀疏结构(如 VLMC),可以允许更快的增长(如 m_n log m_n / n → 0)。 - (iv) Var_{π_n}[ℓ_n / (nπ_n(α_n))] → 0:返回次数的方差相对于其均值可忽略。这是技术性条件,用于保证 ℓ_n / (nπ_n(α_n)) → 1(依概率)。它等价于要求返回次数的波动足够小。 - 函数 g_n 的条件 (i) 和 (ii):保证块和 s_0^(n)(\bar{g}_n) 的二阶矩存在,且其绝对值的二阶矩与二阶矩之比有界(即 Lyapunov 型条件)。这是应用 CLT 的标准矩条件。
相比已有文献放宽或强化了哪些: - 放宽:允许 m_n → ∞,而所有已有工作(Bühlmann and Wyner [1999], Kontoyiannis et al. [2020])假设阶数固定。 - 强化:需要存在一个“好”的状态 α_n 满足 nπ_n(α_n) → ∞。对于均匀链,这要求 m_n = o(log n),比 Bühlmann and Wyner [1999] 的固定阶设定更严格。但对于稀疏链(如 VLMC),这个条件可以放松。
主要结果¶
定理 2.1(核心定理): - 陈述:在假设 (i)-(iv) 和函数 g_n 的条件 (i)-(ii) 下,
推论 3.1.1(VLMC 特例): - 陈述:对于 Example 3.1 中的二元 VLMC,若 p_j = (j+1)/(j+2),则 nπ_n(1^{m_n-1}0) → ∞ 当且仅当 m_n log m_n / n → 0。 - 直觉:在这个 VLMC 中,平稳概率 π_n(1^{m_n-1}0) 的下界是 1 / O(m_n log m_n),因此条件 (iii) 退化为 m_n log m_n / n → 0。 - 意义:给出了一个具体的、可验证的增长速率。例如,若 m_n = n^{0.4},则 m_n log m_n / n → 0 成立;若 m_n = n^{0.6},则不成立。
证明路线与技术技巧¶
整体路线(3-5 步逻辑主干): 1. 嵌入与返回时间分解:将高阶链嵌入一阶链,并将加性泛函分解为“首次到达 α_n 前的片段” + “ℓ_n 个 i.i.d. 块和” + “最后一次返回后的片段”。即:
关键跳跃点: - 最吃功夫的引理:证明边界项可忽略(公式 (2) 之前的推导)。这需要处理 ℓ_n 的随机性——边界项的大小依赖于 ℓ_n,而 ℓ_n 本身是随机的。作者通过将 ℓ_n 替换为 n^ 并证明误差可忽略来绕过这个困难。 - 难点卡在哪:如何控制 s_{\ell_n}^{(n)}(|\bar{g}_n|) / √(n^ v_n)?由于 ℓ_n 是随机的,s_{\ell_n}^{(n)}(|\bar{g}n|) 不是通常的 i.i.d. 和。作者通过将 ℓ_n 限制在区间 [n, \bar{n}] 内,并利用 Kolmogorov 不等式和切比雪夫不等式来证明其可忽略。 - 作者用什么办法绕过去:他们先证明 ℓ_n / n^ → 1,然后对 ℓ_n 进行“夹逼”:对于任意 ϵ > 0,存在 n_0 使得 P(n_ ≤ ℓ_n ≤ \bar{n}) ≥ 1-ϵ,其中 n_ = [(1-ϵ)n^], \bar{n} = [(1+ϵ)n^]。然后分别处理 ℓ_n 在区间内和区间外的情况。
技术技巧点名: - 强马尔可夫性:用于证明块和 s_j^(n)(\bar{g}_n) 是 i.i.d. 的。这是整个分解的基础。 - 返回时间分解:将非 i.i.d. 的马尔可夫链加性泛函转化为 i.i.d. 块和。这是马尔可夫链 CLT 的经典技巧(如“再生方法”)。 - Kolmogorov 不等式:用于控制用 n^ 个 i.i.d. 和逼近 ℓ_n 个 i.i.d. 和时的误差(公式 (3))。 - 切比雪夫不等式 + 联合界:用于证明边界项可忽略(公式 (2) 之前的推导)。 - 三角阵列 CLT:用于 n^ 个 i.i.d. 随机变量的和。这是标准结果,但需要验证 Lyapunov 条件(由假设 (ii) 保证)。
真实例子与应用¶
本文为纯理论 / 无实证例子。论文没有模拟实验或真实数据应用。Example 3.1 是一个理论例子,用于说明条件 (iii) 在二元 VLMC 中如何简化。它展示了如何推导 π_n(1^{m_n-1}0) 的显式下界,并给出了 m_n log m_n / n → 0 这个具体条件。
🔎 结论是否比证明窄¶
- 定理 2.1 的结论是“非自归一化的”:归一化因子 √(E[τ_{α_n}] / E[s_0^(n)(\bar{g}_n)^2]) 依赖于不可观测的分布。这意味着该定理本身不能直接用于构造置信区间或假设检验——需要额外的估计步骤来估计这个归一化因子。作者在结论部分没有讨论如何估计这个因子,这是一个明显的“结论比证明窄”的地方。
- 条件 (iv) 的验证:Var_{π_n}[ℓ_n / (nπ_n(α_n))] → 0 是一个技术性条件,在 VLMC 例子中并未验证。作者仅验证了条件 (iii)(nπ_n(α_n) → ∞),但未验证 (iv)。因此,对于 VLMC 例子,定理 2.1 的完整条件是否满足仍是一个开放问题。
- 函数 g_n 的条件:条件 (i) 和 (ii) 要求块和的二阶矩存在且有界。对于常见的函数(如指示函数、线性函数),这些条件可能成立,但作者没有给出具体的例子或验证。
四、开放问题(点到为止,扎根具体语句)¶
-
SMM 的类似条件:作者在结论中说“Similar reductions may be possible for Sparse Markov Models (SMMs) by exploiting their underlying partition structure. Investigating such conditions for SMMs and other sparse higher-order Markov models is an interesting direction for future work.” 具体要证什么:对于一般的 SMM,能否找到类似于 VLMC 例子中的显式下界,从而将条件 (iii) 简化为一个关于 m_n 和划分结构的具体增长条件?
-
条件 (iv) 的验证与紧性:在 VLMC 例子中,作者仅验证了条件 (iii),但未验证条件 (iv)(Var[ℓ_n / (nπ_n(α_n))] → 0)。一个开放问题是:对于 Example 3.1 中的 VLMC,条件 (iv) 是否自动满足?或者需要额外的假设?更一般地,条件 (iv) 是否可以被更简单的条件(如几何遍历性)所蕴含?
-
自归一化 CLT:定理 2.1 的归一化因子依赖于不可观测的返回时间分布和块和方差。一个实际可用的 CLT 需要自归一化形式,即用可观测的样本方差来归一化。例如,能否证明
\[\frac{\sum_{j=0}^{n-m_n+1} \bar{g}_n(Y_j^{(n)})}{\sqrt{\sum_{j=0}^{n-m_n+1} (\bar{g}_n(Y_j^{(n)}) - \bar{g}_n)^2}} \xrightarrow{d} N(0, 1)?\]这需要额外的理论工作,且可能对 m_n 的增长速率有更严格的限制。 -
m_n 增长速率的紧性:推论 3.1.1 给出了一个充分条件 m_n log m_n / n → 0。是否存在反例表明这个条件是必要的?即,是否存在一个 VLMC(或更一般的 SMM),使得 m_n log m_n / n → c > 0 时 CLT 不成立?这需要构造一个具体的反例,并证明其加性泛函的极限分布不是正态的(例如,是 Poisson 或退化分布)。
Maintained by 陈星宇 · Homepage · Source on GitHub