Given two randomly chosen natural numbers, what is the probability that the second is greater than the first?

Question

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?

Answer 1

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.

Answer 2

As it was mentioned on an answer, you cannot find a way to uniformly choose a random natural number. One way to think about probabilities such as this is the concept of natural density. The natural density of a set $A \subset \mathbb{N}$ is defined as $\displaystyle\lim_{n \rightarrow \infty} \frac{|A \cap I_{n}|}{n}$ where $I_{n} = \{1, ..., n\}$. Thus for instance, the "probability that a randomly-picked number" is prime is the density of the set of primes (which is zero). If we interpret it this way, after you pick some number $k$, you want to find the density of $\{n \in \mathbb{N}; n \neq k\}$, and this is indeed 1. Notice that, however, this concept is not a probability measure. It doesn't satisfy the axiom of countable additivity; indeed, for each $k$, the set $\{k\}$ has density $0$ but $\displaystyle\bigcup_{k = 1}^{\infty} \{k\}$ has density $1$.