Suppose $Y_n$ is a simple random walk on $\mathbb{Z}$. That is $Y_n = X_1 + X_2+...+X_n$, where $\mathbb{P}(X_i=1)=\mathbb{P}(X_i=-1)=\frac{1}{2}$, and $(X_i)$ are i.i.d. I try to show that $E|Y_n^2 - n|$ is finite for any $n\geq 1$.
Here is my proof:
$$E|Y_n^2 - n| =E|(X_1 + X_2+...+X_n)^2- n| = E|X_1^2+...+X_n^2 +2\sum_{1\leq i<j\leq n}(X_iX_j)- n|$$
since $X_i^2 = 1$, the equality becomes $E|2\sum_{1\leq i<j\leq n}(X_iX_j)|$
I stuck here, hope some one can help me.
Thank you
Actually I tried to show $Y_n^2 -n$ is a martingale. Being a Martingale has to satisfy $E|M_n| < \infty$.
You will need that
So, you have: \begin{align}\mathbb E\left[|M_n|\right]&= \mathbb E\left[|Y_n^2-n|\right]\le \mathbb E[Y_n^2]+n\\[0.2cm]&=\mathbb E\left[\left(\sum_{i=1}^n X_i\right)^2\right]+n=\mathbb E\left[\sum_{i=1}^n{X_i^2}+\sum_{i\neq j}X_iX_j\right]+n\\[0.2cm]&= \sum_{i=1}^n\mathbb E[X_i^2]+\sum_{i\neq j}\mathbb E[X_iX_j]+n=n\mathbb E[X_1^2]+0+n=2n<\infty\end{align} Note, that you are not asked to show that the bound $(2n)$ does not grow to $\infty$ as $n\to\infty$. You are only asked to show that $\mathbb E[|M_n|]<\infty$, so the above bound of $(2n)$ does it.