### Kingman's subadditive ergodic theorem by J. Michael STEELE

School of Engineering and Applied Science, Engineering Quadrangle E220,
Princeton University, Prineeton, NJ 08544

ABSTRACT. A simple proof of Kingman's subadditive ergodic theorem is developed from a point of view which is conceptually algorithmic and which does not rely on either a maximal inequality or a combinatorial Riesz lemma.

Key words : Ergodic theorem, subadditive ergodic theorem.

Rtsumt. Une preuve simple du th~or~me ergodique sous-additif de Kinginan est developpee d'unpoint de vue qui est conceptuellement
algorithmique et qui ni se base sur une inegalite maximale ni sur un lemme combinatoire de Riesz.

1. INTRODUCTION

This note concerns the proof and application of the following theorem of Kingman (1968, 1973, 1976):

THEOREM. If T is a measure preserving transformation of the probability space (0, F, g) and {g., 1 :!~ n < oo } is a sequence of integrable functions

Classification A.M.S. : 60010,60 F 15.

i

1

i

1

94 LM.STEELE

satisfying

9. W:5 gn (X) + 9. (T" x), then, with probability one, we have

lim & (x)ln =g (x) 2i  oo,

h  00

where g (x) is an invariant function.
This result has been given elegant proofs in Burkholder (1973), Derriennic (1975), Kadnelson and Weiss (1982), Neveu (1983), and Smeltzer (1977). Also, proofs which relax the original requirements or sharpen the original conclusions have been given by Ackoglu and Sucheston (1978), Ackoglu and Krengle (1981), Ghoussoub and Steele (1980), Del Junco (1977), Derriennic (1983), Ligget (1985), MoulinOllagnier (1983), and Schfirger (1986, 1988). Finally, there have been applications of Kingman's theorem in a variety of areas, including, for example, Deken (1979), Derriennic (1980), Kinginan (1976), and Steele (1978).
The next section gives a proof of Kingman's theorem which is possibly the simplestin conception and in calculationof the available proofs. The third section then examines some evolutionary relationships between approaches to the theory of subadditive processes. Finally, to give an example of its application, Kinginan's theorem is used to prove the ergodic: theorem for vector valued stationary processes.

2. PROOF OF KINGMANS THEOREM

If we define a new process g' by m
M1
g' (x) = gm (x)  g, (T'x),
m
then g' (x):5 0 for all x, and g' again satisfies (1. 1). Since BirkhoWs
m m
ergodic theorem can be applied to the second term of gm, the almost sure
convergence of g'lm implies the almost sure convergence of g.1m. Thus,
without loss of generality, we can assume g. (x):!~ 0.
Next, we cheek that g (x) = lim inf & (x)/n is an invariant function. By
OD
(1 . 1) we have g. (x)/n:S g, (x)/n + gn (T x)ln, so taking the limit inferior we see g(x);5g(Tx). Thus, one finds {g(x)>oc} c T1 {x : g(x)> oc}, and since T is measure preserving, the sets {g(x)>oc} and T` {g(x)>cc} differ by at most a set of measure zero. Consequently, g (T x) =g (x) almost surely, and g is measurable with respect to the invariant afield A. Thus, we can also assume without loss of generality that for all xcQ we have g(T`x)=g(x) for all integers k.

Annales de I'Institut Henri Poincari  Probabilith et Statistiques

Now, given c>O, 1
Gm(x)=max{ M, g(x)} and consider the set

B^ M)= {x: g,(x)>1(G,(x)+F) for all 1:~l:!~N}1

and its complement A(N, M)=B(N, M)'. For any xcn and n~tN, we then decompose the integer set [1, n) into a union of three classes of intervals by the following algorithm:
Begin with k = 1. If k is the least integer in [1, n) which is not in an interval already constructed, then consider T k X. If T k xcA(N, M), then there is an 1 n, we just take the singleton interval [k, k + 1), and finally if T k xCB^ M) we also take the singleton [k, k + 1).
Thus, for any x we have a decomposition of [1, n) into a set of u intervals [,ci, Ti + 1) where g,, (T1i x):!~ li (Gm (x) + F,) with 1 < li < N, and two sets of singletons: one set of v singletons [cri, ai + 1) for which 'B (N. m) (T" x) = 1 and a second set of w singletons contained in (n  N, n).
By the fundamental subadditive inequality (1. 1), our decomposition of [1, n), the invariance of g, and the assumption that g. (x)::~O one has the bounds:

