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
Are all pseudo-random number generators ultimately periodic? Or are they periodic at all in the end?
By periodic I mean that, like rational numbers, they in the end generate a periodic subsequence...
And pseudo-random means algorithmic/mathematical generation of random numbers...
All pseudorandom generators that don't rely on outside randomness and use a bounded amount of memory are necessarily ultimately periodic since they have finite state. You can think of them as huge deterministic finite automata which have special "output" states in which they give their output. All finite automata are eventually periodic, and so all pseudorandom generators produce eventually periodic output.
However, the period length can be enormous. For example, a PRNG with a cryptographic state of 128 bits might only cycle once every $2^{128}$ bits of output, and so even if outputting one bit every nanosecond, the solar system will be dead ere the PRNG repeats.
If the PRNG is allowed to use an unbounded amount of memory (which isn't realistic) then it can, for example, output the binary expansion of $\sqrt{2}$, which we know isn't eventually periodic (since $\sqrt{2}$ is irrational).
PRNGs are state-machines. If they're based only in internal input (in contrast to Poker Stars RNG which is a combination of hardware and software, seeding itself continuously from... sound samples) you'll get (C, S1,...) where C is the current (or previous) value and S1,... could be a set of states:
If there are possible N values (since the memory is bounded) of C and you iterate N+1 times, you will hit the same value for C at least twice. If you iterate 2N+1 times, you will hit the same value for C at least 3 times.
Let T = (Ct, S1t, S2t) be a certain state (current value and other states).
Let M = #{values for S1}X{values for S2}X{...} be the cardinal of possible states combinations (again: since the memory is bounded).
If you iterate NM+1 times the algoritm, you'll reach at least twice the same state (Ct, S1t, S2t, ...), thus generating the same output value and the same following state sequence than the first time, and so becoming periodic.
Simple example of pseudo-random sequence that is not periodic: concatenate together the binary representations of all positive integers, in order:
110111001011101111000...
(Prepend a "." and it's called the binary Champernowne constant.)
Of course this isn't very high quality as far as pseudo-random sequences go, but it demonstrates that it's possible without using much memory.
In this example, the memory needed to store the state is theoretically unbounded; however it grows very slowly (compared to, say, the memory needed to compute digits of $\pi$ or of $\sqrt{2}$). Likewise for the time needed to generate each bit.
The unbounded memory requirement isn't a problem for a turing machine, and it's probably not a problem in practice, either, since the growth is so slow, but it depends on what you intend to use this thing for.
For instance, if all you're doing is actually generating bits in sequence, then you can easily generate arbitrarily many bits of this aperiodic sequence, on a real computer, without ever running out of memory in the lifetime of the universe. However for that use case aperiodicity has no advantage over simply having a very large period such as $2^{128}$, which won't be reached in the lifetime of the universe either. So, not much difference from the point of view of "normal" usage.
The differentiator, I suppose, is if you want to do things like derive other PRNGs from your PRNG, say by taking a subsequence at regular intervals. If you start with the aperiodic PRNG, you'll get an aperiodic result no matter what period you sample at, whereas if you start with a PRNG of period $2^{128}$, you'll start running into trouble if the sampling period is sufficiently large.
