Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


share|cite|improve this question

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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.