Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
The typical and widely used PRNG, the linear congruential generator always has a finite (though possibly "long") period. Are there PRNGs that have no finite period?
For this question it is not necessary that it be practical or used in real-world implementations.
If the state of the PRNG is finite, then it has a finite period. (By finite, I mean the same as we mean when we say that a finite-state automaton is finite: the set of all possible states is finite. For instance, if the state always fits into $b$ bits, for some fixed value of $b$, then its state is finite.)
In practice, worrying about the period of the PRNG may be akin to arguing over angels on a pinhead. A 256-bit state is large enough that a well-designed PRNG will never repeat within the lifetime of the universe. Therefore, concerns about repetition are pretty much irrelevant for any reasonable, well-designed PRNG.
In practice, the real challenge is to make the PRNG unpredictable (or close enough for the application's purposes); ensuring it won't repeat is much easier, relatively speaking.
Yes, this is possible if you are willing to use unbounded space. Consider a generator that stores every previously generated value in an internal history buffer.
Since every infinite cyclic sequence $S^*$ (capital letter $S$ representing a finite sequence of outputs, $S^*$ representing an unbounded repetition of it) must have some prefix $SS$, all that is required is to check if the next output that would be produced would make a sequence $SS$ for any $S$, and produce any other value instead. One can do this by using any underlying PRNG, and modifying outputs when such a length-2 cycle would be detected.
If by 'period' you mean 'period of the suffix', all that is needed is to occasionally drop elements from the front of the internal history buffer before generating a value, say once every other generated value. A proof by contradiction is simple.
Assume this generator generates a sequence with a periodic suffix. The generated sequence must therefore be $PS^*$ for finite sequences $P$ and $S$, where $S$ is much longer than $P$. Eventually the in-memory history buffer must be $RrR$ (lowercase $r$ representing any single output) where $Rr$ is a rotation of $S$, because the history will at some point have that length and $P$ will have been dropped by that point.
But if the history is $RrR$, $r$ cannot be generated again (by construction), so the period of the suffix must be longer than $S$.
To try and answer your question as posed, one possible way to build a PRNG with "no period" would be to have a generator that re-seeds itself periodically by using a subroutine that stores randomly selected output bits and then uses this block of bits as a "new seed" for the generator. So any given seed is only used for a period much smaller than its mathematical potential . So technically the output string is a concatenation of an endless series of generators with "small seeds" that goes on forever. The notion of a period, like the period of a shift register sequence, only has meaning if you assume a fixed seed for the register. If the seed is constantly changing, the notion of a "period" becomes meaningless no matter what the length of the shift register is.
