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

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

for ${\displaystyle \mu }$ -a.e. x, where g(x) is T-invariant.

In particular, if T is ergodic, then g(x) is a constant.

Equivalent statement edit

Given a family of real random variables ${\textstyle X(m,n)}$ , with ${\textstyle 0\leq m<n\in \mathbb {N} }$ , such that they are subadditive in the sense that

They are equivalent by setting

• ${\textstyle g_{n}=X(0,n)}$  with ${\textstyle n\geq 1}$ ;
• ${\textstyle X(m,m+n)=g_{n}\circ T^{m}}$  with ${\textstyle m\geq 0}$ .

Proof due to (J. Michael Steele, 1989).^[3]

Subadditivity by partition edit

Fix some ${\textstyle n\geq 1}$ . By subadditivity, for any ${\textstyle l\in 1:n-1}$ 

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

Constructing g edit

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

By subadditivity,

Taking the ${\textstyle n\to \infty }$  limit, we have

Let ${\textstyle c\in \mathbb {R} }$ , then

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

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

Reducing to the case of gₙ ≤ 0 edit

By subadditivity, using the partition of ${\textstyle 0:n-1}$  into singletons.

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

Bounding the truncation edit

Fix arbitrary ${\textstyle \epsilon ,M>0}$ , and construct the truncated function, still ${\textstyle T}$  -invariant:

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:

Since all ${\textstyle g_{n}\leq 0}$ , we can remove the other kinds of partitions:

The number of type 3 elements is equal to

Peeling off the first qualifier edit

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

Peeling off the second qualifier edit

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

Since we have

In detail, the argument is as follows: since ${\displaystyle {\bar {1}}_{B_{L}}\geq {\bar {1}}_{B_{L+1}}\geq \cdots \geq 0}$ , and ${\displaystyle \int {\bar {1}}_{B_{L}}\to 0}$ , we know that for any small ${\displaystyle \delta ,\delta '>0}$ , all large enough ${\displaystyle L}$  satisfies ${\displaystyle {\bar {1}}_{B_{L}}(x)<\delta }$  everywhere except on a set of size ${\displaystyle \geq \delta '}$ . Thus,

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

Taking all ${\displaystyle g_{n}}$  constant functions, we recover the Fekete’s subadditive lemma.

Kingman's subadditive ergodic theorem can be used to prove statements about Lyapunov exponents. It also has applications to percolations and longest increasing subsequence.^[4]

Longest increasing subsequence edit

To study the longest increasing subsequence of a random permutation ${\displaystyle \pi }$ , we generate it in an equivalent way. A random permutation on ${\displaystyle 1:n}$  is equivalently generated by uniformly sampling ${\displaystyle n}$  points in a square, then find the longest increasing subsequence of that.

Now, define the Poisson point process with density 1 on ${\displaystyle [0,\infty )^{2}}$ , and define the random variables ${\displaystyle M_{k}^{*}}$  to be the length of the longest increasing subsequence in the square ${\displaystyle [0,k)^{2}}$ . Define the measure-preserving transform ${\displaystyle T}$  by shifting the plane by ${\displaystyle (-1,-1)}$ , then chopping off the parts that have fallen out of ${\displaystyle [0,\infty )^{2}}$ .

The process is subadditive, that is, ${\displaystyle M_{k+m}^{*}\geq M_{k}^{*}+M_{m}^{*}\circ T^{k}}$ . To see this, notice that the right side constructs an increasing subsequence first in the square ${\displaystyle [0,k)^{2}}$ , then in the square ${\displaystyle [k,k+m)^{2}}$ , and finally concatenate them together. This produces an increasing subsequence in ${\displaystyle [0,k+m)^{2}}$ , but not necessarily the longest one.

Also, ${\displaystyle T}$  is ergodic, so by Kingman's theorem, ${\displaystyle M_{k}^{*}/k}$  converges to a constant almost surely. Since at the limit, there are ${\displaystyle n=k^{2}}$  points in the square, we have ${\displaystyle L_{n}^{*}/{\sqrt {n}}}$  converging to a constant almost surely.