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
![{\displaystyle \lim _{n\to \infty }{\frac {g_{n}(x)}{n}}=:g(x)\geq -\infty }](https://wikimedia.org/api/rest_v1/media/math/render/svg/0cf38cbc70d113cc053c3529916ed4fb5835a1d5)
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
Then there exists a random variable
such that
,
is invariant with respect to
, and
a.s..
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
We can visualize
as hill-climbing on the graph of
. If
actually causes a nontrivial amount of hill-climbing, then we would get a spatial contraction, and so
does not preserve measure. Therefore
a.e.
Let
, then
and since both sides have the same measure, by squeezing, they are equal a.e..
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.
Now, construct the sequence
which satisfies
for all
.
By the special case,
converges a.e. to a
-invariant function.
By Birkhoff's pointwise ergodic theorem, the running average
converges a.e. to a
-invariant function. Therefore, their sum does as well.
Bounding the truncation
Fix arbitrary
, and construct the truncated function, still
-invariant:
With these, it suffices to prove an a.e. upper bound
since it would allow us to take the limit
, then the limit
, giving us a.e.
And by squeezing, we have
converging a.e. to
. Define two families of sets, one shrinking to the empty set, and one growing to the full set. For each "length"
, define
Since
, the
family shrinks to the empty set.
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:
where
are the heads of the partitions, and
are the lengths.
Since all
, we can remove the other kinds of partitions:
By construction, each
, thus
Now it would be tempting to continue with
, but unfortunately
, so the direction is the exact opposite. We must lower bound the sum
.
The number of type 3 elements is equal to
If a number
is of type 2, then it must be inside the last
elements of
. Thus the number of type 2 elements is at most
. Together, we have the lower bound:
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
satisfying
At the limit, we find that for a.e.
,
Peeling off the second qualifier
Remove the
qualifier by taking the
limit.
Since we have
and
as
, we can apply the same argument used for proving Markov's inequality, to obtain
for a.e.
.
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,
with probability
. Now take both
.
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