Will a Random Number Generator Eventually Repeat Its Numbers?

[ramsey2879]

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.

I beg to differ. In fact on May 7, Greathouse pointed to a sequence of over 40 digits which he said could be expected to occur "an infinite number of times" in an infinite sequence of random digits.
My concept of an infinite sequence is one that never ends, so talking about the probability of a finite sequence happening or not happening does not make sense, the probability of any finite sequence happening in an infinite sequence is 1 since any number less than 1 raised to infinity is zero. Even though one may say that the digits of a infinite sequence are random, there is no such thing as a "random" infinite sequence that does not contain a particular finite sequence. If one says that it is possible for a particular digit or finite sequence to not appear in an infinite sequence then I would say that you just haven't looked far enough.

 

[Moo Of Doom]

In probability theory, having probability 0 is not the same thing as being impossible, and having probability 1 is not the same thing as having to happen. We say something with probability 0 happens "almost never" and something with probability 1 is "almost certain." These are precise terms. We're not talking about probability .9999999999999997 or something like that.

As an example, we can pick a random real number uniformly in the interval [0, 1]. This means that the chance of picking a number in a subinterval [a, b] of [0,1] is precisely b - a, the length of the interval. Let the resulting number be x. The probability that we would pick a number in the interval [x, x] is 0, but x is in that interval. This means an event that occurs with probability 0 (almost never) happened! This is why we say almost never.

The probability that x is rational is 0... in fact, the probability that x is even computable is 0. The probability that x is normal is 1 (being normal means that any finite string of digits occurs as often as expected, that is, 1234 makes up 1/10000 of the four-digit strings, etc.).

 

[ramsey2879]

In probability theory, having probability 0 is not the same thing as being impossible, and having probability 1 is not the same thing as having to happen. We say something with probability 0 happens "almost never" and something with probability 1 is "almost certain." These are precise terms. We're not talking about probability .9999999999999997 or something like that.

As an example, we can pick a random real number uniformly in the interval [0, 1]. This means that the chance of picking a number in a subinterval [a, b] of [0,1] is precisely b - a, the length of the interval. Let the resulting number be x. The probability that we would pick a number in the interval [x, x] is 0, but x is in that interval. This means an event that occurs with probability 0 (almost never) happened! This is why we say almost never.

The probability that x is rational is 0... in fact, the probability that x is even computable is 0. The probability that x is normal is 1 (being normal means that any finite string of digits occurs as often as expected, that is, 1234 makes up 1/10000 of the four-digit strings, etc.).

I agree that in the real world the probability of an event happening or not has nothing to do with the fact of the event coming to past, but when we are talking of an infinite random string of numbers we are not talking about events hapenning in the real world. The fact that one can specify x means that we are talking of the real world, but in an infinite string of random numbers we are not talking of the real world. I stand by my argument.

 

[SW VandeCarr]

I beg to differ. In fact on May 7, Greathouse pointed to a sequence of over 40 digits which he said could be expected to occur "an infinite number of times" in an infinite sequence of random digits.
My concept of an infinite sequence is one that never ends, so talking about the probability of a finite sequence happening or not happening does not make sense, the probability of any finite sequence happening in an infinite sequence is 1 since any number less than 1 raised to infinity is zero. Even though one may say that the digits of a infinite sequence are random, there is no such thing as a "random" infinite sequence that does not contain a particular finite sequence. If one says that it is possible for a particular digit or finite sequence to not appear in an infinite sequence then I would say that you just haven't looked far enough.

CR confirmed that it's not provable that an infinite sequence of (random) digits need contain every possible digit sequence in post 103. He also said the probability that an infinite random sequence may exclude a given sequence with probability 0. Here's how I interpret that statement:

The probability of selecting the nth digit of an infinite sequence is 0. Ditto for a series of digits between the nth and the nth plus k. If we remove any finite number of digits from an infinite sequence, the sequence is still infinite. Therefore, in principle, we can remove any finite sequence such that a particular sequence does not occur. Is the sequence still random if we do that? I don't know, but I would say it could be. I think Moo of Doom is saying something similar although we have to understand that the infinite random digit sequence follows a discrete uniform distribution.

 

[ramsey2879]

