1
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ postscript: it turns out this problem is somewhat related to some very difficult theoretical problems eg in number theory. for example the mobius function can be thought of as a kind of PRNG, and think theres a proof it has no period... also a fairly simple question about its "spread" is equivalent to the Riemann hypothesis. see randomness in number theory by sarnak slides 13-15 $\endgroup$ – vzn Nov 22 '13 at 16:26
  • $\begingroup$ No, there are finite states, so the period is finite, isn't this obvious? $\endgroup$ – Martin Spamer Jan 17 at 18:33
  • $\begingroup$ In fact, this question is not well-defined enough because of one inherent ambiguous concept, pseudo-randomness and one undefined specification, how to use output. Recall that our favorite Turing machines have finite states but can read unbounded output. It is imaginable that some Turing machine will generate pseudo-random numbers without finite period. Note this does not contradict the accepted answer, where it considers the output number more or less as part of its states. $\endgroup$ – Apass.Jack Jan 17 at 18:55
12
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • 2
    $\begingroup$ "If the state of the PRNG is finite, then it has a finite period." This depends on what you mean by "the state... is finite". For example, the sequence 1, 2, 3, 4, ... has infinite period but can be generated while only ever using finite storage, though the amount needed grows without bound over time. $\endgroup$ – David Richerby Nov 22 '13 at 12:42
  • 1
    $\begingroup$ the sequence 1, 2, 3, 4 ... etc.. has a period of 256 for a 8bit size of state. It's period although large is not infinite. You still need to store the number that you last generated to get the next number. $\endgroup$ – over_optimistic Jul 15 '16 at 4:36
0
$\begingroup$

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$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ @D.W. That can't be. If the history is SsS (S is a sequence, s is a value), generating anything except s will prevent a doubled history. You can't get stuck. $\endgroup$ – Veedrac Jan 24 at 14:14
  • $\begingroup$ @D.W. Your RNG can literally just alternate zero and one and this scheme still works. $\endgroup$ – Veedrac Jan 24 at 14:15
  • $\begingroup$ @D.W. Your underlying PRNG has period 1. You skip (or otherwise modify) outputs when the PRNG would enter a length-2 loop. So 0 1 0 0 1 1 0 1 0 1 0 1... $\endgroup$ – Veedrac Jan 24 at 20:58
  • $\begingroup$ @D.W. More complex would be the constraint that no suffix is periodic, but that is also possible (just not using this construction). $\endgroup$ – Veedrac Jan 24 at 21:02
  • $\begingroup$ @D.W. 0101 would be a sequence repeated twice, so the generator refuses to generate the last 1, instead skipping the value. Then 010010 would be a sequence repeated twice, so the generator refuses to generate the last 0, instead skipping the value. I didn't know period typically referred to the period of the suffix, so I'll add a different construction to my post. $\endgroup$ – Veedrac Jan 25 at 2:24
-4
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • 3
    $\begingroup$ How do you create that "subroutine that stores randomly selected output bits"? How can that subroutine select random output bits in the first place? To do that, we need another PRNG or something truly random. So, I am afraid this is not an answer. $\endgroup$ – Apass.Jack Jan 17 at 18:46
  • $\begingroup$ Your reseed procedure is deterministic, so your PRNG would still have a period. If your reseed procedure was not deterministic then you wouldn't have a PRNG anymore. @Apass.Jack In Stack Exchange terminology, this is an answer, but it's a wrong answer. $\endgroup$ – Gilles♦ Jan 18 at 16:29
  • $\begingroup$ A seed is something that is produced externally from the PRNG. If we fix a seed, the PRNG produces a deterministic sequence that "looks random". All you're doing is to say that some intermediate values produced by the PRNG are "new seeds", but that doesn't make them so, because they weren't generated externally to the PRNG. Instead, they're deterministically produced from the original, true seed, so the whole procedure is still deterministic once that original seed is chosen. All you've done is produce a more complicated PRNG, so it still has a period. $\endgroup$ – David Richerby Jan 21 at 18:20
  • $\begingroup$ Please don't use the answer box to respond to other comments. It seems you have created two separate accounts. You can merge them following the instructions here. If you regain access to the account you used to post your original answer, you can edit it to incorporate the relevant information using the 'edit' link under your answer. We have these restrictions to help us maintain our high quality standards here. Thank you for your understanding and participation. $\endgroup$ – D.W.♦ Jan 24 at 2:52

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.