Solution to Exercise 2.7 The Last One!!!.

Problem Statement: A circular stochastic process with period N is defined by Z_t = Z_t+N, for all t.

(a) Show that when N = 2n, the latent roots of the $N \times N$autocorrelation matrix of Z_t are  

$$\lambda_k \; = \; 1 \, + \, 2 \sum_{i=1}^{n-1} \rho_i \cos \left( \frac{\pi i k}{n} \right) \; + \; \rho_n \cos (\pi k) ,$$ (3)

for $k = 1 , 2 , \ldots , N$, and that the latent vectors corresponding to $\lambda_k$, $\lambda_{N-k}$ (with $\lambda_k = \lambda_{N-k}$) are

(b) Verify that as $N \rightarrow \infty$, with k/N fixed, $\lambda_k$ tends to g(k/N)/2, where g(f) is the spectral density function, showing that in the limit the latent roots of the autocorrelation matrix trace out the spectral curve.

Solution: This problem is probably the most difficult of the assignment. I contemplated not assigning it, but left it in in a foolish moment of confidence in the abilities of Rice students (not to detract from that). One problem was with the quaint British terminology of ``latent root'' and ``latent vector.'' We colonists know them more by their Anglicized (``Americanized(?)'') German terms of ``eigenvalues'' and ``eigenvectors.'' Then several students struggled with the sine-cosine stuff and I hinted ``complex exponential'' and they went away and never came back, probably because they eventually gave up. But then the real corker is figuring out how to get the correlation matrix written down correctly so that it incorporates the information that the process is circular. Since Z_t = Z_t+N = Z_t-N, we have  

$$\rho_k \; = \; \mbox{Corr} [Z_{t},Z_{t+k}] \; = \; \mbox{Corr} [Z_{t+N},Z_{t+k}] \; = \; \rho_{N-k} .$$ (4)

Therefore, there are really only n-1 different values. Also, we have for instance

So, when we get to $\rho_{n}$ in a row of the correlation matrix, we start going backwards in the subscript.

The $N \times N$ correlation matrix for $(Z_1,\ldots,Z_N)$ is then  

$$\mbox{\boldmath{R}} \; = \; \left[ \begin{array} {cccccccccc... ...rho_{n-1} & \rho_{n-2} & \cdots & \rho_1 & 1\end{array} \right]$$ (5)

Note how each row is obtained from the previous one by a cyclic permutation wherein the last element is taken off and put in the first position. This is the property of being a circulant matrix (just for future reference). Now consider the complex vector

To complete the proof, we will show that  

$$\mbox{\boldmath$R$}\mbox{\boldmath$v$}_k \; = \; \lambda_k \mbox{\boldmath$v$}_k .$$ (6)

Since $\mbox{\boldmath$R$}$ and $\lambda_k$ are real, there is no mixing of real and imaginary parts in either side of (28), so we may match up the real and imaginary parts using (27) to conclude

$$\mbox{\boldmath$R$}\mbox{\boldmath$\ell$}_k \; = \; \lambda_... ...$\ell$}_{N-k} \; = \; \lambda_k \mbox{\boldmath$\ell$}_{N-k} ,$$

which proves the claims about the ``latent'' vectors and their corresponding ``latent'' roots.

To prove (28), consider the first entry of $\mbox{\boldmath$R$}\mbox{\boldmath$v$}_k$, i.e.

$$1 \cdot \exp[2 \pi ik /N] + \rho_1 \cdot \exp[4 \pi ik /N] + \rho_2 \cdot \exp[6 \pi ik /N] + \cdots$$

$$+ \rho_{n-1} \cdot \exp[2n \pi ik /N] + \rho_n \cdot \exp[2... ...pi ik /N] + \rho_{n-1} \cdot \exp[2(n+2) \pi ik /N] + \cdots$$

 

$$+ \rho_2 \cdot \exp[2(N-1) \pi ik /N] + \rho_1 \cdot \exp[2N \pi ik /N]$$ (7)

$$\; = \; \exp[2 \pi ik /N] \left\{ 1 + \rho_1 \left( \exp[2 \pi ik /N] + \exp[2(N-1) \pi ik /N] \right) + \right.$$

$$\rho_2 \left( \exp[4 \pi ik /N] + \exp[2(N-2) \pi ik /N] \right) + \cdots$$

 

$$\left. + \rho_{n-1} \left( \exp[2(n-1) \pi ik /N] + \exp[2(... ...) \pi ik /N] ] \right) + \rho_n \exp[2n \pi ik /N] \right\}$$ (8)

