TAOCP 3.3.2 Exercise 17

Exercise 17. [M25] Given any numbers $U_0, \ldots, U_{n-1}, V_0, \ldots, V_{n-1}$, let their mean values be

$$\bar{u} = \frac{1}{n} \sum_{0 \le k < n} U_k, \qquad \bar{v} = \frac{1}{n} \sum_{0 \le k < n} V_k.$$

a) Let $U_k' = U_k - \bar{u}$, $V_k' = V_k - \bar{v}$. Show that the correlation coefficient $C$ given in Eq. (24) is equal to

$$\sum_{0 \le k < n} U_k' V_k' \Bigg/ \sqrt{\sum_{0 \le k < n} U_k'^2 \cdot \sum_{0 \le k < n} V_k'^2}.$$

b) Let $C = N/D$, where $N$ and $D$ denote the numerator and denominator of the expression in part (a). Show that $N^2 \le D^2$, hence $-1 \le C \le 1$; and obtain a formula for the difference $D^2 - N^2$. [Hint: See exercise 1.2.3–30.]

c) If $C = \pm 1$, show that $\alpha U_k + \beta V_k = r$, $0 \le k < n$, for some constants $\alpha$, $\beta$, and $r$, not all zero.

Verified: yes
Solve time: 2m07s

Solution

Let the means of the sequences be

$\bar{u} = \frac{1}{n} \sum_{0 \le k < n} U_k, \qquad \bar{v} = \frac{1}{n} \sum_{0 \le k < n} V_k,$

and define the centered sequences

$U_k' = U_k - \bar{u}, \qquad V_k' = V_k - \bar{v}.$

(a) By definition, the sample correlation coefficient $C$ is

C = \frac{\frac{1}{n}\sum_{0 \le k < n} (U_k - \bar{u})(V_k - \bar{v})}{\sqrt{\frac{1}{n}\sum_{0 \le k < n} (U_k - \bar{u})^2 \cdot \frac{1}{n}\sum_{0 \le k < n} (V_k - \bar{v})^2}}}.

Substituting $U_k' = U_k - \bar{u}$ and $V_k' = V_k - \bar{v}$, the numerator becomes $\sum_{0 \le k < n} U_k' V_k'$ and the denominator becomes $\sqrt{\sum_{0 \le k < n} U_k'^2 \cdot \sum_{0 \le k < n} V_k'^2}$. Therefore

$C = \frac{\sum_{0 \le k < n} U_k' V_k'}{\sqrt{\sum_{0 \le k < n} U_k'^2 \cdot \sum_{0 \le k < n} V_k'^2}}.$

(b) Let

$N = \sum_{0 \le k < n} U_k' V_k', \qquad D = \sqrt{\sum_{0 \le k < n} U_k'^2 \cdot \sum_{0 \le k < n} V_k'^2},$

so that $C = N/D$. Consider the square of the numerator and denominator:

$N^2 = \left(\sum_{0 \le k < n} U_k' V_k'\right)^2, \qquad D^2 = \sum_{0 \le k < n} U_k'^2 \cdot \sum_{0 \le k < n} V_k'^2.$

By the Cauchy–Schwarz inequality (or the algebraic identity in exercise 1.2.3–30),

$\left(\sum_{0 \le k < n} U_k' V_k'\right)^2 \le \sum_{0 \le k < n} U_k'^2 \cdot \sum_{0 \le k < n} V_k'^2,$

hence

$N^2 \le D^2,$

which implies $-1 \le C \le 1$. Moreover, the difference can be expressed as

\begin{align*}

D^2 - N^2 &= \sum_{0 \le k < n} U_k'^2 \sum_{0 \le k < n} V_k'^2 - \left(\sum_{0 \le k < n} U_k' V_k'\right)^2 \

&= \frac{1}{2} \sum_{0 \le i,j < n} (U_i' V_j' - U_j' V_i')^2.

\end{align*}

(c) If $C = \pm 1$, then $N^2 = D^2$, so

$(U_i' V_j' - U_j' V_i')^2 = 0 \quad \text{for all } 0 \le i,j < n,$

which implies $U_i' V_j' = U_j' V_i'$ for all $i,j$. Fix $i = 0$, then $V_j' = (\alpha) U_j'$ for some constant $\alpha = V_0'/U_0'$ if $U_0' \ne 0$, or else $U_j' = 0$ for all $j$. In either case, there exist constants $\alpha$, $\beta$, and $r$ (with at least one of $\alpha$, $\beta$ nonzero) such that

$\alpha U_k + \beta V_k = r \quad \text{for all } 0 \le k < n.$

This completes the proof.

∎

$$ \boxed{C = \frac{\sum_{0 \le k < n} U_k' V_k'}{\sqrt{\sum_{0 \le k < n} U_k'^2 \cdot \sum_{0 \le k < n} V_k'^2}}, \quad -1 \le C \le 1, \quad D^2 - N^2 = \frac{1}{2} \sum_{0 \le i,j < n} (U_i' V_j' - U_j' V_i')^2.} $$