🔢 mathematics

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

Die Arbeit beweist die Stabilität des Shannon-McMillan-Breiman-Theorems für sublineare, datenabhängige Parsings auf einseitigen Verschiebungsräumen und zeigt, dass die Sublinearität der Blockanzahl eine scharfe Grenze für die Gültigkeit dieses Ergebnisses darstellt.

Ursprüngliche Autoren: Raphael Grondin

Veröffentlicht 2026-04-16

📖 4 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Raphael Grondin

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Das große Puzzle der Vorhersage

Stellen Sie sich vor, Sie haben einen sehr langen Text oder eine lange Abfolge von Symbolen (z. B. eine DNA-Sequenz, ein Musikstück oder einen langen Satz). In der Informationstheorie wollen wir wissen: Wie viel „Überraschung" oder „Information" steckt eigentlich in diesem Text?

Das klassische Theorem von Shannon, McMillan und Breiman (SMB) sagt uns Folgendes: Wenn Sie einen sehr langen Text betrachten, können Sie die gesamte Information berechnen, indem Sie einfach die Wahrscheinlichkeit des gesamten Textes nehmen und den Logarithmus davon bilden. Das ist wie das Wiegen eines ganzen Koffers, um zu wissen, wie schwer er ist.

Das Problem: Der Koffer ist zu groß

In der Praxis ist es oft schwierig, den ganzen Koffer auf einmal zu wiegen. Stattdessen zerlegen wir den Text in kleine Stücke (Blöcke) und wiegen diese einzeln.

Das Problem: Wenn wir die Stücke einzeln wiegen und die Ergebnisse addieren, ignorieren wir die Verbindung zwischen den Stücken. Es ist, als würden wir die einzelnen Puzzleteile einzeln wiegen und dann behaupten, das Gesamtgewicht sei die Summe der Einzelgewichte – ohne zu berücksichtigen, dass die Teile vielleicht zusammenkleben oder sich gegenseitig beeinflussen.

Die Frage der Wissenschaftler war: Können wir den Text in beliebig viele kleine Stücke zerlegen, die Summe der Einzelgewichte berechnen und trotzdem auf das korrekte Gesamtgewicht kommen?

Die Entdeckung: Die „Sublineare" Regel

Die Antwort von Raphaël Grondin ist ein klares „Jein", das sich in eine einfache Regel verwandeln lässt:

Die Regel lautet: Sie dürfen den Text in so viele Teile zerlegen, wie Sie wollen, ABER die Anzahl der Teile darf nicht im gleichen Tempo wachsen wie die Länge des Textes.

Stellen Sie sich vor, Sie haben einen 1000 Meter langen Weg:

Szenario A (Gut): Sie teilen den Weg in 100 kleine Abschnitte auf. Das ist okay. Die Anzahl der Abschnitte (100) wächst viel langsamer als die Weglänge (1000). Das nennt man sublinear.
Szenario B (Schlecht): Sie teilen den Weg in 500 oder 900 Abschnitte auf. Das ist zu viel. Die Anzahl der Abschnitte wächst fast so schnell wie der Weg selbst.

Grondin beweist:

Wenn Sie den Text in wenige, große Blöcke zerlegen (Szenario A), dann ist die Summe der Informationen der Blöcke fast genau so gut wie die Information des ganzen Textes. Die Fehler, die durch das Ignorieren der Verbindungen entstehen, sind so winzig, dass sie im großen Ganzen verschwinden.
Wenn Sie den Text in zu viele, winzige Blöcke zerlegen (Szenario B), dann bricht die Rechnung zusammen. Die Fehler summieren sich auf, und Sie erhalten ein falsches Ergebnis.

Die Analogie: Der Koch und das Rezept

Stellen Sie sich vor, Sie sind ein Koch, der ein riesiges Menü für eine Party kocht (der lange Text).