U W
g. (x):5 E g,, (T1i x) + g, (Toi x) + g, (Tn1x) (2.1)
t=1
U
:5 (Gm (x) +F,) E li:!~ Gm (x) 1,+np,.

Also, by the construction of the covering intervals we have
n
n Y, IB(N,m)(T k x)  N:!~ li, (2.2)
k=l

so, by BirkhoWs theorem we find
n n
liminfn` E 1,k lim n1 E 'A(N.m)(T k X)
n  00 i=1 n  00 k=l

=1EGB^M)IA) a.s. (2.3)

By (2. 1) we then conclude for any K::~ M that

limsup, g.(x)/n
<=GK(X)(1E(1B(N,M)IA))+s a.s.

Vol. 25, n' 11989.

i

96 LM.STEELE

Now, the definition of B (N, M) guarantees that 'B (N, M) + 0 a. s. as N .> oo for any fixed K, so letting N ~. oo in (2. 4) implies

limsupg,(x)/n:~GK(X)+E a.s. (2.5)
n  X

Since (2. 5) holds for all K > 0 and E > 0, we see

lim sup & (x)/n:~ lim inf & (x)/n a. s.
n  ~ n  ~
and the proof of Kingman's theorem is complete.

3. RELATIONSHIPS AND AN APPLICATION

Kingman's subadditive ergodic theorem has inspired many proofs, possibly even more than the fundamental ergodic theorem of Birkhoff. The preceding approach was motivated by the proof of BirkhoWs ergodic theorem of Shields (1987), which in turn, owes a debt to Kacnelson and Weiss (1982) and Ornstein and Weiss (1983). Further, the proofs of the Birkhoff and Kingman theorems given in Katznelson and Weiss (1982) have roots in the intriguing proof of BirkhoWs theorem given by Kamae (1982) which drew on techniques of nonstandard analysis, specifically the nonstandard measure theory of Loeb (1975). The reduction to negative processes by means of g' developed independently of this evolutionary
M
chain and was introduced in Ackoglu and Sucheston (1978).
As a simple but typical application of Kingman's subadditive ergodic theorem, we will give a brief proof of the Banach space ergodic theorem which extends the law of large numbers of Mourier (1953). If {X,} denotes an ergodic stationary sequence of Bochner integrable random variables with values in the Banach space F with norm 11. 11, we first note that for the purpose of proving an ergodic theorem there is no loss in assuming that E (X 1) = 0. Next, for any E > 0, the Bochner integrability of the {M implies there is a linear operator 0 on F with finite dimensional range such that ElIXiOXill :58 for each 1:5i
0 (X) converges a. s. and in L' to E 0 (X l). The L' convergence
n F F

then guarantees liEmElIS./nEO(X1)11 11 Sjn 11 converges almost surely, and, by the preceding identification, it must now converge almost surely to zero, exactly as was to be proved.

Annales de I'Institut Henri Poincark  Probabilit6s et Statistiques

i

1

ACKNOWLEDGEMENT

Thanks are due Paul Shields for making available a preliminary version
of Shields (1987). Also, David Aldous, Andr~s del Junco, Ulrich Krengle,
Thomas Ligget, Joseph Marhoul, David Pollard, and Klaus Schfirger
kindly provided comments on a (much) earlier draft. In particular, the
proof of Mourier's theorem was provided by David Aldous for inclusion
here. This research was supported in part by NSF Grant # 13MS8414069.

REFERENCES

M. A. ACKOGLu and L. SUCHESTON, A Ratio Ergodic Theorem for Superadditive Processes,
Z. Wahr. Verw. Gebiete, Vol. 44, 1978, pp. 269278.
M. A. ACKOGLu and U. KItENGLE, Ergodic Theorems for Superadditive Processes, J. far die Reine und Angewante Math., Vol. 323, 1981, pp. 5367.
D. L. BURKHOLDER, Discussion of Prof. Kingman's paper, Ann. Probab., Vol. 1, 1973, pp. 900902.
A. DEL JUNCO, On the Decomposition of a Subadditive Stochastic Process, Ann. Probability, Vol. 5, 1977, pp. 298302.
J. G. DEKEN, Some Limit Result for Longest Common Subsequences, Discrete Math., Vol. 26, 1979, pp. 1731.
Y. DERRIENNIC, Sur le th~or~me ergodique sousadditif, C.R. Acad. Sci. Paris, T. 281, Series A, 1975, pp. 985988.
Y. DERRIENNIC, Quelques applications du th6or~me ergodique sousadditif, Astkrisque, Vol. 74, 1980, pp. 183201.
Y. DERRIENNIC, Un th~orame ergodique presque sousadditif, Ann. Probability, Vol. 11, 1983, pp. 669677.
N. GHouSSOUB and J. M. STEELE, Vector Valued Subadditive Processes and Applications in Probability, Ann. Probability, Vol. 8, 1980, pp. 8395.
T. KAMAE, A Simple Proof of the Ergodic Theorem Using NonStandard Analysis, Israel J. Math., Vol. 42, 1982, pp. 284290.
Y. KATZNELsoN and B. WEiss, A Simple Proof of Some Ergodic Theorems, Israel J. Math., Vol. 42, 1982, pp. 291296.
J. F. C. KiNGmAN, The Ergodic Theory of Subadditive Stochastic Processes, J. Roy. Statist. Soc. Ser., Vol. 1130, 1968, pp. 499510.
J. F. C. KiNGmAN, Subadditive Ergodic Theory, Ann. Probability, Vol. 1, 1973, pp. 883909.
J. F. C. KiNGmAN, Subadditive Processes, Lecture Notes in Math., Vol. 539, 1976, pp. 167223.
T. LiGGET, An Improved Subadditive Ergodic Theorem, Ann. Probability, Vol. 13, 1985, pp. 12791285.
P. LOEB, Conversion from NonStandard Measure Theory and Applications to Probability Theory, Transactions ofthe American Math. Soc., Vol. 211, 1975.
E. MOURIER, A16ments a16atoire dans un espace de Banach, Ann. Inst. H. Poinear~, 1953, pp. 161244.
J. MOULINOLLAGNlER, Th~or6me ergodique presque sousadditif et convergence en moyenne de l`information, Ann. Inst. Henri Poincari, Vol. B19, 1983, pp. 257266.
J. NEYEU, Courte d6monstration du th6or~me ergodique suradditif, Ann. Inst. Henri Poincar~, Vol. B19, 1983, pp. 8790.

Vol. 25, n' 11989.

i i
i

1

98 LM.STEELE

D. ORNsTErN and B. WEIss, The ShannonMeMilIanBreiinan Theorem for a Class of Amenable Groups, Israel J. Math., Vol. 44, 1983, pp. 5360.
K. SCHORGER, A limit theorem for almost monotone sequences of random variables, Stochastic Processes and their Applications, Vol. 21, 1986, pp. 327338.
K. SCHORGER, On Derrienic's almost subadditive ergodic theorem, Acta Math. Hungarica, Vol. 52, 1988 (to appear).
P. SHIELDs, The Ergodic and Entropy Theorems Revisited, LE.E.E. Transactions in Information Theory, IT33(2), 1987, pp. 263265.
M. D. SMELTZER, Subadditive Stochastic Processes, Bull. Amer. Math. Soc., Vol. 83, 1977, pp. 10541055.
J. M. STEELE, Empirical Processes and Subadditive Processes, Ann. Probability, Vol. 6, 1978, pp. 118127.

(Manuserit repu le Pr mars 1988)

1~

Annales de VInstitut Henri PoincaM  Probabilith et Statistiques