# Determining the length of a repeating sequence, with noise

first time poster.

I'm trying to determine the length of a repeating sequence, with noise. I.e. given the sequence 4, 12, 3, 4, 12, 3, 4, 12, 3, ... the period is apparently 3.

Now, what if the sequence was more complicated. What if each value had added noise? I was thinking of something with autocorrelation, or Fourier transform (my intuition tells me the repeating signal has a major frequency component, right? How can I determine which?)

It feels like this should be easy, but I'm having trouble implementing a solution.

Thanks

-

If the noise is additive, autocorrelation or Fourier transform seem the way to go. In general, time-domain and frequency-domain approaches are the most basic and standard tools in this area. Beware that the spectra of such sequence will have extra peaks corresponding to the "harmonics" of your signal. You can read about pitch detection, which is very related to your problem.

-

In connection with certain algorithms for integer factorization, there are methods due to Floyd and Brent for the so-called "cycle finding" problem. It would look like you can adapt these to your situation, but in the noisy case you will have to use a "fuzzy equality" comparison function, e.g. |x - y| <= tol where x and y are the two entities being compared, and tol is a small quantity.

-