0

I've been reading a bit about pseudo-random number generators lately. My understanding is that they generate numbers that seem random for all practical purposes but they are actually just really big sets of numbers that are cyclic.

So let's say we have an infinite set of pseudo-random numbers, how can you show that it is cyclic?

Sam Creamer
  • 331
  • 2
    Just from the numbers themselves, you can't tell. – MJD May 30 '14 at 16:29
  • If you have a set and one that is infinite, then it is not cyclic. Cyclic implies that once you have reached some threshold you start getting same outputs as before. It's impossible to get an infinite set in this way (assuming some standard process, for example not one which spits out infinite sets each turn). – dtldarek May 30 '14 at 16:48
  • 1
    What's a cyclic set? ;) (What you mean is a periodic sequence.) – fkraiem May 30 '14 at 18:49
  • exactly! that's what I meant, sorry for bad terminology – Sam Creamer May 30 '14 at 20:33

2 Answers2

1

Being cyclic is repeating certain mode. Like 1,2,3,4,1,2,3,4,... The algorithm that generates series will define if the number sequence is cyclic.

But do you think 1,2,2,3,3,4,4,5,... is also cyclic? Maybe if we can tell the number in a specific position based on some current data, we will think it is cyclic.

zhen
  • 101
1

This at least would work for the finite case.

One approach could be to determine what the set of numbers the pseudo random function F : D -> V is generating. That is given a set of numbers S, is it true that for all x in S, we have x also in V, that is the image of F. Then once you have S = V show that S is cyclic. To show that S is cyclic, One could continue to use the pigeon hole principle. Assume G is a proper subset of D such that G != D and the function H : G -> V is a surjective function. By the pigeon hole principle there must be an x in D that x is not in G so that F(x) in V which shows that the set must begin to repeat itself.

http://en.wikipedia.org/wiki/Pigeonhole_principle

For the infinite case I would like to look into it more.

Gary Drocella
  • 211