So, I was looking at a collection of printed numbers that serve as the basis of reliable random number generators, and I began thinking about “random.” (I don’t recommend that, by the way.)
I think if you really did generate truly random numbers, you would end up with a lot of really big (or small) numbers. I mean five hundred trillion is a pretty small number, as numbers go. It would be much more likely that you would get a number larger than that, if the possibilities were actually random. (The mirror image of negative, or miniscule fraction would be the same, of course.) Heck, a googol or two are still relatively small, considering the available pool of integers.
Am I terribly wrong about this, missing some obvious triviality?
Just wondering.
Tris
“Reserve your right to think, for even to think wrongly is better than not to think at all.” ~ Hypatia of Alexandria ~
Pseudo-random number generators are typically designed to generate numbers within a specified range. Zero to one is pretty common. You want a “random” number between one and 100? Take the number generated, multiply by 99, and add one.
You want a number between zero and a googol? Same concept–just make sure you have plenty of digits in your pseudo-random number.
Your “pool of integers” comment at the end is the key, I think. The pool of integers is infinite. When most people need to generate a random number, it’s usually within a certain set, such as a set of two (flipping a coin), six (rolling a die), or something similar. Even in contexts where numbers generated are relatively large (such as computer cryptography and whatnot), I’m sure there’s still a limited range of useability. In other words, if you could truly generate completely random numbers (approaching infinity), you’d eventually (probably) generate one that your computer (or whatever) would choke on.
Whenever you’re picking random numbers, you have to have some sort of distribution. The most common sort of distribution is what’s called a uniform distribution, which is to say that all numbers are equally likely. For instance, a fair coin has a uniform distribution of heads and tails (50% chance of each), and rolling a fair die gives you a uniform distribution on the numbers 1-6 (1 in 6 chance of each). You could also construct a uniform distribution on the numbers from 1 to 100, or the numbers from 17 to 693, or the numbers from -8 to one trillion.
But for a uniform distribution, you absolutely need to specify a range. You cannot pick numbers from a uniform distribution of all integers, because that distribution just plain does not exist. There are distributions on all the integers that you could use, and which could in principle give you any integer, but these distributions are not uniform. They’ll all have a clump around some particular number, and give you very low probabilities for numbers much higher than that clump.
For instance, suppose I generate my random number by flipping a coin a number of times. If it comes up heads on the first flip, then I’ve got 0. If it’s tails the first flip and then comes up heads on the second, then I’ve got 1. If the first 2 flips are tails and the third is heads, then it’s 2, and so on. You can see that this can give you any positive integer, but it’s much more likely to give you a number close to 0 than it is to give you a trillion.
Chronos is alluding to the notion of the expectation of a random variable. For an integer-valued variable X, that’s defined as sum(x * P(X = x), x [symbol]Î[/symbol] Z). If the expected value is finite, you will get the clustering phenomenon described earlier, but if it’s not, you will (with probability 1) eventually see outcomes with arbitrarily large absolute values.
If you had a computer that (theoretically) could randomly choose an integer from the entire set of integers, what would be the chance of it NOT choosing any specific number? That chance would be .999… out of one.
From other mathematics, we know that .999…=1. In other words, the chance of NOT choosing any specific number is 1 out of 1.
The converse is that the chance of CHOOSING any specific number is 0 out of 1. That means the computer would have zero chance of choosing any specific number. Therefore, such a computer is mathematically impossible.
(I used to believe that this concept proved that .999… didn’t equal one, but I was eventually convinced otherwise).
Random within limits is not the same as just random. Yet limits are pretty much impossible to escape. On a pragmatic level, I have always been aware of this. When asked to “Pick a number” without specified limits, I tend to pick numbers out of the 1 - 1000 range. I am always told that I did it wrong. (Come to think of it, Pi is the most likely number for me to pick, since my daughter’s nickname is Pie.)
Tris
“9347585161964956648246078166387148295250969908578612710405969819568794481417785036403656317241375466397303176883990123494420902183432107345907497867100639080113468661797850668566543056029194808489792075046531186165369683245227062270171645326739558261016151323367247145104178486627636631995176952360575698056100625601157589326959201691231937461429182760707220827605664508039851873442531845172782145598915149322804261897291676699862149355340855525130343982327561238448323035852829331586878075427342436744166821351304040860225627553933039172408679518691659921182099827969203187615305728767809980956869556581293383671828449515341989086546627211502012619273468361502935737009800413699043172634757146888744694425768462012045358215544536257133741847547238746614237886700677525666457546069720528391621549347958639062793476374540519113444801855493699896404396725622931098863151502145750094723618545499132824” ~ e (from about three quarters of the way through two million decimal places) ~
Actually, I’m not alluding to the expectation. Even for a distribution with an infinite expectation, there must be some clustering. That is to say, most of the numbers chosen will be close to some particular number. Or more precisely, given any proportion p, 0 < p < 1, there is some finite central value c and finite range r such that that the area of the distribution from c - r to c + r is greater than p.
It is algorithmically possible to generate a uniform distribution from a set of integers, Just get a RNG that generates from 0 - 9 and run that for an infinite amount of time and concatenate the digit string. Not too much practical uses for it though…
Can one say that something is algorithmically possible when the algorithm is guaranteed not to terminate? I don’t think that’s really meaningful. If one allows “output” from non-terminating algorithms, then one runs into all sorts of paradoces.
There is no uniform distribution over a countable set, for measure-theoretic reasons. Think about your algorithm for a few minutes, and you’ll see the problems with it.
There is a theory of infinitely-long programs, but it’s complicated and not necessarily relevant here.
Perhaps–I’ve never seen a proof of that. Do you have one?
Non-termination is sort of a problem, but you could IN THEORY generate an infinite string of digits. The problem is that that isn’t an integer, since integers are a FINITE string of digits.
(If you said that terminating in an infinite string of zeros counts, you’d have the problem that it’d “almost certainly” not since the chance of that is 0.)
However, I would describe Triskadecamus’s original point as mostly correct, in that “the largest number you could write down by turning the earth into ink to write nines with” is piddly compared to integers that COULD be chosen
It follows from the fact that a distribution must, by definition, be normalized. In other words, if you have a distribution over the integers, then the integral of that distribution from -infinity to infinity is 1. How does one define an integral over an infinite range? By the limit of integrals over a finite range. And by the definition of limit, then, for any given value less than the whole integral (that is to say, 1), there must be some finite range such that the integral over that finite range is greater than that given value. The central value and radius is just a convenient way to specify that.
And strictly speaking, there is no uniform distribution over an infinite countable set. The set {1,2,3,4,5,6} is a countable set, but it does have a uniform distribution. It’s always seemed a bit freaky to me that one can have a uniform distribution on a finite set or on an uncountable set (at least, on some uncountable sets), but not for anything in between. Are there uniform distributions on any set strictly larger than the reals?
OK, if I want to pick a uniform random integer from 1 to 10 (a finite set), I can do that. And if I want to pick a uniform random real number from [0,1] (a set with the same cardinality as the reals), I can do that, too. But suppose my space is all of the functions from [0,1] to [0,1], and I want to pick a function uniformly at random… The cardinality of that set is strictly greater than the cardinality of the reals. Is it possible to have a uniform distribution on that set? Or, for that matter, on any other set strictly greater than the reals?
And I’d never encountered the “denumerable” vs. “countable” distinction before. I’ll file that away in the ol’ brain.
I knew what you meant, I was just trying to see if I could come up with an example. But cardinality isn’t the only issue here–you can have a uniform distribution on [0, 1], but you can’t have one on R, even though those sets are the same size (at least not using the Lebesgue measure).
It’s not necessarily the case that there isn’t one.
