Kingman's subadditive ergodic theorem

In mathematics, Kingman's subadditive ergodic theorem is one of several ergodic theorems. It can be seen as a generalization of Birkhoff's ergodic theorem. Intuitively, the subadditive ergodic theorem is a kind of random variable version of Fekete's lemma (hence the name ergodic). As a result, it can be rephrased in the language of probability, e.g. using a sequence of random variables and expected values. The theorem is named after John Kingman.

Statement of theorem

Let $T$ be a measure-preserving transformation on the probability space $(\Omega ,\Sigma ,\mu )$, and let $\{g_{n}\}_{n\in \mathbb {N} }$ be a sequence of $L^{1}$ functions such that $g_{n+m}(x)\leq g_{n}(x)+g_{m}(T^{n}x)$ (subadditivity relation). Then

$\lim _{n\to \infty }{\frac {g_{n}(x)}{n}}=:g(x)\geq -\infty$

for $\mu$-a.e. x, where g(x) is T-invariant. If T is ergodic, then g(x) is a constant.

Proof

Subadditivity by partition

Fix some ${\textstyle n\geq 1}$. By subadditivity, for any ${\textstyle l\in 1:n-1}$ $$g_{n}\leq g_{n-l}+g_{l}\circ T^{n-l}$$

We can picture this as starting with the set ${\textstyle 0:n-1}$, and then removing its length${\textstyle l}$ tail.

Repeating this construction until the set ${\textstyle 0:n-1}$ is all gone, we have a one-to-one correspondence between upper bounds of ${\textstyle g_{n}}$ and partitions of ${\textstyle 1:n-1}$.

Specifically, let ${\textstyle \{k_{i}:(k_{i}+l_{i}-1)\}_{i}}$ be a partition of ${\textstyle 0:n-1}$, then we have $$g_{n}\leq \sum _{i}g_{l_{i}}\circ T^{k_{i}}$$

Constructing g

Let ${\textstyle g:=\liminf g_{n}/n}$, then it is ${\textstyle T}$-invariant.

By subadditivity, $${\frac {g_{n+1}}{n+1}}\leq {\frac {g_{1}+g_{n}\circ T}{n+1}}$$

Taking the ${\textstyle n\to \infty }$ limit, we have $$g\leq g\circ T$$ We can visualize ${\textstyle T}$ as hill-climbing on the graph of ${\textstyle g}$. If ${\textstyle T}$ actually causes a nontrivial amount of hill-climbing, then we would get a spatial contraction, and so ${\textstyle T}$ does not preserve measure. Therefore ${\textstyle g=g\circ T}$ a.e.

Let ${\textstyle c\in \mathbb {R} }$, then $$\{g\geq c\}\subset \{g\circ T\geq c\}=T^{-1}(\{g\geq c\})$$ and since both sides have the same measure, by squeezing, they are equal a.e..

That is, ${\textstyle g(x)\geq c\iff g(Tx)\geq c}$, a.e..

Now apply this for all rational ${\textstyle c}$.

Reduce to the case of gₙ ≤ 0

By subadditivity, using the partition of ${\textstyle 0:n-1}$ into singletons. $${\begin{aligned}g_{1}&\leq g_{1}\\g_{2}&\leq g_{1}+g_{1}\circ T\\g_{3}&\leq g_{1}+g_{1}\circ T+g_{1}\circ T^{2}\\&\cdots \end{aligned}}$$ Now, construct the sequence $${\begin{aligned}f_{1}&=g_{1}-g_{1}\\f_{2}&=g_{2}-(g_{1}+g_{1}\circ T)\\f_{3}&=g_{3}-(g_{1}+g_{1}\circ T+g_{1}\circ T^{2})\\&\cdots \end{aligned}}$$ which satisfies ${\textstyle f_{n}\leq 0}$ for all ${\textstyle n}$.

By the special case, ${\textstyle f_{n}/n}$ converges a.e. to a ${\textstyle T}$ -invariant function.

By Birkhoff's pointwise ergodic theorem, the running average $${\frac {1}{n}}(g_{1}+g_{1}\circ T+g_{1}\circ T^{2}+\cdots )$$converges a.e. to a ${\textstyle T}$ -invariant function. Therefore, their sum does as well.

Bounding the truncation

Fix arbitrary ${\textstyle \epsilon ,M>0}$, and construct the truncated function, still ${\textstyle T}$ -invariant: $$g':=\max(g,-M)$$ With these, it suffices to prove an a.e. upper bound$$\limsup g_{n}/n\leq g'+\epsilon$$since it would allow us to take the limit ${\textstyle \epsilon =1/1,1/2,1/3,\dots }$, then the limit ${\textstyle M=1,2,3,\dots }$, giving us a.e.

