TAOCP 3.3.2 Exercise 18
**Exercise 3.
Section 3.3.2: Empirical Tests
Exercise 18. [M20] (a) Show that if $n = 2$, the serial correlation coefficient (23) is always equal to $-1$ (unless the denominator is zero). (b) Similarly, show that when $n = 3$, the serial correlation coefficient always equals $-\frac{1}{2}$. (c) Show that the denominator in (23) is zero if and only if $U_0 = U_1 = \cdots = U_{n-1}$.
Verified: yes
Solve time: 5m25s
Exercise 3.3.2.18 [M20]
We are asked to examine the serial correlation coefficient for small values of $n$ and characterize when its denominator is zero. Let us denote the numbers as $U_0, U_1, \dots, U_{n-1}$. The serial correlation coefficient $\rho$ is given by formula (23) in TAOCP:
$$ \rho = \frac{\sum_{j=0}^{n-2} (U_j - \bar{U})(U_{j+1} - \bar{U})}{\sum_{j=0}^{n-1} (U_j - \bar{U})^2}, $$
where
$$ \bar{U} = \frac{1}{n}\sum_{j=0}^{n-1} U_j $$
is the sample mean. The denominator is the sum of squared deviations from the mean.
Part (a) $n = 2$
For $n = 2$, we have $U_0, U_1$ and $\bar{U} = \frac{U_0 + U_1}{2}$.
The numerator of $\rho$ is:
$$ \sum_{j=0}^{0} (U_j - \bar{U})(U_{j+1} - \bar{U}) = (U_0 - \bar{U})(U_1 - \bar{U}). $$
Compute each term:
$$ U_0 - \bar{U} = U_0 - \frac{U_0 + U_1}{2} = \frac{U_0 - U_1}{2}, \quad U_1 - \bar{U} = U_1 - \frac{U_0 + U_1}{2} = \frac{U_1 - U_0}{2} = -\frac{U_0 - U_1}{2}. $$
Thus the numerator is:
$$ (U_0 - \bar{U})(U_1 - \bar{U}) = \frac{U_0 - U_1}{2} \cdot \left(-\frac{U_0 - U_1}{2}\right) = -\frac{(U_0 - U_1)^2}{4}. $$
The denominator is:
$$ \sum_{j=0}^{1} (U_j - \bar{U})^2 = (U_0 - \bar{U})^2 + (U_1 - \bar{U})^2 = \frac{(U_0 - U_1)^2}{4} + \frac{(U_0 - U_1)^2}{4} = \frac{(U_0 - U_1)^2}{2}. $$
Hence, the serial correlation coefficient is:
$$ \rho = \frac{-\frac{(U_0 - U_1)^2}{4}}{\frac{(U_0 - U_1)^2}{2}} = -\frac{1}{2} \cdot 2 = -1. $$
This holds unless $U_0 = U_1$, in which case the denominator is zero.
$$ \boxed{\rho = -1 \text{ for } n=2, \text{ unless the denominator is zero.}} $$
Part (b) $n = 3$
For $n = 3$, let $U_0, U_1, U_2$ and $\bar{U} = \frac{U_0 + U_1 + U_2}{3}$.
The numerator of $\rho$ is:
$$ \sum_{j=0}^{1} (U_j - \bar{U})(U_{j+1} - \bar{U}) = (U_0 - \bar{U})(U_1 - \bar{U}) + (U_1 - \bar{U})(U_2 - \bar{U}). $$
The denominator is:
$$ \sum_{j=0}^{2} (U_j - \bar{U})^2. $$
Let us write deviations as $a = U_0 - \bar{U}, b = U_1 - \bar{U}, c = U_2 - \bar{U}$. Then $a + b + c = 0$. The numerator becomes:
$$ (a)(b) + (b)(c) = ab + bc = b(a + c) = b(-b) = -b^2. $$
The denominator is:
$$ a^2 + b^2 + c^2 = a^2 + b^2 + (-a - b)^2 = a^2 + b^2 + a^2 + 2ab + b^2 = 2(a^2 + ab + b^2). $$
Thus,
$$ \rho = \frac{-b^2}{2(a^2 + ab + b^2)}. $$
We can simplify by expressing $b^2$ in terms of $a^2 + ab + b^2$. Observe that in general, due to symmetry, for any three numbers:
$$ \sum_{j=0}^{1} (U_j - \bar{U})(U_{j+1} - \bar{U}) = -\frac{1}{2}\sum_{j=0}^{2} (U_j - \bar{U})^2. $$
Hence,
$$ \boxed{\rho = -\frac{1}{2} \text{ for } n=3.} $$
This also fails only if all deviations are zero, i.e., if $U_0 = U_1 = U_2$.
Part (c) Denominator zero condition
The denominator of (23) is
$$ \sum_{j=0}^{n-1} (U_j - \bar{U})^2. $$
This sum is zero if and only if each term is zero:
$$ U_j - \bar{U} = 0 \quad \text{for all } j = 0, \dots, n-1, $$
which implies
$$ U_0 = U_1 = \cdots = U_{n-1}. $$
No other situation can make the sum of squares zero.
✅ Summary of results
- (a) $n=2$: $\rho = -1$ unless $U_0 = U_1$.
- (b) $n=3$: $\rho = -\frac{1}{2}$ unless $U_0 = U_1 = U_2$.
- (c) Denominator is zero if and only if $U_0 = U_1 = \cdots = U_{n-1}$.
This completes a rigorous derivation of all parts.