Kingman's subadditive ergodic theorem explained

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.^[1] Intuitively, the subadditive ergodic theorem is a kind of random variable version of Fekete's lemma (hence the name ergodic).^[2] 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\inN} be a sequence of L ^{1} functions such that g _{n+m} (x)\le g _{n(x)+g} ^{nx)} ^{m(T} (subadditivity relation). Then\lim _{n\toinfty} (g _{n(x)})/(n) = :g(x)\ge -inf ty

for

\mu -a.e. x, where g(x) is T-invariant.

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

Equivalent statement

Given a family of real random variables $X(m,\; n)$, with , such that they are subadditive in the sense thatThen there exists a random variable $Y$ such that

Subadditivity by partition

Fix some $n\backslash geq\; 1$. By subadditivity, for any $l\backslash in\; 1:n-1$ $$g\_n\; \backslash leq\; g\_\; +\; g\_l\; \backslash circ\; T^$$

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

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

Specifically, let $\backslash \_i$ be a partition of $0:n-1$, then we have $$g\_n\; \backslash leq\; \backslash sum\_i\; g\_\backslash circ\; T^$$

Constructing g

Let $g\; :=\; \backslash liminf\; g\_n/n$, then it is $T$-invariant.

By subadditivity, $$\backslash frac\; \backslash leq\backslash frac$$

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

Let $c\backslash in\; \backslash R$, then $$\backslash \; \backslash subset\; \backslash \; =\; T^(\backslash )$$ and since both sides have the same measure, by squeezing, they are equal a.e..

That is, $g(x)\; \backslash geq\; c\; \backslash iff\; g(Tx)\; \backslash geq\; c$, a.e..

Now apply this for all rational $c$.

Reducing to the case of gₙ ≤ 0

By subadditivity, using the partition of $0:n-1$ into singletons. Now, construct the sequence which satisfies $f\_n\; \backslash leq\; 0$ for all $n$.

By the special case, $f\_n/n$ converges a.e. to a $T$-invariant function.

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

Bounding the truncation

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

$$\backslash limsup\; g\_n/n\; \backslash leq\; \backslash liminf\; g\_n/n\; =:\; g$$And by squeezing, we have $g\_n/n$ converging a.e. to $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 , ... , define$$B\_L\; :=\; \backslash$$ $$A\_L\; :=\; B\_L^c\; =\; \backslash$$Since $g\text{'}\; \backslash geq\; \backslash liminf\; g\_n/n$, the $B$ family shrinks to the empty set.

Fix $x\; \backslash in\; X$. Fix $L\; \backslash in\; \backslash N$. Fix $n\; >\; L$. 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 partition of the set $0:n-1$. We do this inductively:

Take the smallest $k$ not already in a partition.

If $T^k\; x\; \backslash in\; A\_N$, then $g\_l(T^k\; x)/l\; \backslash leq\; g\text{'}(x)\; +\; \backslash epsilon$ for some $l\backslash in\; 1,\; 2,\; \backslash dots\; L$. Take one such $l$ – the choice does not matter.

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

Else, we cut out $\backslash$. Call these partitions “type 3”.

Now convert this partition into an inequality: $$g\_n(x)\; \backslash leq\; \backslash sum\_i\; g\_(T^x)$$ where $k\_i$ are the heads of the partitions, and $l\_i$ are the lengths.

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

The number of type 3 elements is equal to$$\backslash sum\_\; 1\_(T^k\; x)$$If a number $k$ is of type 2, then it must be inside the last $L-1$ elements of $0:n-1$. Thus the number of type 2 elements is at most $L-1$. Together, we have the lower bound:$$\backslash frac\; 1n\; \backslash sum\_\; l\_i\; \backslash geq\; 1\; -\; \backslash frac\; -\; \backslash frac\; 1n\; \backslash sum\_\; 1\_(T^k\; x)$$

Peeling off the first qualifier

Remove the $n>L$ qualifier by taking the $n\backslash to\; \backslash infty$ limit.

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

Peeling off the second qualifier

Remove the $L\; \backslash in\; \backslash N$ qualifier by taking the $L\backslash to\; \backslash infty$ limit.

Since we have $$\backslash int\; \backslash bar\; 1\_\; =\; \backslash mu(B\_L)\; \backslash to\; 0$$and

\bar 1 _{B _{L}} \geq \bar 1 _{B _{L+1}} \geq … as 1 _{B _{L}} \geq 1 _{B _{L+1}} \geq … , we can apply the same argument used for proving Markov's inequality, to obtain
$$\backslash limsup\_n\; \backslash frac\; \backslash leq\; g\text{'}(x)\; +\; \backslash epsilon$$for a.e. $x\backslash in\; X$.

In detail, the argument is as follows: since

\bar 1 _{B _{L}} \geq \bar 1 _{B _{L+1}} \geq … \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,$$\backslash limsup\_n\; \backslash frac\; \backslash leq\; g\text{'}(x)(1-\backslash delta)\; +\; \backslash epsilon$$with probability \geq 1- \delta' . Now take both \delta, \delta' \to 0 .

Applications

Taking

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

Taking all

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

To study the longest increasing subsequence of a random permutation

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

Now, define the Poisson point process with density 1 on

[ 0 , inf ty) ^{2} , and define the random variables M ^{*} _{k} to be the length of the longest increasing subsequence in the square [ 0 , k) ^{2} . Define the measure-preserving transform T by shifting the plane by ( -1 , -1 ) , then chopping off the parts that have fallen out of [ 0 , inf ty) ^{2} .

The process is subadditive, that is,

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 [ 0 , k) ^{2} , then in the square [k, k + m) ^{2} , and finally concatenate them together. This produces an increasing subsequence in [ 0 , k + m) ^{2} , but not necessarily the longest one.

Also,

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

Notes and References

1. S. Lalley, Kingman's subadditive ergodic theorem lecture notes, http://galton.uchicago.edu/~lalley/Courses/Graz/Kingman.pdf
2. Web site: Subadditive ergodic theorems. Chen. New York University.
3. Steele . J. Michael . 1989 . Kingman's subadditive ergodic theorem . Annales de l'I.H.P. Probabilités et statistiques . en . 25 . 1 . 93–98 . 1778-7017.
4. Pitman, Lecture 12: Subadditive ergodic theory, http://www.stat.berkeley.edu/~pitman/s205s03/lecture12.pdf