Calculating expected value$^4$ for simple random walk over $\mathbb Z$

Question

Let $S_n$ be a random walk over $\mathbb Z$, starting at $0$.

$S_n = X_1+X_2+...+X_n$ where $X_i$ is an independent random variable with $1$ at probability of $\frac{1}{2}$, and $-1$ at probability of $\frac{1}{2}$.

What is $\mathbb E[S_n^4]$ ?

$$$$ I know the answer, and I know one way to solve it, but I'm trying to find where I'm wrong when solving it this way, please help me find the error:

In order to calculate $\mathbb E[S_n^4] $ I can calculate the variance of $S_n^2$. This is because:

$$V(S_n^2) = \mathbb E[S_n^4] - \mathbb E^2[S_n^2]$$

Now, $$\mathbb E[S_n^2] = n$$ This is pretty easy to see.

All I'm left is to calculate $V(S_n^2)$.

We note that $S_n^2 = \sum_{i=1}^n \sum_{j=1}^n X_iX_j$, therefore:

$$V(S_n^2) = \sum_{i=1}^n \sum_{j=1}^n V(X_iX_j) + \sum_{i=1}^n \sum_{j=1}^n\sum_{k=1}^n\sum_{l=1}^nCov(X_iX_j,X_kX_l)$$ (without the $i=j=k=l$ in the summation)

We note that $V(X_iX_j) = 1$ for every $i\ne j$ and $0$ for $i=j$. Therefore the first part equals $2\binom{n}{2} = n(n-1)$.

The summation of the covariance is $0$ for every $i,j,k$.

Therefore we get that $V(S_n^2) = n^2-n$.

And from there we can extract $\mathbb E[S_n^4] = n^2-n+n^2 = n(2n-1)$.

This answer is incorrect, since I know it should be $n(3n-2)$ but I cant seem to find where is the mistake in the solution above.

Thanks!

Answer 1

Consider all pair of ordered $2$-tuples $(i,j)$ and $(k,l)$ where $i,j,k,l\in \{1,2,\ldots, n\}$. Now, you get your first term in the RHS of $V(S_n^2)$ using $(i,j)=(k,l) \implies i=k \wedge j=l$. And the residual summation is over $(i,j)\neq(k,l)$ which happens when either $i \neq k$ or $j \neq l$ or both. However, $(i,j)\neq(k,l)$ can be divided into two scenarios,

1. When $i\neq k$, $i=l$, $j\neq l$ and $j=k$.
2. When $(i \neq k \text{ or } j \neq l \text{ or both}) \text{ and } (i\neq l \text{ or } j \neq k)$.

It is easy to check that the contribution by scenario $1$ is same as the first term in the RHS of $V(S_n^2)$.

Scenario $1$ leads to $\sum\limits_{\substack{i,j\\i\neq j}}Cov(X_iX_j, X_jX_i) = \sum\limits_{\substack{i,j\\i\neq j}}Var(X_iX_j) = n^2-n$.

Also, note that all the covariance terms from scenario $2$ will equal $0$.

And another way to obtain $E(S_n^4)$ is,

$$M_{X_i}(t) = \frac{1}{2}(e^t+e^{-t})$$

$$M_{S_n}(t) = \prod_{i=1}^{n}(M_{X_i}(t))^n = \frac{1}{2^n}(e^t+e^{-t})^n$$

$$E(S_n^4) = \frac{\partial^4 M_{S_n}(t)}{\partial t^4}\bigg\vert_{t=0} = \frac{1}{2^n}(n^22^n+2(n-1)n2^n) = n(3n-2)$$

$(e^t-e^{-t})|_{t=0} = 0$ will make the calculations easier.