Kingman's subadditive ergodic theorem

by

J. Michael STEELE

School of Engineering and Applied Science, Engineering Quadrangle E220,

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), MoulinOllagnier (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 simplestin conception and in calculationof 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

M1

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 T1 {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 afield A. Thus, we can also assume without loss of generality that for all xcQ 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 xcn 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 xcA(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, (Tn1x) (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 n1 E 'A(N.m)(T k X)

n 00 i=1 n 00 k=l

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

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

limsup, g.(x)/n

<=GK(X)(1E(1B(N,M)IA))+s a.s.

Vol. 25, n' 11989.

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 nonstandard analysis, specifically the nonstandard 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 ElIXiOXill :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./nEO(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 # 13MS8414069.

REFERENCES

M. A. ACKOGLu and L. SUCHESTON, A Ratio Ergodic Theorem for Superadditive Processes,

Z. Wahr. Verw. Gebiete, Vol. 44, 1978, pp. 269278.

M. A. ACKOGLu and U. KItENGLE, Ergodic Theorems for Superadditive Processes, J. far die Reine und Angewante Math., Vol. 323, 1981, pp. 5367.

D. L. BURKHOLDER, Discussion of Prof. Kingman's paper, Ann. Probab., Vol. 1, 1973, pp. 900902.

A. DEL JUNCO, On the Decomposition of a Subadditive Stochastic Process, Ann. Probability, Vol. 5, 1977, pp. 298302.

J. G. DEKEN, Some Limit Result for Longest Common Subsequences, Discrete Math., Vol. 26, 1979, pp. 1731.

Y. DERRIENNIC, Sur le th~or~me ergodique sousadditif, C.R. Acad. Sci. Paris, T. 281, Series A, 1975, pp. 985988.

Y. DERRIENNIC, Quelques applications du th6or~me ergodique sousadditif, Astkrisque, Vol. 74, 1980, pp. 183201.

Y. DERRIENNIC, Un th~orame ergodique presque sousadditif, Ann. Probability, Vol. 11, 1983, pp. 669677.

N. GHouSSOUB and J. M. STEELE, Vector Valued Subadditive Processes and Applications in Probability, Ann. Probability, Vol. 8, 1980, pp. 8395.

T. KAMAE, A Simple Proof of the Ergodic Theorem Using NonStandard Analysis, Israel J. Math., Vol. 42, 1982, pp. 284290.

Y. KATZNELsoN and B. WEiss, A Simple Proof of Some Ergodic Theorems, Israel J. Math., Vol. 42, 1982, pp. 291296.

J. F. C. KiNGmAN, The Ergodic Theory of Subadditive Stochastic Processes, J. Roy. Statist. Soc. Ser., Vol. 1130, 1968, pp. 499510.

J. F. C. KiNGmAN, Subadditive Ergodic Theory, Ann. Probability, Vol. 1, 1973, pp. 883909.

J. F. C. KiNGmAN, Subadditive Processes, Lecture Notes in Math., Vol. 539, 1976, pp. 167223.

T. LiGGET, An Improved Subadditive Ergodic Theorem, Ann. Probability, Vol. 13, 1985, pp. 12791285.

P. LOEB, Conversion from NonStandard 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. 161244.

J. MOULINOLLAGNlER, Th~or6me ergodique presque sousadditif et convergence en moyenne de l`information, Ann. Inst. Henri Poincari, Vol. B19, 1983, pp. 257266.

J. NEYEU, Courte d6monstration du th6or~me ergodique suradditif, Ann. Inst. Henri Poincar~, Vol. B19, 1983, pp. 8790.

Vol. 25, n' 11989.

i i

i

1

98 LM.STEELE

D. ORNsTErN and B. WEIss, The ShannonMeMilIanBreiinan Theorem for a Class of Amenable Groups, Israel J. Math., Vol. 44, 1983, pp. 5360.

K. SCHORGER, A limit theorem for almost monotone sequences of random variables, Stochastic Processes and their Applications, Vol. 21, 1986, pp. 327338.

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, IT33(2), 1987, pp. 263265.

M. D. SMELTZER, Subadditive Stochastic Processes, Bull. Amer. Math. Soc., Vol. 83, 1977, pp. 10541055.

J. M. STEELE, Empirical Processes and Subadditive Processes, Ann. Probability, Vol. 6, 1978, pp. 118127.

(Manuserit repu le Pr mars 1988)

1~

Annales de VInstitut Henri PoincaM Probabilith et Statistiques