Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

2 Answers 2

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.