Will a Random Number Generator Eventually Repeat Its Numbers?

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

 

[skeptic2]

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.

Suppose I have a true random number generator and it gives me a string of random digits which I record. Then I go back and recall those digits one by one by a finite algorithm. The same digits will be returned in the same order every time I run the algorithm. Are you saying they are no longer random. When did they change from random to non-random?

 

[skeptic2]

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.

Very true. The situation is made worse by the widespread misuse of the concept. Infinity is not a number and it cannot be approached. One million is no closer to infinity than is one. Thus the common usage of x = 1/n as n approaches infinity, though we know what is meant, is not technically correct.

 

[SW VandeCarr]

Suppose I have a true random number generator and it gives me a string of random digits which I record. Then I go back and recall those digits one by one by a finite algorithm. The same digits will be returned in the same order every time I run the algorithm. Are you saying they are no longer random. When did they change from random to non-random?

Great question. You can't tell if a sequence is truly random unless you know how it's generated. That's something you won't find in many books on mathematical statistics, but it's true. 12345 could be the product of a random generator (assuming we could build one; quantum processes are assumed to be "truly" random in terms of observed outcomes) while 021476 could be predetermined (like someone's birthday, American style).

Assuming the sequence was generated by an acceptable random generator (after n digits, the (n+1)th digit is completely unpredictable by any algorithm that is shorter than n+1 ), I would say it would remain random since your algorithm is as long as the string. There are other views. Some hold that once a sequence is generated, it is no longer random. That's not my view (nor apparently Kolmogorov's).

 

[skeptic2]

From: Kolmogorov Complexity http://www.cs.dartmouth.edu/~akapadia/project2/node5.html

"From this point of view, sequences produced by any RNG and the decimal expansions of irrational numbers like pi are not random since their lengths are much longer than the programs that output them."

Just as in my example in post #71 of using a finite algorithm for extracting pre-existing random numbers, the algorithms for the decimal expansion of pi do not create the digits. The digits of pi exist independently from whatever algorithm is used to extract them. The length of the algorithm thus is irrelevant in whether the digits of pi are random or not.

 

[Hurkyl]

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.

Mathematically, it's made comprehensible through precision and rigor. As soon as you stop being vague about it, and are willing to write down what you really mean, the various notions of 'infinity' and 'infinite' are actually quite straightforward.

Very true. The situation is made worse by the widespread misuse of the concept. Infinity is not a number and it cannot be approached. One million is no closer to infinity than is one. Thus the common usage of x = 1/n as n approaches infinity, though we know what is meant, is not technically correct.

Actually, in the extended real number system, the sequence 1, 2, 3, ... converges to the number +\infty.

 

[ramsey2879]

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

May I attempt a definition of a random string of n digits using digits 0-9? How about each possible string selection has an equal probability 1/10^n of being selected in the next selection.

 

[skeptic2]

Mathematically, it's made comprehensible through precision and rigor. As soon as you stop being vague about it, and are willing to write down what you really mean, the various notions of 'infinity' and 'infinite' are actually quite straightforward.

Actually, in the extended real number system, the sequence 1, 2, 3, ... converges to the number +\infty.

Except that infinity is not a number but a concept. You even referred to it as a notion.

 

[Hurkyl]

Except that infinity is not a number but a concept. You even referred to it as a notion.

+\infty is an element of the extended real numbers. Therefore, it is an extended real number. (And surely you have some concept of numbers anyways )


I made the point to talk about "notions" because there are several distinct mathematical objects which are named "infinity" (or some variant thereof), several classes of mathematical objects that are "infinite", but none of which we would name "infinity", and a other circumstances where "infinity" appears as part of a compund name.

 

[ramsey2879]

