# Can you pick a random natural number? And a random real number?

Is it possible to pick a random natural number? How about a random real number? Is the axiom of choice involved in this?

• We wouldn't have much of probability theory if it wasn't possible... – Karolis Juodelė Oct 29 '14 at 19:31
• You don't need the axiom of choice to pick a natural number; just pick $0$. Ditto for the reals. So it's good if you can clarify what "picking a random number" means. – Marc Oct 29 '14 at 19:33
• If you mean uniformly (with equal probability of choosing any natural or real number), then no. There is no uniform distribution on the space of natural numbers or real numbers. You are certainly allowed to pick them non-uniformly, as you probably know (the normal distribution lets you pick real numbers at random). I do not know if the axiom of choice is related, though, so I won't comment on that. – Nicolás Kim Oct 29 '14 at 19:35
• The number of times you have to toss a coin to get "heads" once is a random natural number, with a geometric distribution. – Michael Hardy Oct 29 '14 at 20:15
• @Mark: xkcd.com/221 – Asaf Karagila Oct 30 '14 at 9:01

The question is what does it mean "by random". Remember that mathematics is built on precision. This means that the terms you are using has to have a precise meaning (or at least a reasonably obvious way how to translate them to such).

Random is not one of these terms. The natural meaning of "random" really just means "arbitrary". To choose an arbitrary element from a non-empty set you don't need anything except existential instantiation, which allows us to go from "There is something" to "This is something". Of course you can't say which element was taken when you instantiate an existential quantifier. That's the true sense of the word arbitrary.

On the other hand, from the probability point of view, random just means that you have some distributions which tells you what are the odds of an element being chosen from a particular collection of element. It might not be able to assign probability to every possible collection, though.

Probability has a few axioms, one of them says that given countably many pairwise disjoint sets, the probability of being in one of them is the sum of all probabilities. Another is that the probability of picking out any element is $1$.

Now it's easy to see why a countably infinite set does not have any probability which assigns singletons probability $0$. Because a countably infinite set can be written as the countable union of singleton, and the axioms of probability would mean that we assign the probability of picking any element from the set as $0$, which is impossible. On the other hand, you can't have that the probability for any number is equal to the other, and non-zero, since then the probability for picking just anything is infinite (it will be the sum of a constant positive number). So essentially it says that some numbers will have a better chance being chosen than others, which might not fit with the natural meaning of the word "random", which we like to think about as a uniform distribution, allowing each possibility the same chance of being selected.

On the real numbers it's better, though, as an uncountable set, and more specifically a set which has those lovely features that the real numbers enjoy from. These allow us to define an assortment of probabilities where singletons have probability $0$. We can restrict ourselves to the interval $[0,1]$, and not the entire set of real numbers, and then we have a very nice probability, which assigns an interval $[a,b]$ the probability of its length, $b-a$.

So far, we have no made any appeal to the axiom of choice. Or have we? It turns out that without the axiom of choice it is possible that the real numbers could be expressed as the countable union of countable sets. If we allow a probability to be countably additive, this means that there is no way to define a probability on the real numbers. We simply extend the problem from countable sets to the real numbers. Note that this doesn't mean that the real numbers are countable, the fact that the countable union of countable sets is countable depends on the axiom of choice.

But finally, you might notice, we haven't picked any number! This is because probability doesn't really deal with picking the actual number, just with the odds of the number being in one set or another. The closest to picking a number that I can think of, an arbitrary number, is existential instantiation that we talked about earlier.

• Thank you very much. What an excellent answer. – Martijn Oct 29 '14 at 19:57
• @user2357112: Yes. I am quite confident about that. You need to first choose an enumeration for each set. – Asaf Karagila Oct 30 '14 at 2:52
• @AsafKaragila: ...ah. I was implicitly imagining each set came with a priviliged enumeration. The axiom of choice is indeed needed before we can do the diagonal stripey thing. – user2357112 supports Monica Oct 30 '14 at 3:10
• You make the reals and the naturals sound too different here. For the naturals give 1 a probability 1/2, 2 1/4, 3 1/8, 4 1/16, etc. and you have a valid distribution. for an "intuitively random" probably is zero, and you certainly can't have intervals on R all having equal probability any more than naturals in N. – djechlin Oct 30 '14 at 15:10
• I'm going to agree that this answer is flawed. If we can randomly pick a number x from R, and we can also determine the largest number y in N such that y<x, then we have a method to randomly pick y in N, with P(Y) = ∫p(x) over the half-open interval [y,y+1) – MSalters Oct 30 '14 at 15:35

There are distributions over all natural numbers, such as the Geometric distribution, and distributions over all real numbers, such as the normal distribution.

But there is no uniform distribution in either case. You can see this as follows: if there were a uniform distribution over natural numbers, it would have to assign some probability $p$ to each natural number. If $p = 0$ then the total probability $\sum_{n\in\mathbb{N}} p(n)$ is 0. But if $p > 0$ then the total probability is $\infty$. In either case we don't have a valid distribution.

Similarly, if there were a uniform distribution over real numbers, it would have to assign some probability $p$ to each interval of the form $[n, n+1)$ for $n\in\mathbb{Z}$. Then an equivalent argument to the above shows that $p$ can't be 0 nor greater than 0 so no such distribution exists.

