Stationary-ergodic LZ77 phrase-length theorem

Fix $\epsilon >0$ and put $S_n=\{w:P(X_0^{n-1}=w)\ge 2^{-n(h+\epsilon \mathrm{/}2)}\}$. By [F1], the current block belongs to $S_n$ with probability tending to one, and $\mathrm{\mid }{S}_n\mathrm{\mid }\le 2^{n(h+\epsilon \mathrm{/}2)}$ because its word probabilities sum to at most one. For $w\in S_n$, let $E_w=\{X_0^{n-1}=w\}$. On $E_w$, $R_n$ is the first positive return to $E_w$ under the inverse shift, which is also measure-preserving and ergodic. Hence [F2] gives ${\int }_{E_w}{R}_{n}dP=1$. On $E_w$, $1_{\{R_n>M\}}\le R_n\mathrm{/}M$ for $M=2^{n(h+\epsilon )}$, so integrating and using [F2] yields $P(E_w\cap \{R_n>M\})\le 1\mathrm{/}M=2^{-n(h+\epsilon )}$. Summing over $S_n$ and adding the atypical-block probability proves $P(R_n>2^{n(h+\epsilon )})\to 0$.

Suppose $h>0$ and choose $0<\epsilon <h$. Fix a past $x^{-}=(\dots ,x_{-2},x_{-1})$ and a current word $w\in {\mathcal{A}}^n$. Write $x^{-}⌢w$ for their concatenation on coordinates $i<0$ and $0\le i<n$; every coordinate used in a match of the current block at positive offset lies in this range. For any fixed offset $j\ge 1$, the match equations $w_i=(x^{-}⌢w{)}_{-j+i}$ determine at most one word $w$: for $i<j$ the right side is fixed by the past, and for $i\ge j$ it equals the already determined letter $w_{i-j}$. Therefore at most $m$ words have $R_n\le m$ for any positive integer $m$.

Put $m_n=\lfloor 2^{n(h-\epsilon )}\rfloor$ and, for each past $x^{-}$, let $G_n(x^{-})=\{w:q_{\mathrm{\infty },n}(w\mid x^{-})\le 2^{-n(h-\epsilon \mathrm{/}2)}\}$. By [F3], the actual block lies outside $G_n(X^{-})$ with probability tending to zero. For fixed $x^{-}$, let $C_n(x^{-},m_n)$ be the words whose recurrence offset is at most $m_n$; step 1.2 gives $\mathrm{\mid }{C}_n(x^{-},m_n)\mathrm{\mid }\le m_n$. Splitting its conditional mass into $G_n(x^{-})$ and its complement gives $P(R_n\le m_n\mid X^{-}=x^{-})\le m_n{2}^{-n(h-\epsilon \mathrm{/}2)}+{\sum }_{w\mathrm{\notin }{G}_n(x^{-})}{q}_{\mathrm{\infty },n}(w\mid x^{-})\mathrm{.}$ The first term is at most $2^{-n\epsilon \mathrm{/}2}$, and the integral of the second term over pasts is exactly $P(X_0^{n-1}\mathrm{\notin }{G}_n(X^{-}))$ by the conditional-law property in [F3]. Therefore $P(R_n\le m_n)\to 0$, so the lower tail below $h-\epsilon$ vanishes.

If $h=0$, the lower tail below $h-\epsilon$ is impossible because $R_n\ge 1$. If $h>0$, step 2.1 handles $0<\epsilon <h$, while larger lower-tail thresholds are also impossible. Together with step 1.1 this proves $n^{-1}{\log }_2{R}_n\to h$ in probability. Kac recurrence makes $R_n$ finite almost surely for every $n$, after intersecting the countably many full-measure recurrence events.

For $h>0$ and all sufficiently large integer $W$, fix $0<\delta <1\mathrm{/}h$ and set $n_{-}(W)=\lfloor (1\mathrm{/}h-\delta ){\log }_{2}W\rfloor$, $n_{+}(W)=\lceil (1\mathrm{/}h+\delta ){\log }_{2}W\rceil$. Step 3.1 implies $P(R_{n_{-}(W)}\le W)\to 1$ and $P(R_{n_{+}(W)}>W)\to 1$: choose $\eta >0$ with $(h+\eta )(1\mathrm{/}h-\delta )<1<(h-\eta )(1\mathrm{/}h+\delta )$ and apply convergence in probability at these indices. Since a match of length $n+1$ is also a match of length $n$, $R_n\le R_{n+1}$. Thus with probability tending to one, $n_{-}(W)\le L_W<n_{+}(W)$. Divide by ${\log }_{2}W$ and let $\delta \downarrow 0$ to obtain $L_W\mathrm{/}{\log }_{2}W\to 1\mathrm{/}h$ in probability.