# Question on the correlation between two dependent variables

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.

• 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)$ ?? Commented Oct 12, 2014 at 13:05

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$$

and

$$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$$