Will a Random Number Generator Eventually Repeat Its Numbers?

In summary, Nassin Nicholas says that a true random number generator, assuming such an object does not exist, will eventually repeat numbers it had turned out previously.
  • #1
kuahji
394
2
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.
 
Physics news on Phys.org
  • #2
Sure the numbers will repeat, but the question is just how many digits are you talking about? Now at dice numbers run from 2 to 12, 7 is the most frequent number. It is not uncommon, not that uncommon for 7 to repeat 3 or even 4 times in a row. Sure, not like everytime, but you keep playing and YOU WILL SEE SUCH REPEATS!

To make a rough estimate, I guess a throw of dice may take only 15 seconds. So that would give 4 throws in a minute. The 7 comes up 1/6 of the time, and four of them every 1296 throws. So that amounts to 5.4 hours of actual play! Now, of course, at the table there is time spent changing dealers, so slower period exists, and probably faster ones too. Of course, your play could be over days or weeks, but certainly if what we are talking about is an average of 5.4 hours of actual play, you don't have to play that game for very long before it may happen!

The trouble with these repeating 7s is they are the bane of the wrong better, who bets against the house. On the pass line, when you first start, the right player will automatically win if a 7 is thrown. (Rather than lose as is usual with a 7.) If the wrong better can get his number, (4,5,6, 8,9,10) he is likely to win because the shooter will probably throw a 7 before hitting the wrong better's number again. Since wrong betters have this advantage once they have their number, they may begin by betting heavy, because otherwise they will have to give odds if they want to add to their bet since with their number the game is now in their favor.) The true bane of being a wrong better is that a series of 7s might occur before he can get his number, then instead of rejoicing over immediate wins, he has immediate losses. (If this happens three times in a row, he may be cured of betting wrong.)