Das SMB-Theorem sagt: „Das Gericht schmeckt so, wie es ist."
Grondins Forschung untersucht, ob Sie das Gericht in viele kleine Teller aufteilen können, um den Geschmack zu testen.

Wenn Sie das Gericht in ein paar große Teller aufteilen (sublinear), können Sie den Geschmack jedes Tellers probieren, die Ergebnisse addieren und kommen immer noch auf den perfekten Gesamteindruck. Die Art und Weise, wie Sie die Teller schneiden (ob Sie den Rand mitnehmen oder weglassen), ist egal, solange Sie nicht zu viele Teller machen.

Wenn Sie aber versuchen, das Gericht in tausende winzige Krümel zu zerlegen (linear), dann verlieren Sie den Überblick. Der Geschmack jedes Krümelchens ist so stark von der Umgebung abhängig, dass die Summe der Krümel nicht mehr dem Geschmack des Ganzen entspricht.

Warum ist das wichtig?

Diese Erkenntnis ist ein Stabilitätstheorem. Es sagt uns, dass unsere Methoden zur Messung von Information (z. B. in Datenkompression, KI oder Biologie) sehr robust sind.

Flexibilität: Wir müssen nicht perfekt sein. Wir können Daten auf sehr unterschiedliche Weise in Blöcke schneiden (sogar basierend auf dem Inhalt selbst), solange wir nicht zu viele Blöcke erzeugen.
Robustheit: Selbst wenn wir kleine Fehler machen (z. B. ein paar Buchstaben am Rand eines Blocks hinzufügen oder weglassen), ändert das das Endergebnis nicht. Das ist wie beim Bauen einer Mauer: Wenn Sie ein paar Steine hier und da verschieben, aber die Gesamtstruktur erhalten bleibt, steht die Mauer trotzdem stabil.
Die Grenze: Es gibt eine harte Grenze. Wenn man zu viele Blöcke macht, funktioniert die Mathematik nicht mehr. Das ist wie ein Schalter: Solange man unter der Grenze bleibt, ist alles sicher; darüber hinaus bricht es zusammen.

Zusammenfassung in einem Satz

Raphaël Grondin hat bewiesen, dass man einen langen Informationsstrom in viele kleine, unregelmäßige Stücke zerlegen darf, um die Gesamtinformation zu berechnen, solange die Anzahl dieser Stücke im Vergleich zur Gesamtlänge verschwindend klein bleibt – eine Entdeckung, die zeigt, dass Informationstheorie erstaunlich widerstandsfähig gegen „schlechte" Zerlegungen ist, solange man nicht zu weit geht.

1. Problemstellung und Motivation

Das Shannon–McMillan–Breiman (SMB) Theorem ist ein fundamentaler Satz der Informationstheorie und der Ergodentheorie. Es besagt, dass für ein maßerhaltendes Verschiebungssystem $(\Omega, \mathcal{F}, P)$ mit einer shift-invarianten Wahrscheinlichkeitsmaß $P$ der normierte negative Log-Likelihood-Wert eines Blocks $x_1^N$ fast sicher gegen die Entropierate $h(P)$ konvergiert:
$\lim_{N \to \infty} -\frac{1}{N} \log P([x_1^N]) = h(P) \quad P\text{-f.s.}$

In vielen praktischen Anwendungen (z. B. bei der Entropieschätzung mittels Lempel-Ziv-Verfahren oder in der großen Abweichungstheorie) arbeitet man jedoch nicht mit festen Blöcken $x_1^N$ , sondern mit variablen Parsings (Zerlegungen) dieser Blöcke. Ein Parsing zerlegt $x_1^N$ in $c_N$ aufeinanderfolgende Blöcke $w_1^{(N)}, \dots, w_{c_N}^{(N)}$ , deren Längen und Anzahl $c_N$ von der Datenfolge $x$ und der Länge $N$ abhängen können.

