Stability of the Shannon--McMillan--Breiman Theorem under Sublinear Parsings

Resumen Técnico: Estabilidad del Teorema de Shannon–McMillan–Breiman bajo Parsers Sublineales

1. Planteamiento del Problema

El Teorema de Shannon–McMillan–Breiman (SMB) es un pilar fundamental de la teoría de la información y la teoría ergódica. Establece que, para una medida de probabilidad invariante bajo desplazamiento $P$ en un espacio de desplazamiento unidireccional de alfabeto finito, la información específica de una secuencia de longitud $N$, dada por $-\frac{1}{N} \log P([x_1^N])$, converge casi seguramente y en $L^1(P)$ a la tasa de entropía $h_P(x)$.

Sin embargo, en muchas aplicaciones prácticas (estimación de entropía basada en algoritmos Lempel-Ziv, construcciones ergódicas, argumentos de grandes desviaciones), no se trabaja con bloques completos $x_1^N$, sino con parsers (descomposiciones) de longitud variable. Un parser descompone la secuencia $x_1^N$ en bloques contiguos $w_1^{(N)}, \dots, w_{c_N}^{(N)}$, donde el número de bloques $c_N$ y sus longitudes pueden depender de los datos observados.

La pregunta central del artículo es: ¿Bajo qué condiciones la suma normalizada de las log-verosimilitudes negativas de estos bloques individuales converge a la tasa de entropía? Es decir, ¿se cumple que:
$$\lim_{N \to \infty} \frac{1}{N} \sum_{i=1}^{c_N(x)} -\log P([w_i^{(N)}(x)]) = h_P(x)$$
El desafío técnico radica en que la suma de los parsers trata los bloques como si fueran independientes, ignorando las correlaciones entre segmentos adyacentes que el teorema SMB original retiene en el bloque global. Además, los límites de los bloques pueden depender arbitrariamente de la muestra y del algoritmo de parsing.

2. Metodología

El autor emplea un enfoque basado en la descomposición de martingalas subyacente a la prueba original de Breiman del teorema SMB, en lugar de depender de refinamientos de grandes desviaciones o suposiciones de tipo Gibbs.

• Descomposición de Martingala: Se define una martingala $Z_n(x) = P([x_2^n]) / P([x_1^n])$ asociada a la medida $P$. Esto permite descomponer $-\log P([x_1^N])$ en una suma de términos que convergen a la entropía más un término residual.
• Análisis de Bloques: Se aplica esta descomposición a cada bloque del parser $w_i^{(N)}$. La suma total se descompone en:
  1. Una suma telescópica que recupera la información del bloque global $x_1^N$.
  2. Términos de error asociados a los límites de los bloques (interacciones entre segmentos).
• Control de Errores: El núcleo de la demostración consiste en probar que los términos de error (que surgen de la falta de independencia entre bloques) son despreciables a escala $N$ siempre que el número de bloques $c_N$ crezca sublinealmente (es decir, $c_N = o(N)$ casi seguramente).
• Lemas Auxiliares: Se utilizan tres lemas clave:
  • Una descomposición de la suma de Birkhoff en función del parser.
  • La demostración de que el término dependiente del parser es $o(N)$ bajo la condición de sublinealidad.
  • La demostración de que la suma de Birkhoff de los términos residuales converge a cero.

3. Contribuciones Clave y Resultados Principales

A. Teorema Principal (Teorema 1.1)
El resultado central establece que para cualquier medida invariante $P$ y cualquier parser (incluso dependiente de los datos) cuyo número de bloques $c_N$ satisfaga $c_N/N \to 0$ casi seguramente, la convergencia a la tasa de entropía se mantiene:
$$\lim_{N \to \infty} \frac{1}{N} \sum_{i=1}^{c_N} -\log P([w_i^{(N)}]) = h_P(x) \quad \text{c.s. y en } L^1(P).$$
Esto valida el uso de esquemas de estimación de entropía basados en parsers (como LZ77/LZ78) sin necesidad de suposiciones adicionales de mezcla o independencia entre bloques.

B. Factorización Aproximada (Corolario 1.2)
El teorema implica un nuevo resultado estructural: la probabilidad de un cilindro $P([x_1^N])$ se puede aproximar por el producto de las probabilidades de los bloques del parser, con un error exponencialmente pequeño relativo a $N$:
$$P([x_1^N]) = \left( \prod_{i=1}^{c_N} P([w_i^{(N)}]) \right) \exp\{r_N(x)\},$$
donde $r_N(x)/N \to 0$. Esto significa que, bajo parsers sublineales, la dependencia entre bloques es asintóticamente insignificante para la probabilidad total.

C. Umbral de Agudeza (Sección 2.6)
El autor demuestra que la condición de sublinealidad es necesaria y aguda. Se construye un contraejemplo donde, si el número de bloques crece linealmente ($c_N \sim N/K$), la convergencia falla para medidas que no son procesos de Markov de orden bajo. Esto demuestra que no se puede relajar la condición a crecimiento lineal en general.

D. Robustez bajo Perturbaciones (Sección 3.1)
El resultado es robusto frente a perturbaciones subextensivas. Si los bloques del parser se modifican (reemplazando un bloque por un sub-bloque o un super-bloque) de tal manera que la longitud total modificada sea $N + o(N)$, la convergencia se mantiene. Esto conecta el resultado con la noción de "coarse-graining" (granulación gruesa) en mecánica estadística.

E. Extensiones (Sección 3.3)
Se discute la extensión potencial del teorema a alfabetos infinitos mediante el teorema SMB generalizado de Barron para densidades, sugiriendo que la descomposición de martingalas y el control de los términos de frontera mediante el teorema ergódico podrían permitir esta generalización.

4. Significado e Impacto

• Fundamentación Teórica de Algoritmos Prácticos: El trabajo proporciona una justificación rigurosa para el uso de algoritmos de compresión y estimación de entropía (como los basados en Lempel-Ziv) que operan mediante parsers de longitud variable, demostrando que su rendimiento asintótico no depende de la estructura específica del parser, sino únicamente de que el número de bloques sea sublineal.
• Independencia de Estructuras Específicas: A diferencia de trabajos anteriores que requerían suposiciones de "decoupling" (desacoplamiento) o propiedades de Gibbs, este resultado es válido para cualquier medida invariante y cualquier procedimiento de parsing, lo que lo hace extremadamente general.
• Interpretación Termodinámica: La robustez bajo perturbaciones subextensivas refuerza la analogía entre la teoría de la información y la mecánica estadística, donde las propiedades macroscópicas (tasa de entropía) son insensibles a cambios microscópicos o en la granulación de la descripción, siempre que estos cambios no sean extensivos.
• Límites de la Generalización: Al demostrar que el crecimiento lineal de bloques rompe la convergencia, el artículo delimita claramente los límites de validez de la factorización aproximada en sistemas dinámicos generales.

En conclusión, Grondin establece que la estructura de martingala subyacente al teorema SMB es inherentemente robusta frente a la fragmentación de la secuencia en bloques, siempre que dicha fragmentación no sea demasiado densa (sublineal), proporcionando así un puente sólido entre la teoría ergódica abstracta y las aplicaciones prácticas de procesamiento de datos.