Celebratio Mathematica

Kai Lai Chung

Sums of independent random variables and Markov chains

by Naresh Jain

Pro­fess­or Kai Lai Chung’s con­tri­bu­tions to prob­ab­il­ity the­ory have had a ma­jor in­flu­ence on sev­er­al areas of re­search in the sub­ject. I will re­strict my com­ments to some of his work in two areas, sums of in­de­pend­ent ran­dom vari­ables and the the­ory of Markov chains, which led to a sig­ni­fic­ant amount of fur­ther work, in­clud­ing some of my own.

Sums of independent random variables

Kai Lai has made many out­stand­ing con­tri­bu­tions to this field, but I would like to con­cen­trate on his 1948 pa­per [1]. If \( X_1,X_2,\dots \) is a se­quence of real-val­ued in­de­pend­ent ran­dom vari­ables, and \[ S_n = X_1+X_2+\dots +X_n \quad\text{for }n\geq 1 \] de­notes the se­quence of par­tial sums, then the al­most-sure be­ha­vi­or of “large val­ues” of \( \{S_n\} \) was very well un­der­stood. In­deed, in the in­de­pend­ent and identic­ally dis­trib­uted (i.i.d) case, Hart­man and Wint­ner in 1941 [e2] had already proved their cel­eb­rated law of the it­er­ated log­ar­ithm: \( EX_1 = 0 \) and \( EX^2_1 = 1 \) im­ply \begin{equation} \limsup_{n\to\infty} \frac{S_n}{(2n\log\log n)^{1/2}} = 1 \ \text{ a.s.} \label{eq1}\end{equation} In a more gen­er­al non-i.d. con­text, Feller in 1943 [e3] had writ­ten al­most the fi­nal word. Chung [1] ob­served that, if \( S_n \) is re­placed by \( |S_n| \) in \eqref{eq1}, the as­ser­tion re­mains val­id. However, if \( S^*_n \) de­notes \( \max_{1\leq j\leq n} |S_j| \), then the be­ha­vi­or of “small val­ues” of \( S^*_n \) had yet to be un­der­stood. He stud­ied this prob­lem in [1] in­clud­ing the non-i.d. situ­ation and proved that, de­not­ing \( E(S^2_n) \) by \( s^2_n \), if \( EX_j\equiv 0 \) then, un­der a nat­ur­al third mo­ment as­sump­tion, \begin{equation}\liminf_{n\to\infty} \frac{S^*_n}{s_n(\log\log s_n)^{-1/2}} = 8^{-1/2}\pi \ \text{ a.s.} \label{eq2}\end{equation} To prove this res­ult, he ob­tained the very pro­found prob­ab­il­ity es­tim­ate \begin{equation} \label{eq3} P(S^*_n < cs_n) ={\frac{4}{\pi}}\sum^\infty_{j=0}\frac{(-1)^j}{2j+1} \exp\Bigl(-{\frac{(2j+1)^2\pi^2}{8c^2}}\Bigr) + O\bigl((\log\log s_n/\log s_n)^{1/2}\bigr). \end{equation} This con­tains the prob­ab­il­ity dis­tri­bu­tion for a stand­ard one-di­men­sion­al Browni­an mo­tion pro­cess \( \{B_t:t\geq 0\} \), if \( S^*_n/s_n \) is re­placed by \( \max_{0\leq t\leq 1} |B_t| \) on the left side, and the second term is re­placed by zero on the right side.

In the i.i.d. case, two ques­tions arose after Chung’s work. The first one was raised by Chung him­self: If \( EX_1 = 0 \) and \( EX^2_1 = 1 \), does \eqref{eq2} hold without any fur­ther as­sump­tions, with \( s^2_n = n \)? The second nat­ur­al ques­tion was to ob­tain the ana­logue of \eqref{eq2} if \( X_1 \) is in the do­main of at­trac­tion of a stable law.