$$\; = \; \exp[2 \pi ik /N] \left\{ 1 + \rho_1 \left( \exp[2 \pi ik /N] + \exp[-2 \pi ik /N] \right) + \right.$$

$$\rho_2 \left( \exp[4 \pi ik /N] + \exp[-4 \pi ik /N] \right) + \cdots$$

 

$$\left. + \rho_{n-1} \left( \exp[2(n-1) \pi ik /N] + \exp[-2... ...) \pi ik /N] ] \right) + \rho_n \exp[2n \pi ik /N] \right\}$$ (9)

$$\; = \; \exp[2 \pi ik /N] \left\{ 1 + 2 \rho_1 \cos[2 \pi k /N] + 2 \rho_2 \cos[4 \pi k /N] + \cdots \right.$$

 

$$\left. + \rho_{n-1} \cos[2(n-1) \pi k /N] + \rho_n \cos[ \pi k] \right\}$$ (10)

 

$$\; = \; \lambda_k \exp[2 \pi ik /N] .$$ (11)

Justifications:

(29)

This follows from the definition of matrix multiplication: the first row of $\mbox{\boldmath$R$}$ in (25) inner product with $\mbox{\boldmath$v$}_k$.

(30)

We've factored out $\exp[2 \pi ik /N]$ from all terms and collected the terms with a common $\rho_k$ and factored out that $\rho_k$. Also, we rewrote some of the complex exponentials, viz.  

$$\exp[2(n+1) \pi ik /N] \; = \; \exp[2(N-(n-1)) \pi ik /N] ] ,$$ (12)

which follows since N = 2n.

(31)

Of course, $\exp[ 2 \pi N i jk /N ] = 1$ for any integers j, k. This was substituted into (30) to obtain (31).

(32)

This follows from $\exp[i \theta] + \exp[- i \theta]$ = $2 \cos \theta$. Also, $\exp[2n \pi ik /N]$ = $\exp[ \pi ik]$ $\; = \;$ $\cos[\pi k]$ = (-1)^k.

(33)

This is clear from the previous line and the definition of $\lambda_k$ in (21). Note that (33) is $\lambda_k$ times the first entry in $\mbox{\boldmath$v$}_k$.

Now let's move on to the second component of $\mbox{\boldmath$R$}\mbox{\boldmath$v$}_k$. This is

$$\rho_1 \cdot \exp[2 \pi ik /N] + 1 \cdot \exp[4 \pi ik /N] + \rho_1 \cdot \exp[6 \pi ik /N] + \cdots$$

$$+ \rho_{n-2} \cdot \exp[2n \pi ik /N] + \rho_{n-1} \cdot \e... ... \pi ik /N] + \rho_{n} \cdot \exp[2(n+2) \pi ik /N] + \cdots$$

 

$$+ \rho_3 \cdot \exp[2(N-1) \pi ik /N] + \rho_2 \cdot \exp[2N \pi ik /N]$$ (13)

$$\; = \; \exp[4 \pi ik /N] \left\{ 1 + \rho_1 \left( \exp[-2 \pi ik /N] + \exp[2 \pi ik /N] \right) + \right.$$

$$\rho_2 \left( \exp[4 \pi ik /N] + \exp[2(N-2) \pi ik /N] \right) + \cdots$$

 

$$\left. + \rho_{n-1} \left( \exp[2(n-1) \pi ik /N] + \exp[2(... ...) \pi ik /N] ] \right) + \rho_n \exp[2n \pi ik /N] \right\}$$ (14)

$$\; = \; \exp[4 \pi ik /N] \left\{ 1 + 2 \rho_1 \cos[2 \pi k /N] + 2 \rho_2 \cos[4 \pi k /N] + \cdots \right.$$

 

$$\left. + \rho_{n-1} \cos[2(n-1) \pi k /N] + \rho_n \cos[ \pi k] \right\}$$ (15)

 

$$\; = \; \lambda_k \exp[4 \pi ik /N] .$$ (16)

