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
SUBADDITIVE ERGODIC THEOREM 95
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
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
Annales de I'Institut Henri Poincark Probabilit6s et Statistiques
i
1
SUBADDITIVE ERGODIC THEOREM 97
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