As to the first ques­tion, sev­er­al pa­pers ap­peared on the sub­ject get­ting close to the con­di­tions stip­u­lated by Chung. The ques­tion was fi­nally settled in the af­firm­at­ive by Jain and Pruitt in 1975 [e12]. The prob­ab­il­ity dis­tri­bu­tion giv­en in \eqref{eq3} by Chung played a key role in the fi­nal solu­tion. For the second ques­tion, if the in­dex of sta­bil­ity is \( \alpha < 2 \), it was not even clear if one should ex­pect an ana­logue of \eqref{eq2}.

Fris­tedt had already ob­served that an ana­logue of \eqref{eq1} could not ex­ist if \( \alpha < 2 \). However, Fris­tedt and Pruitt [e10] and Jain and Pruitt [e11] showed, un­der dif­fer­ent con­di­tions on \( X_1 \), the ex­ist­ence of a real se­quence \( \{b_n\} \) in­creas­ing to in­fin­ity such that \( \liminf (S^*_n/b_n) = c \) a.s., with \( 0 < c < \infty \). However, it was not clear if the con­stant \( c \) de­pended on the dis­tri­bu­tion of \( X_1 \) or on the lim­it dis­tri­bu­tion alone.

Don­sker and Varadhan [e13] ap­proached these prob­lems through their large-de­vi­ations prob­ab­il­ity es­tim­ates for stable pro­cesses, and ob­tained ex­pli­cit ex­pres­sions for the lim­it con­stants. Jain [e14] was then able to show, through an in­vari­ance prin­ciple, that the lim­it con­stant for the \( \liminf \) be­ha­vi­or of \( (S^*_n/b_n) \) is the same as for the rel­ev­ant stable pro­cess ob­tained by Don­sker and Varadhan [e13].

The story by no means ends here. For a two-para­met­er Browni­an mo­tion \( B(s,t) \) with \( 0\leq s,t\leq 1 \), the lead­ing term of the “small ball” prob­ab­il­ity es­tim­ate for \[ P\bigl(\,\max_{0\leq s,t\leq 1}|B(s,t)|\leq c\bigr) \quad\text{as }c\downarrow 0 \] is of great in­terest, and turned out to be a chal­len­ging prob­lem, solved by Bass [e16] and Talag­rand [e18]. Much work has been done by oth­er au­thors for para­met­er di­men­sion lar­ger than 2; these res­ults, however, are not as defin­it­ive as in the two-di­men­sion­al para­met­er case. Many dif­fi­cult ques­tions still re­main to be answered, and we can ex­pect these in­vest­ig­a­tions to con­tin­ue, all ow­ing their ori­gins to Chung’s pi­on­eer­ing work.

Markov chains

It is dif­fi­cult to ima­gine that any­body work­ing in the area of Markov pro­cesses would not be fa­mil­i­ar with Chung’s mono­graph, Markov Chains with Sta­tion­ary Trans­ition Prob­ab­il­it­ies [3]. This mono­graph deals with count­able-state Markov chains in both dis­crete time (Part I) and con­tinu­ous time (Part II). Much of Kai Lai’s fun­da­ment­al work in the field is in­cluded in this mono­graph. My com­ments will be con­fined to Part I. Here, for the first time, Kai Lai gave a sys­tem­at­ic ex­pos­i­tion of the sub­ject, which in­cludes clas­si­fic­a­tion of states, ra­tio er­god­ic the­or­ems, and lim­it the­or­ems for func­tion­als of the chain.

