Wikipedia:Reference desk/Archives/Mathematics/2015 September 5

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

September 5

How can I pick one of all the natural numbers, really any one, randomly? If at all

Picking a random number from a range seems easy to me. This can have its pitfalls, but I would have a good shot with a pair of dice. However, the question is not about this case.

I am wondering about picking any natural number randomly from the whole infinite series. Intuitively I'd say it's not possible, but that's a poor argument about the impossibility of picking a random number from an infinite set. Maybe I am just too stupid to device a method for accomplishing it. --Jubilujj 2015 (talk) 12:09, 5 September 2015 (UTC)

Here's my limited understanding of this. If you're talking about choosing a natural number with the chance of choosing every number being the same, you're quite right, it's a priori not possible. One way of looking at it is that the probability of choosing any particular number must be the same, and all the probabilities must sum to 1. But there's simply no way of doing that over an infinite set of numbers for any finite probability of getting any individual number, no matter how small.

However, there are infinite series that do sum to finite numbers, so it might in theory be possible to take about the choosing of random integers with those distributions. (For example, p(0) = 1/2, p(1) = 1/4, p(2) = 1/8...) But now you would need a physical process to carry out that computation, and that would require either infinite precision or infinite time, neither of which are physically realizable.

No doubt someone more mathematically knowledgeable than me will be along in a moment to give a more accurate answer. -- Impsswoon (talk) 13:04, 5 September 2015 (UTC)

Yes, you got my point. The requirement of all numbers to sum to 1 is better than my intuition and a step in the right direction.--Jubilujj 2015 (talk) 13:13, 5 September 2015 (UTC)

Presumably my geometric series example would be a supertask, for someone with a magic random coin. And, for the mathematically more sophisticated, it would be interesting to hear your opinions about what choosing a random real number might mean, in terms of physical realizability. Would this be a hypertask? -- Impsswoon (talk) 13:19, 5 September 2015 (UTC)

Another approach is to take a uniform distribution with parameter n, solve whatever problem you're trying to solve, then take the limit as n goes to infinity. For example there is the famous result that the probability that two integers are relatively prime is 6/π². As stated this doesn't really make sense, but is an informal way of saying that as n approaches infinity the probability that two random numbers from 1 to n are relatively prime approaches 6/π². Natural density has more on this. --RDBury (talk) 13:23, 5 September 2015 (UTC)

A thought: presumably if you can do supertasks, you can make an arbitrary non-negative integer by just adding random binary digits to the left of the binary point, and arbitrary reals between 0 and 1 by just adding them to the right of the binary point. But since the unit interval can be mapped to the whole real line, this would suggest that the cardinality of the reals is the same as that of the integers, which is nonsense, by the diagonalization argument. Help! -- Impsswoon (talk) 13:29, 5 September 2015 (UTC)

There is no uniform distribution on a countably infinite set. There are lots of perfectly good probability distributions on a countably infinite set. Actually drawing from one of these distributions is impossible in a practical sense for reasons that have nothing to do with fancy concepts like super-tasks: it is not possible because you can't actually write down infinitely many different things. The correspondence you've written down sends integers to real numbers with terminating binary expansions; this is not all real numbers. --JBL (talk) 15:16, 5 September 2015 (UTC)

Ah! Yes, of course. I knew I had something wrong, but now you point it out, that should have been obvious. -- Impsswoon (talk) 20:58, 5 September 2015 (UTC)

To pick a natural number at random with a nonzero probability of choosing any one, just do this:

            n = 0
            while random() < 0.5:
                n += 1
            return n

This is not a supertask; it's an ordinary algorithm that can be run on a probabilistic Turing machine. It terminates with probability 1 after finitely many steps.

You can't produce a random real number this way because the size of the output is infinite (for all but countably many reals, regardless of the representation you choose). But you could output it incrementally in a form used in computable real arithmetic, such as a converging sequence of rationals or a continued fraction. -- BenRG (talk) 04:54, 7 September 2015 (UTC)

Would the number 454856234309486 have the same probability of being picked as the number 3?--Yppieyei (talk) 12:08, 8 September 2015 (UTC)

No, both because that's impossible and because it's easy to see that this gives the other distribution we've been discussing, where the probability of getting n+1 is 2^(-n). --JBL (talk) 12:26, 8 September 2015 (UTC)

Take a real-valued random number generator with a uniform density on the unit range [0,1). Scan natural numbers in order, replacing the temporary result with the current number with the probability decreasing as 1/t. After infinite number of steps you'll have some natural number as the final result:

int temp, counter, result;

for( counter = 1; counter < ∞; counter ++ )
    if( random() < 1.0/counter )
        temp = counter;

result = temp;

For any finite number N of steps (and good quality of random() function) this returns one of {1,..., N} with uniform probability distribution. Hopefuly it could maintain a uniform distribution for infinite number of steps, too, provided you find a counter long enough to count ALL natural numbers — and enough time to wait for the final result! --CiaPan (talk) 12:25, 8 September 2015 (UTC)

That's the same hypertask problem pointed at above.--Yppieyei (talk) 12:44, 8 September 2015 (UTC)