Given a sequence of numbers of length one may want to look for evidence of its periodic behavior. One way to do this is by computing autocorrelation, the correlation of the sequence with a shift of itself. Here is one reasonable way to do so: for lag values compute the correlation coefficient of with . That the lag does not exceed ensures the entire sequence participates in the computation, so we are not making a conclusion about its periodicity after comparing a handful of terms at the beginning and the end. In other words, we are not going to detect periodicity if the period is more than half of the observed time period.

Having obtained the correlation coefficients, pick one with the largest absolute value; call it R. How large does R have to be in order for us to conclude the correlation is not a fluke? The answer depends on the distribution of our data, but an experiment can be used to get some idea of likelihood of large R.

I picked independently from the standard normal distribution, and computed as above. After 5 million trials with a sequence of length 100, the distribution of R was as follows:

Based on this experiment, the probability of obtaining |R| greater than 0.5 is less than 0.0016. So, 0.5 is pretty solid evidence. The probability of is two orders of magnitude less, etc. Also, |R| is unlikely to be very close to zero unless the data is structured in some strange way. Some kind of correlation ought to be present in the white noise.

Aside: it’s not easy to construct perfectly non-autocorrelated sequences for the above test. For length 5 an example is 1,2,3,2,3. Indeed, (1,2,3,2) is uncorrelated with (2,3,2,3) and (1,2,3) is uncorrelated with (3,2,3). For length 6 and more I can’t construct these without filling them with a bunch of zeros.

Repeating the experiment with sequences of length 1000 shows a tighter distribution of R: now |R| is unlikely to be above 0.2. So, if a universal threshold is to be used here, we need to adjust R based on sequence length.

I did not look hard for statistical studies of this subject, resorting to an experiment. Experimentally obtained p-values are pretty consistent for the criterion . The number of trials was not very large (10000) so there is some fluctuation, but the pattern is clear.

Length, L | P(L^{0.45}|R| > 4) |
---|---|

100 | 0.002 |

300 | 0.0028 |

500 | 0.0022 |

700 | 0.0028 |

900 | 0.0034 |

1100 | 0.0036 |

1300 | 0.0039 |

1500 | 0.003 |

1700 | 0.003 |

1900 | 0.0042 |

2100 | 0.003 |

2300 | 0.0036 |

2500 | 0.0042 |

2700 | 0.0032 |

2900 | 0.0043 |

3100 | 0.0042 |

3300 | 0.0025 |

3500 | 0.0031 |

3700 | 0.0027 |

3900 | 0.0042 |

Naturally, all this depends on the assumption of independent normal variables.

And this is the approach I took to computing r in Python:

import numpy as np n = 1000 x = np.random.normal(size=(n,)) acorr = np.correlate(x, x, mode='same') acorr = acorr[n//2+1:]/(x.var()*np.arange(n-1, n//2, -1)) r = acorr[np.abs(acorr).argmax()]