23
$\begingroup$

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

$\endgroup$
  • 7
    $\begingroup$ This is a pedantic point to make, but on a finite-memory computer, every non-halting program is ultimately periodic. You could analyse the algorithm as running on a Turing machine, but any PRNG whose memory use is unbounded with time wouldn't be very practical. $\endgroup$ – Peter May 5 '14 at 20:20
  • $\begingroup$ @Peter you say "any PRNG whose memory use is unbounded with time wouldn't be very practical". It may not be practical when the memory use is quadratic or linear with respect to time, but what if it's only logarithmic? See my answer. $\endgroup$ – Don Hatch May 26 '16 at 4:34
38
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – D.W. May 26 '16 at 19:51
  • $\begingroup$ Link to the chat is broken. Is it still possible to see a log of the discussion? :/ @D.W. $\endgroup$ – oink Aug 22 '16 at 3:56
  • $\begingroup$ @cchan3141, I've restored it; try now. However, beware that comments are by design transitory, and the same goes for chat rooms. If you find anything in there that has lasting value to others, I encourage you to suggest an edit to the answer to incorporate that information, or post a new answer of your own. Thank you! $\endgroup$ – D.W. Aug 22 '16 at 3:59
7
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$

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.