Some thoughts on generating random members of infinite sets

Here’s a challenge for you. Think of a random natural number (i.e. one of the numbers in the sequence 0, 1, 2, …). If you think about this, this is a rather difficult task, because of the fact that there are infinitely many natural numbers, but if the choice is random, then every natural number should have a non-zero chance of being chosen. In fact, I can give you an argument that it is impossible. Assuming there is a positive lower bound on the length of time it takes to think of a natural number, then, since there are only finitely many minds in the universe, there are only finitely many natural numbers which have ever been thought of. And the random natural number you thought of must have been one of these natural numbers. So there are infinitely many natural numbers—the ones which have never been thought of—which you were never going to choose. Their chance of being chosen was zero, so the choice was not truly random. In fact, it was non-random in a pretty serious way: not just one or two natural numbers had zero chance of being chosen, but infinitely many natural numbers had zero chance of being chosen.

It is possible to generate a random natural number using an algorithm, provided you have some way of generating random natural numbers up to some upper bound. For example, here’s one algorithm you could use.

  1. Let n be 0.
  2. Generate a random natural number which is either 0 or 1, and let x be this number.
  3. If x is 0, stop and return n. Otherwise, add 1 to n and repeat from step 2.

For every natural number n, this algorithm will generate n if and only if 1 is generated in step 2 n times, so the probability that it will generate n is 2−(n + 1) (since the probability that 1 will be generated in step 2 is 1/2).

Of course, you could ‘think of’ a natural number by performing this algorithm in your head, which kind of invalidates the argument above. We can rescue the argument by noting that, if you perform the algorithm in your head, you will need time to perform each step. Therefore, if you are required to think of a natural number within a given length of time, you will only have time to repeat from step 2 a finite number of times. Let’s call this number of times n. Then there will not be enough time for you to generate n + 1, or any greater natural number, using the algorithm.

Now, although this algorithm can generate every natural number, it doesn’t generate them all with the same probability. 0 is twice as likely to be generated as 1, which in turn is twice as likely to be generated as 2, and so on. In fact, it is not actually possible to devise an algorithm that generates every natural number with the same probability. Suppose you have an algorithm and for every natural number n, the probability that the algorithm will generate n upon execution is Pn. Then the infinite sum Σn ∈ ℕ Pn has to be 1, because the algorithm always generates some natural number. But if the value of Pn does not depend on the value of n, this is impossible: the sum evaluates as 0 if the value of Pn is always 0, and the sum evaluates as ∞ if the value of Pn is always a real number greater than 0. On the other hand, we do have that Σn ∈ ℕ 2−(n + 1) = 1, so that’s why the algorithm above does work.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s