# 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, 2015 at 17:25
• No, not yet.... Jan 22, 2015 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. Jan 22, 2015 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}$. Jan 23, 2015 at 4:35
• Yeah, that's why I said I wasn't sure. Just an idea I had. Jan 23, 2015 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$. Mar 27, 2017 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. Mar 28, 2017 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.

I find a different way to solve this exercise.

Let $$S^*:= \limsup_{n\to \infty }S_n$$ and $$S_n:= \sum_{k=1}^nX_k$$. Then its easy to see that $$\{ \omega :S^*=\infty \}$$ is a tail event so $$\Pr [S^*=\infty ]\in\{0,1\}$$. Then the sequence $$(X_k)$$ induces the product measure $$\mu:= \left(\frac12 \delta _1+\frac12 \delta_{-1}\right)^{\otimes {\mathbb N}}$$ in $$\{-1,1\}^{{\mathbb N}}$$ and setting $$A:=\{x\in \{-1,1\}^{{\mathbb N}}:\limsup_{n\to \infty } \sum_{k=1}^n x_k\geqslant 0\}$$ then we have that $$\Pr [S^*\geqslant 0]=\mu(A)$$.

Now note that for every $$x\in \{-1,1\}^{{\mathbb N}}$$ such that $$\limsup_{n\to \infty }\sum_{k=1}^n x_k<0$$ (where $$x_k$$ is the $$k$$-th coordinate of $$x$$) then the sequence $$y$$ defined by $$y_k:=-x_k$$ have the property that $$\limsup_{n\to \infty }\sum_{k=1}^n y_k> 0$$, so $$\mu(A^\complement )=\mu(-A^\complement )$$ by the definition of $$\mu$$ (where $$-A^\complement$$ is the set of sequences in $$A^\complement$$ with the signs changed), so $$-A^\complement \subset A$$, hence it follows that $$\mu(A^\complement )\leqslant \mu(A)$$ and consequently $$\Pr [S^*\geqslant 0]>0$$.

By last note that if $$\limsup_{n\to \infty }\sum_{k=1}^n x_k=m$$ then the sequence $$y$$ defined by $$y_k:=x_{k+1}$$ and $$y_1:=1$$ have the property that $$\limsup_{n\to \infty }\sum_{k=1}^n y_k=m+1$$ so $$\Pr [S^*=m+1]\geqslant \Pr [S^*=m]$$ following a similar argument as the above one. Then the conclusion follows.