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

1. 問題設定 (Problem)

• 背景: 産業品質管理や通信ネットワークの故障検出など、逐次変化検出は重要な応用分野です。Page の CUSUM 検定は、事前分布（変化前）と事後分布（変化後）が既知である場合に最適性（漸近的または厳密）が証明されています。
• 課題: 現実の状況では、事前分布も事後分布も未知であることが多く、パラメータを推定する必要があります。
  • 既存の研究（Jacob & Bansal, Malik & Bansal など）は、i.i.d. ソース（メモリなし）に対して、事前分布を経験分布で、事後分布をユニバーサル符号（Universal Code）で推定する手法を提案し、その漸近最適性を示していました。
  • しかし、**マルコフソース（メモリあり）**において、事前分布と事後分布の両方が未知である場合の理論的保証は確立されていませんでした。
• 目的: 2022 年の i.i.d. に対する結果を、定常かつエルゴード的な有限次数マルコフソースに拡張し、未知の事前・事後分布下での CUSUM 検定の漸近最適性を証明すること。

2. 手法と提案アルゴリズム (Methodology)

提案手法は、マルコフ特性を考慮した「修正された CUSUM 検定」です。

A. 事前分布の推定 (Pre-change Distribution Estimation)

• トレーニングセグメント: 変化が発生する前の最初の $n_0$ 個の観測値 $x_1, \dots, x_{n_0}$ を用いて、事前分布 $\mu_0$ を推定します。
• 経験分布の構築: 1 次マルコフ過程を仮定し、遷移確率 $\hat{\mu}_0(b|a)$ と状態確率 $\hat{\mu}_0(b)$ を経験頻度から計算します。
  • $\hat{\mu}_0(b, a)$: 対 $(b, a)$ が出現した回数 / 全対の出現回数
  • $\hat{\mu}_0(b)$: 状態 $b$ の出現回数 / 全状態の出現回数
• 条件: $n_0$ は十分に大きく、すべての可能な遷移と状態が少なくとも 1 回観測されていることを仮定します。

B. 事後分布の推定 (Post-change Distribution Estimation)

• ユニバーサル符号: 事後分布 $\mu_1$ は未知であるため、**点ごとのユニバーサル符号（Pointwise Universal Code）**の符号長 $L(\cdot)$ を使用します。
• これにより、真の事後分布の対数尤度を、符号長 $-L(x)$ で近似します（Lempel-Ziv 符号や Context Tree Weighting 符号などが該当）。

C. 検定統計量 (Test Statistic)

• 変化点以降の観測 $x_{n_0+1}, \dots, x_{n_0+n}$ に対して、以下の統計量を計算します。
  $$\max_{1 \le k \le n} \left( -L(x_{n_0+n}^{n_0+k}) - \log \hat{\mu}_0(x_{n_0+n}^{n_0+k}) - n\lambda \right) \ge \log \gamma$$
  • ここで、$\hat{\mu}_0$ はトレーニングセグメントから推定された事前分布です。
  • $\lambda$ は、変化前の regime において統計量が負のドリフトを持つように設定される閾値パラメータです。
  • $\gamma$ は検出の感度を制御する閾値です。

3. 主要な貢献と理論的解析 (Key Contributions & Analysis)

A. 誤り確率の上限導出 (Lemma 3)

• 変化がない場合（$\mu_0$ の下）に検出が停止してしまう確率（偽陽性）の上限を導出しました。
• 推定誤差 $\hat{\mu}_0$ と真の分布 $\mu_0$ の差を $\delta, \delta'$ とし、これらが小さくなる（$n_0 \to \infty$）条件下で、誤り確率が $\alpha$（偽警報率）に比例して制御可能であることを示しました。
• 既存の既知分布ケースと比較し、推定誤差による項（$\beta_1, \beta_2$）が誤り確率に影響を与えるが、$n_0$ を大きくすることで無視できるレベルにできることを証明しました。

B. 検出の確実性と停止時間 (Lemma 4 & Theorem 2)

• 変化があった場合（$\mu_1$ の下）に、検定が確率 1 で停止すること（$\mu_1(N(\alpha) < \infty) = 1$）を示しました。
• 停止時間の期待値が、$\frac{|\log \alpha|}{D(\mu_1 || \hat{\mu}_0) - \lambda}$ に漸近することを証明しました。

C. 漸近最適性の証明 (Theorem 5 & 6)

• Lorden の基準（最小最大遅延）を用いて性能を評価しました。
• 偽警報率が 0 に近づく極限（$\gamma \to \infty$）において、提案された検定が以下の漸近最適性を満たすことを示しました。
  $$E_1(M) \sim (1+\vartheta) \inf_{S \in S_\gamma} E_1(S)$$
  • ここで、$\inf E_1(S)$ は分布が既知な場合の理論的下限（$\frac{\log \gamma}{D(\mu_1 || \mu_0)}$）です。
  • $\vartheta$ は任意の小さな正の値であり、トレーニングデータ $n_0$ を増やすことで $\vartheta \to 0$ とでき、分布既知の場合の最適性能に収束することを示しています。

4. 結果 (Results)

• 誤り制御: 適切な $\lambda$ の選択（$\lambda > \max(\log \beta_1, D(\mu_0 || \hat{\mu}_0))$）により、偽警報率を任意に小さく制御可能です。
• 最適性: 事前分布と事後分布の両方が未知であっても、ユニバーサル符号と経験分布の組み合わせを用いることで、分布が既知な場合の CUSUM 検定と同等の漸近的な性能（遅延のオーダー）を達成できることが証明されました。
• マルコフへの拡張: i.i.d. 仮定を緩和し、Berk の混合条件（Berk's mixing conditions）を満たす定常エルゴードマルコフソースに対して一般化されました。

5. 意義と将来展望 (Significance & Future Work)

• 理論的進展: 実用的な「両分布未知」かつ「メモリあり（マルコフ）」という複雑な条件下での逐次変化検出の最適性を初めて体系的に確立しました。
• 実用性: 実際のネットワークトラフィックや工業プロセスなど、マルコフ特性を持ち、かつ事前の統計モデルが不明な環境でのリアルタイム検出システムへの応用可能性を示唆しています。
• 将来の課題:
  • Lai のフレームワーク [20] を用いて、変化前後の観測の独立性の仮定をさらに緩和する拡張。
  • 異なるコスト関数や検出基準での性能評価。

結論

この論文は、情報理論（ユニバーサル符号）と統計的検定（CUSUM）を組み合わせることで、マルコフソースにおける未知パラメータの逐次変化検出問題を解決し、その理論的限界（漸近最適性）を証明した重要な成果です。