Will a Random Number Generator Eventually Repeat Its Numbers?

Click For Summary
Random number generators (RNGs) will eventually repeat their outputs due to the finite number of possible states they can produce. While true random number generators, based on physical phenomena, can theoretically avoid repetition, most digital RNGs are pseudo-random and will cycle through a limited set of numbers. The frequency of repeats can be estimated based on the range of numbers and the number of trials conducted. Discussions highlight that while some sequences may appear random, they are ultimately deterministic and will repeat over time. Understanding the nature of randomness and the limitations of RNGs is crucial for applications in gaming and cryptography.
  • #31
moving finger said:
How do we know that an analogue source has (in practice) an infinite number of internal states? If space and time are quantised at the Planck scale, then it is possible that even analogue sources have finite numbers of states.

Best Regards

Even if analog sources really do have a finite number of states at the Planck level, there would be so many states (the Planck scale is extremely small) that the system would not necessarily repeat for many, many times the age of the universe.

There's currently no way to "prove" that analog randomness is truly random -- although it is an axiom of quantum mechanics, the most successful scientific theory in existence -- but there are many means to prove that no pseudorandom number generator can ever be truly random.

- Warren
 
Physics news on Phys.org
  • #32
chroot said:
Even if analog sources really do have a finite number of states at the Planck level, there would be so many states (the Planck scale is extremely small) that the system would not necessarily repeat for many, many times the age of the universe.
Agreed - but the important issue here is that it would in fact repeat in principle, thus would only be pseudo-random.

chroot said:
There's currently no way to "prove" that analog randomness is truly random -- although it is an axiom of quantum mechanics, the most successful scientific theory in existence -- but there are many means to prove that no pseudorandom number generator can ever be truly random.

- Warren
Sorry, chroot, but randomness is NOT an axiom in all interpretations of QM.

The Heisenberg Uncertainty Principle says the world is epistemically indeterminable, but this is not the same thing as being ontically indeterminate. The difference explained here :

http://philsci-archive.pitt.edu/archive/00000939/

