# How to compute autocorrelation of signal defined by difference equations?

I have no experience with difference equations and I want to learn how to compute the following, but I found no resource online. Any help would be greatly appreciated.

Find:

$$\mathbb{E}\left[d[n]d[n + k]\right]$$

Where:

• $$d[n]$$ is a discrete time signal of the form:

$$d[n] = \alpha \,d[n−1]+v[n] \quad (\alpha \in [0;1])$$

• $$v[n]$$ is a sequence of uncorrelated zero-mean unit-variance random variables.
• Hint: Your definition for $d[n]$ still works if we replace $n$ by $m=n+1$ and so you know how $d[n+1]$ relates to $d[n]$. Proceed iteratively to find $d[n+2]$ in terms of $d[n+1]$ and replace $d[n+1]$ by the just discovered formula $\alpha d[n]+\nu[n+1]$ for $d[n+2]$. Lather, rinse, repeat, working backwards to ultimately find $d[n+k]$ in terms of $d[n]$ and $\nu[n+i], 0 \leq i \leq k$. Then substitute into $E[d[n]d[n+k]]$ and work from there. Oct 25 '18 at 14:21
• Thanks @DilipSarwate, but it doesn't help because I'm stuck with terms in d[n]v[n+k]. Even for $$\mathbb{E}[d[n]d[n+1]] = \mathbb{E}[\alpha d[n]^2 + d[n]v[n+1]]$$ I don't know how to proceed Oct 25 '18 at 14:41
• What is $$\mathbb{E}[ d[n]v[n+1] ]$$? Oct 25 '18 at 14:43
• Your model probably forgot to mention this explicitly or maybe you forgot to include this in your description of the problem, but it is typically assumed than the noise $\nu$ is independent of the signal $d$ and so $E[d[n]\nu[m]]=E[d[n]]\cdot E[\nu[m] = E[d[n]]\cdot 0 = 0$ for all $n$ and $m$. Oct 25 '18 at 15:07

There are different approaches to compute the requested auto-correlations but I would like to provide the simplest that suits to your case provided that.

• The difference equation is an LCCDE type indicating an LTI system.
• The input to the system $$v[n]$$ is WSS (wide sense stationary) random process.

Both of which I assume to be observed in your question. Then I would use the following well known relation between the input and output auto-correlations of an (real) LTI system driven by (real) WSS input $$v[n]$$:

$$r_{dd}[k] = h[k] \star h[-k] \star r_{vv}[k]$$

where the auto-correlation of WSS $$v[n]$$ is $$r_{vv}[k] = \sigma_v^2 \delta[k] = \delta[k]$$ for an uncorrelated, zero mean, unit variance process. And $$h[n]$$ is the impulse-response of the LTI system signified by the LCCDE.

Then the auto-correlation sequence of the WSS output $$d[n]$$ is $$r_{dd}[k] = h[k] \star h[-k] = \sum_{m=-\infty}^{\infty} h[m]h[-(k-m)]~~~,~~~\text{ for } k = 0,\pm 1, \pm 2,...$$

So assuming that your LCCDE : $$d[n] - \alpha ~d[n-1] = v[n] ~~~, ~~~\text{ with } |\alpha| < 1$$

signifies a causal LTI system, then its impulse response is:

$$h[n] = (-\alpha)^n u[n]$$

and yields the auto-correlations to be: $$r_{dd}[k] = \sum_{m=-\infty}^{\infty} (-\alpha)^m u[m] (-\alpha)^{m-k} u[m-k]~~~,~~~\text{ for } k = 0,\pm 1, \pm 2,...$$

I hope you can proceed the rest.

I would approach this by trying to express $$d(n)$$ differently, as difference equations might be confusing. Notice that:

\begin{align} d(n) &= \alpha d(n-1) + v(n) \\ &= \alpha^2 d(n-2) +\alpha v(n-1) +v(n) \\ &=\alpha^3 d(n-3) + \alpha^2 v(n-2)+\alpha v(n-1) +v(n) \\ &=... \end{align}

You can see from the pattern that you can express $$d(n)$$ as a summation:

$$d(n) =\alpha^nd(0)+\sum_{i=0}^{n-1}\alpha^iv(n-i)$$

where I assumed that the procces started at $$n=0$$. For simplicty, let me take $$d(0)=0$$ so that we don't have to carry that constant throughout the calculations.

Then we are left with:

$$\mathbb{E}[d(n)d(n+k)] = \mathbb{E}\left[ \left(\sum_{i=0}^{n-1}\alpha^iv(n-i) \right) \left(\sum_{i=0}^{n+k-1}\alpha^iv(n+k-i) \right)\right]$$

Knowing that the noise is uncorrelated with zero-mean, this expression can be really simplified.

Notice that the expression depends on $$n$$ because the process is not WSS (due to the fact that I assumed that it began at $$n=0$$, i.e. that it hasn't been running since the beginning of times).

• I haven't proof-read your answer but the last line seems to wrong, as it yields the WSS autocorrelation $r_{dd}[k]$ to be dependent on $k$ and $n$ ? $$r_d[k] = E\{ \sum_{i=0}^{n-1} \alpha^i v(n-i) \sum_{m=0}^{n+k-1} \alpha^m v(n+k-m) \}$$ $$= \sum_{i=0}^{n-1} \sum_{m=0}^{n+k-1} \alpha^m \alpha^i E\{v(n-i) v(n+k-m) \}$$ $$= \sum_{i=0}^{n-1} \sum_{m=0}^{n+k-1} \alpha^m \alpha^i \delta[k+i-m]$$ $$= \sum_{i=0}^{n-1} \alpha^{k+i} \alpha^i$$ $$= \alpha^k \sum_{i=0}^{n-1} (\alpha^2)^i$$ $$= \alpha^k \frac{1 -\alpha^{2n} }{1 - \alpha^2}$$ Oct 25 '18 at 17:57
• It should be independent from n Oct 25 '18 at 19:03
• @Julien__ But it cannot, as the noise sequence $v[n]$ is assumed to start at $n=0$, instead of $n=-\infty$. If you are into computing the theoretical auto-correlation sequence $r_{dd}[k]$ of WSS $d[n]$ that would result by applying a true white noise sequence $v[n]$ (which starts at $n=-\infty$) to your LTI system, then you may better consider my answer. Oct 25 '18 at 19:53
• I think it starts at $-\infty$ Oct 25 '18 at 20:07
• @Julien__ theoretically it should start at $n=-\infty$. But in his analysis he preferred to start at it $n=0$. Therefore the result will not be compliant with the former case. Oct 25 '18 at 20:12