I have this data plotted on a graph in which all points have the same value on the y-axis, e.g a constant integer "c", while the x-axis is the time in seconds. So, for a c = 25 on the y-axis, there are points on the graph corresponding to values on the x-axis equals to, let's say, 32, 59, 78, 142, 249, 286, 301, 310, 398, etc..

My goal is to find a sequence (arithmetic progression) of the type

$a_n = a_{n-1} + T $

Where, where $a_n$ is the time in the x-axis and $T$ the ratio of the AP.

I don't know the period $T$ nor the first element of the sequence (and therefore when the sequence begins) and there is white noise (probably most of the points that are in the data are not part of the sequence).

So, in short, I would like to discover a sequence with period $T$ in the middle of a bunch of "random" numbers, given these numbers.

I am thinking first about a brute force algorithm but that would have a running time of $O(n^2)$ but I believe there might be ways to improve or even algorithms that might suit this kind of job. Beforehand, I tried FFT (Fast Fourier Transform), but it did not work on this case because the data is not uniform. Any suggestions on algorithms or ideas to tackle this problem are more than welcome.

Here is the representation of the data on a graph: Image

  • $\begingroup$ This sounds like a problem of what's called "cycle detection". Perhaps see Floyd's cycle detection algorithm which apparently has complexity $\mathcal{O}(n)$. $\endgroup$
    – user20857
    Jun 28, 2017 at 22:48
  • 1
    $\begingroup$ So the arithmetic progression is an unknown subset of the given numbers? Could you write down a mathematical, rigorous description of a model by which the data is generated? Also, this being a question about statistical inference, rather than computational science, it might get better answers on stats.stackexchange.com. $\endgroup$
    – Kirill
    Jun 28, 2017 at 23:51
  • $\begingroup$ @Kirill, Yes, AP is an unknown subset of the given numbers. There is no description of such a model. This data is obtained from real users. Some of them have programs to do the job for them in regular intervals. My goal is to discover who are those users based on finding their regular activity points, which I know nothing as when they begin acting, what is the frequency of their acting, i.e where they have points (may be 2 points per minute or 1 point per 10 minutes) and when their activity ends. $\endgroup$
    – rgoncalv
    Jun 29, 2017 at 0:43
  • 2
    $\begingroup$ You need a model anyway in order to do inference: it doesn't have to be the "real" model, which you might not know, but could be your guess at an approximate random process, with some unknown parameters (such as $T$, among others) that generates this data. I still think you should consider stats.SE—this type of question is more common over there. $\endgroup$
    – Kirill
    Jun 29, 2017 at 1:19
  • $\begingroup$ Do you mean that the equation $a_n = a_{n-1}+T$ holds modulo some (possibly large) constant on the right hand side? $\endgroup$ Jun 29, 2017 at 17:06

1 Answer 1


This is essentially a linear fit of the data


This is obvious once you realize that an AP forms a straight line when plotted in 2-dimensions. Any linear regression tool (even Excel) should suffice for this exercise.

$T$ is given by the slope of the fit.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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