Autocorrelation Function

Compute the sample autocorrelation of a series for lags 0 to max_lag.

Autocorrelation measures how much a series looks like a shifted copy of itself. A strong value at lag 12 in monthly data points to a yearly cycle. The values are what you read to choose the order of an AR or MA model.

Use the standard estimator, which divides every lag by the same total variance:

m   = mean(x)
r_k = sum_{t=0}^{n-1-k} (x_t - m) * (x_{t+k} - m)  /  sum_{t=0}^{n-1} (x_t - m)^2

r_0 is always 1.

Function signature

def autocorrelation(x, max_lag):

Example

Input

autocorrelation(np.array([1.0, 2.0, 3.0, 4.0]), max_lag=2)

Output

array([ 1.  ,  0.25, -0.3 ])

Reasoning

The deviations from the mean 2.5 are [-1.5, -0.5, 0.5, 1.5], and their squares sum to 5. Lag 1 pairs neighbours: 0.75 - 0.25 + 0.75 = 1.25, so r_1 = 0.25. Lag 2 pairs values two apart: -0.75 - 0.75 = -1.5, so r_2 = -0.3.

Constraints and notes

• 0 <= max_lag < len(x).
• The series is not constant, so the denominator is not zero.
• Return an array of length max_lag + 1.