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

1. Problem Statement

The paper addresses the problem of sequential change detection in a stochastic process where the statistical properties of the data change at an unknown time point. Specifically, the authors tackle a scenario with three significant complexities:

• Markov Sources: The data is generated by stationary, ergodic, finite-order Markov processes (specifically first-order in the analysis), rather than independent and identically distributed (i.i.d.) sources.
• Unknown Distributions: Both the pre-change distribution ($\mu_0$) and the post-change distribution ($\mu_1$) are unknown.
• Goal: To design a detection algorithm that minimizes the detection delay while maintaining a low false alarm rate, achieving asymptotic optimality as the false alarm rate approaches zero.

This extends previous work (Jacob-Bansal and Malik-Jacob-Bansal) which handled unknown distributions only for i.i.d. sources or sources with memory where only the post-change distribution was unknown.

2. Methodology

The proposed methodology involves a two-stage approach combining empirical estimation with universal coding theory.

A. Preliminaries and Assumptions

• Source Model: The source $X = \{X_n\}$ is a stationary, ergodic, first-order Markov process.
• Mixing Conditions: The sources satisfy Berk's mixing conditions, which ensure that the likelihood ratios converge sufficiently fast (specifically, "1-quick convergence").
• Universal Codes: The authors utilize strongly pointwise universal codes (e.g., Lempel-Ziv or Context Tree Weighting) to estimate the post-change distribution. These codes satisfy specific length constraints where the code length $L(x^n)$ approximates the negative log-likelihood of the true distribution.

B. The Proposed Algorithm (Modified CUSUM Test)

The algorithm, referred to as Test 3, operates in two phases:

1. Training Phase (Pre-change Estimation):

   • The system observes an initial training sequence of length $n_0$ ($x_1, \dots, x_{n_0}$) assumed to be generated by the pre-change distribution $\mu_0$.
   • An empirical estimate $\hat{\mu}_0$ is calculated based on transition frequencies and symbol frequencies in this training set.
   • $\hat{\mu}_0(b, a)$ represents the empirical probability of transitioning from state $b$ to $a$.

2. Detection Phase (CUSUM Statistic):

   • For subsequent samples $x_{n_0+1}, \dots$, the algorithm computes a modified CUSUM statistic.
   • Instead of using the true log-likelihood ratio, it uses the universal code length $L(\cdot)$ for the post-change estimate and the empirical log-likelihood $\log \hat{\mu}_0(\cdot)$ for the pre-change estimate.
   • The stopping rule is defined as:
     $$\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$$
     Where:
     • $L(\cdot)$ is the length of the universal code for the segment.
     • $\lambda$ is a drift parameter chosen such that $D(\mu_0 || \hat{\mu}_0) < \lambda < D(\mu_1 || \hat{\mu}_0)$.
     • $\gamma$ is the threshold controlling the false alarm rate.

3. Key Contributions

1. Extension to Markov Sources: The paper successfully generalizes the "unknown pre-change and post-change" detection framework from i.i.d. sources to Markov sources. This is non-trivial because Markov dependencies require handling transition probabilities rather than just symbol frequencies.
2. Dual Unknown Estimation: It provides a rigorous framework where both distributions are unknown. It uses empirical estimation for the pre-change distribution (via a training window) and universal coding for the post-change distribution.
3. Asymptotic Optimality Proof: The authors prove that the proposed test is asymptotically optimal in the Lorden minimax sense. As the false alarm rate ($\alpha \to 0$) and the threshold ($\gamma \to \infty$) increase, the expected detection delay approaches the theoretical lower bound.
4. Error Analysis: The paper derives an upper bound on the probability of false alarm, explicitly showing how the error depends on the accuracy of the empirical estimate ($\hat{\mu}_0$) and the training size $n_0$.

4. Key Results and Theoretical Findings

• Probability of False Alarm (Lemma 3):
  The probability of error (false alarm) is bounded by:
  $$\mu_0(N(\alpha) < \infty) \le \frac{\alpha}{\beta_1 (2^{\lambda - \log \beta_1} - 1)} \beta_2 + \epsilon_0$$
  Where $\beta_1, \beta_2$ are factors related to the deviation of the empirical estimate from the true distribution, and $\epsilon_0 \to 0$ as the training size $n_0 \to \infty$. This confirms that with sufficient training data, the false alarm rate can be controlled.

• Detection Delay (Theorem 2 & 5):
  Under the post-change distribution $\mu_1$, the expected stopping time (detection delay) conditioned on the training data behaves as:
  $$E_1(M(\gamma) | x_1^{n_0}) \sim \frac{\log \gamma}{D(\mu_1 || \hat{\mu}_0) - \lambda}$$
  As $n_0 \to \infty$, $\hat{\mu}_0 \to \mu_0$, and the delay approaches:
  $$\frac{\log \gamma}{D(\mu_1 || \mu_0)}$$

• Asymptotic Optimality (Theorem 6):
  The paper proves that the proposed test achieves the minimax lower bound for detection delay. Specifically, for any arbitrarily small $\vartheta > 0$, the expected delay of the proposed test is within a factor of $(1+\vartheta)$ of the optimal delay achievable if the distributions were known:
  $$E_1(M) \sim (1+\vartheta) \inf_{S \in S_\gamma} E_1(S)$$
  This establishes that the cost of estimating the distributions vanishes asymptotically.

5. Significance

• Practical Applicability: In real-world scenarios (e.g., industrial quality control, network intrusion detection), the "normal" (pre-change) behavior is often not perfectly known and must be learned from historical data, while the "abnormal" (post-change) behavior is entirely unknown. This paper provides a theoretical foundation for such scenarios in systems with memory (Markovian).
• Bridging Information Theory and Statistics: The work effectively bridges universal source coding (Lempel-Ziv, etc.) with sequential hypothesis testing, demonstrating that universal codes can serve as robust proxies for unknown probability distributions in change detection.
• Foundation for Future Work: The authors suggest that these results can be further generalized to weaken the independence assumptions between pre- and post-change regimes (following Lai's framework) and applied to higher-order Markov sources.

In summary, this paper presents a robust, theoretically sound algorithm for detecting changes in Markovian systems with completely unknown statistical parameters, proving that such a system can achieve the same efficiency as a system with known parameters given sufficient training data.