Will a Random Number Generator Eventually Repeat Its Numbers?

[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 :tongue:)


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?

 

[SW VandeCarr]

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.

Yes, except for 'trivial' algorithms which simply specify item by item. This does not mean that an RNG won't occasionally produce strings that could also be produced by algorithms. I go back to my earlier statement: If you want to know if a string is truly random, you need to know how it is generated. Given any finite string of length n, the (n+1)th item is unpredictable from a RNG, but entirely predictable from an 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?

That's beyond my pay grade.

 

[ramsey2879]

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

Multiplication by a positive number is the same thing as dividing by its inverse which is also a positive number. If you say that the inverse of $$+\infty$$ is undefined or zero, then it is not a positive number. If it is not a positive number then what is it?.

 

[Dragonfall]

Multiplication by a positive number is the same thing as dividing by its inverse which is also a positive number. If you say that the inverse of $$+\infty$$ is undefined or zero, then it is not a positive number. If it is not a positive number then what is it?.

A positive number does not need to have an inverse.

 

[ramsey2879]

A positive number does not need to have an inverse.

Why not?
Which positive numbers other than $$+\infty$$ do not have inverses?
If $$+\infty$$ does not have an inverse than what good is it to consider it as a positive number rather than just an concept?

 

[CRGreathouse]

If $$+\infty$$ does not have an inverse than what good is it to consider it as a positive number rather than just an concept?

It allows the extended real numbers to have an order defined on them, unlike the projective reals.

 

[Dragonfall]

Why not?
Which positive numbers other than $$+\infty$$ do not have inverses?

A positive number needs only to be a "number", the definition of which I'll leave to philosophers, and "positive", which means greater than 0, under some order.

If $$+\infty$$ does not have an inverse than what good is it to consider it as a positive number rather than just an concept?

A number is also a concept, isn't it?

If you want infinite and infinitesimal numbers along with maintaining the "totally ordered field" property, then you'd probably need the "surreal numbers". I'm told they don't form a set. That brings up a whole other lot of problems.

 

[Antuan]

In terms of cumulative probability, 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.

I see your point, but I still think it should happen somewhere WITHIN infinity and not specifically “on infinity”, thus shouldn't we try to find p with a variable such as "n-x" since n NEVER reaches (or equals) infinity? Instead n-x would simply mean “given enough time” or “in due time”, where x could probably never be determined exactly due to its random nature. Do you follow me ?

G.Antuan

***If something can’t be proven it doesn’t mean it is false.***

 

[SW VandeCarr]

I see your point, but I still think it should happen somewhere WITHIN infinity and not specifically “on infinity”, thus shouldn't we try to find p with a variable such as "n-x" since n NEVER reaches (or equals) infinity? Instead n-x would simply mean “given enough time” or “in due time”, where x could probably never be determined exactly due to its random nature. Do you follow me ?

G.Antuan

***If something can’t be proven it doesn’t mean it is false.***

I'm sorry, I don't. You might try following the parallel discussion going on in this thread regarding infinity.

 

[SW VandeCarr]

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.

I don't know if you were disputing my post or not. In the specific case of calculating cumulative probability, I was simply stating (in plain language) that the probability of a given digit or digit sequence is not computable (Turing definition) when the number of generations (n) equals infinity. Moreover, I don't think it's provable that an infinite random digit sequence must contain all possible finite digit sequences although I believe it's probably true (but not necessarily true).

 

[CRGreathouse]

I don't know if you were disputing my post or not. In the specific case of calculating cumulative probability, was simply stating (in plain language) that the probability of a given digit or digit sequence is not computable (Turing definition) when the number of generations (n) equals infinity. Moreover, I don't think it's provable that an infinite random digit sequence must contain all possible finite digit sequences although I believe it's probably true (but not necessarily true).

It is possible for an infinite digit sequence (with more than one digit having positive probability) to avoid a finite digit sequence. It only happens with probability 0, though.

 

[SW VandeCarr]

It is possible for an infinite digit sequence (with more than one digit having positive probability) to avoid a finite digit sequence. It only happens with probability 0, though.

When you say it's possible for an infinite digit sequence to avoid a finite digit sequence, is that the same as saying it cannot be shown that an infinite digit sequence must contain all possible finite digit sequences? (I know I'm quibbling, but I want to be sure of what you are saying.)

 

[CRGreathouse]

When you say it's possible for an infinite digit sequence to avoid a finite digit sequence, is that the same as saying it cannot be shown that an infinite digit sequence must contain all possible finite digit sequences? (I know I'm quibbling, but I want to be sure of what you are saying.)

Yes. (No apologies needed for quibbling; math needs precision. You always have my precision to call me out if I'm imprecise.)

Edit: Actually, I'm saying a little more. It can't be shown that an infinite digit sequence contains all possible finite digit sequences, but it's not undecidable: it can be shown that an infinite digit sequence could avoid some (any!) finite digit sequence. As before, the probability will be 0.

 

[SW VandeCarr]

Yes. (No apologies needed for quibbling; math needs precision. You always have my precision to call me out if I'm imprecise.)

Edit: Actually, I'm saying a little more. It can't be shown that an infinite digit sequence contains all possible finite digit sequences, but it's not undecidable: it can be shown that an infinite digit sequence could avoid some (any!) finite digit sequence. As before, the probability will be 0.

Thanks CR. I wanted to confirm that I wasn't misleading Antuan.(post 68)

 

[CRGreathouse]

Thanks CR. I wanted to confirm that I wasn't misleading Antuan.(post 68)

I did see one mistake in that post:

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.

The probability that an infinite sequence of decimal digits chosen uniformly at random contains all digits 0-9 is actually 1. It need not happen -- it's possible that all digits will be 3 -- but it happens with probability 1.

 

[ramsey2879]

I did see one mistake in that post:



The probability that an infinite sequence of decimal digits chosen uniformly at random contains all digits 0-9 is actually 1. It need not happen -- it's possible that all digits will be 3 -- but it happens with probability 1.

when does one stop adding a digit to the end of an infinite sequence of 3's?; seems like an impossible sequence to me simply based on the fact that the probability is 1-1 or zero. Not only that, but the probability of any specific infinite sequence hapening is zero because there is no end to the sequence or point in time at which the sequence is complete.