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 be a measure-preserving transformation on the probability space , and let be a sequence of functions such that (subadditivity relation). Then
for -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 , with , such that they are subadditive in the sense that
They are equivalent by setting
- with ;
- with .
Proof
Proof due to (J. Michael Steele, 1989).[3]
Subadditivity by partition
Fix some . By subadditivity, for any
We can picture this as starting with the set , and then removing its length tail.
Repeating this construction until the set is all gone, we have a one-to-one correspondence between upper bounds of and partitions of .
Specifically, let be a partition of , then we have
Constructing g
Let , then it is -invariant.
By subadditivity,
Taking the limit, we have
Let , then
That is, , a.e..
Now apply this for all rational .
Reducing to the case of gₙ ≤ 0
By subadditivity, using the partition of into singletons.
By the special case, converges a.e. to a -invariant function.
By Birkhoff's pointwise ergodic theorem, the running average
Bounding the truncation
Fix arbitrary , and construct the truncated function, still -invariant:
Fix . Fix . Fix . 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 . We do this inductively:
Take the smallest not already in a partition.
If , then for some . Take one such – the choice does not matter.
If , then we cut out . Call these partitions “type 1”. Else, we cut out . Call these partitions “type 2”.
Else, we cut out . Call these partitions “type 3”.
Now convert this partition into an inequality:
Since all , we can remove the other kinds of partitions:
The number of type 3 elements is equal to
Peeling off the first qualifier
Remove the qualifier by taking the limit.
By Birkhoff's pointwise ergodic theorem, there exists an a.e. pointwise limit
Peeling off the second qualifier
Remove the qualifier by taking the limit.
Since we have
In detail, the argument is as follows: since , and , we know that for any small , all large enough satisfies everywhere except on a set of size . Thus,
Applications
Taking recovers Birkhoff's pointwise ergodic theorem.
Taking all 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 , we generate it in an equivalent way. A random permutation on is equivalently generated by uniformly sampling points in a square, then find the longest increasing subsequence of that.
Now, define the Poisson point process with density 1 on , and define the random variables to be the length of the longest increasing subsequence in the square . Define the measure-preserving transform by shifting the plane by , then chopping off the parts that have fallen out of .
The process is subadditive, that is, . To see this, notice that the right side constructs an increasing subsequence first in the square , then in the square , and finally concatenate them together. This produces an increasing subsequence in , but not necessarily the longest one.
Also, is ergodic, so by Kingman's theorem, converges to a constant almost surely. Since at the limit, there are points in the square, we have converging to a constant almost surely.
References
- ^ S. Lalley, Kingman's subadditive ergodic theorem lecture notes, http://galton.uchicago.edu/~lalley/Courses/Graz/Kingman.pdf
- ^ Chen. "Subadditive ergodic theorems" (PDF). New York University.
- ^ Steele, J. Michael (1989). "Kingman's subadditive ergodic theorem" (PDF). Annales de l'I.H.P. Probabilités et statistiques. 25 (1): 93–98. ISSN 1778-7017.
- ^ Pitman, Lecture 12: Subadditive ergodic theory, http://www.stat.berkeley.edu/~pitman/s205s03/lecture12.pdf
Recent Comments