Why is the probability of picking an odd number from the set of natural numbers not $\dfrac{1}{2}$?

Could anyone explain it to me in simple terms?

I am only curious about the reason why and that's the reason why I asked for a "simple" explanation. I remember my teacher mentioning that it is because the set is infinite. Is that right? can someone elaborate?

  • 5
    $\begingroup$ There isn't really a coherent notion of picking a natural number at random. $\endgroup$ – Lord Shark the Unknown Mar 6 '18 at 19:47
  • 4
    $\begingroup$ Related: math.stackexchange.com/q/1431750/504810 $\endgroup$ – Mauve Mar 6 '18 at 19:47
  • 2
    $\begingroup$ Well, what's the distribution? The natural density of the odds is $1/2$, which gives a reasonable notion of what you're after without having to define a probability distribution. $\endgroup$ – T. Bongers Mar 6 '18 at 19:49
  • 2
    $\begingroup$ @mrnobody The whole point is that it's you who needs to elaborate. What precisely do you mean by "choose at random"? The point is that there are various different reasonable things this could mean, and there are various intuitively-plausible properties a notion of randomness (for natural numbers) could have that it turns out are inconsistent. So, what do you mean by "random"? $\endgroup$ – Noah Schweber Mar 6 '18 at 19:59
  • 7
    $\begingroup$ @NoahSchweber Could you have supplied the above enlightening comments before repeatedly chiding the OP for not providing a definite notion of 'random'? There is a clearly a naive sense in which half of all numbers are odd, and if the OP were aware of the subtleties which render such a statement indeed naive, they probably would not have asked the question. If we only tolerate well-posed questions, the mathematically inexperienced will be left by the wayside! $\endgroup$ – gj255 Mar 6 '18 at 20:59

The trouble with probability is that it's not as intuitive as it seems.

If you roll a six-sided die, there are six outcomes, and it's fair to assume they're all equally likely. In that case, the probability of getting a 3 is $\frac{1}{6}$, and the probability of getting an odd number is $\frac{3}{6} = \frac{1}{2}$.

Certainly this doesn't depend depend too much on the number of sides to the die. If it has $2n$ sides, numbered $1$ through $2n$, the probability of getting a 3 is $\frac{1}{2n}$, and the probability of an odd-numbered side is $\frac{n}{2n} = \frac{1}{2}$.

Now what if you have a die with one face for each natural number? What is the probability of getting a 3 now? Since there are infinitely many possible outcomes, you can't just count them and consider them equally likely. Instead, you need, for each natural number $k$ a nonnegative probability $p_k$ which is the probability of getting a $k$. Since the possible outcomes are the set of natural numbers, we require $$ p_0 + p_1 + p_2 + p_3 + \dots = 1 $$ Even so, there's no guarantee that $$ p_1 + p_3 + p_5 + \dots = \frac{1}{2} $$

This is why your teacher said that the problem isn't well-defined when the full infinite set of natural numbers is concerned. You need to know the probability function before you can answer the question.

  • $\begingroup$ Can't we define in this case that $N/(2N) \le p_{odd} \le (N+1)/(2N)$ for $N \to \infty$ ? $\endgroup$ – G Cab Mar 9 '18 at 23:55

Let's start with the hypothesis there would be an uniform distribution on the natural numbers, where we would think the searched probability would be $\frac{1}{2}$. I will give intuitive arguments why this cannot possibly work.

I'm borrowing the idea from Matthew of the die with a face for each natural number. Let's image this dice as a perfect marble, which each infinite small point on it to be a natural number. Once you rolled the marble, you will get a message on your computer which number was rolled, since we can't read what stands on infinite points. But no matter how much storage your PC has, it will instantly stop working because the storage is filled.

Example: Image your storage is 1 exabyte, about 1 billion gigabytes or $10^{18}$ bytes. For simplicity, let a byte can represent 1 digit. How big is the probability that you get a number that is small enough to be represented? Well, there are not simply numbers with maximal $10^{18}$ digits (the smallest number with $10^{18}$ digits is $10^{\left(10^{18}\right)}$) but also numbers with $10^{18}+1$ digits or $10^{19}$ digits, which is much more. So lets forget for a moment that we have infinite natural numbers and only deal with numbers with up to $10^{19}$ digits. The probability to roll a number with at most $10^{18}$ digits out of all numbers with at most $10^{19}$ digits is

