(Note: The original version of the question generated 1 upvote. Adding various explanatory comments in 3 subsequent Edits, generated 2 downvotes, which leads me to think added in the overall confusion, so I am reverting this back to the original. Eric Towers covered the question with his answer sufficiently.)

How can I extract the period of an eventually periodic sequence $a_n$, other than manually examining the entire orbit and making comparisons?

If my function is $f(z)$, my starting point is $z_0$, denoting the iterates of $f$ as $f^{(n)}(z)$, $n\in \mathbb{N}$, the orbit will be: $\{z_0, f(z_0), f^{(2)}(z_0), \ldots,f^{(n)}(z_0),\ldots\}$, and the sequence is given by $a_n=f^{(n)}(z_0)$, with $a_0=z_0$, etc.

A necessary (but not sufficient - depends on precision $\epsilon$, etc) condition for an eventually $p$-periodic convengence is obviously $|a_{n+p}-a_n|\le \epsilon$, for given $\epsilon>0$, so if I check a (finite always) orbit backwards starting at the last point $a_N$ for matches, then if the condition is satisfied for $a_N$ and $a_{N-p}$, then that's close to the converging period being $p$.

This calculation obviously contributes at least $O(N)$ for each point on my graphics plane in the worst case and stalks badly the calculations for the overall convergence.

Is there a faster way to check a finite list of values of $a_n$ for (almost - eventual) periodicity, under the assumption that $a_n$ is eventually periodically convergent?

  • 5
    $\begingroup$ You might want to try to formulate this question very very carefully. Is the input sequence infinite? Is the algorithm supposed to be $O(p)$, where $p$ is the period? Or $O(N)$, where $N$ is the number of sequence-values examined? How, by examining finitely many values in a sequence, could one possibly tell that the remainder of the sequence was periodic, or almost periodic? Are we to answer this question only for sequences defined by iterated function application, or general sequences? That's a lot of questions, but on the face of it, this question seems ludicrous, so...they need answers. $\endgroup$ Sep 19 '20 at 21:54
  • 3
    $\begingroup$ Moreover, you are talking about real numbers. How do you give a real as input to an algorithm? $\endgroup$
    – J.-E. Pin
    Sep 19 '20 at 23:00
  • $\begingroup$ And how is this sequence given? In general there is obviously no way to determine the period of a sequence just by examining finitely many terms... $\endgroup$ Sep 19 '20 at 23:03
  • $\begingroup$ What "clarification"? What you're literally asking for is obviously impossible - if what you want is something thats not obviously impossible i can't see what it might be. You say your edit "reflects" his comments - it would be better to answer his questions. HOW IS THE SEQUENCE GIVEN? (eg, you have a formula, or a recurrence, or just the first million terms...) $\endgroup$ Sep 19 '20 at 23:21
  • $\begingroup$ It's clear that the question makes no sense unless you have a formula. It does not follow, obviously or not, that you do have such a formula. $\endgroup$ Sep 19 '20 at 23:36

You describe a search for a cycle in iterated function values. This is called "cycle detection".

If exact computation is possible in reasonable time (for instance if this is a sequence of integers), Floyd's algorithm finds the period in time $O(\mu +\lambda)$, where $\mu$ is the index of the first element of the cycle and $\lambda$ is the period. It requires $O(1)$ storage (since it only ever stores two sequence values). Brent has a similar algorithm with the same asymptotics. There are several algorithms that trade increased space complexity for time complexity.

If exact computation is not possible, then you are looking at "approximate period detection" (example paper). There are various definitions of approximate period, for instance this, this, and this. Algorithms strongly depend on what sort of approximation you are willing to use. A method is to use the Fourier transform to estimate the period -- note that this makes no claim that the values of the sequence approximately repeat.

If you attempt to use an exact method for an inexact iterator or inexact sequence, then you should not expect the algorithm to ever find a period. See chaotic iterated maps, for instance the logistic map -- (imagine that your iterations should be right at the edge of a transition from periodic to chatoc behaviour. If you had infinite working precision, you could stay on the periodic side, but since you don't you should expect unpredictable transitions from periodic to chaotic behaviour and back.)

  • $\begingroup$ Thanks. That's what I was looking for. I will go through the refs and upvote as appropriate, asap. $\endgroup$ Sep 20 '20 at 0:57

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.