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

Titel: Stabiliteit van de Shannon–McMillan–Breiman-stelling onder Sublineaire Parsings

Auteur: Raphaël Grondin (Columbia University)
Vakgebied: Informatietheorie, Ergodische theorie, Wiskundige Statistiek

---

1. Probleemstelling

De Shannon–McMillan–Breiman (SMB) stelling is een hoeksteen van de informatietheorie en ergodische theorie. Deze stelling stelt dat voor een verschuiving-invariante waarschijnlijkheidsmaat $P$ op een one-sided eindige shift-ruimte $\Omega = A^{\mathbb{N}}$, de genormaliseerde negatieve log-waarschijnlijkheid van een blok $x_1^N$ convergeert naar de entropiesnelheidsfunctie $h_P(x)$:
$$\lim_{N \to \infty} -\frac{1}{N} \log P([x_1^N]) = h_P(x) \quad P\text{-bijna zeker (a.s.) en in } L^1(P).$$

In veel praktische toepassingen (zoals schatting van entropie via Lempel-Ziv algoritmen, ergodische constructies met stoptijden, of grote afwijkingen-theorie) werkt men niet met volledige blokken $x_1^N$, maar met variabele lengte parsings. Een parsing decomposeert het blok $x_1^N$ in een reeks opeenvolgende sub-blokken $w_1^{(N)}, \dots, w_{c_N}^{(N)}$ waarbij het aantal blokken $c_N$ en de lengtes data-afhankelijk kunnen zijn.

De centrale vraag die dit artikel behandelt is: Onder welke voorwaarden convergeert de som van de negatieve log-waarschijnlijkheden van deze individuele blokken naar dezelfde entropiesnelheid?
$$\frac{1}{N} \sum_{i=1}^{c_N} -\log P([w_i^{(N)}]) \xrightarrow{N \to \infty} h_P(x)$$

De moeilijkheid hierbij is dat deze som de afhankelijkheid tussen opeenvolgende blokken negeert (ze worden behandeld alsof ze onafhankelijk zijn), terwijl de originele SMB-stelling de globale correlaties behoudt. Bovendien kunnen de blok-grenzen willekeurig data-afhankelijk zijn, zonder noodzakelijk te voldoen aan strukturele eisen zoals stoptijden.

---

2. Methodologie

De auteur gebruikt een martingaal-decompositie die inherent is aan de originele bewijzen van de SMB-stelling (specifiek die van Breiman uit 1957/1960), in plaats van te vertrouwen op grote-afwijkingen refinements of Gibbs-achtige aannames.

Kerncomponenten van de methode:

1. Martingaal Decompositie: De negatieve log-waarschijnlijkheid wordt opgesplitst in een hoofdterm (een som van martingaal-differenties) en een restterm. De auteur definieert variabelen $Z_n$ gebaseerd op verhoudingen van cylinder-waarschijnlijkheden.
2. Truncatie: Om de analyse te vereenvoudigen, worden de variabelen getruncateerd op een niveau $M$, zodat ze slechts van een eindig aantal coördinaten afhangen.
3. Decompositie van de Parsing: De som over de geparsed blokken wordt herschreven als een som over de originele martingaal-termen plus een "parsing-afhankelijke" foutterm. Deze foutterm bevat de grenseffecten tussen de blokken.
4. Ergodische Stelling: De Birkhoff-ergodische stelling wordt gebruikt om te laten zien dat de gemiddelde bijdrage van de martingaal-termen convergeert naar de entropie.
5. Sublineaire Voorwaarde: De cruciale aanname is dat het aantal blokken $c_N$ sublineair groeit ten opzichte van de totale lengte $N$ (d.w.z. $c_N = o(N)$ bijna zeker).

---

3. Belangrijkste Resultaten en Bijdragen

Hoofdstelling (Theorema 1.1)

Voor elke verschuiving-invariante maat $P$ en elke data-afhankelijke parsing met $c_N$ blokken die voldoet aan $c_N/N \to 0$ (bijna zeker), geldt:
$$\lim_{N \to \infty} \frac{1}{N} \sum_{i=1}^{c_N} -\log P([w_i^{(N)}]) = h_P(x)$$
Deze convergentie treedt op zowel bijna zeker als in $L^1(P)$.

