 # 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 . 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  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  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 . 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 , 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 . 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  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].

### Works

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

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

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