The justifications are pretty much the same. Note that at (36) we factored out $\exp[4 \pi ik /N]$ from everything since this is the second component of $\mbox{\boldmath$v$}_k$ and we want to see something (namely $\lambda_k$) times it in the end (i.e. (38).

You are probably getting the general idea by now. Can we make a formal mathematical argument? Let

$$\mbox{\boldmath$r$}_i \; = \; (\rho_{i-1} ,\rho_{i-2} , \ldots , \rho_i )$$

denote the $N \times 1$ vector which is the transpose of the i'th row of $\mbox{\boldmath$R$}$. Of course, $\rho_0 = 1$, $\rho_{-k} = \rho_k$, and $\rho_{k\pm N} = \rho_k$. Let

$$\mbox{\boldmath$M$} \; = \; \left[ \begin{array} {cccccc} 0... ...ot & \cdot \\ 0 & 0 & 0 & \cdots & 1 & 0 \end{array} \right]$$

be the cyclic $N \times N$ permutation matrix which takes the last element off an N-vector and moves it to the front. Then

$$\mbox{\boldmath$r$}_i \; = \; \mbox{\boldmath$M$}^{i-1} \mbo... ...th$r$}_1 \; = \; \mbox{\boldmath$M$}^i \mbox{\boldmath$r$}_0 ,$$

where $\mbox{\boldmath$r$}_0$ is defined in the obvious way. Note that the transpose $\mbox{\boldmath$M$}^T$ is the inverse, i.e. it moves the first element to the end of the vector. Also,

The j'th entry of $\mbox{\boldmath$R$}\mbox{\boldmath$v$}_k$ is

which is just the j'th entry of $(\mbox{\boldmath$r$}_0^T \mbox{\boldmath$v$}_k) \mbox{\boldmath$v$}_k$. This shows that multiplying $\mbox{\boldmath$R$}$ times $\mbox{\boldmath$v$}_k$ gives $\mbox{\boldmath$v$}_k$ back again but multiplied by $(\mbox{\boldmath$r$}_0^T \mbox{\boldmath$v$}_k)$. We have already worked out that $(\mbox{\boldmath$r$}_0^T \mbox{\boldmath$v$}_k) = \lambda_k$, so we have completed a fairly rigorous proof of (28).

Part (b) sort of seems trivial at this point. If $N \rightarrow \infty$ but k/N = f is always fixed, then of course

where g(f) is given in (2.2.13), p. 40. Clearly, we are assuming that $\rho_{N/2} \rightarrow \infty$ as $N \rightarrow \infty$.

Well, this is all a little hard to swallow, because the process was circular with period N (remember that Z_t = Z_t+N for all N which gave us that $\rho_k$ = $\rho_{k+N}$ for all k), so we can't be talking about the same process for all N, i.e. there is a different process for each N so all the $\rho_k$'s need an additional subscript or something to show they depend on N, and then they would be involved in taking the limit as $N \rightarrow \infty$. Hmm. What's it all about? Well, one can actually make sense of what the authors are getting at at this point. Let Z_t be a fixed stationary process satisfying a few nice properties (e.g., that $\sum_{k=1}^{\infty} \vert\rho_k\vert \; < \; \infty$). For each N construct a circular process of period N from Z_t by

$$Z_t^{(N)} \; = \; Z_{(t+\kappa) \mbox{mod}N}$$

where $s \mbox{mod}N$ is the remainder on division of s by N and $\kappa$ is a random number which is uniformly distributed on $0 , 1 , \ldots , N-1$ (discrete uniform distribution). Here, we basically take Z₀, Z₁, $\ldots$, Z_N-1 and repeat them over and over as a block, and then give a random starting point $\kappa$. This creates a circular process with period N that looks a lot like the original Z_t. In particular, if $\rho_k$ is the ACF for the original Z_t, then the lag 1 ACF for Z_t^(N) is $(1-1/N)\rho_1 + (1/N)\rho_{N-1}$ where the perturbation comes from sticking the value of Z_N-1 next to Z₀ in forming Z_t^(N). Similarly, the lag 2 ACF for Z_t^(N) is $(1-2/N) \rho_2 + (1/N)(\rho_{N-1} + \rho_{N-2})$, etc. Anyway, these modified ACF values will converge to the originals as $N \rightarrow \infty$. `Nuff said.