I am trying to calculate the probability of picking perfect squares out of first $n$ positive integers.

There are $\operatorname{floor}(\sqrt n)$ number of perfect squares less than $n$, if we assume picking each number is equally likely then probability of picking perfect squares less than $n$ is $p(n) =\operatorname {floor}(\sqrt n) /n$

But if we consider all positive integers then ( I think but I am not sure) the probability is $\lim_{n\to \infty} p(n) = 0$. That means the probability of selecting a square is $0$ even though there are infinitely many squares! Does this mean I that I will not get any squares when I pick any positive integers? This appears like a paradox.

I think I have not very much understood what it means by $P(A) = 0$, does this mean the event $A$ is impossible or something else?

Can you give some insights about this?

  • 6
    $\begingroup$ There are no uniform distribution on natural numbers: You can't pick a number 'with equal probability'. The limit you discribe is called density in number theory, which is not as relevant to probability. $\endgroup$
    – Trebor
    Sep 26 at 6:35
  • $\begingroup$ What is the probability that if you select a positive integer $\leq n$, the number that you select is $2$, assuming that $n \geq 2.$ The probability is $\frac{1}{n}$. This means that as $n \to \infty$, the probability of selecting the number $2$ goes to $0$. However, if you are asked to select any positive integer, while the probability of selecting the number $2$ is $0$, it is still not impossible to select the number $2$. $\endgroup$ Sep 26 at 6:51
  • $\begingroup$ In the same way, if a Real number $r$ is selected at random from the interval $[0,1]$ the chance that $r = (1/2)$ will be $0$. Despite this, it is not impossible for the number selected to equal $(1/2).$ $\endgroup$ Sep 26 at 6:55

The problem is that you are assuming that you can define a uniform distribution on the natural numbers by considering the limit of the uniform distribution on $\{1,\ldots,n\}$ as $n\to\infty$.

However, there is no such thing as a uniform distribution on the natural numbers.

If $\Pr(N=n)=p$ for every $n\in\mathbb{N}$ then if $p=0$ we have $\sum_{n\in\mathbb{N}}\Pr(N=n)=0$, whereas if $p>0$ we have $\sum_{n\in\mathbb{N}}\Pr(N=n)=\infty$. However, we need $\sum_{n\in\mathbb{N}}\Pr(N=n)=1$ for a probability distribution, so it doesn't exist.


One can understand the problem using the notion of natural density. Specifically, $$ d(A)=\lim_{n\to\infty}\frac{|A\cap \{1,\ldots,n\}|}{n} $$ if the limit exists. In your case, $$ d(A)=\lim_{n\to\infty}\frac{\lfloor \sqrt{n} \rfloor}{n}=0. $$

See this question for another (related) interpretation.


When dealing with a sample set that has infinite possibilities, a probability of zero is not the same as something being impossible.

A classic example of this is picking a random number $x$ between zero and one. It isn't impossible for you to pick $\frac12$, as $0<\frac12<1$. However, we can show that the probability is zero:

Suppose the probability is $\epsilon>0$. We can then define $N=\lceil \frac1\epsilon \rceil$. We can then define the set $M=\{\frac12,\frac1{N+2},\frac1{N+3},...\frac1{2N+2}$. We have that $M\subset (0,1)$ and therefore $P(x=\frac12)=P(x=\frac12\cap x\in M)+ P(x=\frac 12\cap x\not\in M)=P(x=\frac12\cap x\in M)=P(x=\frac12\cap x\in M)= P(x\in M)P(x=\frac12\mid x\in M)\leq P(x=\frac12\mid x\in M)=\frac1{N+1}<\epsilon$. However, this contradicts our assumption that $P(x=\frac12)=\epsilon$, and therefore we must conclude that $P(x=\frac12)=0$


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.