Autocorrelation at lag k

mediumMathsacceptance —~20 min

Implement autocorr(x, k) — the lag-k sample autocorrelation: with m the mean of the whole series, Σ_{t=k}^{n-1} (x_t - m)(x_{t-k} - m) divided by Σ_{t=0}^{n-1} (x_t - m)².

It is the first thing to compute before believing a signal: if today's return does not remember yesterday's, most of technical analysis has nothing to hold on to. Return the value rounded to 4 decimal places.

example 1

input

x=[0.01, -0.01, 0.02, -0.02, 0.015, -0.015], k=1

output

-0.8448

example 2

input

x=[0.01, 0.02, 0.015, 0.03, 0.025, 0.02], k=1

output

constraints

k + 2 ≤ len(x) ≤ 10_000
x is not constant

teacher · 2 hints · the first is free

↗ read the theory

the chapter this problem is cut from

▶ open in the workbench

run the same math on a real tape

●solution.py· utf-8 · spaces:4

def autocorr(x: list, k: int) -> float:
    """Lag-k autocorrelation, rounded to 4 dp."""
    n = len(x)
    # TODO: demean the series first — deviations from the mean, not raw values
    num = sum(x[t] * x[t - k] for t in range(k, n))
    den = sum(v * v for v in x)
    return round(num / den, 4)

ln 1, col 1tab indent · esc leave editor

python 3.13 · pyodide

+ 6 hidden on submit

input · keyword arguments to autocorr()

x=[0.01, -0.01, 0.02, -0.02, 0.015, -0.015], k=1

expected

-0.8448

the judge calls autocorr() with exactly these inputs · outputs are compared to 6 decimal places

● standing bypython 3.13 in your browser · pyodide 0.28.3 · judged on the server to 6 dp⌘↵ run · ⌘⇧↵ submit

paper only · educational · not advice