Why is the "period of a (pseudo)random number generator" important?

Question

I've been trying to understand (pseudo)random number generator code from various sources and the concept of the period continues to elude me. To satisfy the minimum level of understanding, I've tried to think of it in terms of "sample size" from statistics.

However, I believe my understanding may be overly simplistic. The documentation I've found for functions/calls that allow (or require) a period indicate the value is important but fall flat in explaining why...

Where it is possible for a programmer to set the period for a (pseudo)random number generator, what defines a good (optimal or desirable) period and why?

Additionally (for focused understanding): - Is it important (or helpful) to define the period using a prime number? - Does a large period or a small period produce a more desirable output?

Answer 1

Computers are not Turing Machines. They are Deterministic Finite State Machines.

Turing Machines have infinite memory, computers have finite memory. Turing Machines have arbitrarily many (though finite) states, computers can't have arbitrarily many states, the number of different states that a computer can be in is bounded by its memory (a computer with 1 KiByte of memory and 4 8-bit registers can only be in 8*2¹⁰²⁴ + 4*2⁸ =~ 10³⁰⁰ distinct states).

The program itself is also stored in memory, therefore it is itself part of the state. Any program which runs long enough must at some point end up in a state in which it was once before. And since the program itself is part of the state and computers are deterministic, this means that it will do the exact same thing it did the last time it was in this state, thus it will end up in the same followup-state it ended up the last time, which means that it will now do the same thing it did … and so on. Any programs which runs long enough will at some point end up in a state it was in before and from that point on run in exactly the same way it did the last time.

This length of steps when the program starts to repeat itself is called the period. Every program has one, not just Pseudo-Random Number Generators.

Note that mostly, those periods are theoretical. Even if the 1 KiByte computer I mentioned above had a 5 THz CPU, it would still take 10²⁷⁰ times the current age of the universe to cycle through 10³⁰⁰ states.

However, most programs, and certainly most PRNGs don't use the entire memory of the computer just for their own state. (PRNGs in particular are usually embedded into much larger programs and thus need to "steal" their memory from them.) Plus, programs don't cycle through all possible states perfectly, typically, they can only be in a much smaller number of states. The period length can never be longer than the number of internal states, and is typically shorter. For a badly designed PRNG, it is way shorter.

The RANDU PRNG that was used on the IBM System/360 in the Scientific Subroutine Library and ported to other mainframes was used for decades in research, simulations, statistics and so on, and it has (among other major flaws, e.g. it can only ever generate odd integers, never an even one) a period of just 2²⁹. Which means that after about only 10 billion steps you know exactly what number is going to come next. (It takes only about 40 GiByte to store the entire sequence!) If you play online black jack, you know all the cards that are coming, if you play online roulette, you know what number is going to come next, and so on.

Where it is possible for a programmer to set the period for a (pseudo)random number generator

Generally, it isn't. The period length is a property of the algorithm. There are some algorithms where you can choose the size of the internal state, which influences the length of the period.

what defines a good (optimal or desirable) period

Long. The longer the better.

How long? Well, cynically speaking: long enough that buying enough harddisks to store it will be more expensive than attacking some other part of the system (e.g. bribing the casino's datacenters janitor to let you in and install a backdoor on the server which sends you the player's cards).

and why?

I hope that's obvious now. A PRNG with a small period (say 5) will give the same 5 numbers over and over again. That's not very "random".

Answer 2

Take your favorite program using some PRNG.

Then imagine what would happen if the period of the PRNG becomes very small (e.g. 100).

Of course it depends upon the program, but if you use the weak PRNG for encryption, an attacker could easily notice the periodicity, and eventually be able to decrypt secret messages. If you use the weak PRNG for Monte Carlo simulation, running your simulation for a long time won't teach you anything more than running it for a short time, etc.

I am not a PRNG expert, but AFAIK the period is usually not some tunable parameter. However, you can choose your PRNG, and some PRNG give (in their documentation) some promises (or expectations) about their period. Usually a PRNG with a longer period has a bigger state, so is slower. So you have a tradeoff to make.