CR confirmed that it's not provable that an infinite sequence of digits need contain every possible digit sequence in post 103. He also said the probability that an infinite sequence may exclude a given sequence with probability 0. Here's how I interpret that statement:

The probability of selecting the nth digit of an infinite sequence is 0. Ditto for a series of digits between the nth and the nth plus k. If we remove any finite number of digits from an infinite sequence, the sequence is still infinite. Therefore, in principle, we can remove any finite sequence such that a particular sequence does not occur. Is the sequence still random if we do that? I don't know, but I would say it could be. I think Moo of Doom is saying something similar although we have to understand that the infinite random digit sequence follows a discrete uniform distribution.

Your argument would make sense if the given sequence occurs only a finite number of times in a infinite sequence, but I don't think you can show that. I believe though that no matter how many times you could remove a given finite sequence there would still be an infinite number of occurences of the same sequence left within the infinite sequence of random numbers. You may say simply that one could remove all occasions of a given sequence, but then you have seriously altered the randomness of the sequence when you have done this an infinite number of times have you not?

 

[SW VandeCarr]

Your argument would make sense if the given sequence occurs only a finite number of times in a infinite sequence, but I don't think you can show that. I believe though that no matter how many times you could remove a given finite sequence there would still be an infinite number of occurances of the same sequence left within the infinite sequence of random numbers. You may say simply that one could remove all occasions of a given sequence, but then you have seriously altered the randomness of the sequence when you have done this an infinite number of times have you not?

I agree. The word "remove" probably should be replaced by "avoid" which is the word CR used. I see no reason however that an infinite random sequence could not avoid certain finite sequences with probability 0.

 

[ramsey2879]

I agree. The word "remove" probably should be replaced by "avoid" which is the word CR used. I see no reason however that an infinite random sequence could not avoid certain finite sequences with probability 0.

Would you say that one could toss a penny a million billion times (assuming that one lived long enough) and never have heads come up.

 

[SW VandeCarr]

Would you say that one could toss a penny a million billion times (assuming that one lived long enough) and never have heads come up.

