Convergence of $\sum_{i \leq n} X_i/n$

I have a question like this:

Let $(X_n)$ be an i.i.d sequence of random variables with values in $\{-1,1\}$, and define $Y_n:= \sum_{i \leq n} X_i/n$. Show that $(Y_n)$ converges almost surely and in $L_1$. Do not appeal to the law of large numbers.

The question is under the classification of martingale. I know we should be able to do this using backwards martingales. but we never learned the backwards martingales in class and can we do it using regular martingales? I mean, can we define a suitable filtration so that the $(Y_n)$ is indeed a martingale?

• $(nY_n)$ is definitely a martingale – gt6989b May 5 '16 at 1:29
• @gt6989b If $\mathbb P(X_1=1)=\mathbb P(X_1=-1)$, yes. Otherwise it is slightly more involved. – Math1000 May 5 '16 at 1:41
• @Math1000 yes, otherwise use $Z_n = nY_n - n\mu_X$ where $\mu_X = \mathbb{E}[X]$... – gt6989b May 5 '16 at 1:52
• @gt6989b Hence the inclusion of "slightly" :) – Math1000 May 5 '16 at 1:55
• You can use Kronecker's lemma applied to the sequence $\sum_{i=1}^n \frac{X_i-\mu}{i}$. – Kolmo May 14 '16 at 0:28

2 Answers

I do not know how one can use the particular Rademacher distribution, but there is a useful reverse martingale trick: it is easy to see that $$E[X_1|S_n, S_{n+1},\dots] = \frac{S_n}{n}.$$ Denoting $\mathcal{F_n} = \sigma\{S_n, S_{n+1},\dots\}$, we thus have a (reverse) Levy martingale $Y_n = E[X_1|\mathcal{F_n}]$. By the reverse martingale convergence, $Y_n\to Y_\infty = E[X_1|\mathcal{F_\infty}]$, $n\to\infty$, where $\mathcal{F}_\infty = \cap_{n\ge 1} \mathcal F_n$. But $\mathcal{F}_\infty$ consists of exchangeable events, which by the Hewitt-Savage 0-1 law have probability $0$ and $1$. Therefore, $Y_\infty = E[X_1]$ a.s.

If the sequence $\left(Y_l-c_l\right)_{l\geqslant 1}$ is a martingale with respect to $\left(\mathcal F_n\right)_{l\geqslant 1}$ (where $c_l$ is a deterministic constant), then for each $l$, the random variables $X_1,\dots,X_l$ are measurable with respect to $\mathcal F_n$. Since we should have that $\mathbb E\left[Y_{n+1}-c_{n+1}+c_n-Y_n\mid\mathcal F_n\right]=0$, we would obtain that $$\left(\frac 1{n+1}-\frac 1n\right)\sum_{j=1}^nX_j+\frac{\mathbb E\left[X_1\right]}{n+1}+c_n-c_{n+1}=0 \mbox{ a.s.}$$ which is not possible.

The idea is to introduce a martingale which is bounded in $\mathbb L^2$. Define for $l\geqslant 1$ the random variable $$Z_l:=\sum_{i=1}^l\frac{X_i-\mathbb E\left[X_1\right]}i.$$ Then the sequence $\left(Z_l\right)_{l\geqslant 1}$ is a martingale with respect to its natural filtration. Now, we can get the wanted result using the following facts:

• the sequence $\left(\mathbb E\left[Z_l^2\right]\right)_{l\geqslant 1}$ is bounded.
• The sequence $\left(Z_l\right)_{l\geqslant 1}$ is thus convergent to some $Y$ in $\mathbb L^1$ and almost surely. Now, $$\frac 1n\sum_{i=1}^nX_i=Z_n-\frac 1n\sum_{l=1}^{n-1}Z_l+\mathbb E\left[X_1\right].$$