• The general (albeit probably a bit too advanced for OP...) fact is that a locally compact group has a finite (nonzero) invariant measure if and only if it is compact. Integers and reals are non-compact, so they don't have finite invariant measures. – tomasz Oct 30 '14 at 3:40

The first question is easier: to decide what it means to pick a random natural number, we need a probability distribution, which is just an assignment of a probability $p_n$ to each $n$ such that $\sum p_n=1$. But to have that sum, we can't have all $p_n$ equal-so in that sense there's no standard way to pick a random natural number.

In the case of the natural numbers, it's easy enough to describe how to make a choice once we've chosen a distribution: assign to each $n$ the interval $I_n=[\sum_{m< n} p_m,\sum_{m \leq n} p_n]\subset [0,1]$, then flip a bunch of coins to get an approximation of some real number $x\in [0,1]$ (specifically, a segment of the binary expansion of $x$.) After enough flips we'll learn in which $I_n$ $x$ lies, and then choose $n$ as our "random" number. Observe this definitely does not appeal to the axiom of choice: AC is really about choosing elements of abstract sets, whereas it's very easy to choose elements of $\mathbb{N}$ since the natural numbers have so much structure.

Things get trickier in the case of the real numbers. For the same reason as above, there's no distribution with equal probabilities for all numbers, but it's worse: there actually can't be more than countably many numbers with a nonzero probability at all! (This follows from the fact that an uncountable sum of positive numbers is always infinite.) In fact the most interesting probability distributions on real numbers assign a probability of zero to every real. In that case there's really no way to pick a random real, because the intervals corresponding to $I_n$ above are only a single point, and we can't pick out a single real number by flipping a finite number of coins. But we do have positive probabilities of landing in certain intervals $[a,b]$. Making those intervals very small and picking randomly from them-according to some probability distribution-is the closest one can get to picking a random real number.

This might not be terribly helpful, but here is another reason why this should not be possible.

First, we will say that "picking a random real number $x$", means that $x$ has the same probability of being any real number. Thus $\mathscr P(x=\pi) = \mathscr P(x=e^{41}) =\dots$

Next, define the function $D(y) :=\mathscr P(x=y)$ (roughly). This isn't completely rigorous, but it's enough. $D$ is called the probability density function -- what you would like is for $D$ to be a constant. Intuitively, if you pick a random real number then the probability of it being, say, $\pi$ will be zero (there are just too many other things it could be).

Taking another level of rigor, the following should hold for $D$:

$$\int_{-\infty}^{\infty}D(x)dx = 1$$

This is basically saying the probability that you've picked something is $1$. If you want to satisfy this, $D(x)$ (which you want to be constant), clearly can't be zero since $\int_{\mathbb R} 0dx = 0$. If $D\neq 0$ is constant:

$$\int_{-\infty}^{\infty}Ddx = Dx\,\biggr\rvert_{-\infty}^{\infty}\neq 1$$

Therefore you can have no constant probability density on $\mathbb R$.

YES! (sort of)

Here is a construction (note it uses the axiom of choice):

Pick your favorite irrational number and call it $$\alpha$$. Now, the ergodic circle rotation by $$\alpha$$ starting at $$x$$ is the set $$\{x + n \alpha \pmod{1} : n \in \mathbb{Z}\}$$. That is, you add (or subtract) $$\alpha$$ a bunch of times and then keep the fractional part. What's convenient about this is that the orbits form equivalence classes and never repeat, so each element in an equivalence class (with the starting point $$x$$ given) can be indexed by the value of $$n \in \mathbb{Z}$$.

OK, so, partition the inteval $$[0, 1]$$ (or $$[0, 1)$$ if that makes your life easier, whatever) into orbits of ergodic circle rotations, each with a given starting point $$x$$ (that is, a representative of the equivalence class of each orbit). We can do this if we assume the axiom of choice.

Now, generating a uniform random integer is easy!

Start by taking a random real number $$y$$ from $$[0, 1]$$. It must be in one of the orbits, since they partition the interval. Since you have a fixed starting value $$x$$ for the orbit, you have a well defined $$n \in \mathbb{Z}$$ such that $$y = x + n \alpha$$. So, your random integer is this $$n$$.

OK, so you might wonder whether this is "uniform" and with good reason. What is the probability of, say, picking the number $$5$$? Well, it doesn't exist. The set of real numbers $$y$$ corresponding to any fixed $$n$$ is not a measurable subset of $$\mathbb{R}$$, so, technically, no uniform distribution was involved; there weren't even any probabilities!

However, if "uniform" means to you (like it does to me) without bias toward any outcome (or without carrying any information), then this certainly fits the bill! It doesn't favor any integer over another.

And of course this can be extended by a bijection to any countable set, such as the natural numbers. And certainly you can now form a "random" real number by taking a random integer $$x \in \mathbb{Z}$$ and a random real $$y \in [0, 1)$$ and adding them together.

• In showing that you can take a random natural number, you say 'start by taking a random real number from [0,1]'. How does one go about this? Why can I do this, but I can't 'start by taking a random natural number'? – Tom Rush 21 hours ago