Answer 3

The other answers provide some good theory, but there is a piece of the practical application missing.

Where it is possible for a programmer to set the period for a (pseudo)random number generator

Generally, this cannot be set. This is a property of the generator function. Need a different period? Select a different function (or variation)

what defines a good (optimal or desirable) period and why?

Generally, a period should be as long as possible. A true RNG that uses real-world entropy has no period, and these are ideal for certain applications.

The longer the period, the less time before it repeats itself. If a PRNG repeats itself at the wrong moment, it could manifest as a user-visible anomaly (e.g. a card game dealing using the same deck order). Sometimes this is desirable: for example, one could give a Minecraft seed to someone else to check out the same generated world (technically nearly-same in the case of Minecraft, as the accepted answer points out). Sometimes, it is not: cryptographic applications are particularly sensitive to PRNGs that repeat, which is why they tend to include entropy as well.

PRNGs are necessarily bounded by the size of the variable used to hold its internal state: as the accepted answer says, the current state of the PRNG defines its next state. It is essentially a finite state automaton where you can (usually) pick your initial state (seed) and the states are one big loop. Using the pigeonhole principle one can prove that if the internal state is e.g. 32 bits, then the period of the PRNG has an upper bound of 2³² unique states. Note that the actual period is likely to be lower: the state merely defines the theoretical upper bound.

In reality, it is possible, and increasingly more common, to increase the effective period or reduce the potential damage done when the period repeats by using these methods:

• Use a larger internal state than is required by the user of the PRNG and return only part of the number. For example: if 32 bit integers are needed, use 64 bit state internally and simply return the lower 32 bits of each number. The same 32 bit integer may be returned multiple times. However the next number returned is unlikely to be the same because the actual internal state is different. For example:

  Internal state: 0100 0110 returns 0110.

  Internal state: 0011 0110 also returns 0110.

  This is part of the strategy employed by the Mersenne Twister which has a famously long period (although it has certain drawbacks that should be considered).

• Use multiple values to generate a single number. This is a strategy employed by some "real" entropy-based generators to "normalize" the data. For example: given a stream of binary digits, discard pairs that are different, and only use consecutive digits that match.

  10 01 11 00 10 00 01 11 becomes 11 00 00 11 and like digits are combined, giving the quad 1001.

  Depending on the data being extracted, this can alter the meaning of a value as it is reused as the period repeats, effectively making it something different. This is less useful for PRNGs than entropy-based RNGs, but it is still possible to treat the state as a bit stream. This can make the effective period larger depending on the strategy used and the data retrieved.

• If the same value is treated differently when it repeats, it can mask the fact that the period repeated. This is similar to how Java's java.util.Random class works. If a value is retrieved as a 64 bit integer the first time and a 32 bit integer the next time, nobody might know it actually repeated. Examples of how to make this work assuming a 64 bit internal state:

  • If a 64 bit integer is requested, simply return the internal state.
  • If a shorter integer is requested, mask off some of the bits or combine them. Perhaps a 32-bit value could XOR both halves of the 64 bit value together.
  • If a boolean is requested, apply a technique to use all of the bits to determine the value (e.g. even number of bits set is false, odd is true).
  • Floating point values can be trickier due to IEEE 754 constraints on the bit pattern, but there are ways to use random bits to get random values.

• If a bounded value (e.g. give me an integer from 1 to 100) is required, that makes the task even easier. A simple modulo operation can introduce bias, but one can apply techniques to use more of the bits to distribute the value evenly. The same state used twice but distributed against different intervals will likely return different numbers.

• Include entropy when returning a value. Keep the same internal state, but maybe combine it with binary data representing something non-deterministic such as the internal temperature of the computer's CPU to many decimal places when returning a value from the PRNG. Maybe do the same thing but with the more precise internal clock that measures individual CPU ticks. This is on the edge of what a PRNG is, technically it is more of a hybrid approach, but similar tactics are used for seeding PRNGs in the first place.