I'm working on this question and it's stumping me.

Let $S_n = X_1 + \ldots + X_n$ (with $n>=1$) be a random walk with $X_1, \ldots, X_n$ be iid RV's.
$$ E(X_k)=\mu,\,{\rm Var}(X_k)=\sigma^2. $$ Find the covariance of $S_n$ and $S_m$

Can anyone help out? I am trying to use the equation: $${\rm Cov}[S_n, S_m] = E[S_nS_m] - E[S_n]E[S_m]$$ but can't quite figure it out.

  • $\begingroup$ The question is not clear as you have not defined $S_m$. In particular, are you intending that $S_m$ is a fresh start, or are you intending that $S_m$ uses the same realisations of $X_1, X_2, \dots, $ as used by $S_n$, up to $min(n,m)$ ?? $\endgroup$
    – wolfies
    Commented Oct 12, 2014 at 13:05

2 Answers 2


The trick is to use the bilinearity of the covariance function. For any collection of random variables $X_i$, $i=1,\ldots,n$ and $Y_j$, $j=1,\ldots,m$: $$ \mathrm{Cov}\left(\sum_{i=1}^n X_i,\sum_{j=1}^m Y_j\right)=\sum_{i=1}^n\sum_{j=1}^m\mathrm{Cov}\left(X_i, Y_j\right). $$ Now, for your case, since $X_i$, $i=1,\ldots,n$, are independent (i) and identically distributed (id):

1) If $n=m$, $$ \mathrm{Cov}\left(S_n,S_n\right)=\sum_{i=1}^n\sum_{j=1}^n\mathrm{Cov}\left(X_i, X_j\right)\stackrel{i}{=}\sum_{i=1}^n\mathbb{V}\mathrm{ar}\left(X_i, X_i\right)\stackrel{id}{=}n\sigma^2. $$ 2) If $n<m$, \begin{align} \mathrm{Cov}\left(S_n,S_m\right)=&\sum_{i=1}^n\sum_{j=1}^m\mathrm{Cov}\left(X_i, X_j\right)=\sum_{i=1}^n\left[\sum_{j=1}^n\mathrm{Cov}\left(X_i, X_j\right)+\sum_{j=n+1}^m\mathrm{Cov}\left(X_i, X_j\right)\right]\\ \stackrel{i}{=}&\sum_{i=1}^n\left[\sum_{j=1}^n\mathrm{Cov}\left(X_i, X_j\right)+0\right]\stackrel{1)}{=}n\sigma^2. \end{align} 3) If $n>m$, obviously, $\mathrm{Cov}\left(S_n,S_m\right)=m\sigma^2$.

So a compact way of expressing this result is $\mathrm{Cov}\left(S_n,S_m\right)=\min(n,m)\sigma^2$.


For a direct derivation using ${\rm Cov}[S_n, S_m] = E[S_nS_m] - E[S_n]E[S_m]$

we have

$$E[S_n]E[S_m] = n\mu\cdot m\mu = nm\mu^2$$


$$S_nS_m = \left(\sum_{i=1}^n X_i\right)\left(\sum_{i=1}^m X_i\right) = \sum_{i=1}^{\text{min}(m,n)} X_i^2 + \sum_{i\neq j} X_iX_j$$

where the number of terms in $\sum_{i\neq j} X_iX_j$ are $nm-\text{min}(m,n)$. Taking the expected value

$$E[S_nS_m] = \text{min}(m,n)E(X^2) + [nm-\text{min}(m,n)]\mu^2$$ Bringing it all together

$${\rm Cov}[S_n, S_m] = \text{min}(m,n)E(X^2) + [nm-\text{min}(m,n)]\mu^2 - nm\mu^2$$

and cancelling off

$${\rm Cov}[S_n, S_m] = \text{min}(m,n)\cdot\left (E(X^2) -\mu^2\right) = \text{min}(m,n)\cdot\sigma^2$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.