$\lim\sup$ of random variables a.s. converging to $\infty$

Question

Revisiting my Probability Theory book, I found an exercise in the chapter concerning the zero-one-law of Kolmogorov where it says

One proves the following: Let $(X_n)_{n \in \mathbb{N}}$ independent random variables with $\mathbf{P}(X_n = -1)= \mathbf{P}(X_n = 1) = \frac{1}{2}$, let $S_n = X_1 + ... + X_n , n \in \mathbb{N}$. Then $\lim\sup _{n \to \infty} S_n = \infty$ a.s.

Why can this be true and - more specifically - why is $\lim\sup _{n \to \infty} S_n = \infty$ almost sure when the individual random variables have equal chance of cancelling out each other?

Answer 1

First, there is no contradiction with the fact that "the random variables have equal chance of cancelling out each other". You don't have that $S_n$ almost surely goes to infinity, but only that its limsup is infinite. This just means that you reach arbitrarily large elements of $\mathbb{N}$. By the way, the same argument will show that $\liminf S_n=-\infty$, so again, there is no contradiction.

Now, first, you show that $P(\limsup S_n=+\infty)$ is 0 or 1. Indeed, the event $\limsup S_n=+\infty$ is the same as the event $\limsup (S_n-S_k)=+\infty$. But $S_n-S_k=X_{k+1}+...+X_{n}$, so this event is measurable with respect to $\mathcal{F}_{k+1}=\sigma (X_{k+1},X_{k+2},...)$. This is true for all $k$, so by independence and by the 0-1 law, you have the conclusion.

Observe then that since the random variables are symmetric, the two events $\limsup S_n=+\infty$ and $\liminf S_n=-\infty$ have the same probability (which is 0 or 1). To conclude, you just need to prove that the random walk is almost surely not bounded. This will mean that $P(\limsup S_n=+\infty \cup \liminf S_n=-\infty)=1$ and will thus give you the result you want.

Answer 2

It might help first to think about what the distribution of $S_n$ is. The central limit theorem implies it looks roughly like a normal with mean zero and variance $\sqrt{n}.$ So sure, zero is the most likely value here, but the fluctuations keep growing as $n$ increases.

Here is a picture of 100 paths of $S_n$ for $n$ up to 1000.

Notice that the paths are all roughly contained within a square root envelope. Essentially, the paths $S_n$ "wander" within this envelope. This isn't a proof of this fact (or even a precise statement of it), but hopefully seeing the picture makes it more plausible.

$\limsup_n S_n=\infty$ means that for any $k\in \mathbb Z,$ we will have $S_n>k$ infinitely many times. This is consistent with, and in fact expected from the behavior I described.

Answer 3

Note given any random variables $(Y_n)_{n \geq 1}$, we have that $Y^* := \limsup Y_n$ and $Y_* := \liminf Y_n$ are both $\mathcal T((Y_n)_{n \geq 1})$-measurable. By the Kolmogorov $0$-$1$ law, given any $m \in \mathbb N$, $\mathbb P[Y^* \geq m] \in \{0,1\}$ and $\mathbb P[Y_* \leq -m] \in \{0,1\}$.

Consider the event $A_m := \{S^* \leq m\} \cap \{S_* \geq -m\}$.

Claim: $\mathbb P[A_m] = 0$ for every $m \geq 1$. (Proven below.)

