Sequential Change Detection Under Markov Setup With Unknown Prechange And Postchange Distributions

这是一份关于论文《Sequential Change Detection under Markov Setup with Unknown Pre-change and Post-change Distributions》（马尔可夫设定下预变点和后变点分布均未知的序贯变化检测）的详细技术总结。

1. 研究背景与问题定义 (Problem Definition)

核心问题：
序贯变化检测（Sequential Change Detection）旨在实时检测随机过程分布发生突变的时间点。传统的 Page CUSUM 检验要求预先知道变化前（$\mu_0$）和变化后（$\mu_1$）的分布。然而，在实际应用中，这两个分布往往都是未知的。

研究缺口：

• 现有的工作（如 Jacob & Bansal, Malik & Bansal）主要针对**独立同分布（i.i.d.）**源，或者仅处理分布部分未知的情况。
• 对于具有记忆性（Memory）的源（即马尔可夫源），且预变点和后变点分布均未知的情况，缺乏有效的通用检测算法及其渐近最优性证明。

本文目标：
将 2022 年针对 i.i.d. 源提出的改进算法（利用经验分布估计预变点分布，利用通用码估计后变点分布），推广到平稳遍历的有限阶马尔可夫源，并证明其在假警率趋于 0 的渐近区域下的最优性。

---

2. 方法论 (Methodology)

本文提出了一种针对马尔可夫源的改进 CUSUM 检验（Modified CUSUM Test），主要包含以下三个关键步骤：

A. 预变点分布估计 (Estimating Pre-change Distribution)

由于 $\mu_0$ 未知，算法首先利用一段长度为 $n_0$ 的“训练序列”（假设该段未发生分布变化）来估计预变点分布 $\hat{\mu}_0$。

• 估计方法： 采用最大似然估计（MLE）。对于一阶马尔可夫源，计算符号出现的频率 $\hat{\mu}_0(b)$ 和符号对 $(b, a)$ 的转移频率 $\hat{\mu}_0(a|b)$。
• 假设： $n_0$ 足够大，使得所有非零概率的状态和转移对都在训练序列中出现过，从而保证估计的准确性。

B. 后变点分布估计 (Estimating Post-change Distribution)

由于 $\mu_1$ 未知，算法不使用具体的参数模型，而是利用通用码（Universal Code）。

• 工具： 使用满足强逐点通用性（Strongly Pointwise Universal）的固定长度到可变长度码（FV code），如 Lempel-Ziv (LZ-77/78) 或 Context Tree Weighting (CTW) 码。
• 原理： 通用码的码长 $L(x)$ 近似于 $-\log \mu(x)$。在检验统计量中，用 $-L(x)$ 替代未知的 $\log \mu_1(x)$。

C. 检验统计量与停止规则

定义检验统计量，并在满足特定条件时停止：
$$\max_{1 \le k \le n} \left( -L(x_{n_0+k}^{n_0+n}) - \log \hat{\mu}_0(x_{n_0+k}^{n_0+n}) - n\lambda \right) \ge \log \gamma$$

• 参数说明：
  • $L(\cdot)$：通用码的码长。
  • $\hat{\mu}_0(\cdot)$：基于训练序列估计的预变点分布。
  • $\lambda$：一个正参数，用于确保在预变点阶段统计量具有负漂移（Negative Drift），防止误报。
  • $\gamma$：控制假警率的阈值。
• 停止时间： 当上述不等式首次成立时，判定发生了分布变化。

---

3. 关键贡献 (Key Contributions)

1. 从 i.i.d. 到马尔可夫源的扩展：
   成功将 Malik 和 Bansal (2022) 针对 i.i.d. 源的“双未知分布”检测框架，扩展到了更通用的平稳遍历有限阶马尔可夫源。这是通过利用 Berk 混合条件（Berk's mixing conditions）和遍历定理实现的。

2. 双重未知分布的处理：
   提出了一种同时处理预变点分布（通过经验估计）和后变点分布（通过通用码）的联合检测方案，解决了实际应用中分布完全未知的难题。

3. 理论性能界限的推导：

   • 假警率界限： 推导了预变点阶段（无变化时）检测停止的概率上界（Lemma 3），证明了随着训练长度 $n_0 \to \infty$，该概率可以任意小。
   • 检测延迟界限： 证明了在变化发生后，算法以概率 1 停止，并给出了检测延迟的渐近表达式。

4. 渐近最优性证明：
   在 Lorden 准则（Lorden's criterion）下，证明了该算法是渐近最优的。即当假警率趋于 0 时，该算法的平均检测延迟与已知分布情况下的最优检测延迟之比趋近于 1（允许任意小的偏差 $\vartheta$）。

---

4. 主要结果 (Key Results)

A. 误差概率分析 (Lemma 3)

在预变点分布 $\mu_0$ 下，算法错误停止（假警）的概率 $P_{FA}$ 满足：
$$\mu_0(N(\alpha) < \infty) \le \frac{\alpha}{\beta_1 (2^{\lambda - \log \beta_1 - 1}) \beta_2} + \epsilon_0$$
其中 $\beta_1, \beta_2$ 是与估计误差 $\delta, \delta'$ 相关的因子。当训练长度 $n_0 \to \infty$ 时，$\beta_1, \beta_2 \to 1$ 且 $\epsilon_0 \to 0$，表明可以通过增加训练数据将假警率控制在极低水平。

B. 检测延迟分析 (Theorem 5 & 6)

在变化后分布 $\mu_1$ 下，给定初始训练段 $x_1^{n_0}$，平均检测延迟 $E_1(M(\gamma) | x_1^{n_0})$ 的渐近行为为：
$$E_1(M(\gamma) | x_1^{n_0}) \sim \frac{\log \gamma}{D(\mu_1 || \hat{\mu}_0) - \lambda}$$
当 $\gamma \to \infty$（即假警率 $\to 0$）且 $n_0 \to \infty$ 时，$\hat{\mu}_0 \to \mu_0$，且通过优化 $\lambda$，检测延迟收敛于：
$$E_1(M) \sim (1+\vartheta) \frac{\log \gamma}{D(\mu_1 || \mu_0)}$$
这与已知分布时的最优检测延迟（由 Theorem 4 给出）仅相差一个任意小的因子 $(1+\vartheta)$。

C. 最优性结论

该算法在 Lorden 意义下是渐近最优的。它证明了即使在没有先验分布知识且源具有记忆性的情况下，利用通用码和经验估计依然可以达到理论上的最佳检测速度。

---

5. 意义与影响 (Significance)

• 理论突破： 填补了序贯变化检测理论中关于“马尔可夫源 + 双未知分布”这一复杂场景的空白。之前的研究多局限于 i.i.d. 或仅单侧未知。
• 实际应用价值： 工业质量控制、网络故障检测等场景中的数据往往具有时间相关性（马尔可夫性），且故障前后的统计特性往往未知。本文提出的算法无需预先建模，具有极强的鲁棒性和适应性。
• 通用性框架： 该方法结合了信息论（通用码）与统计学（经验估计），为处理更复杂的非平稳、非马尔可夫源提供了新的思路。
• 未来方向： 论文指出可以进一步在 Lai 的框架下（放宽变化前后观测的独立性假设）进行推广，并探索其他性能指标（如平均运行长度 ARL 的优化）。

总结：
这篇文章通过严谨的数学推导，成功将基于通用码和估计的序贯变化检测算法推广到了马尔可夫环境，并证明了其在渐近意义下的最优性，为处理现实世界中复杂的、分布未知的时序数据变化检测问题提供了强有力的理论工具。