0
$\begingroup$

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

Improve this question
$\endgroup$
  • $\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$ – Spencer Bryngelson Jun 28 '17 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 '17 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 '17 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 '17 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$ – Wolfgang Bangerth Jun 29 '17 at 17:06
1
$\begingroup$

This is essentially a linear fit of the data

$a_{n}=a_{n−1}+T(1)$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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