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

1. Problem Statement

The Shannon–McMillan–Breiman (SMB) theorem is a foundational result in information theory and ergodic theory. It states that for a shift-invariant probability measure $P$ on a sequence space $\Omega = A^{\mathbb{N}}$ (where $A$ is a finite alphabet), the normalized negative log-probability of a block $x_1^N$ converges almost surely to the entropy rate function $h_P(x)$:
$$\lim_{N \to \infty} -\frac{1}{N} \log P([x_1^N]) = h_P(x)$$
However, in many practical applications (e.g., Lempel-Ziv compression, cross-entropy estimation, and large deviation theory), one does not analyze the full block $x_1^N$ directly. Instead, the sequence is decomposed into a parsing of variable-length contiguous blocks:
$$x_1^N = w_1^{(N)} \cdot w_2^{(N)} \cdots w_{c_N}^{(N)}$$
where $c_N$ is the number of blocks. The paper investigates the convergence of the parsing-based sum:
$$S_N = \frac{1}{N} \sum_{i=1}^{c_N} -\log P([w_i^{(N)}])$$
The Core Question: Under what conditions does $S_N$ converge to the same entropy rate $h_P$ as the original SMB theorem?
The Challenge: The sum $S_N$ treats blocks as if they were independent (multiplying their probabilities), thereby ignoring the correlations between successive blocks that are present in the joint probability $P([x_1^N])$. Furthermore, the parsing can be data-dependent (the block boundaries depend on the observed sequence $x$), potentially introducing bias.

2. Methodology

The author employs a martingale decomposition approach, rooted in Breiman's original proof of the SMB theorem, rather than relying on large-deviation principles or specific Gibbsian assumptions.

Key Technical Tools:

1. Martingale Decomposition: The proof utilizes a martingale sequence $Z_n(x) = P([x_2^n]) / P([x_1^n])$. The negative log-probability of a block is decomposed into a "main" term (a sum of log-martingale differences) and a "residual" term.
   $$-\log P([x_1^N]) = \sum_{k=0}^{N-1} \log Z(T^k x) + \text{Residual}$$
2. Truncation: To handle the infinite nature of the shift space, the author introduces truncated versions of the martingale terms ($Z_M$) to ensure quantities depend only on finitely many coordinates.
3. Birkhoff Sums vs. Parsing Sums: The proof compares the sum over the parsing blocks against the standard Birkhoff sum over the entire sequence. The difference is shown to be negligible if the number of blocks $c_N$ grows slowly enough.
4. Auxiliary Lemmas:
   • Lemma 2.4: Decomposes the error introduced by parsing into a "Birkhoff sum" term (which vanishes by the Ergodic Theorem) and a "parsing-dependent" boundary term.
   • Lemma 2.5: Proves that the boundary term is $o(N)$ (negligible) if and only if the number of blocks $c_N$ is sublinear ($c_N/N \to 0$).
   • Lemma 2.7: Establishes the convergence of the Birkhoff sums of the residual terms to zero.

3. Key Contributions and Results

A. Main Theorem (Theorem 1.1)

The paper establishes that for any shift-invariant probability measure $P$ and any parsing (even data-dependent and arbitrary) where the number of blocks $c_N$ satisfies the sublinear condition:
$$\lim_{N \to \infty} \frac{c_N(x)}{N} = 0 \quad P\text{-a.s.}$$
the normalized sum of negative log-likelihoods converges to the entropy rate:
$$\lim_{N \to \infty} \frac{1}{N} \sum_{i=1}^{c_N} -\log P([w_i^{(N)}]) = h_P(x)$$
This convergence holds both almost surely and in $L^1(P)$.

B. Structural Reformulation (Corollary 1.2)

The result implies an approximate factorization of cylinder probabilities. For any sublinear parsing:
$$P([x_1^N]) = \left( \prod_{i=1}^{c_N} P([w_i^{(N)}]) \right) \exp\{r_N(x)\}$$
where the error term $r_N(x)$ satisfies $r_N(x)/N \to 0$ almost surely and in $L^1$. This means that under sublinear parsings, the joint probability behaves asymptotically like the product of the block probabilities, despite the presence of correlations.

C. Sharpness of the Condition (Section 2.6)

The paper proves that the sublinear condition is sharp.

• If $c_N$ grows linearly (e.g., $c_N \sim N/K$), convergence can fail for non-Markov measures.
• The author constructs a counterexample where a deterministic parsing and a data-dependent parsing (both with linear block counts) yield different limits for the normalized sum, proving that the limit does not exist or does not equal $h_P$ in the general case.

D. Robustness (Section 3.1)

The result is robust under subextensive perturbations. If the parsing blocks are modified by adding or removing a sub-extensive amount of symbols (i.e., the total modification is $o(N)$), the convergence to $h_P$ still holds. This includes replacing blocks with sub-blocks or super-blocks, provided the overlap with neighbors is controlled.

E. Extensions (Section 3.3)

The author discusses extending these results to non-finite alphabets (densities) using Barron's generalized SMB theorem. While the martingale decomposition extends naturally, the boundary term control requires careful handling of integrability, which is suggested to be solvable via ergodic theorems for set-valued functions (Proposition 3.2).

4. Significance and Interpretation

• Universality: The result holds for any shift-invariant measure, without requiring mixing conditions, Gibbs properties, or specific structural assumptions on the parsing procedure.
• Data-Dependence: It validates the use of adaptive, data-dependent parsing schemes (like those in Lempel-Ziv algorithms) for entropy estimation, provided the number of parsed segments does not grow linearly with the data length.
• Thermodynamic Analogy: The paper draws a parallel to coarse-graining in statistical mechanics. The parsing represents a "mesoscopic" view of the system. The theorem proves that as long as the coarse-graining is not too fine (sublinear blocks), the macroscopic observable (entropy rate) remains invariant and identical to the microscopic limit.
• Methodological Insight: By isolating the robustness of Breiman's martingale decomposition, the paper provides a new structural understanding of the SMB theorem, showing that the "independence" assumption inherent in parsing sums is asymptotically valid as long as the number of boundaries is negligible relative to the sequence length.

In summary, Grondin's work rigorously justifies the stability of entropy rate estimation via block parsings, defining the precise boundary (sublinearity) between valid and invalid regimes for general shift-invariant processes.