Die zentrale Fragestellung des Papers ist: Unter welchen Bedingungen konvergiert die Summe der negativen Log-Likelihoods der einzelnen Parsings-Blöcke, normiert durch $N$ , ebenfalls gegen die Entropierate $h(P)$ ?
$\lim_{N \to \infty} \frac{1}{N} \sum_{i=1}^{c_N} -\log P([w_i^{(N)}]) \stackrel{?}{=} h(P)$

Das Hauptproblem besteht darin, dass die Summe in (1.2) die Abhängigkeiten zwischen den Blöcken ignoriert (sie behandelt sie als unabhängig), während das ursprüngliche SMB-Theorem die globalen Korrelationen im gesamten Block $x_1^N$ berücksichtigt. Zudem können die Blockgrenzen willkürlich datenabhängig gewählt werden, was die Struktur des Systems stören könnte.

2. Methodik

Der Autor entwickelt einen Beweis, der auf der Martingal-Zerlegung basiert, die ursprünglich von Breiman für den Beweis des SMB-Theorems verwendet wurde. Die Methodik lässt sich wie folgt zusammenfassen:

Martingal-Zerlegung: Es wird eine Martingal-Sequenz $Z_n$ definiert, die aus den bedingten Wahrscheinlichkeiten abgeleitet ist ( $Z_n = P([x_2^n])/P([x_1^n])$ ). Der negative Log-Likelihood-Wert $-\log P([x_1^N])$ wird in einen Hauptteil (eine Summe von Martingal-Gliedern) und einen Restterm $J_N$ zerlegt.
Approximation durch Trunkierung: Um die Abhängigkeit von unendlich vielen Koordinaten zu vermeiden, werden die Martingal-Glieder durch Trunkierung auf eine endliche Länge $M$ approximiert.
Analyse der Parsings-Fehler: Der Beweis untersucht, wie sich die Zerlegung auf die einzelnen Blöcke $w_i^{(N)}$ überträgt. Dabei wird gezeigt, dass die Summe der Fehlerterme über alle Blöcke hinweg kontrolliert werden kann, solange die Anzahl der Blöcke $c_N$ sublinear wächst.
Hilfssätze (Lemmas):
- Ein Lemma zeigt, dass der „parsing-abhängige" Term (der durch die willkürlichen Grenzen der Blöcke entsteht) vernachlässigbar ist, wenn $c_N = o(N)$ .
- Ein weiteres Lemma nutzt den Birkhoff-Ergodensatz, um zu zeigen, dass die Summe der Restterme über die gesamte Länge $N$ gegen Null konvergiert.
Gegenbeispiel-Konstruktion: Um die Schärfe der Bedingung zu beweisen, wird ein Gegenbeispiel konstruiert, bei dem $c_N$ linear mit $N$ wächst ( $c_N \sim N/K$ ). In diesem Fall wird gezeigt, dass die Konvergenz für nicht-Markovsche Maße versagt.

3. Hauptergebnisse

Das Paper liefert zwei zentrale Ergebnisse:

A. Der Stabilitätssatz (Theorem 1.1)

Sei $P$ ein shift-invariantes Wahrscheinlichkeitsmaß auf dem einseitigen Shift-Raum über einem endlichen Alphabet. Für jedes datenabhängige Parsing $x_1^N = w_1^{(N)} \dots w_{c_N}^{(N)}$ , das die Sublinearitätsbedingung erfüllt:
$\lim_{N \to \infty} \frac{c_N(x)}{N} = 0 \quad P\text{-f.s.}$
gilt die Konvergenz:
$\lim_{N \to \infty} \frac{1}{N} \sum_{i=1}^{c_N} -\log P([w_i^{(N)}]) = h_P(x) \quad P\text{-f.s. und in } L^1(P).$
Hierbei ist $h_P$ die Entropierate-Funktion aus dem SMB-Theorem.

B. Strukturelle Umformulierung (Approximative Faktorisierung)

