Autocorrelation function

Background

The autocorrelation function (ACF) measures how a time series correlates with a lagged copy of itself. At lag $k$ it answers: "how similar is the series to itself $k$ steps ago?" The ACF is the basis for detecting seasonality and choosing the order of AR/MA models — for example, a slowly decaying ACF signals a trend, while a spike at lag 12 on monthly data signals yearly seasonality.

Problem statement

Implement autocorrelation(x, max_lag) returning the (biased) sample ACF for lags $0, 1, \dots, \text{max\_lag}$.

With $\bar x$ the mean and $n$ the length, define the autocovariance and the ACF:

$$c_k = \frac{1}{n}\sum_{t=0}^{n-k-1} (x_t - \bar x)(x_{t+k} - \bar x), \qquad \rho_k = \frac{c_k}{c_0}$$

(The same divisor $n$ is used for every lag — the standard biased estimator.)

Input

• x — 1-D sequence (np.ndarray or list) of length $n$.
• max_lag — int, the largest lag to compute ($0 \le \text{max\_lag} < n$).

Output

An np.ndarray of length max_lag + 1 with $\rho_0, \rho_1, \dots$ ; $\rho_0$ is always 1.

Examples

Example 1

Input:  x = [1, 2, 3, 4, 5], max_lag = 2
Output: [1.0, 0.4, -0.1]

Explanation: the mean is 3, so deviations are $[-2,-1,0,1,2]$ and $c_0=2$. Then $c_1 = (2+0+0+2)/5 = 0.8 \Rightarrow \rho_1 = 0.4$, and $c_2 = (0-1+0)/5 = -0.2 \Rightarrow \rho_2 = -0.1$.

Constraints

• Divide every autocovariance by $n$ (not $n-k$) — the biased estimator used by most ACF tools.
• Normalize by $c_0$ so $\rho_0 = 1$.
• If the series is constant ($c_0 = 0$), return 1.0 at lag 0 and 0.0 for all other lags.

Notes

• The biased estimator (dividing by $n$) guarantees a positive-semidefinite ACF and is what statsmodels.acf uses by default.
• Confidence bands of roughly $\pm 1.96/\sqrt{n}$ are used to judge which lags are significantly nonzero.