High autocorrelation when taking the L-th order of difference of a sequence of independent random numbers

Question

To explain this question in more detail, I'll first elaborate my approach:

1. I simulated a sequence of independent random numbers $X = \{x_1,...,x_N\}$.

2. I then take $L$ times the difference; i.e. I create the variables:

   $dX_{1} = \{X(2)-X(1),...,X(N)-X(N-1)\}$

   $dX_{2} = \{dX_{1}(2)-dX_{1}(1),...,dX_{1}(N-1)-dX_{1}(N-1-1)\}$

   $...$

   $dX_{L} = \{dX_{L-1}(2)-dX_{L-1}(1),...,dX_{L-1}(N-L)-dX_{L-1}(N-L-1)\}$

I observe that the (absolute) autocorrelation of $dX_{L}$ increases as $L$ becomes larger; the ac approaches even 0.99 for $L >100$. I.e. when taking the L-th order of difference, we create a series of highly dependent numbers (sequence) out of an initially independent sequence.

Here are some graphs to illustrate my observations:

My questions:

• Is there any theory behind this approach, and its implications or applications for it?

• Does this indicate that this approach exploits the weaknesses of a pseudo-randomn generator (of the computer). I.e. the generated "random" sequence is not trully random, and this is illustrated/proved from my approach?

• Can we exploit the high autocorrelation of the L-th order of differences, in order to predict the next number in the sequence (i.e. $X(N+1)$). I.e. if we can predict the next number of $dX_{L}$ (through e.g. linear regression), we can deduce back the estimated sequence $X(i)$ through taking $L$ times the cumulative sum. Is this a feasible approach?

Objective Note that I am trying to predict $X(N+1)$, but since the numbers are generated independentaly and random, this is very hard (low ac of $N$).

Answer 1

Theory

If the autocorrelation is going to have any meaning, we must suppose the original random variables $X_0, X_1, \ldots, X_N$ have the same variance, which--by a suitable choice of units of measure--we may set to unity. From the formula for the $L^\text{th}$ finite difference

$$X^{(L)}_i=(\Delta^L(X))_i = \sum_{k=0}^L (-1)^{L-k}\binom{L}{k} X_{i+k}$$

for $0 \le i \le N-L$ and the independence of the $X_i$ we readily compute

$$\operatorname{Var}(X^{(L)}_i) = \sum_{k=0}^L \binom{L}{k}^2 = \binom{2L}{L}\tag{1}$$

and for $0 \lt j \lt L$ and $i \le N-L-j$,

$$\operatorname{Cov}(X^{(L)}_i, X^{(L)}_{i+j}) = (-1)^{j}\sum_{k=0}^{L-j} \binom{L}{k}\binom{L}{k+j} = (-1)^{j}\frac{4^L \binom{L}{j} j!\Gamma(L+1/2)}{\sqrt{\pi}(L+j)!}.\tag{2}$$

Dividing $(2)$ by $(1)$ gives the lag-$j$ serial correlation $\rho_j$. It is negative for odd $j$ and positive for even $j$.

Stirling's Formula gives a readily interpretable approximation

$$\log(|\rho_j|) \approx -\left(\frac{j^2}{L} - \frac{j^2}{2 L^2} + \frac{j^2 \left(j^2+1\right)}{6L^3}-\frac{j^4}{4 L^4} + O(L^{-5})O(j^6)\right)$$

As a function of $j$ its magnitude is roughly a Gaussian ("bell-shaped") curve, as we would expect of any diffusion-based procedure like successive differences. Here is a plot of $|\rho_1|$ through $|\rho_5|$ as a function of $L$, showing how rapidly the serial correlation approaches $1$. In order from top to bottom the dots represent $|\rho_1|$ through $|\rho_5|$.

Conclusions

Because these are purely mathematical relationships, they reveal little about the $X_i$. In particular, because all finite differences are linear combinations of the original variables, they provide no additional information that could be used to predict $X_{N+1}$ from $X_0, X_1, \ldots, X_N$.

Practical observations

As $L$ grows, the coefficients in the linear combinations grow exponentially. Notice that each $X^{(L)}_i$ is an alternating sum: specifically, in the middle of that sum appear relatively large coefficients close to $\binom{L}{L/2}$. Consider actual data subject to a little bit of random noise. This noise is multiplied by these large binomial coefficients and then those large results are nearly canceled by the alternating addition and subtraction. As a result, computing such finite differences for large $L$ tends to wipe out all information in the data and merely reflects tiny amounts of noise, including measurement error and floating point roundoff error. The apparent patterns in the differences shown in the question for $L=100$ and $L=168$ almost surely provide no meaningful information. (The binomial coefficients for $L=100$ get as large as $10^{29}$ and as small as $1$, implying double-precision floating point error is going to dominate the calculation.)

Answer 2

This is more a comment or, at best, maybe a further clue to solve your question, but my reputation doesn't allow me to post comments.

I replicated your experiment in Stata using draws from a standard Normal with the following code:

clear all
set obs 100000

gen t = _n
tsset t

drawnorm x, n(100000)

forvalues i = 1(1)100 {
generate D`i' = D`i'.x
}

Looking at the correlograms of the differenced variables, I was wondering why the confidence bands are so tiny. I have never seen such small confidence bands in a Stata correlogram. Any ideas?

I was thinking this could be a clue because, with confidence bands so small, even the tiny autocorrelations from the furthest lags are being counted in your absolute autocorrelation, if I'm interpreting "absolute" correctly.

Here is the correlogram for my dX_10...

...and here it is again, zoomed in on the first 10 lags...

Answer 3

This is expected because the differences are not independent of each other. For example, $dX_1(1) \equiv X(2) - X(1)$ is directly proportional to $X(2)$ while $dX_1(2) \equiv X(3) - X(2)$ is inversely proportional to $X(2).$ Because the definitions of consecutive elements of $dX_1$ share elements of $X$ in this inverse way, we expect them to be inversely correlated to each other. In fact, as we go to higher order differences $dX_i$, consecutive values share a higher and higher fraction of the elements of $X$ that go into their definition, and their anticorrelation increases. However, if we did not know the shared element ($X(2)$ in my example) we would not be able to calculate any differences that include this element. We therefore cannot use the anticorrelations in the differences to predict unknown elements of $X$ if they are generated independently of the known elements.