Als Korollar (Corollary 1.2) wird ein neues strukturelles Ergebnis für shift-invariante Maße hergeleitet. Für jedes sublineare Parsing gilt:
$P([x_1^N]) = \left( \prod_{i=1}^{c_N} P([w_i^{(N)}]) \right) \exp\{r_N(x)\}$
wobei der Fehlerterm $r_N(x)$ so beschaffen ist, dass $r_N(x)/N \to 0$ fast sicher und in $L^1(P)$ . Dies bedeutet, dass die Wahrscheinlichkeit eines langen Pfades approximativ durch das Produkt der Wahrscheinlichkeiten der sublinearen Blöcke dargestellt werden kann, wobei die Korrelationen zwischen den Blöcken nur einen vernachlässigbaren Fehler verursachen.

C. Notwendigkeit der Sublinearität (Section 2.6)

Der Autor beweist, dass die Bedingung $c_N = o(N)$ scharf ist. Wenn $c_N$ linear mit $N$ wächst (z. B. $c_N \sim N/K$ ), existieren ergodische Maße (die keine Markov-Maße der Ordnung $\le K$ sind) und spezifische Parsings, für die die Konvergenz in (1.2) nicht stattfindet. Dies zeigt, dass die Unterdrückung von Korrelationen durch zu viele Blöcke die Konvergenz zur Entropierate zerstören kann.

D. Robustheit (Section 3.1)

Das Ergebnis ist robust gegenüber subextensiven Störungen der Parsings-Blöcke. Das bedeutet, dass einzelne Blöcke durch Unter- oder Über-Blöcke ersetzt werden können, solange die Gesamtänderung der Länge $o(N)$ beträgt. Die Konvergenz bleibt auch unter solchen Modifikationen erhalten.

4. Signifikanz und Bedeutung

Verallgemeinerung des SMB-Theorems: Das Paper zeigt, dass das SMB-Theorem nicht nur für feste Blöcke gilt, sondern extrem robust gegenüber beliebigen, datenabhängigen Zerlegungen ist, solange die Anzahl der Blöcke sublinear bleibt. Dies ist eine starke Aussage über die Struktur von Entropie in dynamischen Systemen.
Keine starken Abhängigkeitsannahmen nötig: Im Gegensatz zu früheren Arbeiten, die oft Gibbs-Maße oder explizite Entkopplungsbedingungen (Decoupling) zwischen Blöcken voraussetzten, basiert dieser Beweis nur auf der Shift-Invarianz und der Martingal-Struktur.
Anwendbarkeit: Die Ergebnisse sind direkt relevant für:
- Entropieschätzung: Algorithmen wie Lempel-Ziv, die auf Parsings basieren, sind theoretisch gerechtfertigt, auch wenn die Blockgrenzen dynamisch gewählt werden.
- Große Abweichungen: Die Zerlegung von Trajektorien in Blöcke ist ein Standardwerkzeug; das Paper liefert die theoretische Basis dafür, dass solche Zerlegungen die Entropierate nicht verfälschen.
- Thermodynamische Grenze: Die Ergebnisse werden im Sinne der statistischen Mechanik als „Coarse-Graining" interpretiert: Selbst wenn man das System auf einer makroskopischen Ebene (durch Blöcke) betrachtet, bleibt die spezifische Information erhalten.
Erweiterbarkeit: Der Autor skizziert, wie die Ergebnisse auf unendliche Alphabete (Dichten) übertragen werden könnten, indem die Martingal-Zerlegung nach Barron verwendet wird, wobei die Sublinearität der Parsings auch dort als kritischer Faktor für die Kontrolle der Randfehler dient.

Zusammenfassend etabliert Grondin, dass die Entropierate ein inhärent stabiles Maß ist, das gegenüber einer Vielzahl von Daten-zentrierten Zerlegungen resistent ist, solange diese Zerlegungen nicht zu fein werden (d.h. sublinear bleiben).