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

Resumen Técnico: Detección de Cambios Secuencial bajo Configuración Markoviana con Distribuciones Pre y Post-Cambio Desconocidas

1. Problema Abordado

El trabajo se centra en el problema de la detección de cambios secuenciales (SCD) en fuentes de datos que siguen un proceso Markoviano de primer orden (o de orden finito), en lugar de asumir que las observaciones son independientes e idénticamente distribuidas (i.i.d.).

El desafío principal es que, en escenarios del mundo real, tanto la distribución pre-cambio ($\mu_0$) como la distribución post-cambio ($\mu_1$) son desconocidas.

• La mayoría de los métodos clásicos (como la prueba CUSUM de Page) requieren conocer ambas distribuciones.
• Trabajos anteriores (Jacob-Bansal, Malik-Bansal) han abordado casos con distribuciones desconocidas para fuentes i.i.d., pero este artículo extiende esos resultados a fuentes con memoria (Markov) bajo condiciones de mezcla de Berk.

2. Metodología Propuesta

Los autores proponen una extensión del algoritmo CUSUM modificado que integra dos técnicas clave para manejar la incertidumbre en las distribuciones:

• Estimación Empírica de la Distribución Pre-Cambio ($\hat{\mu}_0$):

  • Se utiliza una fase de entrenamiento inicial de longitud $n_0$ (donde se asume que no ha ocurrido ningún cambio).
  • A partir de esta secuencia, se calcula una estimación empírica de la distribución de transición y las probabilidades marginales del proceso Markoviano.
  • Se asume que $n_0$ es lo suficientemente grande para garantizar que la estimación empírica converja a la verdadera distribución $\mu_0$ (Teorema Ergódico).

• Codificación Universal para la Distribución Post-Cambio:

  • En lugar de conocer $\mu_1$, se utiliza un código universal fuertemente puntual (como los códigos Lempel-Ziv o Context Tree Weighting) para estimar la longitud de la secuencia post-cambio.
  • La longitud del código $L(x)$ actúa como un sustituto de la log-verosimilitud $-\log \mu_1(x)$.

• La Prueba Modificada (Test 3 extendido):

  • La estadística de prueba se define como:
    $$\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$$
  • Donde:
    • $-L(\cdot)$ es la longitud del código universal (estimación de $\mu_1$).
    • $-\log \hat{\mu}_0(\cdot)$ es la log-verosimilitud basada en la estimación empírica de la fase pre-cambio.
    • $\lambda$ es un parámetro de desplazamiento (drift) negativo introducido para asegurar que la estadística tenga una tendencia negativa bajo la hipótesis nula (sin cambio).
    • $\gamma$ es el umbral de decisión.

3. Contribuciones Clave

1. Generalización a Fuentes Markovianas: Extienden los resultados de 2022 (diseñados para fuentes i.i.d.) a fuentes estacionarias, ergódicas y Markovianas de orden finito que satisfacen las condiciones de mezcla de Berk.
2. Manejo de Doble Desconocimiento: Demuestran que es posible estimar simultáneamente la distribución pre-cambio (vía empírica) y la post-cambio (vía codificación universal) sin perder la optimalidad asintótica.
3. Análisis de Convergencia y Error:
   • Establecen que la estimación empírica $\hat{\mu}_0$ introduce un error acotado que depende de la longitud de la fase de entrenamiento $n_0$.
   • Demuestran que, a medida que $n_0 \to \infty$, los términos de error ($\beta_1, \beta_2, \epsilon_0$) tienden a 1 o 0, permitiendo recuperar el comportamiento óptimo.
4. Optimalidad Asintótica: Probaron que la prueba propuesta es asintóticamente óptima en el régimen donde la tasa de falsas alarmas tiende a cero.

4. Resultados Principales

El análisis teórico proporciona los siguientes resultados fundamentales:

• Acotación de la Probabilidad de Falsa Alarma:
  Se demuestra que la probabilidad de que la prueba se detenga bajo la distribución pre-cambio $\mu_0$ está acotada superiormente por una función que depende de $\alpha$ (tasa de error deseada) y los parámetros de convergencia de la estimación empírica. A medida que $n_0$ crece, esta probabilidad se controla efectivamente.

• Terminación bajo Hipótesis Alternativa:
  Bajo la distribución post-cambio $\mu_1$, la prueba se detiene con probabilidad 1, siempre que $\lambda < D(\mu_1 || \hat{\mu}_0)$.

• Optimalidad Asintótica (Criterio de Lorden):
  El tiempo esperado de detección ($E_1[M(\gamma)]$) bajo la hipótesis alternativa satisface:
  $$E_1[M(\gamma)] \sim \frac{\log \gamma}{D(\mu_1 || \mu_0)}$$
  Esto coincide con el límite inferior teórico (óptimo) para pruebas de cambio secuencial, demostrando que el uso de la estimación empírica y el código universal no degrada el rendimiento asintótico en comparación con el caso donde las distribuciones son conocidas.

• Condiciones de Estabilidad:
  Se requiere que el parámetro $\lambda$ satisfaga:
  $$D(\mu_0 || \hat{\mu}_0) < \lambda < D(\mu_1 || \hat{\mu}_0)$$
  Lo cual garantiza un desplazamiento negativo bajo $\mu_0$ y un desplazamiento positivo bajo $\mu_1$.

5. Significado e Impacto

• Aplicabilidad Práctica: Este trabajo es crucial para aplicaciones en control de calidad industrial, detección de fallos en redes de comunicación y monitoreo de sistemas donde los datos tienen memoria (dependencia temporal) y los modelos de falla o estado normal no se conocen a priori.
• Avance Teórico: Cierra la brecha entre la teoría de detección de cambios para fuentes i.i.d. y fuentes con memoria, integrando conceptos de teoría de la información (códigos universales) con estadística secuencial.
• Robustez: Proporciona un marco robusto que no requiere suposiciones paramétricas estrictas sobre las distribuciones de cambio, utilizando en su lugar propiedades universales de compresión de datos y estimación empírica.

En conclusión, los autores han logrado extender con éxito el marco de CUSUM modificado a entornos Markovianos con parámetros desconocidos, demostrando que la optimalidad asintótica se mantiene incluso cuando se deben estimar tanto la distribución de referencia como la de cambio utilizando datos observados y códigos universales.