2
$\begingroup$

Is there any upper limit for the period of any pseudo-random number generating algorithm with a fixed number of bits? I know there are some algorithms with a very large period, such as MT19937, but I wonder if it is possible to derive a theoretical maximum period for any given bit length.

Edit:

As pointed out in the comments, this is not so much about the number of output bits as about the total number of bits that the algorithm can use to store a state.

  • 0
    What you're implicitly using is a 'functional iteration' state machine for the PRNG where at each step we have some state $s_n\in S$, apply a function $f: S\rightarrow S$ to get our new state $s_{n+1}=f(s_n)$, and then output as our random number $r_{n+1}=g(s_{n+1})$ for some output function $g$. This is a very standard (and convenient) model for purposes of PRNGs, but it's obviously far from the only formal machine model.2011-09-28

3 Answers 3

1

I think the answer you want is two raised to the power of the number of bits of internal state it has. But the real-world answer is that it can be entirely aperiodic.

For example, a Mersenne twister that mixes in the TSC value on every query on a modern networked PC with a hard drive is aperiodic -- the output partially depends on microscopic zone temperature variations in the quartz crystals in its oscillators (which determine the relative rates of the core clock, network clock, and hard drive controller clock) and turbulent shearing forces in the hard drive (which affect access time). These never repeat.

4

To expand on my comment: making this an answerable question means formalizing the notion of 'generating algorithm with a fixed number of bits'; because (as cardinal essentially points out) quite a bit of state can be embedded in the algorithm itself (or in a Turing Machine implementing it). To eliminate this possibility, it's easiest to take a Universal Turing Machine as your 'algorithm implementor' and use the total length of the input tape (i.e., the description of the algorithm as well as its starting data) as the parameter. This turns the original question into 'given a $b$-bit input tape to a UTM, what is the longest period an output sequence of that UTM can have?'. This is somewhat analagous to the Busy Beaver problem, and akin to that problem, I strongly suspect that the answer - as a function of $b$ - grows uncomputably fast. Of course, these maximal sequences won't be pseudo-random in the sense that they won't pass statistical tests for randomness; but it's not clear to me how to even begin tackling the problem in the presence of an additional constraint like 'the periodic sequence must satisfy some statistical properties'.

4

MT19937 and many other practical PRNG algorithms are deterministic functions on a state space of fixed size ($s$ bits). The state can be thought of as a "seed" that is initialized (usually from an external bit source such as the clock time when the computer was booted) and is updated each time the random number routine is called. The output of the pseudorandom number generator is some fixed function of the state, such as its final $k$ bits. For any PRNG of this type, the maximum possible period is the number of possible states, $2^s$.

For a broader notion of PRNG the period could be much larger, or uncomputable as explained in the other answer.

  • 0
    @Steven: thanks. I think state is (essentially) uniquely defined, but yes, it's easy to imagine "seed" being used to mean not the initial state of the PRNG, but some other data that are processed to produce an initial state.2011-09-28