6
$\begingroup$

"It's well known that there are infinitely many prime numbers, but they become rare, even by the time you get to the 100s," Ono explains. "In fact, out of the first 100,000 numbers, only 9,592 are prime numbers, or roughly 9.5 percent. And they rapidly become rarer from there. The probability of picking a number at random and having it be prime is zero. It almost never happens."

--Source: phys.org

I feel really skeptical about the statement in bold above. I think the probability tends to approach zero but can never be zero. Please explain how the probability is being calculated mathematically?

$\endgroup$

marked as duplicate by YuiTo Cheng, TheSimpliFire, Asaf Karagila May 22 at 10:05

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

16
$\begingroup$

The sentence "The probability of picking a number at random and having it be prime is zero." is, mathematically speaking, either very sloppy or plain wrong (depending on who you ask) and, if you ask me, is a clear demonstration of why there's always a bit of tension between mathematicians and physicists. We call them sloppy, they call us hair splitters.

The correct sentence would be this:

If $p_n$ is the probability of picking a prime when (uniformly) selecting a random number from $1$ to $n$, then $\lim_{n\to\infty} p_n = 0$.

This statement follows directly from the prime number theorem. That theorem tells us that the if $P_n$ is the number of primes smaller than or equal to $n$, then $$\lim_{n\to\infty}\frac{P_n}{\frac{n}{\log n}} = 1.$$ Clearly, we have $p_n=\frac{P_n}{n}$, which means that $$\lim_{n\to\infty} p_n=\lim_{n\to\infty}\frac{P_n}{n} = \lim_{n\to\infty}\left(\frac{P_n}{\frac{n}{\log n}}\cdot\frac{1}{\log n}\right) = \lim_{n\to\infty}\frac{P_n}{\frac{n}{\log n}} \cdot\lim_{n\to\infty}\frac{1}{\log n} = 1\cdot 0=0$$

This also tells you that $p_n\approx \frac{1}{\log n}$ for large values of $n$, so you also know the speed at which $p_n$ converges to $0$ (rather slowly, in fact).


(*) The statement is wrong or sloppy because of a simple reason: there is a lot left out in the statement "pick a random number". What's the distribution? Uniform? There is no uniform distribution over all integers! OK, which distribution are we talking about then? Because surely, there exist probability distributions over $\mathbb N$ with a nonzero probability of picking a random number. For example, picking a random number by throwing a 6 sided die has a $0.5$ chance of picking a prime number.

$\endgroup$
  • 2
    $\begingroup$ To stick up for physicists a little, what else could be meant by "the probability of picking a number at random and having it be prime is zero?" $\endgroup$ – Charles Hudgins May 22 at 7:56
  • 3
    $\begingroup$ @CharlesHudgins I'm just saying that "picking a random number" is an ill-formed statement without telling us the distribution. $\endgroup$ – 5xum May 22 at 7:58
  • 7
    $\begingroup$ it obviously meant rolling a dice with faces labelled 4,12,15,21,22,25 $\endgroup$ – mercio May 22 at 7:59
  • 1
    $\begingroup$ @CharlesHudgins We could "pick a random number" as follows. We pick $n>0$ with probability $1/2^n$. That IS a well defined distribution (unlike just saying "pick a random positive integer"). Observe that with this distribution the probability of picking a prime number is strictly positive (larger than $1/2^2+1/2^3=3/8$ actually). It doesn't tend to anything. To get any kind of "tending" you need a sequence of probability distributions, and that is exactly what 5xum is explaining. $\endgroup$ – Jyrki Lahtonen May 22 at 8:45
  • 2
    $\begingroup$ While complaining about the quote leaving out the distribution you managed to do it as well in the "correct" sentence. $\endgroup$ – Todd Sewell May 22 at 9:49
4
$\begingroup$

From the Prime number theorem one can interpret as saying that if you pick a random integer of size about n, then the probability that it is prime is about $\frac{1}{\ln n}$.

If for one second, you relax the size about n condition, then the answer depends on what you mean by "picking an integer randomly."

The problem is that there is no way to pick an integer uniformly at random, which precisely means that if every integer has the same probability of being picked then that probability has to be zero, there is no probability distribution on the positive integers that assigns equal weight to every integer.

If you were to let $S\subseteq \mathbb{N}$ be a set of positive integers, and for every positive integer $n$, let $S_n$ be the set of all $k\in S$ such that $k\le n$. Let $|S_n|$ be the number of elements in $S_n$. Then $$\lim_{n\to\infty} \frac{|S_n|}{n},$$ if it exists, can be viewed as a measure of how large $S$ is. The measure for how large the primes is $0$.

$\endgroup$
  • $\begingroup$ What is the distribution of Sn. You seem to imply that Sn decreases as n increases which I don't get. $\endgroup$ – manav m-n May 22 at 7:57
2
$\begingroup$

The probability of picking a random positive integer and is prime is defined as $$ \lim_{n\to\infty}\frac{1}{n}|\{k : 1\le k\le n\,\,\,\&\,\,\,\text{$k$ prime}\}| $$ where $|A|$ is the number of elements of the set $A$ (i.e., its cardinal number.)

Prime Number Theorem implies that the above limit is equal to zero.

$\endgroup$
2
$\begingroup$

Layman's explanation. You are walking up the number line. If you meet a new prime number, you increase the count primes by just 1. But you can multiply this new prime number with all the previously encountered primes or composites once, twice ... or infinitely many times to create infinitely many new composites i.e. finding 1 new prime results in infinitely many new composites somewhere up in the number line so if you stop your walk randomly at a number, you are infinitely times more likely to be standing on a composite than on a prime.

$\endgroup$
0
$\begingroup$

If $N\in\mathbb N$, then, if you pick a number at random in $\{1,2,\ldots,N\}$ (assuming that all numbers have the same probability of being chosen), then the probability that that number is prime is about $\frac1{\log N}$ (this is the prime number theorem). Therefore, the limit as $N$ goes to infinity of that probability is $0$.

$\endgroup$

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