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

1. Problema e Contesto

Il teorema di Shannon–McMillan–Breiman (SMB) è un pilastro fondamentale della teoria dell'informazione e della teoria ergodica. Esso afferma che, per una misura di probabilità invariante per traslazione $P$ su uno spazio di shift a un lato con alfabeto finito, la quantità normalizzata $-\frac{1}{N} \log P([x_1^N])$ converge quasi certamente e in $L^1(P)$ alla funzione di tasso di entropia $h_P(x)$ (che è costante $h(P)$ se $P$ è ergodica).

Il problema affrontato in questo articolo riguarda la stabilità di questo teorema quando non si considera l'intero blocco di lunghezza $N$ ($x_1^N$), ma una sua decomposizione (parsing) in blocchi contigui di lunghezza variabile.
Sia $x_1^N = w_1^{(N)} \dots w_{c_N}^{(N)}$ una partizione del percorso in $c_N$ blocchi, dove le lunghezze dei blocchi e il numero totale $c_N$ possono dipendere dai dati osservati (parsing data-dipendente).
La domanda centrale è: sotto quali condizioni la somma normalizzata delle log-verosimiglianze negative dei singoli blocchi converge ancora al tasso di entropia?
$$\lim_{N \to \infty} \frac{1}{N} \sum_{i=1}^{c_N} -\log P([w_i^{(N)}]) = h_P(x)$$
La difficoltà principale risiede nel fatto che la somma dei blocchi tratta i segmenti come se fossero indipendenti, ignorando le correlazioni tra i blocchi adiacenti che sono invece presenti nel termine globale $-\log P([x_1^N])$. Inoltre, i confini dei blocchi possono essere scelti arbitrariamente in base ai dati, potenzialmente per massimizzare o minimizzare le probabilità condizionate.

2. Metodologia

L'autore sviluppa una dimostrazione basata su una decomposizione martingala, che è alla base della prova originale di Breiman del teorema SMB (1957/1960), ma adattata per gestire decomposizioni arbitrarie.

• Decomposizione Martingala: Viene introdotta una sequenza di variabili aleatorie $Z_n(x) = P([x_2^n]) / P([x_1^n])$ (con $Z_1 = 1/P([x_1])$). Si dimostra che $(Z_n)$ è una martingala rispetto alla filtrazione naturale. Il termine $-\log P([x_1^N])$ può essere scomposto in una somma di termini martingala ($I_N$) e un termine residuo ($J_N$) che tende a zero.
• Analisi dei Blocchi: Applicando questa decomposizione a ciascun blocco $w_i^{(N)}$ del parsing, l'autore separa il contributo "interno" ai blocchi (che si telescopia per ricostruire il termine globale) dai termini di "bordo" o residui ($J$) che sorgono alle interfacce tra i blocchi.
• Stima degli Errori: Il cuore della dimostrazione consiste nel mostrare che la somma dei termini residui associati alle interfacce dei blocchi è trascurabile rispetto a $N$, a condizione che il numero di blocchi $c_N$ cresca sottolinearmente (cioè $c_N = o(N)$ quasi certamente).
• Lemmi Ausiliari: Vengono utilizzati tre lemmi chiave:
  1. Una decomposizione della somma di Birkhoff rispetto al parsing.
  2. La trascurabilità del termine dipendente dal parsing (grazie alla condizione $c_N = o(N)$ e alla limitatezza uniforme dei termini logaritmici su alfabeti finiti).
  3. La trascurabilità della somma di Birkhoff dei termini residui tramite il teorema ergodico puntuale.

3. Contributi Chiave e Risultati Principali

Teorema 1.1 (Risultato Principale)

Il teorema stabilisce che per qualsiasi misura di probabilità invariante per traslazione $P$ e per qualsiasi parsing data-dipendente tale che il numero di blocchi $c_N$ soddisfi:
$$\lim_{N \to \infty} \frac{c_N(x)}{N} = 0 \quad P\text{-quasi certamente}$$
la somma normalizzata delle log-verosimiglianze dei blocchi converge a $h_P(x)$ sia quasi certamente che in $L^1(P)$.
$$\lim_{N \to \infty} \frac{1}{N} \sum_{i=1}^{c_N} -\log P([w_i^{(N)}]) = h_P(x)$$

Corollario 1.2 (Fattorizzazione Approssimata)

Il risultato può essere riformulato come una proprietà strutturale delle probabilità dei cilindri. Per ogni parsing sottolineare, la probabilità del blocco globale è approssimata dal prodotto delle probabilità dei singoli blocchi, con un errore esponenziale che diventa trascurabile:
$$P([x_1^N]) = \left( \prod_{i=1}^{c_N} P([w_i^{(N)}]) \right) \exp\{r_N(x)\}$$
dove $r_N(x)/N \to 0$ quasi certamente e in $L^1$. Questo implica che, a livello asintotico, le correlazioni tra i blocchi di un parsing sottolineare non influenzano il tasso di informazione specifico.

Necessità della Condizione Sottolineare (Sezione 2.6)

L'autore dimostra che la condizione $c_N = o(N)$ è sharp (ottimale). Se il numero di blocchi cresce linearmente (ad esempio $c_N \sim N/K$), è possibile costruire parsing (alcuni deterministici, altri data-dipendenti) e misure ergodiche (non markoviane di ordine basso) per cui la convergenza fallisce. In questi casi, la somma dei blocchi può convergere a valori diversi dal tasso di entropia, a seconda di come i confini dei blocchi catturano le dipendenze a lungo raggio.

Robustezza (Sezione 3.1)

Il risultato è robusto rispetto a perturbazioni sub-estensive dei blocchi. È possibile sostituire ogni blocco $w_i^{(N)}$ con un suo sottoblocco o un super-blocco (che si sovrappone ai vicini), purché la modifica totale della lunghezza sia $o(N)$. Questo rafforza l'analogia con il "coarse-graining" (granulazione grossolana) in meccanica statistica.

4. Significato e Implicazioni

• Generalità: Il risultato vale per qualsiasi procedura di parsing data-dipendente, senza richiedere che i blocchi siano definiti da tempi di arresto o che soddisfino condizioni strutturali specifiche rispetto allo shift. Questo è cruciale per applicazioni pratiche come gli algoritmi di compressione Lempel-Ziv o stime di entropia basate su parsing.
• Indipendenza dalle Correlazioni: Dimostra che, finché il numero di "tagli" nella sequenza è piccolo rispetto alla lunghezza totale, l'ipotesi di indipendenza tra i blocchi (implicita nella somma delle log-verosimiglianze) non introduce errori asintotici nel calcolo dell'entropia.
• Connessione con la Meccanica Statistica: L'autore interpreta il risultato come una forma di "coarse-graining". La descrizione microscopica (l'intera sequenza) e quella mesoscopica (la somma dei blocchi) forniscono lo stesso limite termodinamico (l'entropia specifica), a condizione che la granularità della descrizione mesoscopica non sia troppo fine (sottolineare).
• Estensibilità: Sebbene la dimostrazione si basi su alfabeti finiti, l'autore discute brevemente come il risultato possa estendersi ad alfabeti infiniti (densità) utilizzando il teorema di Barron e proprietà ergodiche, suggerendo che la barriera principale non è la finitudine dell'alfabeto ma la struttura della decomposizione martingala.

In sintesi, il lavoro di Grondin fornisce una giustificazione teorica rigorosa per l'uso di schemi di parsing variabili nella stima dell'entropia, dimostrando che la stabilità del teorema SMB è garantita dalla sola condizione di crescita sottolineare del numero di blocchi, indipendentemente dalla complessità della procedura di parsing.