Will a Random Number Generator Eventually Repeat Its Numbers?

[Playdo]

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 [itex]x_{[i+1]}=x_{}^2+c[/itex]. 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?

 

[Alkatran]

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.

 

[Playdo]

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

 

[Crosstalk]

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.

 

[HallsofIvy]

That is believed to be true but has never been proven.

 

[itsjustme]

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.

 

[NateTG]

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.

 

[•H3TTING3R]

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?

 

[matt grime]

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?

 

[itsjustme]

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.

 

[chroot]

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

 

[itsjustme]

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.

 

[matt grime]

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.

 

[robert Ihnot]

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"?"

 

[ramsey2879]

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.

 

[ramsey2879]

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.

 

[ramsey2879]

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.

 

[matt grime]

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.

 

[itsjustme]

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.

 

[ramsey2879]

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

 

[HallsofIvy]

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.

 

[matt grime]

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.

 

[makc]

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.

 

[out of whack]

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.

 

[jwhit88]

http://www.redorbit.com/news/science/126649/can_this_black_box_see_into_the_future/

 

[CRGreathouse]

http://www.redorbit.com/news/science/126649/can_this_black_box_see_into_the_future/

Poppycock.

 

[HallsofIvy]

Hmmm, well the digits of PI and e are quite random aren't they.

As I am constantly telling students, "An example is NOT a definition!"

 

[NoShenk]

If your random number generator is Really random, (virtually impossible)Then, idealy, no the numbers would not repeat in a pattern. Sure you would certainly see the number 3 more than once, but not in a pattern.

 

[CRGreathouse]

If your random number generator is Really random, (virtually impossible)Then, idealy, no the numbers would not repeat in a pattern. Sure you would certainly see the number 3 more than once, but not in a pattern.

What do you mean "in a pattern"? I'd expect to see the sequence 3330333133323333333433353336333733383339333 appear infinitely often; would you call this a pattern? If not, what would be a pattern?

 

[SW VandeCarr]

Hmmm, well the digits of PI and e are quite random aren't they.

Not according to the Kolmogorov definition. There are finite algorithms for such numbers and they will produce exactly the same digit sequence every time they are run. A true random number generator has an 'algorithm' that is as long as the digit sequence it produces, which is to say infinite; and arbitrary finite portions of the digit sequences they produce are unpredictable from a compact algorithm.

For example the nth digit of the decimal expansion of PI is a fixed number that will be generated by its finite algorithm every time it is run. The nth digit of a random digit sequence is not a fixed number and cannot be known by any finite algorithm that is shorter than n.

 

[Antuan]

I see Kuahji's original question has a mathematical and philosophical dual character. I guess this can happen with all concepts that imply infinity. That's the beauty of it.

I would say that the best answer yet to his question has been given by BoTemp. It seems logical that given infinite time, any sequence of numbers produced before would be contained within the "ongoing" infinite -and obviously larger- sequence.

I stumbled upon this same contemplation while creating such a random sequence of simple digits from 1 to 9. Say I had some way to pop out such numbers and somehow find a way to record them throughout infinity. For example, first might come out a 3, then a 9, then a 2, etc. In the mean time I'd simply go collecting them, while eventually a huge number will be formed starting with those three: 392... Then my previous statement will certainly be true even if no machine would ever be able to produce infinity: "any sequence of numbers produced before would be contained within the "ongoing" infinite -and obviously larger- sequence." That is, the first sequence is 39 and the second sequence is 392, and so on, and given infinity, all would be reproduced many times more throughout it.

I’m not an expert on number theory but there should be some way to prove this, if it hasn’t been done already.

It might seem contradictory, but randomness does have a pattern, or better say, a tendency, the tendency to “not repeat”, but that doesn’t mean it wouldn’t repeat. Philosophically speaking, “In this universe, randomness is always an illusion, a false or incomplete view of events”, since knowing everything would be impossible, but if you knew everything –all causes within a system-, the ability to predict any event would be part of your nature.

We see and seek patterns. Patterns are product of intelligence, since without intelligence the need to rationalize or correlate events in order to be able to predict wouldn’t be necessary.

In conclusion, this contemplation is simply giving us some insight -mathematical, numerical and philosophical- on the character of infinity. Within infinity, almost anything is possible. I guess the only thing infinity wouldn't produce is something larger than itself.

G.Antuan

 

[Dragonfall]

