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

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$).

• I am sorry.You edited it twice but there is a lot I don't understand. I doubt that the problem is with the pseudo random number generator. Are you transforming the uniform random numbers to some other distribution? You are taking differences but why if the variables are suppose to be independent? Why are you trying to predict numbers in the sequence? Differencing is usual done to remove polynomial trend. – Michael Chernick Dec 10 '16 at 2:14
• @Michael My goal is to predict the next number in the sequence, not to change the distribution. Trying to predict X(N+1) is hard because the numbers of the sequence are independent and random (low autocorr as well). So I differenced the sequence L times amd found that the ac increases when L increases, which led to me wondering what this means and whether it can be exploited. – JohnAndrews Dec 10 '16 at 8:41
• I added some graphs for illustration. – JohnAndrews Dec 10 '16 at 10:00
• The difference of order $L$ is a linear combination of the original values across a window of width $L+1$, so of course there will be strong relationships among successive values of the differences. There's no way to exploit this, because you're basically predicting tiny deviations from the values you already know. – whuber Dec 12 '16 at 17:34

## 3 Answers

### 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.)

• Very clear, and after reading this it totally makes sense. On your last point, indeed I tested it out by adding a small number (e.g. 0.00001) for a large $L$, and its astonishing to see that it has such a huge effect on $X_i$, this due to the large coefficients. In other words, one would need a highly accurate forecast in order to predict the next sequence, but since there is no additional info in the sequences for a large $L$, it would seem an impossible task. – JohnAndrews Dec 12 '16 at 22:55

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.

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 Di' = Di'.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...

• Looking at your graph, are the confidence bands also small for smaller lags? I only use AC(1) of the differenced variables. With absolute I simply mean either negative or positive ac. – JohnAndrews Dec 10 '16 at 8:50
• Yes, the bands are also very small for dX_1 through dX_9. And, sorry, I thought by "absolute" you somehow meant the sum of the correlations for all lags. – Alvaro Fuentes Dec 10 '16 at 18:29
• AC(1) is indeed higher the more we difference like you said... interesting. – Alvaro Fuentes Dec 10 '16 at 18:33