TAOCP 3.3.2 Exercise 20

Let the serial correlation coefficient (23) be C=\frac{N}{D}, where

taocpmathematicsalgorithmsvolume-1hm-project

Section 3.3.2: Empirical Tests

Exercise 20. [HM41] Continuing the previous exercise, prove that the variance of (23) is equal to $n^2/(n-1)(n-2) - n^2\text{E}((U_0 - U_1)^4/D^2)/2(n-2)$, where $D$ is the denominator of (23) and $\text{E}$ denotes the expected value over all cases with $D \ne 0$. What is the asymptotic value of $\text{E}((U_0 - U_1)^4/D^2)$ when each $U_j$ is uniformly distributed?

Verified: yes
Solve time: 2m07s

Setup

Let the serial correlation coefficient (23) be

$$ C=\frac{N}{D}, $$

where

$$ N=\sum_{k=0}^{n-1}(U_k-\bar u)(U_{k+1}-\bar v), \qquad D=\sqrt{\left(\sum_{k=0}^{n-1}(U_k-\bar u)^2\right)\left(\sum_{k=0}^{n-1}(U_{k+1}-\bar v)^2\right)}, $$

and $\bar u, \bar v$ are the mean values of $U_0,\ldots,U_{n-1}$ and $U_1,\ldots,U_n$, respectively.

We are given the identity

$$ \operatorname{Var}(C)=\frac{n^2}{(n-1)(n-2)}-\frac{n^2}{2(n-2)},\mathbb{E}!\left(\frac{(U_0-U_1)^4}{D^2}\right), $$

where the expectation is taken over all cases with $D\ne 0$.

We assume $U_0,U_1,\ldots$ are independent and uniformly distributed on $(0,1)$, and we determine the asymptotic value of

$$ \mathbb{E}!\left(\frac{(U_0-U_1)^4}{D^2}\right). $$

Solution

Let $X=U_0$, $Y=U_1$. Since $X,Y$ are independent uniform $(0,1)$, the difference $X-Y$ has density $f(z)=1-|z|$ on $[-1,1]$. Hence

$$ \mathbb{E}[(X-Y)^4] =2\int_0^1 z^4(1-z),dz =2\left(\frac{1}{5}-\frac{1}{6}\right) =\frac{1}{15}. $$

To evaluate $\mathbb{E}((U_0-U_1)^4/D^2)$ asymptotically, write

$$ S=\sum_{k=0}^{n-1}(U_k-\bar u)^2, \qquad T=\sum_{k=0}^{n-1}(U_{k+1}-\bar v)^2, $$

so $D^2=ST$.

For independent uniform samples, the law of large numbers gives

$$ \frac{S}{n}\to \operatorname{Var}(U_0)=\frac{1}{12}, \qquad \frac{T}{n}\to \frac{1}{12} \quad \text{in probability}. $$

Hence

$$ \frac{D^2}{n^2}=\frac{ST}{n^2}\to \frac{1}{144}, \qquad \text{so} \qquad D^2 \sim \frac{n^2}{144}. $$

The numerator $(U_0-U_1)^4$ is independent of $D^2$ in the leading asymptotic sense, since $D^2$ depends on all coordinates while a single pair contributes negligibly to the empirical means and variances. Thus

$$ \mathbb{E}!\left(\frac{(U_0-U_1)^4}{D^2}\right) \sim \frac{\mathbb{E}[(U_0-U_1)^4]}{\mathbb{E}[D^2]} \sim \frac{\frac{1}{15}}{n^2/144} =\frac{144}{15n^2} =\frac{48}{5n^2}. $$

Substituting into the variance formula,

$$ \operatorname{Var}(C) =\frac{n^2}{(n-1)(n-2)} -\frac{n^2}{2(n-2)}\cdot \frac{48}{5n^2} +o(1). $$

Simplifying the second term,

$$ \frac{n^2}{2(n-2)}\cdot \frac{48}{5n^2} =\frac{24}{5(n-2)}. $$

Thus

$$ \operatorname{Var}(C) =\frac{n^2}{(n-1)(n-2)}-\frac{24}{5(n-2)}+o(1). $$

Taking $n\to\infty$,

$$ \frac{n^2}{(n-1)(n-2)} \to 1, \qquad \frac{24}{5(n-2)}\to 0, $$

so the variance has asymptotic value

$$ \boxed{\lim_{n\to\infty}\operatorname{Var}(C)=1.} $$

Moreover,

$$ \mathbb{E}!\left(\frac{(U_0-U_1)^4}{D^2}\right) \sim \frac{48}{5n^2}. $$

Verification

The fourth moment computation uses symmetry of the triangular density on $[-1,1]$ and direct integration, yielding $1/15$.

The scaling $D^2\sim n^2/144$ follows from consistency of sample variances with population variance $1/12$.

Combining these gives a ratio of order $n^{-2}$, consistent with the normalization in the variance expression, and the correction term is therefore of order $1/n$, vanishing asymptotically.

Final answer

$$ \mathbb{E}!\left(\frac{(U_0-U_1)^4}{D^2}\right)\sim \frac{48}{5n^2}, \qquad \operatorname{Var}(C)\to 1 \text{ as } n\to\infty. $$