Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
It is not the bit length that matters as much as the number and size of the state variables that are associated with the PRNG. (And, of course, the mathematical details of the implementation.) –  cardinal Sep 28 '11 at 2:25
    
@cardinal: I believe he's counting those state variables as part of the number of bits; in other words, 'given an initial state specified by $b$ bits, what's the greatest period length of a generator on those bits?'. I suspect the answer, incidentally, is that the answer is uncomputable as a function of $b$ - this is pretty closely related to the Busy Beaver function... –  Steven Stadnicki Sep 28 '11 at 2:55
    
I asked the question in a wrong way, Steven is right, as is cardinal, of course. –  Felix Dombek Sep 28 '11 at 3:33
1  
@Steven Stadnicki: If the internal state of the PRNG consists of $b$ bits, then its output must repeat after at most $2^b$ iterations. Furthermore, it's not hard to construct PRNGs that achieve this maximal period regardless of their initial state. (Indeed, if the period is maximal for some initial state, it obviously must be so for all initial states, since all states will lie on the same cycle.) The size of the seed only affects the number of possible distinct output sequences, not the period length of those outputs. –  Ilmari Karonen Sep 28 '11 at 20:21
1  
Ilmari: that's true as long as you consider the 'internal state' to also include all of the 'variables' used by the PRNG, the algorithm itself, etc; otherwise the program could do something as simple as 'print state 0 out 5 times, then print state 1 out 5 times, then' or other period-amplification techniques. This is why having a formal description of your machine model has to be part of the problem. –  Steven Stadnicki Sep 28 '11 at 23:31

3 Answers 3

up vote 4 down vote accepted

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.

share|improve this answer
    
It's worth noting that this requires the right definition of state; for instance, it's easy to imagine initializing some LFSR generator by taking a single $32$-bit seed and running some linear-congruential generator to fill in all the elements of the shift register from it. In this case the 'state' is the full shift register, not simply the seed that was used to initialize it; there can only be $2^{32}$ different sequences from the generator (one for each seed), but the period of each can be much longer than this. –  Steven Stadnicki Sep 28 '11 at 17:22
    
@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. –  zyx Sep 28 '11 at 19:17

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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