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_{n}\leq 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 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 that a.e.
$$\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. - $$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, and the ${\textstyle A}$ family grows to the full set.

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

We partition an initial segment of the orbit of ${\textstyle x}$. Equivalently, we partition the set ${\textstyle 0:n-1}$ inductively.

Take the smallest ${\textstyle k}$ not already partitioned.

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 the 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, we must have ${\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}}$. -

$${\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)$$ - 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}$.

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

By pointwise ergodic theorem, there exists an a.e. pointwise limit $${\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$$ - 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$$ we can apply the Markov inequality, to obtain
$$\limsup _{n}{\frac {g_{n}(x)}{n}}\leq g'(x)+\epsilon$$ for a.e. ${\textstyle x\in X}$

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)