$$p=\frac{10^{\left(10^{18}\right)}}{10^{\left(10^{19}\right)}}=10^{\left(10^{18}-10^{19}\right)}=10^{-\left(9\cdot 10^{18}\right)}$$

Whoops, that is a little bit too small to imagine, it is basically $0$ in every sense imaginable. But let's note that $p< 2.76\cdot 10^{-16}$ (by a really big margin) which is the probability of throwing two 1's with two six-sided dice 10 times in a row. You can try out how inprobable that is at home. So in conclusion, if we have just $10^{10^{19}}$ of the infinite possible numbers, we can almost certainly not record the result of throwing our marble. If we have all numbers on it, the probability can only become smaller.

But let's say, by chance, we actually get one of these numbers with $10^{18}$ digits at max and it is saved on our computer, a file of size 1 exabyte. By a similar argument as before, it is reasonable to assume our number has at least $10^{17}$ digits, our in our experiment, exactly that many. We already banded luck already by getting it on there in the first place, so let's not try that again. Since our PC can store one exabyte, we can just say it is cutting edge and has a processor of 1 Terahertz or 1000 Gigahertz, meaning it can perform $10^{12}$ elementary operations per second. Lets say we want to inspect our random number digit by digit and the PC only needs one elementary operation to display 1 digit (which is unrealistic fast, but easy to work with). Then our PC would need

$$t_{PC}=\frac{10^{17}}{10^{12}}= 10^{17-12} = 100,000$$

seconds or over 27 hours just to display them all. Yeah, but that doesn't really help us, with the numbers just flashing through the screen, we want to read them. Let's generously assume we could read 100 digits per seconds, then we would need

$$t = \frac{10^{17}}{100} = 10^{15} $$

seconds or over 31 million years to read them all. Not too bad.

But let's go back and assume the computer can tell us if the random number is odd or even, because it is clever and only looks up the last digit in a second. Now we would like to test our initial hypothesis and draw some numbers to find out if the empirical probability will be close to $\frac{1}{2}$. Who knows a bit about statistics would argue that this isn't the best way to test our hypothesis, but we have a supercomputer so shut up. It would be save to assume that loading 1 random number the computer can save would take over a day (since writing one digit can at most be an elementary operation). BUT we still have the problem that we can only store numbers with at most $10^{18}$ digits. So we have to throw our marble as often as needed until we get such a number. Again, instead of infinite numbers, lets say they only go up until $10^{19}$ digits. How often do we, in average, have to throw the marble until a saveable number occurs? According to Wikipedia the expected number of failures before the first success is

$$E=\frac{1-p}{p}= p^{-1} - 1 = 10^{\left(9\cdot 10^{18}\right)} -1 $$

Huh, again that big exponent. Smaller than a Googolplex, but still... If we assume we make one try per second and a million years contains roughly $10^{13}$ seconds we would need about

$$Y=\frac{E}{10^{13}}\approx 10^{\left(9\cdot 10^{18}-13\right)}$$

million years. Well, that didn't help much. But let's note that $Y$ is much much much greater than $10^{85}=10^{\left(10^3-15\right)}$, the maximum estimate of fundamental particles in the universe. If we were to deal with the full set of natural numbers, we would probably observe a gazillion of big bangs and universe deaths before getting a number small enough to save. One number. One. Normally we conduct experiments to test hypotheses with more than 1 example. Also we don't observe the death of the universe in the mean time.


The notion of an uniform probability distribution on the natural numbers can only seem intuitively working for us because we have absolutely no intuition about how big these natural numbers can become. Therefore we can also not make reasonable predictions about if a uniformly random number would be odd or even because this kind of random cannot exist. I hope that I could give some insight into bigger numbers with this post. As noted in the comment of Air Conditioner, for a more formal approach read this question, it is very informative.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.