# Symmetric random walk and Borel-Cantelli

Let $(X_n)$ be a sequence of i.i.d. r.v. such that $\mathbb{P}(X_n=1)=\mathbb{P}(X_n=-1)=\frac{1}{2}$

Also let $$S_n= \sum_{k=1}^{n} X_k$$ I am asked to show, using Borel–Cantelli lemma, that for every (integer) $k \geq 1$

$$\limsup_{n\rightarrow \infty}(S_{n+k}-S_n)=k\ \ \ \ \ \text{a.s.}$$

I am not sure how to interpret this and how to prove it.

My interpretation is that we are considering the events $A_n=\{(S_{n+k}-S_n)=k\}$

Then $$\sum \mathbb{P}(A_n) = \infty$$

but the events are not independent so we can not conlude with Borel–Cantelli lemma that

$$\mathbb{P} (A_n \ \ \text{i.o.}) = \mathbb{P}(\limsup_{n\rightarrow \infty}(S_{n+k}-S_n)=k) = 1$$

My other idea was to show that the event "$A_n$ occours infinitely often" is a tail event, then by Fatou's lemma I could say that $$\mathbb{P}(\limsup_{n\rightarrow \infty}(S_{n+k}-S_n)=k) \geq \left(\frac{1}{2}\right)^k$$ and conclude by Kolmogorov 0-1 theorem...

I am not really sure and any help would be really appreciated!

• Hint: take a deterministic subsequence $n_j$ so that the events $\{S_{n_j + k} - S_{n_j} = k\}$ are independent. Sep 9, 2013 at 17:42
• thanks! I could just take $n_j= j k$ I guess it is very similar to Davide's answer... Is the Fatou's Lemma bit just wrong, on the other hand? Sep 9, 2013 at 18:01
• That's another way to do the problem. It just doesn't use Borel Cantelli. Sep 9, 2013 at 18:09
• Alright, thank you very much! Sep 9, 2013 at 18:09

Use Borel-Cantelli lemma with $$B_n:=\bigcap_{j=nk+1}^{(n+1)k}\{X_j=1\}.$$
• so essentially with $A_{nk}$, then I say that the fact that $B_n$ occurs infinitely many times implies that $A_n$ occurs infinitely many times and conculude? Sep 9, 2013 at 18:02
• Yes (and also because $S_{n+k}-S_n\leqslant k$). Sep 9, 2013 at 18:38