For a gen­er­al state space, Doeblin had giv­en a clas­si­fic­a­tion scheme in a sem­in­al pa­per in 1937 [e1]. This and oth­er work of Doeblin had a ma­jor im­pact on the field, and led to fur­ther de­vel­op­ments by Chung [2], Doob [e4], Har­ris [e5], and Orey [e6], [e9]. In the early 1960s there were a num­ber of ba­sic in­gredi­ents of a gen­er­al state-space the­ory that would lead to an ex­act coun­ter­part of Part I of Chung [3]. Much fun­da­ment­al ground work, in­clud­ing pos­it­ive re­cur­rence (the so-called Doeblin’s con­di­tion), was done by Doob [e4]. Har­ris [e5] in­tro­duced his re­cur­rence con­di­tion: There ex­ists a nonzero \( \sigma \)-fi­nite meas­ure \( \varphi \) on the state space \( S \) such that \( \varphi (E) > 0 \) im­plies that start­ing from every \( x\in S \),  \( E \) is vis­ited in­fin­itely of­ten a.s. He proved the ex­ist­ence of a (unique) \( \sigma \)-fi­nite in­vari­ant meas­ure \( \pi \) un­der this con­di­tion. If \( \pi (S) = +\infty \), one could call the pro­cess null-re­cur­rent, and one could ask if \( \pi (E) < \infty \) im­plied that, for every \( x\in S \),  \( P^n(x,E)\to 0 \) as \( n\to\infty \); here, \( P^n(x,E) \) de­notes the \( n \)-step trans­ition prob­ab­il­ity from \( x \) to \( E \). This res­ult was con­jec­tured by Orey [e6], and was a nat­ur­al ex­ten­sion to the gen­er­al state-space situ­ation of the cor­res­pond­ing well-known res­ult for a count­able state chain. Un­der Har­ris’s re­cur­rence con­di­tion, one could also ask if an ana­log­ous ra­tio er­god­ic the­or­em was true; namely, if \( \pi (F) > 0 \) and \( \pi (E) < \infty \), does \begin{equation} \label{eq4} \sum^n_{j=1} P^j(x,E)\big/\sum^n_{j=1}P^j(y,F) \,\to\, \pi (E)/\pi (F) \quad\text{as }n\to\infty \end{equation} for all \( x,y\in S \)? These ques­tions were answered in [e7] un­der Chung’s guid­ance. Chung gave an ex­ample, re­por­ted in [e7], to show that in the gen­er­al case (as op­posed to the count­able state space case) \eqref{eq4} is true only for \( \pi \)-al­most all \( x,y \), and not for all \( x,y \). The situ­ation is dif­fer­ent when the state space is not count­able, be­cause one could stay in a \( \pi \)-null set for a rather long time! A little later, Jain and Jam­is­on [e8] in­tro­duced an ir­re­du­cib­il­ity con­di­tion: There ex­ists a nonzero \( \sigma \)-fi­nite meas­ure \( \varphi \) on \( S \) such that \( \varphi (E) > 0 \) im­plies that, start­ing from every \( x\in S \), the pro­cess vis­its \( E \) with pos­it­ive prob­ab­il­ity. In this pa­per they es­sen­tially brought the pro­gram of Doeblin [e1] and Chung [2] to com­ple­tion. Chung’s in­flu­ence can be seen throughout these works. For oth­er work in the area one can refer to mono­graphs by Orey [e9], Re­vuz [e15] and Meyn and Tweedie [e17].


[1]K. L. Chung: “On the max­im­um par­tial sums of se­quences of in­de­pend­ent ran­dom vari­ables,” Trans. Amer. Math. Soc. 64 (1948), pp. 205–​233. MR 0026274 Zbl 0032.​17102 article

[2]K. L. Chung: “The gen­er­al the­ory of Markov pro­cesses ac­cord­ing to Doeblin,” Z. Wahr­schein­lich­keit­s­the­or­ie und Verw. Ge­bi­ete 2 : 3 (1964), pp. 230–​254. MR 0166835 Zbl 0119.​34604 article

[3]K. L. Chung: Markov chains with sta­tion­ary trans­ition prob­ab­il­it­ies, 2nd edition. Die Grundlehren der math­em­at­ischen Wis­senschaften 104. Spring­er (New York, NY), 1967. MR 0217872 Zbl 0146.​38401 book