Kingman's subadditive ergodic theorem
/ KING-man /
Kingman's theorem is the great generalisation of Birkhoff's: it provides a law of large numbers for quantities that are not sums but only subadditive — where the cost of a long stretch is at most the sum of the costs of its pieces. Many natural quantities (matrix-product norms, first-passage times, longest increasing subsequences) are exactly subadditive and not additive, and Birkhoff cannot touch them; Kingman can.
Setup: let T be a measure-preserving transformation and let (g_n)_(n>=1) be a sequence of integrable functions that is subadditive over the dynamics, meaning g_(m+n) <= g_m + g_n compose T^m almost surely for all m, n. Assume the integrals are bounded below appropriately (inf_n E[g_n]/n > -infinity). Then g_n / n converges almost surely (and in L^1) to an invariant limit g, and E[g] = lim_n E[g_n]/n = inf_n E[g_n]/n. The infimum formula for the mean is Fekete's subadditive lemma; the deep content is the almost-sure convergence of the random sequence g_n/n, not merely of its expectation. When T is ergodic the limit g is the deterministic constant lambda = inf_n E[g_n]/n. Birkhoff is the special case g_n = sum_(k<n) f compose T^k, where subadditivity holds with equality (additivity).
Its applications are exactly the places where additivity breaks. (1) Lyapunov exponents: g_n = log ||M_n M_(n-1) ... M_1|| for a stationary sequence of random matrices is subadditive (norm is submultiplicative), so (1/n) log ||product|| -> lambda_1, the top Lyapunov exponent (Furstenberg-Kesten). (2) First-passage percolation: the minimal passage time T(0, n e_1) between two points on Z^d is subadditive, giving the time constant mu = lim T(0, n e_1)/n. (3) Longest increasing subsequence of a random permutation: its length L_n satisfies E[L_n] / sqrt(n) -> 2 (Vershik-Kerov / Logan-Shepp), proved via a subadditive structure. The honest caveat: Kingman tells you the limit exists and equals an infimum, but it generally does NOT give you the value of the constant or its fluctuations — finding lambda explicitly (or even bounding it) is usually a separate, hard problem.
Random matrix products: let M_1, M_2, ... be iid 2x2 invertible matrices and S_n = M_n ... M_1. Since ||S_(m+n)|| <= ||product of last n|| * ||product of first m||, the logs are subadditive, so (1/n) log ||S_n|| -> lambda_1 almost surely. That deterministic lambda_1 is the top Lyapunov exponent governing exponential growth of the product.
Subadditivity (submultiplicative norms, minimal passage times) is the structure Kingman converts into an almost-sure linear growth rate.
Kingman delivers existence of the constant, not its value. The longest-increasing-subsequence constant is 2 and the first-passage time constant mu is, for most lattices, still unknown in closed form — subadditivity guarantees a limit, computing it is a separate fight.