Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

share|improve this question
5  
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. –  Peter May 5 at 20:20
    
You should check out this video on youtube. I found this video during one of those times where you just click through the suggested videos list. It has a lot of information about random numbers and how they work. And yes, they are periodic as said in the video. –  matthapkidokarate May 5 at 20:28
    
for an example of a PRNG-like construction that seems to be aperiodic see collatz problem (or other fractal-like problems). any proof of its periodicity would likely be a proof of the problem (still unsolved for ~¾ century). this question also would seem to have some connection to the busy beaver problem and undecidability. however this is an unconventional view. might attempt to work this into answer with some comment upvotes. –  vzn May 6 at 16:16
    
Another unconventional view is based on real numbers: assume that the digits of some real number are considered random... If I have an algorithm to generate the digits, those digits will not be necessarily periodic...? –  user13675 May 11 at 17:27

2 Answers 2

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

share|improve this answer
2  
Why can't they be general Turing machines? –  Niklas B. May 5 at 20:03
1  
Ah I see, they would also need to use infinitly much space –  Niklas B. May 5 at 20:25
1  
Wouldn't $\sqrt 2$ have to be normal as well, for it to be a true PRNG? I don't believe this is known. –  WChargin May 6 at 0:39
2  
Could you use some sort of iterative algorithm with the BBP $\pi$-digit generation formula to generate PR numbers, assuming $\pi$ is normal? Or some other formula to extract a given digit from a normal irrational number? Seems like there might be a way to do this in finite memory (though maybe not for BBP due to precision)/ –  WChargin May 6 at 0:41
1  
@WChargin Note that what you are suggesting does take unbounded memory. If you have a function f(i) that returns the ith digit of pi, you must have unbounded memory to list all the digits, because i does take growing memory amounts, even though its grow is logarithmic. If you fix the amount of memory such a function can only compute the digits up to a certain I that fills all the available memory (and proably less, since some space is required to perform the calculations). –  Bakuriu May 6 at 11:12

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.

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.