# Autocorrelation: numpy versus FFT

I have a series a of values (0 and 1) coming from a Brownian process with drift for which I am studying the autocorrelation.

I used two methods:

1) numpy autocorrelation:

corr = np.correlate(a,a,mode='full')/a.size
corr = corr[corr.size//2:]


2) Fourier transforms (Wiener-Khinchin):

A = np.fft.fft(a)
S = np.conj(A)*A/a.size
c_fourier = np.fft.ifft(S)


However, I get different results:

I am not very experienced with stochastics or signal processing, so I have some difficulties understanding where the difference comes from.

## 1 Answer

As this page https://ccrma.stanford.edu/~jos/ReviewFourier/FFT_Convolution.html mentions, when you perform cyclic convolution (FFT convolution) you have to add zeros to your signal $$A$$ to the length $$N_Y = N_A + N_A -1,$$ where $$N_Y$$ is the length of the output convolution and $$N_A$$ is length of your signal. In your case you are performing the FFT Correlation, which is almost the same operation and you should extend your signal $$A$$ with zeros as well.

So for example:

a = np.concatenate((a,np.zeros(len(a)-1))) # added zeros to your signal
A = np.fft.fft(a)
S = np.conj(A)*A
c_fourier = np.fft.ifft(S)
c_fourier = c_fourier[:(c_fourier.size//2)+1]


After that you should get the same results as for numpy auto-correlation.