# For a sequence of i.i.d. (Bernoulli ?) RV we have for the partial sums $S_{n+m}-S_n=m$ i.o. almost surely

Problem: Given a sequence $(X_n)_{n \geq 1}$ of i.i.d. RV and $P(X_1=1)=P(X_1=-1)=1/2$ we have for $m \geq 2k+1 \in \mathbb{N}$ for the partial sums $S_{n+m}-S_n=m$ i.o. a.s.

My approach: I want to show two things to conclude the statement, namely $$P(\limsup \lbrace S_{n+m}-S_n \geq m \rbrace)=1 \\P ( \limsup \lbrace S_{n+m}-S_n >m \rbrace)=0$$ From which I could conclude that $P(\limsup \lbrace S_{n+m}-S_n =m \rbrace )=1$ i.e. $S_{n+m}-S_n=m$ i.o. a.s. This looks like a typical setup for the two Borel Cantelli Lemmas. So $$S_{n+m}-S_n=X_1 + \dots + X_n+X_{n+1}+ \dots + X_{n+m}-(X_1 + \dots + X_n) \\ = X_{n+1}+ \dots + X_{n+m}$$

Since $P(X_1=1)=P(X_1=-1)=1/2$ (I guess that means they behave like Bernoulli Variables) I obtain for the expected value $E(X_1)=\sum_{k \in \mathbb{Z}} kP(X_1=k)=0$, because the sequence are i.i.d. it follows that $$E(S_{n+m}-S_n)=m \cdot E(X_1)=m \cdot 0 =0$$

Thanks to the law of large numbers I can state now that $$\frac{X_{n+1}+ \dots + X_{n+m}}{m} \to 0 \text{ almost surely as }m \to \infty$$

If this is true then I have for arbitrary $\epsilon >0$ and $m$ large enough that $$- \epsilon m \leq X_{n+1}+ \dots + X_{n+m} \leq m \epsilon$$

I don't think that I am on the right track. Can someone provide me with a hint? I don't see how to include the $m \geq 2k+1$ part

Update: The following idea also struck me. I have $E(X_1)=0$, and it is easy to verify that
Var$(X_1)= \sum_{k \in \mathbb{Z}}k^2 P(X_1=k)=1$. Now we know that all our RV are i.i.d and therefore we obtain that $$\text{Var}(S_{n+m}-S_n)=m\text{Var}(X_1) = m$$

Thanks to Chebyshev's Inequality this gives me another bound (which however is useless for Borel Cantelli) namely $$P(|S_{n+m}-S_n| \geq m ) \leq \frac{1}{m}$$

• Hint: Borel-Cantelli for the events $A_i=[S_{(m+1)i}-S_{mi}=m]=[X_{mi+1}=X_{mi+2}=\ldots=X_{(m+1)i}=1]$.
– Did
Apr 30 '16 at 13:13

Use Borel-Cantelli. Let $n=k\cdot 2m$ and $$A_k:=\left\{X_{2m\cdot k }=1\cap X_{2m\cdot k+1 }=1\cap\ldots\cap X_{2m\cdot k+m-1}=1\right\}$$ Then $A_k$ are independent, and $$\mathbb{P}(A_k)=\prod_{j=0}^{m-1}\mathbb{P}(X_{2m\cdot k+j }=1)=p^m$$ So: $$\sum_{k=1}^\infty\mathbb{P}(A_k)=\infty$$ Thus by Borel-Cantelli, infinitely many $A_k$ will happen a.s.
• Thanks for your answer @Ákos Somogyi. I understand your approach, but would you mind telling me why you introduce $n=2mk$?. After getting the general idea I wrote my "proof" down like this $$P(X_{n+1}+ \dots + X_{n+m}=m)= P(X_{n+1}=1, \dots , X_{n+m}=1) = P(X_{n+1}=1) \cdot ... \cdot P(X_{n+m}=1)= 0.5^m$$ I was going to conclude from here with Borel Cantelli 2. Apr 30 '16 at 13:56
• It was to make the events independent. You could choose $n=km$. Apr 30 '16 at 19:09