I'm kinda late to this convo, but you can simulate a fair coin with a simple quantum circuit with 1 qubit. Just initialize to |0>, Hadamard gate, measure in computational basis, and repeat.

Now the fun part is that if you somehow become entangled with this "coin", and if the "parallel universes" crowd is right, then every time you use the circuit, you create 2 universes, and "you" enter one of them with about 50% chance. Flipping a real coin doesn't have this property.

 

[SW VandeCarr]

It seems logical that given infinite time, any sequence of numbers produced before would be contained within the "ongoing" infinite -and obviously larger- sequence.

G.Antuan

It may not seem logical, but there is no necessity that an infinite random sequence of digits contain all the digits (0-9) even if all the digits have an equal and finite probability of occurring. In fact an infinite sequence of zeros, punctuated by a single randomly placed '1' would qualify as a randomly generated sequence. This is based on the fact that in a random sequence of digits, any digit has a finite probability of occurring (or not occurring) independently of what came before (Bayesian considerations not withstanding). The cumulative probability of any given digit occurring for the first time after n generations is 1-(0.9)^n. The cumulative probability converges to, but is never equal to, unity. If you're simply saying that if a sequence begins with 392..., then it contains 392 no matter how long it gets, that seems self-evident and trivial. However, if you're saying that the sequence 392 must repeat, that is wrong. It is highly probable that it will, but not certain.

 

[Antuan]

...there is no necessity that an infinite random sequence of digits contain all the digits (0-9) even if all the digits have an equal and finite probability of occurring. SW VandeCarr

Interesting thought. I think Bayes personally would love to join in on this conversation. I liked that you used the word "necessity" and it brings lots of thoughts or questions into mind. Who's necessity? Suppose we had a raffle with nine numbered balls inside and after a good random shake pick one out, record the number then put back the ball inside the box and do the whole process again through infinity, every time letting the box roll down a cliff or giving it a "random shake". I'd say, that due to the laws of equilibrium (physic's stuff...conservation of KE, etc.) there is actually "the necessity" that each 1-9 balls will come out, except if you forget to put back the one you've just pulled out...but that wouldn't happen would it? -our mind experiment should have no problem throughout infinity- In this sort of nature, the mere existence of any given variable within the system would make it a possible inevitable result, considering the rules of the game being "that the balls won't break and nothing in the system would ever fail...such and such...etc.".

About 392, rest assured that what happened once will happen again. That's the thing about infinity...it's infinite, and that's all probable outcomes will happen at some point in time given each probability exists -if it never popped out in the rest of infinity, then it would have been equally non-existing, which would make our original assumption invalid. That's "probably" the reason for our existence, since it's almost improbable that we exist...but we do!

I previously said that randomness is anyway a sort of illusion since if you knew all the sequences of events related to one single event in an instant of time you could very well predict the following changes of that single event.

G.Antuan

 

[SW VandeCarr]

About 392, rest assured that what happened once will happen again. That's the thing about infinity...it's infinite, and that's all probable outcomes will happen at some point in time given each probability exists -if it never popped out in the rest of infinity.

Interesting reply. It's probably fair to say that no one knows what infinity 'really' is. Mathematically, it's made comprehensible by considering it as a sequence or process that doesn't end. However long it is, it can be made longer by some rule or some generator assumed to be random (ie each generation is completely independent of any and all preceding output). There is no rule for termination. Such sequences however can be amenable to analysis in terms of limits (if the sequence converges) such as the example I gave for the cumulative probability of a given digit where p = 1 - 0.9^n and n increases without limit. Divergent sequences can be analyzed in terms of how rapidly they diverge in comparison with other sequences, etc.

I know it's difficult to understand that an infinite random sequence of digits need not repeat any given sequence. In terms of cumulative probability (above), the limit is unity or certainty that any digit or sequence of digits of will occur or recur after n generations IF n=infinity. But n NEVER equals infinity. It just gets bigger and bigger without limit. Therefore p NEVER equals unity and there is no necessity that any digit of digit sequence will repeat or even occur. This has nothing to do with what is highly probable or even 'virtually' certain. Indeed, the probability of any digit sequence (randomly generated under a uniform distribution) can (in principle) be calculated for any n. For 392 (as for any given three digit sequence) it's p=1-0.999^n. Bayesian inference leads to the same conclusion since, by definition, a randomly generated digit or sequence is assumed to be completely independent of all prior generations.