The wave equation evolves completely deterministically, and in practice we can prepare certain quantum states with determined properties. And I have yet to see a coherent and complete ontological interpretation of the Delayed Choice Quantum Eraser experiment which assumes quantum randomness (paper here http://www.citebase.org/fulltext?format=application%2Fpdf&identifier=oai%3AarXiv.org%3Aquant-ph%2F9903047) .

Depending upon which "interpretation" of QM one assumes to be correct, the world may or may not be fundamentally (ontically) random. The Copenhagen interpretation is silent on the issue (it simply says that what we cannot measure, we have no right to ask about - the shut up and calculate approach), whereas Bohmian mechanics assumes non-local hidden variables.

Best Regards
 
Last edited by a moderator:
  • #33
It's pretty damned irrelevant to go into interpretations of quantum mechanics in this thread. The topic is deterministic pseudo-random number generators. As I said, regardless of which interpretation of QM you prefer, there is no such thing as a perfect deterministic PRNG. There need not be any appeals to quantum mechanics to show this is correct.

Neither of us could prove that analog sources of randomness like diode thermal noise are or are not truly random, because we certainly can't wait long enough. It's a moot point.

- Warren
 
  • #34
Let's say we had a hypothetical truly random source that outputs 1000000 numbers randomly and then stops. There's an unlimited number of programs that output the same 1000000 numbers. The only way to distinguish between the output of "random" objects and "deterministic" objects is in the actually infinite case--which is out of the reach of experiments. For practical purposes there is no hard line between random and nonrandom.

I think that the true issue is practical predictability. With a hard coded self contained algorithm, someone could know the algorithm ahead of time and predict all of the numbers it outputs. Whereas with a physical source it is much harder to predict its output since you can't get total knowledge of its start conditions. It's a practical barrier, not a philosophical one.

However, with some arrangements, it is possible to allow a self contained program to generate numbers that it are in practice impossible to predict even if you know the code for the program. What you need:
1. Some pseudo random system
2. The fastest computer in the world, dedicated to the task
If no other computer is as fast as your random number generator, the generator will produce every number before any other computer can predict it, even with complete knowledge of start conditions.
 
  • #35
chroot said:
It's pretty damned irrelevant to go into interpretations of quantum mechanics in this thread.
Well I'm sorry, chroot - but YOU were the one who claimed that randomness is an axiom of quantum mechanics (and what is that if not "an interpretation of QM"?) - I was simply responding to your claim, that's all.

chroot said:
Neither of us could prove that analog sources of randomness like diode thermal noise are or are not truly random, because we certainly can't wait long enough.
I agree completely - but I'm not the one claiming that randomness is an axiom of QM, am I?

Best Regards
 
  • #36
A random sequence has no discernable pattern because it has no pattern, each digit (say we are talking about {0, ..., 9}) happens randomly. In that setting there is really no chance at all, as the number of trials goes to infinity, of getting a repeating decimal.

An interesting little experiment is to try generating sequences using recurrence relations like x_{[i+1]}=x_{<i>}^2+c</i>. Apparently there also exist real numbers between zero and one which do not allow any shorter version than to write out all the digits, you can discover they exist but never write them down. Would that be a truly random number?
 
  • #37
Intuitive said:
I am an advanced Programmer in Vbscript and in order to have what's called a true random number generator you'd have to deal with infinity.

You can not deal with infinty on a system that requires a time limit therefore you can not have a true random number generator but you can give it very large odds.

I can build you a true random number generator but it would never stop functioning and freeze your system.

If I hadn't just looked at the thread with all the joke math articles, this would be the funniest thing I read all night. :smile:
 
  • #38
I'm trying to think of natural phenomenon that will give you a flat continuous distribution. Dice are not too bad, roulette wheel but those are discrete. What about just using a ten sided die and rolling it repeatedly, that ought to be a random rational number. Each trial is independent and about as random as you can get. You could map the ratio of two parametric chaotic sequences and see if you can't adjust the parameters so you get an equal density on the range. You might investigate a ratio of sequences from this family x_{i+1}=|a log x_{i}|.
 
  • #39
Going back to the question of whether a random sequence will ever repeat, there are random number generators that do not work with seeds and never repeat. They often use what is called an entropy pool, which is just a big file filled with data that is supposedly random like where you move your mouse. Between when you call these random number generators, the pool is updated. As computers get faster and faster, the time it takes for you to reach a point where it repeats grows smaller and smaller, but at an equal rate the time it takes before the pool gets more data decreases. Therefore, the random number generators never let the program that calls the random number generator call it fast enough it gets a repeat.
Also, some of the algorithms for getting data into an entropy pool are sensitive enough they can sometimes grab results from events caused by quantum physics, which are often truly random. Then, a truly random number is put into a pool used to calculate other random numbers, making those numbers truly random. Truly random numbers never repeat, so the sequence never would either.
One such random number generator is included in the linux kernel. Look it up if you want, for programmers who know where it is the source code is free.
Now, onto pseudorandom number generators that work using a seed. Because a computer has limited memory, they will always repeat.
 
  • #40
That is believed to be true but has never been proven.
 
  • #41
OK, if you want a randon integer number in the set {-inf < x < inf} or {0 < x < inf} you would get a number infinete in lenght. And i think QM would be pretty appropriate here. forget decimal, think binary. the only truly random event is nuclear decay (or so we think as observing it makes it change its properties). if you did the schrodinger's cat experiment an infinete amount of times and recorded your results in binary 1 for alive and 0 for dead or vise versa, you would get a truly random number.
 
  • #42
Discussing what 'truly random' is, is a topic for philosophers. You might as well be talking about how many angels can dance on the head of a pin.

This argument:
the only truly random event is nuclear decay (or so we think as observing it makes it change its properties). if you did the schrodinger's cat experiment an infinete amount of times and recorded your results in binary 1 for alive and 0 for dead or vise versa, you would get a truly random number
Is obviously circular, and uninformed to boot. Nuclear decay is not 'truly random' there are many examples of it being affected by external factors.
 
  • #43
wow, wouldn't it be possible to make a random number generator, with like som bug or something inside, so when it randomly steps on things, every place it steps on has a digit, and then it keeps adding the last digits it made to the new digits, and then it sometimes multiplies, sometimes divides or subtracts, so it always makes random stuff [if the screen tht the numbers were displayed on was massive, so it could go forever, and just keep making the numbers smaller? o even without a screen, just a data base thingy. but then you'd have to replace the bug. but would tht be classified as random?
 
Last edited:
  • #44
Everyone seems to want an infinite amount of time to generate a single random number. Why does that not make them pause for thought for just one second?
 
  • #45
wow, wouldn't it be possible to make a random number generator, with like som bug or something inside, so when it randomly steps on things, every place it steps on has a digit, and then it keeps adding the last digits it made to the new digits, and then it sometimes multiplies, sometimes divides or subtracts, so it always makes random stuff [if the screen tht the numbers were displayed on was massive, so it could go forever, and just keep making the numbers smaller? o even without a screen, just a data base thingy. but then you'd have to replace the bug. but would tht be classified as random?

That would be quite random i imagine, however it would still be predictable and you will not be able to get it in the domain of {0 =< x < inf} as it will only give you a very long number.

Everyone seems to want an infinite amount of time to generate a single random number. Why does that not make them pause for thought for just one second?

lets take a look at probability from the basics. let x= possible outcomes and u= favorable outcomes. The probability of getting u will be:
P=\frac{u}{x}
Now let's bring it into context. Regardless of what number u is as long as it is a countable number:
\stackrel{lim}{x\rightarrow\infty}\frac{u}{x}=0
This means that it would take infinite time to get a truly random number in domain {0 =< x < inf} as the number would be infinite in lenght.
 
  • #46
itsjustme:

This is the second time in this thread that you've asserted that "truly random" numbers are "infinite in length." That's ridiculous, of course. Zero is a perfectly valid random number, given that it was generated in a "truly random" way.

In fact, most pseudo- and true-random number generators just emit streams of bits -- ones and zeros -- each of which is a random number in its own right, just one in the set {0, 1}.

- Warren
 
  • #47
yes, zero and one and two would be perfectly valid. but what would the probability of geting it be? \frac{1}{\infty}

Try thinking of the biggest number you can think of. then visualise its place in the number line and zoom out, the number line never ends. eventually that number along with every other number before it will be less than what you define to be a division on the number line, the probability of getting it as a result will be practically zero.
 
  • #48
Please can someone lock this before it degenerates into anymore nonsense?

1a. There is no discrete uniform distribution on an infinite set.
1b. There isn't a uniform continuous distribution on the real numbers.
2. There is no such thing as a 'number drawn uniformly at random from the real line' in real life (see 1b).
3. Real "random number" generators only choose from a large but finite state space.
4. Ants walking across paper, killing of infinitely many cats, all this is just nonsense.
 
  • #49
MeJennifer: Hmmm, well the digits of PI and e are quite random aren't they.

If so, why are these numbers constant?

I am reminded of the Clinton impeachment, "What is the meaning of "is"?"
 
  • #50
MeJennifer said:
Hmmm, well the digits of PI and e are quite random aren't they.
Because it is common in this thread for statements to be misinterperted and then poked fun of, I will try to explain how I interpret MeJennifer's quote. As the last post I read stated Pi and e are constants. However, I agree the the "distribution" of the digits is such that a presudo random number genetator that gives a result in base 10 having a fixed number of digits, could presumably include the Pi sequence to generate such numbers since I believe (and no one has asserted otherwise) that every possible base ten number less than some fixed number can be found somewhere in the Pi sequence.

Of course no number generater that always generates numbers that are always from some fixed number set {0,1,2,...n} with a relatively smooth distribution within the set is truly a random number generator but in the real world that is most people in fact demand of a "random number" generator.

I interpret MeJennifer's quote in that light, but believe that there are better "random number" generators, such as those where a seed number for a first random number generator is use to generate the seed of a second random number generator.

If one pays attention to the requirement that the distribution within the set of numbers generated by a "random number" generator be uniform then some sort of cyclic number generator such as those based upon raising a number to a given power mod z will best fulfill that requirement.
 
Last edited:
  • #51
chroot said:
A random-number generator based on such sources of true randomness will never repeat.

- Warren

Why is it that people say that a truly random event will never repeat? Numbers larger than the number of particles in our universe can be created by those ten digits or just the digits 0 and 1 if in base two. If some power had the ability at a given time to instantly describe the position of each particle in our total universe, it could be done with a finite number. That number which describes the whole state of our universe at say this instant would be take more atoms to express than are in our universe, but would repeated in the decimal expansion of Pi many times over were some unnatural power in some other universe able to calculate Pi to such an extent.

I think that the number of universes is infinite beyond our imagination and no one can say that a given event will not repeat somewhere. Events do repeat which is why most people can be satisfied with presudo random number generators.
 
Last edited:
  • #52
kuahji said:
I am just curious. If I have a random number generator, eventually, if I wait long enough all possible numbers should began to repeat. Or would the numbers not repeat? For example, if say the first hundred numbers were totally random 455688132547... etc. would the machine eventually repeat the numbers? If so, how would I go about calculating an approximation of when they'd repeat?
Anyway, hope that all made sense.
To answer how one could predict when the numbers in a presudo ramdom number generator will repeat one would have to reconstruct the algorithim responsible for generating the number sequence. Presumably, if based upon only a partial list of numbers in a cycle, that would be next to impossible even if the sequence was in fact cyclic. For more on random number generators try searching the term on the internet.
 
Last edited:
  • #53
And now we're just getting even more nonsense.

When poeple say the digits of pi are random, they typically mean 'normal'.

The probablity of any reasonable random variable being repeatedly sampled and giving periodic behaviour over any large chunk of time is zero.

Sorry I can't include any wildly speculative and completely unjustified assertions as to the nature of the universe.
 
  • #54
look quantum events are the only type of events which are unpredictable. i am just saying that even with a finite set, other input sources are predictable and controlable. I am not in any way commenting on the practicality of any of my suggestions above because they are impossible, just like getting a random number in the set{x: x\in R} is.
 
Last edited:
  • #55
matt grime said:
And now we're just getting even more nonsense.

When poeple say the digits of pi are random, they typically mean 'normal'.

The probablity of any reasonable random variable being repeatedly sampled and giving periodic behaviour over any large chunk of time is zero.

Sorry I can't include any wildly speculative and completely unjustified assertions as to the nature of the universe.
Matt, just as the digits of Pi could be normally populated, integer sequences could also be normally populated within the Pi sequence. I certainly am not asserting that though. If any sequence is normally populated, it could be used as a random number generator as long as the index was randomly generated, that is all that I am saying. Likewise, sequences from Pi could ve randomly generated by randomly generating the starting index from which the digits were consecutively picked.

I agree with you that a sequence which is randomly generated will not be cyclic. However, presudo random generators liked Y^x mod z where x takes on successive terms from an arithematic sequence would be cyclic.

Sorry about the wild assertions about the nature of the universe, but my point was that if anyone could describe the whole universe with a single numeric sequence, chances would be high that that sequence could also be found within an infinite series such as Pi ( even though the Pi sequence is completely predetermined).
 
  • #56
I don't recognize the phrase "normally populated" in this sense. Matt Grime was talking about "normal numbers" (essentially that all combinations of n digits [for any positive integer n] occur equally often in its decimal representation). It is widely believed that pi is a "normal number" but I don't believe it has been proved.

It is NOT true that a "normal number" must be "random". In fact since any "normal number", like any number, is "predetermined" I don't believe "random" makes any sense here. Nor is it true that a randomly generated sequence cannot be cyclic. Any true random number generator must be capable of producing all possible sequences including cyclic ones.
 
  • #57
ramsey2879 said:
it could be used as a random number generator as long as the index was randomly generated,

What you have just said is that if we have a random number generator we can create a random number generator... (incidentally, how many digits after the randomly generated index point will you randomly select?).


Sorry about the wild assertions about the nature of the universe, but my point was that if anyone could describe the whole universe with a single numeric sequence, chances would be high that that sequence could also be found within an infinite series such as Pi ( even though the Pi sequence is completely predetermined).

If you mean 'a finite length string of digits' then that is preceisely the definition of a normal number. It has nothing to do with life the universe of everything. Indeed the probability of any given integer appearing at some point in the decimal expansion of a normal number is 1.
 
  • #58
chroot said:
You cannot implement a true random number generator entirely on a digital computer. The best you can do is a "pseudo-random number generator," which, as has been said, will eventually repeat.
Why can't I write a program that will log all sequence and, every time it generates a number, search it and, if repetition is detected, re-generate it? Or, more realistically, why can't there be generation based on some parameter that will be slowly changed on every generation? Both cases are limited only by memory (for sequence log, or bits per parameter), which is not a problem with algorithm itself.
 
  • #59
makc said:
Why can't I write a program that will log all sequence and, every time it generates a number, search it and, if repetition is detected, re-generate it?
Since any real implementation has finite storage, eventually it will cease to function when it is full, or else it must forget (drop) some of the past output and cease to guarantee non-repeatablility.

Or, more realistically, why can't there be generation based on some parameter that will be slowly changed on every generation?
This is the previously-mentioned idea of feeding it real-world data as a source of "true" randomness. There are simple and practical ways to inject randomness into a pseudo-random (PR) generator. A server of PR digits can provide a client with the next group of digits in exchange for some random input, for example. This can be simply a timestamp of when the query is made, or it can be any other value that is unpredictable by the PR server. In this scenario, the client provides new seeds that the server cannot anticipate and the PR server scrambles them into patterns that are unrecognizable and unpredictable to the client, which makes every bit of the program tingle with anticipation.

Both cases are limited only by memory (for sequence log, or bits per parameter), which is not a problem with algorithm itself.
True, being limited by physical reality may not be a problem for some algorithm per se. But it does make such an algorithm useless for any practical purpose.
 

Similar threads

Undergrad Experiment with gamers, random numbers and entanglement
  • · Replies 5 ·
Replies
5
Views
2K
Undergrad Generating Irrational Ratios in Wave Simulations
  • · Replies 6 ·
Replies
6
Views
2K
By Listing Them Randomly, Could we Count the Irrationals?
  • · Replies 11 ·
Replies
11
Views
4K
Is the Decimal Expansion of an Irrational Number Truly Random?
  • · Replies 25 ·
Replies
25
Views
4K
Graduate Concrete examples of randomness in math vs. probability theory
  • · Replies 11 ·
Replies
11
Views
3K
High School Definition of a random variable in quantum mechanics?
  • · Replies 12 ·
Replies
12
Views
2K
Found Some Pattern in prime numbers
  • · Replies 21 ·
Replies
21
Views
9K
Graduate Understanding Kolmogorov-Smirnov Test Results for Random Number Generators
  • · Replies 1 ·
Replies
1
Views
4K
A philosophical question regarding random numbers....
  • · Replies 8 ·
Replies
8
Views
2K
Automotive Random Vibration and PSD spectrum profiles
  • · Replies 4 ·
Replies
4
Views
4K