# Limit superior of $\sum_{j=1}^n X_j$ with $\mathbf{P}[X_j = 1] = \mathbf{P}[X_j = -1] = 0.5$

This is Exercise 2.3.1 from Achim Klenke: »Probability Theory — A Comprehensive Course«.

Exercise: Let $(X_n)_{n\in N}$ be an independent family of $\mathrm{Rad}_{1/2}$ random variables (i.e., $\mathbf{P}[X_n = −1] = \mathbf{P}[X_n = +1] = \frac{1}{2}$) and let $S_n = X_1 + \dots + X_n$ for any $n \in \mathbb{N}$. Show that $\limsup_{n\rightarrow\infty} S_n = \infty$ almost surely.

I can't solve that one.

My thoughts so far: Ok, $A:=\bigl\{\limsup_{n\rightarrow\infty} S_n = \infty \bigr\} = \bigl\{\inf_{n\geq 1}\sup_{\nu\geq n} S_\nu = \infty\bigr\}$ is in the tail field $A\in\mathcal{T}\bigl((X_n)_{n\in\mathbb{N}}\bigr)$. Because $\sup_{\nu\geq n} S_\nu$ is monotonically decreasing, $A$ happens exactly when $A_n := \bigl\{\sup_{\nu\geq n} S_\nu = \infty\bigr\}$ happen for all $n\in\mathbb{N}$. But since $A_{n+1}$ implies $A_n$ (the supremum is monotonically decreasing) and $A_{n+1}^c$ implies $A_{n}^c$ (if $\sup_{\nu\geq n+1} S_\nu$ is finite, $\sup_{\nu\geq n} S_\nu$ will still be finite), we get $A_n = A_{n+1}$ and inductively that $A_1 = A_{n}$.

Now, By Kolmogorov’s $0-1$ Law, $\mathbf{P}[A]\in\{0, 1\}$. So we must show that $\mathbf{P}[A^c] = \mathbf{P}[ A_1^c] < 1$. $$A_1^c = \biguplus_{m\in\mathbb{Z}} \Bigl\{\sup_{\nu\geq 1} S_\nu = m \Bigr\} \, .$$ It seems very plausible that all $\mathbf{P}\biggl[\Bigl\{\sup_{\nu\geq 1} S_\nu = m \Bigr\}\biggr]=0$ for all $m\in\mathbb{Z}$, but how do I prove that?

Thank you!

Ok, I don't know if what I've written is helpful or even right (you can disregard it if you want). The question is:

How do I prove the exercise above?

• Do you know martingales? – saz Jan 22 '15 at 17:25
• No, not yet.... – Ystar Jan 22 '15 at 18:06
• It seems to me that $\mathbf P\{\sup_{\nu\geqslant1} S_\nu = m\}$ should be equal for all $m$, and the only way for a countable sum of real numbers to be finite is if they are all zero. But I'm not sure. – Math1000 Jan 22 '15 at 19:32
• @Math1000: I think we would need to prove that, it isn't that obvious. For example $\mathbf{P}[\{\sup_{\nu\geq1}\frac{1}{\nu} S_\nu = m\}]$ would surely be different for different $m\in\mathbb{Z}$. – Ystar Jan 23 '15 at 4:35
• Yeah, that's why I said I wasn't sure. Just an idea I had. – Math1000 Jan 23 '15 at 12:46

You are on a good start. We already know that $\mathbb{P} (A) \in \{0, 1\}$, but how do we decide which one?

First remark: a sequence $(X_n)$ is in $A^c$ if and only if its sum is bounded from above, i.e., if and only if there exists $N \in \mathbb{N}$ such that $S_n \leq N$ for all $n$.

Now, let's use the symmetry of the random walk. The map $(X_n)_{n \in \mathbb{N}} \mapsto (-X_n)_{n \in \mathbb{N}}$ preserve the distribution of the sequence of random variables (they are still independent, and have the same distribution for all $n$). Hence,

$$\mathbb{P} (\limsup_n S_n = + \infty) = \mathbb{P} (\limsup_n -S_n = + \infty) = \mathbb{P} (\liminf_n S_n = - \infty).$$

If I write $B$ the event $\{\liminf_n S_n = - \infty\}$, then $\mathbb{P} (A) = \mathbb{P} (B) \in \{0, 1\}$. Let $C$ be the complement of $A \cup B$. Then $C$ is exactly the set of sequences which are bounded from above and from below, so the set of bounded sequences. Hence,

$$C = \bigcup_{N \in \mathbb{N}} C_N,$$

where $C_N = \{|S_n| \leq N \ \forall n \in \mathbb{N} \}.$

I sum up. If $\mathbb{P} (C) = 0$, then $\mathbb{P} (A \cup B) = 1$. But $A$ and $B$ have the same probability, so $\mathbb{P} (A) \geq 1/2$. Since $\mathbb{P} (A) \in \{0, 1\}$, this forces $\mathbb{P} (A) = 1$. Hence, I only need to prove that $\mathbb{P} (C) = 0$, that is, that each $C_N$ has measure $0$.

Fix $N$. Remark that if there is a sequence of $2N+1$ elements of $(X_n)$ which have the same sign, then the sequence cannot belong to $C_N$.

For $k \geq 0$, let $D_k$ be the event $\{(X_{(2N+1)k}, X_{(2N+1)k+1}, \cdots, X_{(2N+1)k+2N} \text{ all have the same sign} \}$. Then all the $(D_k)$ are independent, and $\mathbb{P} (D_k) = 2^{-2N - 1}$ for all $k$. By Borel-Cantelli's lemma, almost surely, a sequence will lie in an infinity of $D_k$'s, and thus in at least one of them. Since being in any $D_k$ precludes being in $C_N$, this yields $\mathbb{P} (C_N) = 0$.

Since this is true for all $N$, we get $\mathbb{P} (C) = 0$, and from there, $\mathbb{P} (A) = 1$.

• I think there is a little problem, since $A \notin\mathcal{T}\bigl((X_n)_{n\in\mathbb{N}}\bigr)$, see for example math.stackexchange.com/questions/1231129/…. Only the Cesàro means $\frac{1}{n}\sum_{i=1}^{n}X_i$ are tail-measurable, but not $\sum_{i=1}^{n}X_i$. – user144921 Mar 27 '17 at 16:16
• @user144921: I would agree for $M \in \mathbb{R}$, but here, $M = + \infty$, and the event $A$ is indeed a tail event. The event "the sequence $S_n$ takes arbitrarily large values" does not depend on any finite number of $X_i$'s. – D. Thomine Mar 28 '17 at 11:01

By the CLT, we have the convergence in distribution $$\frac{S_n}{\sqrt{n}}\Longrightarrow N(0,1).$$ Thus since $\sqrt{n}\nearrow \infty$, it follows that $\limsup_n S_n=\infty$ a.s.

More details: Since $\lim_{n\to\infty}\mathbb P(S_n>\sqrt{n})=\int_1^{\infty}e^{-x^2/2}>0$, it follows that $\mathbb P(\limsup_n S_n=\infty)>0$. Thus by the Kolmogorov 0-1 Law, $\limsup_n S_n=\infty$ a.s.