Consider a simple random walk on the number line $\mathbb{Z}.$ At each unit, the walker moves left or right with probability $\frac{1}{2}.$ Assuming the walker starts at point $x$, we can define $$S_{n}=x+X_{1}+...+X_{n}$$ as the position of the walker at time $n.$ The increments $X_{1},X_{2}...$ are independent random variables with $$\mathbb{P}(X_{j}=1)=\mathbb{P}(X_{j}=-1)=\frac{1}{2}.$$ My question is about the computation of $\mathbb{E}\left [ S_{n}^2 \right ].$ I am reading that $$\mathbb{E}\left [ S_{n}^2 \right ]= \mathbb{E}\left [ \left ( \sum_{j=1}^{n}X_{j} \right )^2 \right]=\mathbb{E}\left [ \sum_{j=1}^{n}\sum_{k=1}^{n}X_{j}X_{k} \right ]=\sum_{j=1}^{n}\sum_{k=1}^{n}\mathbb{E}\left [ X_{j}X_{k} \right ].$$ I understand that. However, the author then writes $$\sum_{j=1}^{n}\sum_{k=1}^{n}\mathbb{E}\left [ X_{j}X_{k} \right ]=n+\sum_{j\neq k}^{ } \mathbb{E}\left [ X_{j}X_{k} \right ].$$ I do not understand that derivation. I know that there are four possibilities of $(X_{j},X_{k})$. Mainly, $$(1,1),(1,-1),(-1,1), \ \ \text{and} \ \ (-1,-1).$$ Can anyone explain this derivation?
Thanks in advance!
Notice that if $j=k$, then we have $X_j = X_k$, then $X_j X_k=X_j^2 = 1$.
Hence $$\sum_{j=1}^n X_j^2 = \sum_{i=1}^n (1)=n$$
That is we have
$$\sum_{j=1}^n \sum_{k=1}^n E[X_jX_k]=\sum_{j=1}^n E[X_j^2]+ \sum_{j \ne k} E[X_jX_k]= n + \sum_{j \ne k} E[X_jX_k]$$