If this claim is true, it follows that $$ \mathbb P\left[ \left\{ S^* > m\right\} \cup \left\{ S_* < -m\right\}\right] = 1. $$ Note $\mathbb P\left[ S^* > m\right] = \mathbb P\left[S_* < -m \right]$. Indeed, $\mathbb P\left[S_* < -m\right] = \mathbb P\left[ -(S_*) > m\right] = \mathbb P\left[(-S)^* > m\right] = \mathbb P\left[S^* > m\right]$, where $(-S)^* = \limsup (-S_n)$, since $S_n$ and $-S_n$ are equivalently distributed. So, since $\mathbb P\left[S^* > m\right] \in \{0,1\}$, $$ 1 = \mathbb P\left[ \left\{ S^* > m\right\} \cup \left\{ S_* < -m\right\}\right] \leq \mathbb P\left[ S^* > m\right] + \mathbb P\big[S_* < -m\big] = 2\mathbb P\left[S^* > m\right] \in \{0,2\}. $$ Therefore $\mathbb P\left[S^* > m\right] = 1$ for every $m \geq 1$. Since $\{S^* = \infty\} = \mathop \bigcap_{m=1}^\infty \{S^* > m\}$ and $\{S^* > m\} \supset \{S^* > m+1\}$ for every $m$, by upper semicontinuity of probability measures, $\mathbb P\left[ S^* = \infty \right] = 1$.

Proof of Claim. Note that \begin{equation} A_m = \mathop\bigcup_{k= 1}^\infty \mathop \bigcap_{n=k}^\infty \{|S_n| \leq m \} \tag{1} \end{equation} In order for $\mathop \bigcap_{n=k}^\infty \{|S_n| \leq m \}$ to occur, no $2m+1$ consecutive $X_n$'s can be the same for $n \geq k$. Indeed, if for some $\ell \geq 1$ we have $X_\ell = X_{\ell+1} = \cdots = X_{\ell+2m} = 1$, the sum of these random variables is $2m+1$, and if $S_{\ell-1} = -m$, we'd have $S_{\ell+2m} = m+1$, contradiction. In particular, $$ \mathop \bigcap_{n=k}^\infty \big\{|S_n| \leq m \big\} \subset \ \mathop\bigcap_{n=0}^\infty \big\{ X_{k+(2m+1)n}, X_{k+(2m+1)n+1}, \ldots, X_{k+(2m+1)n+2m} \textrm{ are not all $-1$ or $1$} \big\} \tag{2} $$ Note the events in the intersection on the right side of the above statement each involve different random variables. In particular, these events are independent since $(X_n)_{n \geq 1}$ is independent. There are $2^{2m+1}$ possible arrangements of any collection of $2m+1$ $\mathrm{Rad}_{1/2}$-distributed random variables; e.g. for $m=1$, we could have $(X_1, X_2, X_3) = (1,1,1)$ or $(1,1,-1)$ or $(1,-1,1)$, etc., with $2^3 = 8$ possible arrangements. If the $\mathrm{Rad}_{1/2}$ random variables are independent, each of these arrangements occurs with the same probability of $2^{-2m-1}$. Each event $\left\{ X_{k+(2m+1)n}, X_{k+(2m+1)n+1}, \ldots, X_{k+(2m+1)n+2m} \textrm{ are not all $-1$ or $1$} \right\}$ allows any arrangement of $2m+1$ $\mathrm{Rad}_{1/2}$ random variables, except two: the arrangements of all $1$s and of all $-1$s. Therefore, $$ \mathbb P\big[X_{k+(2m+1)n}, X_{k+(2m+1)n+1}, \ldots, X_{k+(2m+1)n+2m} \textrm{ are not all $-1$ or $1$} \big] = \frac{2^{2m+1}-2}{2^{2m+1}} $$ By independence of the events on the right side of (2), we get: \begin{align} \mathbb P \left[ \mathop \bigcap_{n=k}^\infty \big\{|S_n| \leq m \big\}\right] &\leq \prod_{n=0}^\infty \mathbb P\big[X_{k+(2m+1)n}, X_{k+(2m+1)n+1}, \ldots, X_{k+(2m+1)n+2m} \textrm{ are not all $-1$ or $1$} \big] \\ &= \prod_{n=0}^\infty \frac{2^{2m+1}-2}{2^{2m+1}} = 0. \end{align} By $\sigma$-subadditivity, (1) now gives us $$ \mathbb P\left[ \left\{ S^* \leq m \right\} \cap \left\{ S_* \geq -m \right\}\right] = 0. $$ QED.