Selecting a random element from an infinite set?

**danbaron** · 04-09-2011, 11:06

Proposition:

It is impossible to select a random element (member) from an infinite set.

(I don't know how to rigorously prove this.)

Arguments:

1)
Say we have a box filled with 100 ping pong balls, numbered from 1 to 100. If we shake the box and select one of the balls without looking, the probability of selecting a particular ball is, 1/100.

If the box has 1000 balls, the probability is, 1/1000.

If the box has an infinity of numbered balls (assume that somehow we can write the number on the ball no matter how big the number is), then, the probability is,

the limit as n approaches infinity, of 1/n, which equals 0.

It means that if the box contains an infinite number of balls, the probability of randomly selecting any particular ball, say, number 2, is 0. (Actually, I think this argument alone comprises a proof of the proposition.)

2)
Say, that instead of a box filled with ping pong balls, we decide to simulate the experiment using a computer. We can use a random number generator to do so. Usually computers use pseudo random number generators, which are actually repeating sequences with very long periods. However, if I remember correctly, it is possible to generate real random numbers on a computer by using a device that produces electronic white noise. We could use the device to randomly set bits. It is easiest if the number of balls in the box we are simulating, is a power of 2. So, to simulate a box filled with 1024 balls, we would randomly set 10 bits, and we would get a base 2 number equivalent to the decimal range of 0 to 1023.

In the general case, if we are simulating a box filled with x ping pong balls, then, we need y bits such that, 2^y is equal to x.

But, how about if we are simulating a box filled with an infinity of ping pong balls?

Then, in order to perform the simulation we would need a computer with an infinity of bits, which is impossible.

Additionally, pretend that somehow we did have a computer with an infinity of bits. When we ran the simulation, would the computer return a random number in the range of 0 to infinity?

I don't think it would. I think the computer would always return infinity. Think of it like this. The first bit the computer returns will represent the value (0 or 1) for 2^0, the second bit it returns will represent the value for 2^1, etc. Since it has to be able to represent every possible value in the range of 0 to infinity, it will return an infinite string of bits. In order for it to return any finite number (representing the number on the ping pong ball), at some point in the string, it must never return another value of 1. All of the infinity of succeeding bits must be set to 0. And, since the probability is exactly 0.5 for each bit being 0 or 1, the probability that an infinite sequence of bits is 0, is 0. It would be the same as if you flipped a fair coin forever, and never got a tail. So, in my opinion, the result of this thought experiment is that, the computer would always return the value, infinity.

3)
You might say, "But what if I was suspended above an infinite ocean of mixed up numbered ping pong balls, couldn't I close my eyes and randomly select one?".

I think the answer is, you could not. Why? Because, I think it is impossible to mix an infinity of ping pong balls. No matter how many you mixed together, you would always have an infinity remaining that you had not mixed.

**LanceGary** · 04-09-2011, 12:36

I presume that you are referring to discrete numbers (integers) rather than real numbers.

There are formulae from calculus for calculating the probability density of particular
distributions of continuous numbers within particular bounds. Within any interval
of real numbers there are of course an infinity of other real numbers.

I presume that you are using the frequentist definition of probability.

Perhaps all that is required to show the difficulty of selecting an integer from an infinite
set of integers is to argue that each number needs an index to enable selection, and to
determine that each number has an equal chance of being selected. But in an infinite
set of integers the indexes are also going to be infinite. That means that no upper and
lower bounds can be formulated for the index numbers. But the formulae for selecting a number
at random require upper and lower index boundaries. Therefore the formulae for selecting a
random number from an infinite set of integers are undefined.

If you adopt a Baysesian definition of probability (probability relates to belief) then perhaps
a random number can be defined as a number which will surprise you. Benford's Law shows that
human beings are highly biased towards smaller numbers, and very large numbers have a
vanishingly small chance of being contemplated by a human being. Suppose we define a set of
humanly accessible numbers (numbers which we can think about even if very rarely). Then since
the set from which we have to select the random number is infinite, and the integer numbers will
thus be indexed by an infinite set of integers, it follows that a number that has an index that
falls outside the set of human accessible numbers will contain the maximum possible surprise.
But since the set of index numbers is infinite, there must be an infinity of numbers that will
have the maximum possible surprise. Therefore it is not possible to select a single random number
from an infinite set of integers.

Lance

**danbaron** · 04-09-2011, 22:25

From what I understand of what you wrote, I agree with you, Lance.

I know about continuous probability density functions.

Say, you have a uniform continuous probability density function for the interval 3 to 4.

It means, for instance, that the probability of randomly selecting a real number in the sub-interval (open or closed, it doesn't matter) 3.5 to 3.6, is, 0.1.

However, the probability of randomly selecting any particular real number, say, 3.7, in the interval, is 0.

How can that be?

I think the reason is that in order to randomly select (by chance) 3.7, the number would have to be 3.70000000000.., i.e., the digit 7 would have to be followed by an infinite string of zeroes.

And, there is no possibility that you could ever select that infinitely precise real number, by chance.

Similarly, there is no possibility (the probability is 0) that you could ever randomly select the exact value of pi, because in order to do so, you would have had to unwittingly select the real number with pi's infinite decimal expansion, and, it turns out, that is impossible.

We could look at it like this. No matter how finely we divide a sub-interval, it always can be divided infinitely finer. That is what you said,

"Within any interval of real numbers there are of course an infinity of other real numbers.".

I agree that humans never think about numbers that are larger than anything in their experience. If I remember correctly, there are only approximately 10^70 particles in the universe. So, it seems that for humans, numbers larger than that have no meaning, because they have nothing to measure them against.

Donald Knuth, the amazingly smart numerical computer scientist, did invent the "up arrow notation" to represent numbers beyond human comprehension.

http://en.wikipedia.org/wiki/Ackermann_function

http://en.wikipedia.org/wiki/Knuth's_up-arrow_notation

From the Ackermann article, concerning A(4,3),

"Written as a power of 10, this is roughly equivalent to 10^{6.031×10^19,727}.".

I think that no one has any idea how big that number is.

Just the relatively tiny number, 4^4^4^4, has approximately 10^154 decimal digits.

http://www.thinbasic.com/community/s...teger-function

Dan

------------------------------------------------------------------------------------------------------

Interestingly, and maybe almost unbelievably, Don Knuth believes in God.

http://www.amazon.com/3-16-Bible-Texts-Illuminated/dp/0895792524/ref=sr_1_7?s=books&ie=UTF8&qid=1315169498&sr=1-7

http://en.wikipedia.org/wiki/Donald_Knuth

And, at least about some things, our minds (his and mine) work similarly.

http://www-cs-faculty.stanford.edu/~knuth/iaq.htm