Lag-$k$ Autocorrelation

This empirical test directly assesses the degree of independence of samples. As pointed out in Section 2.1, if the samples are independently and identically distributed (IID) random variables, the autocorrelation should be 0. The lag-$k$ autocorrelation statistic $\rho_k$ of samples $U_1,U_2, \ldots$ is defined as

$$\rho_k = \frac{C_k}{C_0}$$

where

$$C_k = \mbox{Cov}(U_i,U_{i+k}) = \mbox{E}(U_iU_{i+k}) - \mbox{E}(U_i)\mbox{E}(U_{i+k})$$

and $C_0$ is the sample variance. If $U_i$'s are uniformly distributed, $\mbox{E}(U_i) = \mbox{E}(U_{i+k}) = \frac{1}{2}$, $C_0=\frac{1}{12}$. Then we have $\rho_k = 12 \mbox{E}(U_iU_{i+k}) - 3$.

In practice, we do not calculate $\rho_k$ directly; instead, an estimate of $\rho_k$ can be obtained by just plugging $U_1$, $U_{1+k}$, $U_{1+2k}$, $\ldots$ into following formula as shown in [10]:

$$\hat{\rho_k}= 12 \sum_{i=0}^{h} U_{1+ik}U_{1+(i+1)k} - 3$$

where $h = \lfloor (n-1)/k \rfloor -1$. If we further assume that $U_i$'s are independent, then we have

$$\mbox{Var}(\hat{\rho_k}) = \frac{13h+7}{(h+1)^2}$$

Under the null hypothesis that $\rho_k =0$ (independence), the following statistic has an approximate standard normal distribution

$$A_k = \frac{\hat{\rho_k}}{\sqrt{\mbox{Var}(\hat{\rho_k})}}$$

The hypothesis will be rejected at significance level $\alpha$ if $\vert A_k\vert > \Phi^{-1}(1-\alpha/2)$. $\Phi$ is the distribution function of standard normal distribution.

In this project we have tested up to 10-lag autocorrelation of each RNG.