Will a Random Number Generator Eventually Repeat Its Numbers?

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

 

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