$$\limsup g_{n}/n\leq \liminf g_{n}/n=:g$$And by squeezing, we have ${\textstyle g_{n}/n}$ converging a.e. to ${\textstyle g}$. Define two families of sets, one shrinking to the empty set, and one growing to the full set. For each "length" $L=1,2,3,\dots$, define$$B_{L}:=\{x:g_{l}/l>g'+\epsilon ,\forall l\in 1,2,\dots ,L\}$$ $$A_{L}:=B_{N}^{c}=\{x:g_{l}/l\leq g'+\epsilon ,\exists l\in 1,2,\dots ,L\}$$Since ${\textstyle g'\geq \liminf g_{n}/n}$, the ${\textstyle B}$ family shrinks to the empty set.

Fix ${\textstyle x\in X}$. Fix ${\textstyle L\in \mathbb {N} }$. Fix ${\textstyle n>N}$. The ordering of these qualifiers is vitally important, because we will be removing the qualifiers one by one in the reverse order.

To prove the a.e. upper bound, we must use the subadditivity, which means we must construct a partion of the set ${\textstyle 0:n-1}$. We do this inductively:

Take the smallest ${\textstyle k}$ not already in a partition.

If ${\textstyle T^{k}x\in A_{N}}$, then ${\textstyle g_{l}(T^{k}x)/l\leq g'(x)+\epsilon }$ for some ${\textstyle l\in 1,2,\dots L}$. Take one such ${\textstyle l}$ – the choice does not matter.

If ${\textstyle k+l-1\leq n-1}$, then we cut out ${\textstyle \{k,\dots ,k+l-1\}}$. Call these partitions “type 1”. Else, we cut out ${\textstyle \{k\}}$. Call these partitions “type 2”.

Else, we cut out ${\textstyle \{k\}}$. Call these partitions “type 3”.

Now convert this partition into an inequality: $$g_{n}(x)\leq \sum _{i}g_{l_{i}}(T^{k_{i}}x)$$ where ${\textstyle k_{i}}$ are the heads of the partitions, and ${\textstyle l_{i}}$ are the lengths.

Since all ${\textstyle g_{n}\leq 0}$, we can remove the other kinds of partitions: $$g_{n}(x)\leq \sum _{i:{\text{type 1}}}g_{l_{i}}(T^{k_{i}}x)$$ By construction, each ${\textstyle g_{l_{i}}(T^{k_{i}}x)\leq l_{i}(g'(x)+\epsilon )}$, thus $${\frac {1}{n}}g_{n}(x)\leq g'(x){\frac {1}{n}}\sum _{i:{\text{type 1}}}l_{i}+\epsilon$$ Now it would be tempting to continue with ${\textstyle g'(x){\frac {1}{n}}\sum _{i:{\text{type 1}}}l_{i}\leq g'(x)}$, but unfortunately ${\textstyle g'\leq 0}$, so the direction is the exact opposite. We must lower bound the sum ${\textstyle \sum _{i:{\text{type 1}}}l_{i}}$.

The number of type 3 elements is equal to$$\sum _{k\in 0:n-1}1_{B_{L}}(T^{k}x)$$If a number ${\textstyle k}$ is of type 2, then it must be inside the last ${\textstyle L-1}$ elements of ${\textstyle 0:n-1}$. Thus the number of type 2 elements is at most ${\textstyle L-1}$. Together, we have the lower bound:$${\frac {1}{n}}\sum _{i:{\text{type 1}}}l_{i}\geq 1-{\frac {L-1}{n}}-{\frac {1}{n}}\sum _{k\in 0:n-1}1_{B_{L}}(T^{k}x)$$

Peeling off the first qualifier

Remove the ${\textstyle n>N}$ qualifier by taking the ${\textstyle n\to \infty }$ limit.

By Birkhoff's pointwise ergodic theorem, there exists an a.e. pointwise limit$$\lim _{n}{\frac {1}{n}}\sum _{k\in 0:n-1}1_{B_{L}}(T^{k}x)\to {\bar {1}}_{B_{L}}(x)$$ satisfying
$$\int {\bar {1}}_{B_{L}}=\mu (B_{L});\quad {\bar {1}}_{B_{L}}(x)\in [0,1]$$ At the limit, we find that for a.e. ${\textstyle x\in X,L\in \mathbb {N} }$, $$\limsup _{n}{\frac {g_{n}(x)}{n}}\leq g'(x)(1-{\bar {1}}_{B_{L}}(x))+\epsilon$$

Peeling off the second qualifier

Remove the ${\textstyle L\in \mathbb {N} }$ qualifier by taking the ${\textstyle L\to \infty }$ limit.

Since we have $$\int {\bar {1}}_{B_{L}}=\mu (B_{L})\to 0$$and ${\bar {1}}_{B_{L}}\geq {\bar {1}}_{B_{L+1}}\geq \cdots$ as $1_{B_{L}}\geq 1_{B_{L+1}}\geq \cdots$, we can apply the same argument used for proving Markov's inequality, to obtain
$$\limsup _{n}{\frac {g_{n}(x)}{n}}\leq g'(x)+\epsilon$$ for a.e. ${\textstyle x\in X}$.

In detail, the argument is as follows: since ${\bar {1}}_{B_{L}}\geq {\bar {1}}_{B_{L+1}}\geq \cdots \geq 0$, and $\int {\bar {1}}_{B_{L}}\to 0$, we know that for any small $\delta ,\delta '>0$, all large enough $L$ satisfies ${\bar {1}}_{B_{L}}(x)<\delta$ everywhere except on a set of size $\geq \delta '$. Thus,$$\limsup _{n}{\frac {g_{n}(x)}{n}}\leq g'(x)(1-\delta )+\epsilon$$with probability $\geq 1-\delta '$. Now take both $\delta ,\delta '\to 0$.

Applications

Taking $g_{n}(x):=\sum _{j=0}^{n-1}f(T^{j}x)$ recovers Birkhoff's pointwise ergodic theorem.

Kingman's subadditive ergodic theorem can be used to prove statements about Lyapunov exponents. It also has applications to percolations and probability/random variables.

External links

• Theorem proof (Steele)