Suppose that there exists some apparatus that, when prompted, displays a random natural number (i.e. it picks an integer uniformly from the range $[1, \infty)$).
A man writes down a number generated by this apparatus, denotes it as the first number, and afterwards prompts the apparatus for another number, writes it down, and denotes it as the second number. What is the probability that the second number will be greater than the first number?
I think the answer is $\frac{1}{2}$, because in the general case, the probability of the second number being greater than the first given two integers selected from the range $[1, n]$ is $\frac{n – 1}{2n}$. If you take the limit of this as $n$ approaches infinity, you get $\frac{1}{2}$.
I have a friend who says that the answer is $1$, since the first number is guaranteed to be finite. He argues that if you have some finite number and then choose a random number from the set $[1, n]$, the resulting number, with probability $1$, will be greater than the originally chosen finite number.
Which one of us, if not both, is wrong? Or is the problem poorly defined and thus impossible to answer?
Best Answer
It is not possible to pick an integer in the range $[1,\infty)$ in such a way that each possible selection has equal probability, and you have discovered one of many arguments for this impossibility.
More specifically, assume that there was such a probability distribution. If the shared probability $p$ of choosing any particular number is greater than $0$, then it must also be greater than $\frac{1}{n}$ for some $n$ (that is how real numbers work). But then the total probability of getting one of the numbers $1$, $2$, $3,\ldots, n$ would be greater than $1$ which is absurd.
On the other hand, if $p=0$, then the probability of getting any natural number at all would be $0$ (which is also absurd). This is because probability distributions are required to be countably additive.
Therefore $p$ can neither be $0$ nor different form $0$, which is a contradiction; we must conclude that a probability distribution over the naturals where each outcome has equal probability is not possible.