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

Resumo Técnico: Estabilidade do Teorema de Shannon–McMillan–Breiman sob Parsings Sublineares

1. Problema e Contexto

O Teorema de Shannon–McMillan–Breiman (SMB) é um pilar fundamental da teoria da informação e da teoria ergódica. Ele estabelece que, para uma medida de probabilidade invariante por deslocamento $P$ em um espaço de deslocamento unidirecional de alfabeto finito, a entropia específica de uma sequência finita $x_1^N$ converge quase certamente e em $L^1(P)$ para a função de taxa de entropia $h_P(x)$:
$$\lim_{N \to \infty} -\frac{1}{N} \log P([x_1^N]) = h_P(x)$$
onde $[x_1^N]$ denota o cilindro definido pela sequência.

No entanto, muitas aplicações práticas (como estimativa de entropia baseada em Lempel-Ziv, construções ergódicas e argumentos de grandes desvios) não trabalham com blocos completos $x_1^N$, mas sim com parsings (decomposições) variáveis e dependentes dos dados da sequência em blocos menores $w_1^{(N)}, \dots, w_{c_N}^{(N)}$.

A questão central abordada pelo autor é: Sob quais condições a soma normalizada das negativas log-verossimilhanças desses blocos parsidos converge para a taxa de entropia?
$$\frac{1}{N} \sum_{i=1}^{c_N(x)} -\log P([w_i^{(N)}(x)]) \xrightarrow{?} h_P(x)$$
A dificuldade reside no fato de que essa soma substitui a probabilidade do bloco global (que retém todas as correlações) por um produto de probabilidades de blocos menores, efetivamente tratando os blocos como se fossem independentes. Além disso, as fronteiras dos blocos podem depender arbitrariamente dos dados observados.

2. Metodologia

O autor desenvolve uma prova baseada na decomposição de martingale subjacente à prova original de Breiman do teorema SMB (1957), em vez de depender de refinamentos de grandes desvios ou suposições de decoupling explícito (como medidas de Gibbs).

Estrutura da Prova:

1. Decomposição de Martingale: Utiliza-se a identidade $-\log P([x_1^N]) = I_N(x) + J_N(x)$, onde $I_N$ é uma soma de Birkhoff de uma variável aleatória associada a um martingale e $J_N$ é um termo residual que tende a zero.
2. Análise de Parsings: O parsing é definido como uma decomposição $x_1^N = w_1^{(N)} \cdots w_{c_N}^{(N)}$. O autor introduz uma decomposição análoga para cada bloco $w_i^{(N)}$.
3. Lemas Auxiliares:
   • Lema 2.4 (Decomposição Soma de Birkhoff-Parsing): Demonstra que a soma dos termos residuais dos blocos parsidos pode ser limitada por uma soma de Birkhoff global de uma função de erro $\psi$ e um termo dependente do parsing.
   • Lema 2.5 (Negligibilidade do Termo Dependente do Parsing): Prova que, se o número de blocos $c_N$ cresce sublinearmente ($c_N = o(N)$), o termo dependente do parsing é negligenciável na escala $N$.
   • Lema 2.7 (Negligibilidade da Soma de Birkhoff): Utiliza o Teorema Ergódico de Birkhoff para mostrar que a média temporal do erro de truncamento converge para zero.
4. Convergência: Combina-se a convergência do termo global (pelo teorema SMB original) com a negligibilidade dos termos de erro introduzidos pela decomposição em blocos para provar a estabilidade.

3. Principais Contribuições e Resultados

A. Teorema Principal (Teorema 1.1)
O resultado central estabelece que, para qualquer medida invariante por deslocamento $P$ e qualquer parsing dependente de dados onde o número de blocos $c_N$ satisfaz:
$$\lim_{N \to \infty} \frac{c_N(x)}{N} = 0 \quad \text{quase certamente (P-a.s.)}$$
a seguinte convergência vale:
$$\lim_{N \to \infty} \frac{1}{N} \sum_{i=1}^{c_N(x)} -\log P([w_i^{(N)}(x)]) = h_P(x) \quad \text{P-a.s. e em } L^1(P).$$
Isso significa que a taxa de entropia é recuperada mesmo quando a sequência é fragmentada em blocos arbitrários, desde que o número de fragmentos seja sublinear em relação ao comprimento total.

B. Reformulação Estrutural (Corolário 1.2)
O teorema implica um novo resultado estrutural sobre a fatoração aproximada de probabilidades de cilindros. Para qualquer parsing sublinear:
$$P([x_1^N]) = \left( \prod_{i=1}^{c_N} P([w_i^{(N)}]) \right) \exp\{r_N(x)\}$$
onde $r_N(x)/N \to 0$ quase certamente e em $L^1$. Isso generaliza a ideia de que, sob invariância por deslocamento, a dependência entre blocos adjacentes torna-se assintoticamente insignificante se o número de "quebras" for pequeno o suficiente.

C. Necessidade da Condição Sublinear (Seção 2.6)
O autor demonstra que a condição $c_N = o(N)$ é aguda (sharp). Ele constrói um contraexemplo onde, se $c_N$ cresce linearmente (ex: $c_N \sim N/K$), a convergência falha para medidas que não são processos de Markov de ordem finita. Isso mostra que a sublinearidade não é apenas uma conveniência técnica, mas uma condição necessária para a validade do resultado em geral.

D. Robustude (Seção 3.1)
O resultado é robusto sob perturbações subextensivas. Se os blocos originais forem substituídos por sub-blocos ou super-blocos (com sobreposições limitadas), desde que a modificação total do comprimento seja $o(N)$, a convergência para a entropia permanece válida.

E. Extensões (Seção 3.3)
O autor discute brevemente como o resultado pode ser estendido para alfabetos infinitos (densidades), baseando-se no trabalho generalizado de Barron, sugerindo que a barreira principal (finitude do alfabeto) pode ser contornada usando argumentos ergódicos diretos em vez de limitações uniformes.

4. Significado e Implicações

• Generalidade: O teorema remove a necessidade de suposições fortes sobre a estrutura de dependência entre os blocos (como ser um processo de Markov ou satisfazer condições de Gibbs). A única exigência é a invariância por deslocamento e o crescimento sublinear do número de blocos.
• Aplicações em Estimativa de Entropia: Valida teoricamente esquemas de estimativa de entropia baseados em parsings (como variantes de Lempel-Ziv) que operam em blocos variáveis, garantindo que a estimativa converge para a entropia verdadeira mesmo com a perda de informações de correlação entre as fronteiras dos blocos.
• Analogia Termodinâmica: A Seção 3.2 conecta o resultado ao conceito de "coarse-graining" (granulação grosseira) na mecânica estatística. O teorema mostra que a informação específica é uma propriedade macroscópica estável que não é destruída pela agregação de observáveis microscópicos, desde que a granulação não seja excessiva (sublinear).
• Limites Fundamentais: O contraexemplo na Seção 2.6 define um limite fundamental: se o número de blocos for grande demais (linear), a perda de correlação nas fronteiras acumula-se o suficiente para distorcer a estimativa da entropia, a menos que o processo tenha memória finita (Markoviano).

Em suma, o trabalho de Grondin fornece uma fundamentação rigorosa e geral para o uso de parsings em análise de informação, estabelecendo que a taxa de entropia é um invariante robusto sob decomposições de dados, desde que a granulação da decomposição seja suficientemente fina em relação ao tamanho da amostra.