The matter in general is discussed by the mathemtician and philosopher Nassin Nicholas, writer of "Fooled by Randomness." He asks what happens, "When the black swan alights"? (While some have compared them to unicorns, it's not true, black swans do exist.) http://www.fooledbyrandomness.com/ I quote: NNT is the Dean’s Professor in the Sciences of Uncertainty at the University of Massachusetts at Amherst. He is also an essayist, belletrist, literary-philosophical-mathematical flâneur, and practitioner of uncertainty (“mathematical trader”) focusing on the attributes of unexpected events, with a focus on extreme deviations, the “Black Swans” (i.e. outliers), their unpredictability, and our general inability to forecast.

Again, what is involved in the problem of kuahji is the range, R, of the numbers involved. Take Pick 3 there are 1000 numbers involved, 000 to 999. So that a reapeat of a GIVEN NUMBER would be 1/million, but normally what is being sought is the repeat of ANY NUMBER, and that is just 1/1000 or the range of the numbers in question. So if we suppose that Pick 3 is played twice a day for 6 days a week, we should expect that after about 83 weeks we would see the same number come up twice in two successive drawings. If one has the time or inclination, he could check this out!
 
Last edited:
  • #3
robert Ihnot said:
Sure the numbers will repeat, but the question is just how many digits are you talking about?
Sure?
Well in principle one could make a random number generator that does not repeat.
 
  • #4
Random number generators, as normally thought of, are programs on digital computers, where numbers have a finite number of bits. Therefore there are only a finite number of possibilities for numbers out of the generator. As a result, the generator must eventually repeat numbers it had turned out previously.
 
  • #5
mathman said:
Random number generators, as normally thought of, are programs on digital computers, where numbers have a finite number of bits. Therefore there are only a finite number of possibilities for numbers out of the generator. As a result, the generator must eventually repeat numbers it had turned out previously.
Then I suppose I do not think normally :blushing:

Furthermore a true random number generator, assuming such a device would exist, that would never give any duplicate numbers would most certainly not be a true random generator.
 
Last edited:
  • #6
MeJennifer said:
Then I suppose I do not think normally :blushing:

Furthermore a true random number generator, assuming such a device would exist, that would never give any duplicate numbers would most certainly not be a true random generator.

Excellent point, but the failure of pseudo-random generators would be to repeat whole cycles of previously generated numbers, since they're just periodic with very long periods.
 
  • #7
selfAdjoint said:
Excellent point, but the failure of pseudo-random generators would be to repeat whole cycles of previously generated numbers, since they're just periodic with very long periods.
Well not quite.
For instance it is not true that if a random generator is not periodic it must be true random.
Being periodic is just one of the criteria that disqualifies a generator as random. :smile:
 
  • #8
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.
 
  • #9
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. This is because computer programs are deterministic, and can do no better than shuffling bits in a complex (yet not random) way.

There are, however, many sources of true randomness available in the physical world. The voltage across a temperature-sensing diode in the processor, the time between successive user keystrokes, the receipt of random broadcast packets on a network interface, etc. are all random enough, at least in aggregate, for most cryptographic purposes. A random-number generator based on such sources of true randomness will never repeat.

- Warren
 
  • #10
chroot said:
A random-number generator based on such sources of true randomness will never repeat.

- Warren

It depends on what you mean by "repeat". Any random number generator must pick over a finite set, so let's say you want to generate random integers from 1-100. A pseudorandom number generator would repeat it's sequence infinitely many times. A truly random number generator could never be guaranteed to repeat, but it must. Any sequence it generated once would be generated again later, but only given infinite time. Given finite time, the probability of repeating a sequence of length n starting from a given point would be (1/100)^n, same as it was for being generated the first time.
 
  • #11
BoTemp said:
Any sequence it generated once would be generated again later, but only given infinite time.

Who cares? Why don't we keep the discussion to things that are physically realistic?

- Warren
 
  • #12
chroot said:
Who cares? Why don't we keep the discussion to things that are physically realistic?
Hmmm, this is the Mathematics / Number theory section right? :smile:
 
  • #13
MeJennifer said:
Hmmm, this is the Mathematics / Number theory section right? :smile:

Random number generators, including those implemented on computers, are rather physical things. The qualities being discussed -- repitition, for example -- depend on the actual physical nature of their implementation.

- Warren
 
  • #14
MeJennifer said:
Hmmm, this is the Mathematics / Number theory section right? :smile:

You want to do it mathematically? Define random then. What is the sample set, and what is the probability distribution on that sample set, i.e. what are the measurable subsets, the sigma algebra, whatever you choose to call it.

Integer values? That doesn't have a uniform distribution. The interval [0,1] with the uniform measure? Then you're into all kinds of issues as to what it means to actually sample a single element from a continuous distribution. Remember, such things are purely mathematical constructs, and only model of what we find in the real world.
 
Last edited:
  • #15
matt grime said:
You want to do it mathematically? Define random then. What is the sample set, and what is the probability distribution on that sample set.
Hmmm, well the digits of PI and e are quite random aren't they.
 
  • #16
That isn't a good enough definition. There are many interpretations of that sentence.

What is true is that pi is believed to be normal (no proof exists) and that means something very specific, so its *digits* are believed to be 'random' in the sense of 'normal' (see e.g. wolfram for an explanation). If you wanted to generate a 3 digit string at random then sure picking some 3 digit string from pi would create a random (conjecturally) 3 digit string, but it is not producing a random number (how many digits in the string should you pick? And that doesn't even then begin to address what it means to pick a string at random).
 
Last edited:
  • #17
With random number generators, a quickly built one will often generate a series like 174891029174891029174891029174891029, where it repeats forever. Often, though, it is a long time before a repitition occurs. A good random number generator is designed to not have repitition as obvious as that, in fact a very good random number generator has no repitition that goes on forever. So, yes, if you took the output of some random number generators, they would repeat forever, and for some they wouldn't ever start repeating forever.
 
  • #18
Any pseudo-random number generator that is written on a computer with a finite amount of memory must output a sequence that a repeating tail. This is because the computer only has a finite number of states it can take, so it must repeat some state eventually, and once it does that it gets locked into a loop of states which repeatedly outputs the same finite string of numbers.
 
  • #19
MeJennifer said:
Hmmm, well the digits of PI and e are quite random aren't they.
Okay, now you need to define "random" and "quite random"! I don't see how that responds to
matt grime said:
Define random then. What is the sample set, and what is the probability distribution on that sample set.
 
  • #20
Computers can be made to output an arbitrarily large randomish number, since it's not really required that the whole number be kept in memory. For example, an algorithm that outputs the digits of a random number in batches of k random digits only keeps at most k digits in memory. The difficulty is in deciding when to stop outputting the number. After how many digits will the computer stop? It should be a random number of digits. To be a perfect random generator the probability of stopping at the nth digit should be the same as that of stopping at the (n+1)th digit, approximately 0, which is not really feasible.
Unless perhaps we start the computer and let it naturally come to a stop (i.e. due to destruction, insufficient resources, etc). If the universe is truly random, then the system will be a true random number generator.
 
Last edited:
  • #21
It is necessary to have at least as many states in the computer as the length of the repeating tail of the sequence. I am using the following kind of model:
1. Computer outputs a number based deterministically on its state, of which there are a finite number
2. Computer moves to a new state, which is based deterministically on its previous state. Goto 1
With finite memory eventually the path of states, and therefore the string of numbers that are output, will fall into a cycle. If the computer's states at any time become xaya, where a is a single state and x and y are strings of states, then they must repeat xayayaya... and the output numbers will also repeat since there can be only one number per state.
 
  • #22
Actually, about the fact that once it passes a state twice it will get locked in a cycle, that is false. If you think about any irrational number, and figure out a way to calculate the next digit quickly, where it doesn't slow down based on number of numbers already computed, it will never give a repeating sequence. That would be an easy way to make a random number generator. In that case it would not repeat. It may hit a similar state where it puts out the same number, but it would be possible to make a random number generator that never gets locked in a cycle.
I thought up a quick random number generator that would never get locked in a cycle. You would start with the first digit of tan(1), rounded, and the second number would be the rounded second digit of tan(1), making a list of random values like:
round(tan(1))
round(tan(1)*10)-round(tan(1))
round(tan(1)*100)-round(tan(1)*10)-round(tan(1))
and so on...
This would never get locked in a repeating state, since tan(1) is irrational. I am also trying to make one that runs fast and doesn't repeat.
Also, to stress the point that a random number generator that doesn't repeat doesn't have to slow down with each digit, you could make one that takes the square root of 2.1428304820483 using a algorithm that doesn't slow down during each digit. If you research, there are a lot of methods to take a square root that don't slow down with each digit, and some don't need knowledge of the rest of the digits already calculated, just the last few.
The only problem with ones that don't repeat is they probably run slowly.
 
Last edited:
  • #23
Pi_memorizer said:
Actually, about the fact that once it passes a state twice it will get locked in a cycle, that is false. If you think about any irrational number, and figure out a way to calculate the next digit quickly, where it doesn't slow down based on number of numbers already computed, it will never give a repeating sequence.

To calculate an arbitrary number of digits would take an unbounded amount of memory. Of course it may be possible to calculate with a finite amount of internal memory plus the Turing machine tape output, but that's still an unbounded number of internal states (tape + memory).
 
  • #24
selfAdjoint said:
Excellent point, but the failure of pseudo-random generators would be to repeat whole cycles of previously generated numbers, since they're just periodic with very long periods.
I don't see that a pseudo-random number generator need necessarily be periodic in principle - that depends on the seed and the algorithm for each random number generated.

orthodontist said:
Any pseudo-random number generator that is written on a computer with a finite amount of memory must output a sequence that a repeating tail. This is because the computer only has a finite number of states it can take, so it must repeat some state eventually, and once it does that it gets locked into a loop of states which repeatedly outputs the same finite string of numbers.
This applies if the computer algorithm is completely digitally self-contained with a finite number of internal states and takes no outputs from the external world. Add an interface to the computer so that it can utilise information from the outside world in its random number generation algorithm, and your potential number of states is as large as you like.

Best Regards
 
Last edited:
  • #25
moving finger said:
This applies if the computer algorithm is completely digitally self-contained with a finite number of internal states and takes no outputs from the external world. Add an interface to the computer so that it can utilise information from the outside world in its random number generation algorithm, and your potential number of states is as large as you like.
True--or do something drastic like increase the memory by a gigabyte or two every million years.
 
  • #26
0rthodontist said:
True--or do something drastic like increase the memory by a gigabyte or two every million years.
or make part of the computer analogue instead of digital? could this create a potentially infinite number of internal states?
 
  • #27
If you want true randomness, you need to sample an analog source. Commonly, the noise in a diode is used as a source of randomness in commercially available true-random number generators. You could also use other phenomena, like the decay events of a small radioactive sample.

You cannot, even in principle, achieve true randomness from any algorithmic process with finite states.

- Warren
 
  • #28
chroot said:
You cannot, even in principle, achieve true randomness from any algorithmic process with finite states.
Sure you could--you could, for example, prepare an algorithm by sampling an analog source, transforming the data to randomize it, and recording it in a large database. Then your algorithm might be just to read off the database.
 
  • #29
chroot said:
If you want true randomness, you need to sample an analog source. Commonly, the noise in a diode is used as a source of randomness in commercially available true-random number generators. You could also use other phenomena, like the decay events of a small radioactive sample.

You cannot, even in principle, achieve true randomness from any algorithmic process with finite states.

- Warren
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
 
  • #30
0rthodontist said:
Sure you could--you could, for example, prepare an algorithm by sampling an analog source, transforming the data to randomize it, and recording it in a large database. Then your algorithm might be just to read off the database.

...Except your "algorithm" still has finite states, and thus eventually repeats. Unless of course you've pioneered infinite-capacity hard drives?

- Warren
 
  • #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
 
  • #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) [Broken].

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
 
<h2>1. Will a random number generator eventually repeat its numbers?</h2><p>Yes, a random number generator will eventually repeat its numbers. This is because a random number generator is a finite system with a limited number of possible outcomes. As the number of generated numbers increases, the likelihood of repeating numbers also increases.</p><h2>2. How long does it take for a random number generator to repeat its numbers?</h2><p>The length of time it takes for a random number generator to repeat its numbers depends on the specific generator and the number of possible outcomes. For example, a simple random number generator with only 10 possible outcomes will repeat its numbers much sooner than a more complex generator with millions of possible outcomes.</p><h2>3. Can a random number generator be truly random?</h2><p>No, a random number generator cannot be truly random. This is because they are programmed algorithms that use mathematical equations to generate numbers. While these numbers may appear random, they are actually following a specific pattern determined by the algorithm.</p><h2>4. How can we ensure that a random number generator is fair?</h2><p>To ensure that a random number generator is fair, it should be tested and certified by a reputable organization. This involves running statistical tests to check for patterns or biases in the generated numbers. Additionally, the algorithm should be regularly audited and updated to prevent any potential biases.</p><h2>5. Are there different types of random number generators?</h2><p>Yes, there are different types of random number generators. Some common types include pseudorandom number generators, which use mathematical algorithms, and hardware random number generators, which use physical processes such as atmospheric noise to generate numbers. Each type has its own advantages and limitations, and the choice of which to use depends on the specific application.</p>

1. Will a random number generator eventually repeat its numbers?

Yes, a random number generator will eventually repeat its numbers. This is because a random number generator is a finite system with a limited number of possible outcomes. As the number of generated numbers increases, the likelihood of repeating numbers also increases.

2. How long does it take for a random number generator to repeat its numbers?

The length of time it takes for a random number generator to repeat its numbers depends on the specific generator and the number of possible outcomes. For example, a simple random number generator with only 10 possible outcomes will repeat its numbers much sooner than a more complex generator with millions of possible outcomes.

3. Can a random number generator be truly random?

No, a random number generator cannot be truly random. This is because they are programmed algorithms that use mathematical equations to generate numbers. While these numbers may appear random, they are actually following a specific pattern determined by the algorithm.

4. How can we ensure that a random number generator is fair?

To ensure that a random number generator is fair, it should be tested and certified by a reputable organization. This involves running statistical tests to check for patterns or biases in the generated numbers. Additionally, the algorithm should be regularly audited and updated to prevent any potential biases.

5. Are there different types of random number generators?

Yes, there are different types of random number generators. Some common types include pseudorandom number generators, which use mathematical algorithms, and hardware random number generators, which use physical processes such as atmospheric noise to generate numbers. Each type has its own advantages and limitations, and the choice of which to use depends on the specific application.

Similar threads

  • Programming and Computer Science
Replies
1
Views
591
Replies
5
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
11
Views
393
Replies
6
Views
1K
Replies
12
Views
687
Replies
25
Views
3K
Replies
1
Views
3K
  • Set Theory, Logic, Probability, Statistics
Replies
7
Views
193
  • Linear and Abstract Algebra
Replies
11
Views
3K
  • Precalculus Mathematics Homework Help
Replies
14
Views
1K
Back
Top