+\infty is an element of the extended real numbers. Therefore, it is an extended real number. (And surely you have some concept of numbers anyways

How about
1/+\infty = 2/+\infty In this situation +\infty can't be treated as a positive number

 

[skeptic2]

Not to mention that \aleph_0 ≠ \aleph_1.

[I once had the pleasure of shaking hands with Paul J. Cohen when he was on campus for a series of lectures on the continuum hypothesis. During the lectures, as he was taking a long question from someone in the audience, he would do magic number squares on the overhead projector]

 

[CRGreathouse]

How about
1/+\infty = 2/+\infty In this situation +\infty can't be treated as a positive number

Why not?

 

[Hurkyl]

How about
1/+\infty = 2/+\infty In this situation +\infty can't be treated as a positive number

In the extended reals, one most certainly does have 0 < +\infty.

 

[ramsey2879]

Why not?

If +\infty were a positive number you multiply each side to get 1 = 2 which is impossible.

 

[Hurkyl]

If +\infty were a positive number you multiply each side to get 1 = 2 which is impossible.

Why would I get 1=2? Why would the products even be defined? Positiveness is not sufficient to make those claims about extended real number arithmetic...

 

[SW VandeCarr]

From: Kolmogorov Complexity http://www.cs.dartmouth.edu/~akapadia/project2/node5.html

"From this point of view, sequences produced by any RNG and the decimal expansions of irrational numbers like pi are not random since their lengths are much longer than the programs that output them."

Just as in my example in post #71 of using a finite algorithm for extracting pre-existing random numbers, the algorithms for the decimal expansion of pi do not create the digits. The digits of pi exist independently from whatever algorithm is used to extract them. The length of the algorithm thus is irrelevant in whether the digits of pi are random or not.

Your citation states that K "captures the concept of randomness well". That, in itself is worthwhile since it is a difficult concept. There are a number of algorithms for calculating pi, each of somewhat different lengths. The length can refer to a string of bits expressed in binary digits or some high level language. K postulated the shortest length that can implemented on a computer (without defining what that might be). The key is that the algorithm is finite (k characters) and in the case of pi it will produce a sequence (n=k+m characters) such that any nth digit is the same every time the algorithm is run. An algorithm which simply reproduces (as opposed to calculating) a set that was previously generated is not creating anything. If the original was deemed to be random, its exact reproduction is random, at least according to the K definition. In effect, the algorithm DOES create the digits insofar that it is a program to do so (as part of a system that will generate readable output). If you create an algorithm to write a string in Roman numerals or from an ad hoc character set, it presumably will do that.

 

[skeptic2]

An algorithm which simply reproduces a set that was previously generated is not creating anything.

Agreed

If the original was deemed to be random, its exact reproduction is random, at least according the K definition.

Agreed

In effect, the algorithm DOES create the digits insofar that it is a program to do so. If you create an algorithm to write a string in Roman numerals or from an ad hoc character set, it presumably will do that.

The algorithms for pi, though finite in length, do produce an endless sequence of digits that agree with those for pi. I don't know if pi is random or not but I'm inclined to assume it's random unless shown otherwise. Though it may be possible to disprove the randomness of the digits of pi, I suspect it isn't possible to prove they are random.

 

[SW VandeCarr]

The algorithms for pi, though finite in length, do produce an endless sequence of digits that agree with those for pi. I don't know if pi is random or not but I'm inclined to assume it's random unless shown otherwise. Though it may be possible to disprove the randomness of the digits of pi, I suspect it isn't possible to prove they are random.

Your missing the whole point! How can a sequence that is fully determined be random?? In principle any digit or digit sequence of pi can be calculated. There's nothing random about it. A pi generator will produce exactly the same digit sequence every time it is run (ignoring computer errors). A true RNG will almost never produce the exact same digit sequence more than once for any but very short lengths. The probability of a true RNG producing a specific string of 30 digits twice is 1/10^30. The universe is thought be only about 4.1x10^18 seconds old!

 

[skeptic2]

"Your missing the whole point! How can a sequence that is fully determined be random??"

The same way that a random sequence when stored and the digits recalled by algorithm is still random. I thought we had agreed on that (#73).

 

[SW VandeCarr]

"Your missing the whole point! How can a sequence that is fully determined be random??"

The same way that a random sequence when stored and the digits recalled by algorithm is still random. I thought we had agreed on that (#73).

I must be missing something here. A randomly generated string (by a true RNG) is still random (K definition) when recalled by a (trivial) algorithm which simply copies (or recalls) it.

A non-random string (generated by a non-trivial algorithm) is still non-random when recalled or copied by a trivial algorithm (one that does no computations).

To further explain, true RNGs are not algorithmic. They are based on physical processes which are assumed to be fundamentally random. To the extent that algorithms are involved with a true RNG, they are trivial. They simply express the results of the process item by item. Therefore the K definition that the length of the algorithm is at least the length of the string.

To the the extent that algorithms are used for generating "random" strings, such strings are actually pseudo-random.

 

[skeptic2]

Then what you are saying is that no sequence, even if it passes all the tests for randomness, can be considered random if its sequence can be duplicated by algorithm.

Conversely a random sequence is one which cannot be produced by any algorithm. Are you suggesting then that the number of random sequences is a higher order of infinity than the number of possible algorithms?