Dit betekent dat de "verlies van correlatie" door het opsplitsen in blokken verwaarloosbaar is zolang het aantal blokken sublineair blijft.

Structureel Resultaat (Corollary 1.2: Benaderende Factorisatie)

De stelling kan worden herschreven als een structureel resultaat voor cylinder-waarschijnlijkheden. Voor een sublineaire parsing geldt:
$$P([x_1^N]) = \left( \prod_{i=1}^{c_N} P([w_i^{(N)}]) \right) \exp\{r_N(x)\}$$
waarbij $r_N(x)/N \to 0$ bijna zeker en in $L^1(P)$. Dit impliceert dat de gezamenlijke waarschijnlijkheid van een lange reeks bij benadering kan worden gefactoriseerd in de product van de waarschijnlijkheden van de sub-blokken, met een relatieve fout die exponentieel klein is ten opzichte van $N$.

Noodzaak van Sublineariteit (Sectie 2.6)

De auteur bewijst dat de voorwaarde $c_N = o(N)$ scherp is. Als $c_N$ lineair groeit (bijvoorbeeld $c_N \sim N/K$), dan bestaat er een ergodische maat (die geen Markov-maat van orde $\le K$ is) en een parsing waarbij de limiet niet bestaat. Dit wordt aangetoond via een tegenvoorbeeld waarbij twee verschillende parsings (een deterministische en een data-afhankelijke) tot verschillende limieten leiden.

Robuustheid (Sectie 3.1)

Het resultaat is robuust tegen subextensieve perturbaties. Zelfs als de blokken worden vervangen door sub-blokken of super-blokken (waarbij de blokken overlappen of iets korter/langer zijn), zolang de totale wijziging $o(N)$ is, blijft de convergentie naar de entropiesnelheid gelden.

Verbinding met Coarse-graining (Sectie 3.2)

De auteur trekt een parallel met statistische mechanica: de SMB-stelling beschrijft de "microscopische" informatie-inhoud, terwijl de sublineaire parsing een "mesoscopische" of "coarse-grained" beschrijving is. De stelling toont aan dat de specifieke informatie-inhoud invariant blijft onder deze grovere beschrijving, zolang de schaal van de blokkering sublineair blijft.

Extensie naar oneindige alfabeten (Sectie 3.3)

Hoewel het bewijs gebaseerd is op een eindig alfabet, suggereert de auteur dat het resultaat kan worden uitgebreid naar dichtheidsfuncties (Barron's generalisatie) door gebruik te maken van een ergodisch-theoretisch argument (Propositie 3.2) dat sublineaire verzamelingen van indices als verwaarloosbaar beschouwt voor ergodische gemiddelden.

---

4. Significatie en Impact

1. Generaliteit: De stelling geldt voor willekeurige data-afhankelijke parsings, zonder de noodzaak van stoptijden of specifieke afhankelijkheidsstructuren tussen blokken. Dit maakt het zeer breed toepasbaar in algoritmen zoals Lempel-Ziv.
2. Fundamenteel Begrip: Het isoleert een specifieke eigenschap van de Breiman-decompositie: de robuustheid tegen willekeurige sublineaire blokkering. Dit was eerder niet expliciet geïsoleerd in deze algemene vorm.
3. Scherpe Grens: Het artikel definieert precies waar de theorie faalt (bij lineaire groei van het aantal blokken), wat belangrijk is voor het ontwerpen van schattingen en compressie-algoritmen.
4. Methodologische Innovatie: Door de martingaal-decompositie te gebruiken in plaats van complexe grote-afwijkingen-theorie, biedt het een zuiverder en meer structureel inzicht in waarom de SMB-stelling stabiel blijft onder parsing.

Samenvattend bewijst Grondin dat de entropiesnelheid een fundamentele, stabiele grootheid is die niet gevoelig is voor de manier waarop een tijdreeks in sublineaire blokken wordt opgedeeld, zelfs als die opdeling volledig data-gedreven en willekeurig is.