Yes, with a probability of (1/2)^15, assuming you only used fair coins. (You can do better than that, can't you?)

 

[ramsey2879]

Yes, with a probability of (1/2)^15, assuming you only used fair coins. (You can do better than that, can't you?)

How about if you can measure an object i.e. if it is finite, then it must exist in this universe, but infinity includes every number or concept in this universe and beyond. I don't expect you to agree however, since that may be beyond the concepts of mathematics.

 

[SW VandeCarr]

How about if you can measure an object i.e. if it is finite, then it must exist in this universe, but infinity includes every number or concept in this universe and beyond. I don't expect you to agree however, since that may be beyond the concepts of mathematics.

You're trying to understand infinity in physical terms. I said in one of my earlier posts that I don't think anyone really understands infinity. Some might disagree. Mathematically it is treated in a well defined way. You need to learn the mathematical rules regarding infinite numbers and infinite sets. Some of the results are counter-intuitive (at least to me) but they can be understood in terms of the definitions and rules. One book that I particularly I enjoyed is "Infinity and the Mind" by Rudy Rucker. It's a classic with very few formulas, although it may be a little bit dated.

 

[CRGreathouse]

I said in one of my earlier posts that I don't think anyone really understands infinity. Some might disagree.

I think I understand many infinite numbers. They're actually quite easy to work with; I typically use them because they make things simpler.

 

[SW VandeCarr]

I think I understand many infinite numbers. They're actually quite easy to work with; I typically use them because they make things simpler.

I said that in the context of people trying to imagine infinity in physical terms. In the context of mathematics where things are defined, I agree. It's much easier. For example try to imagine conditions at the time of the Big Bang. What does infinite (physical) density mean? Physics has long been plagued by infinities popping up in calculations. Getting rid of them can lead to a Nobel Prize.

 

[ramsey2879]

I think I understand many infinite numbers. They're actually quite easy to work with; I typically use them because they make things simpler.

Just a thought an infinite random distribution would be a normal distribution, and you can put a decimal point before any finite string to show that it exists between 0 and 1 as a finite number, but an infinite string contains an infinite number of such universes.

 

[SW VandeCarr]

Just a thought an infinite random distribution would be a normal distribution.

If you mean 'normal' in a statistical sense (Gaussian), that's incorrect. An random infinite series of digits where each digit has an equal probability of occurring has a uniform distribution.

 

[ramsey2879]

If you mean 'normal' in a statistical sense (Gaussian), that's incorrect. An random infinite series of digits where each digit has an equal probability of occurring has a uniform distribution.

Ok here is what I have for a normal distribution "being normal means that any finite string of digits occurs as often as expected, that is, 1234 makes up 1/10000 of the four-digit strings, etc". Is that what you mean 'normal' in a statistical sense? What would a "uniform distribution" be? If it is one with a equal number of each digit? In that case a "uniform" distribution would just be a particular requirement of a "normal" distribution. I don't see the logic of why a uniform random infinite sequence that would be a "uniform" distribution would not also be a "normal" distribution.

 

[CRGreathouse]

Ok here is what I have for a normal distribution "being normal means that any finite string of digits occurs as often as expected, that is, 1234 makes up 1/10000 of the four-digit strings, etc". Is that what you mean 'normal' in a statistical sense? What would a "uniform distribution" be? If it is one with a equal number of each digit? In that case a "uniform" distribution would just be a particular requirement of a "normal" distribution. I don't see the logic of why a uniform random infinite sequence that would be a "uniform" distribution would not also be a "normal" distribution.

The rational 123456789/9999999999 has exactly (in an asymptotic sense) 1/10 of its digits as 0, 1, ..., 9, but it's not normal because 11 doesn't appear in its decimal expansion.

 

[ramsey2879]

The rational 123456789/9999999999 has exactly (in an asymptotic sense) 1/10 of its digits as 0, 1, ..., 9, but it's not normal because 11 doesn't appear in its decimal expansion.

I agree that all uniform distributions are not necessarily normal but I am saying that if one holds that a infinite random sequence would be a uniform sequence then by the same logic that the number 9 is 1/10 of the random sequence then 11 would be 1/100 of the random sequence since the logic would not depend upon what number base you are working with in that case.

 

[SW VandeCarr]

I agree that all uniform distributions are not necessarily normal but I am saying that if one holds that a infinite random sequence would be a uniform sequence then by the same logic that the number 9 is 1/10 of the random sequence then 11 would be 1/100 of the random sequence since the logic would not depend upon what number base you are working with in that case.

There is apparently more than one usage of 'normal distribution' here. In statistics the term refers to the Gaussian probability distribution. In a uniform probability distribution each outcome has the same probabilty. This is not the case in a Gaussian distribution.

 

[ramsey2879]

There is apparently more than one usage of 'normal distribution' here. In statistics the term refers to the Gaussian probability distribution. In a uniform probability distribution each outcome has the same probabilty. This is not the case in a Gaussian distribution.

Doesn't "11" have the "same probability" that any other two digit number? Doesn't the number "123456789" have the same probability as any other 9 digit number? Then what is the difference between saying that 9 occurs 1/10 of the time in an infinite random sequence because each digit has an equal probability from saying that "1234" occurs 1/10000 th of the time because each 4 digit number has the same probability?

 

[CRGreathouse]

There is apparently more than one usage of 'normal distribution' here. In statistics the term refers to the Gaussian probability distribution. In a uniform probability distribution each outcome has the same probabilty. This is not the case in a Gaussian distribution.

Normal *number*, not normal *distribution*. No one here is talking about the distribution produced by the Central Limit Theorem.

 

[ramsey2879]

Normal *number*, not normal *distribution*. No one here is talking about the distribution produced by the Central Limit Theorem.

Thanks, I studied the information re central central limit therom and agree that my terminology was wrong. The central limit therom applies when there are a large number of finite samples of "normal" numbers (each having the same probability of occurring within the applicable range) is taken and the mean of each sample is taken. Then the distribution of the means will approach a normal distribution.
But getting back to my understanding of a uniform distribution, if each digit has an equal probability has a 1/10th probility, then each 2 digit number has a 1/100th probability etc., and by the same argument that a infinite random sequence of one digit numbers will have a uniform distribution then the same sequence cam be considered as an infinite sequence of n-digit numbers, the distribution of which will be a uniform distribution.

 

[CRGreathouse]

The relevant answer would be that a number generated from the suitable uniform distribution of digits is normal with probability 1.