I know there's no uniform distribution for a countably infinite set, but I'm wondering if there's still a way to determine the probability of picking from a subset of a countably infinite set.

For example, what's the probability that I pick an odd number from the set of naturals, assuming I'm picking randomly? Is this even a coherent question? If so, is there a textbook approach to this problem in measure theory/probability theory/probability measure?


  • 14
    $\begingroup$ Definitely not a probability, but in number theory there is the useful concept of natural density (please see Wikipedia). Here the natural density is $1/2$. $\endgroup$ – André Nicolas Sep 12 '15 at 5:11
  • 4
    $\begingroup$ To add detail, let $S$ be a set of natural numbers, and let $f(n)$ be the number of elements of $S$ that are $\le n$. If the limit of $\frac{f(n)}{n}$ exists, that limit is called the natural density or asymptotic density of $S$. There are other related notions of density. $\endgroup$ – André Nicolas Sep 12 '15 at 5:15
  • 3
    $\begingroup$ In my first comment, I mentioned that natural density is not a probability. Little connection, different fields. But it is useful, and nice results have been obtained using related notions. $\endgroup$ – André Nicolas Sep 12 '15 at 5:24
  • 4
    $\begingroup$ A different option than the one advocated above, to give a precise meaning to all this while staying fully in the realm of probability, is to consider, for every $s>1$, the probability measure $\mu_s$ on the set of positive integers defined by $$\mu_s(n)=\frac1{\zeta(s)n^s}$$ for every positive integer $n$. Then one solves the problem with respect to each $\mu_s$, here $$\mu_s(2\mathbb N)=\frac1{2^s}$$ and one considers the limit when $s\to1$, here $$\frac12.$$ An advantage is that ... $\endgroup$ – Did Sep 13 '15 at 6:44
  • 3
    $\begingroup$ ... each $\mu_s$ is a probability measure hence one escapes the paradoxes associated to the "natural" density $d$ defined on some subsets of the natural integers by $$d(A)=\lim\frac1n\# A\cap\{1,2,\ldots,n\},$$ which is defined on a class not even stable by finite intersections. Exercise: When $d(A)$ exists, $d(A)$ is also the limit of $\mu_s(A)$ when $s\to1$ (which is pretty reassuring). $\endgroup$ – Did Sep 13 '15 at 6:44

I'd like to give a semi-philosophical, semi-mathematical defense of the answer 1/2.

The received view in contemporary mathematical probability theory, due to Kolmogorov, is that probability functions are normalized measures: nonnegative, countably additive set functions that are defined on $\sigma$-fields and that assign the sure event measure $1$. This hasn't always been the received view, however.

Bruno DeFinetti argued, famously, that the concept of probability does not mandate countable additivity. His argument is based on the fact, pointed out by you and commenters, that countable additivity rules out the possibility of a uniform distribution on the natural numbers. DeFinetti, a subjectivist, thought there was nothing rationally incoherent about distributing one's credences uniformly over $\mathbb{N}$, and, on these grounds, argued that the countable additivity axiom be weakened. For DeFinetti, probabilities need only be finitely additive.

Working in the tradition of finitely additive probability, it is indeed possible to define a uniform distribution on $\mathbb{N}$. The needed extension results can be found in Rao and Rao's Theory of Charges and Hrbacek and Jech's Introduction to Set Theory. I will sketch a construction here so that this answer has some mathematical content (if needed or requested, I will edit later to include more details).

First, we define the natural density, as in comments above, to be the limit (if it exists) $$ \lim_{n \to \infty} \frac{|A \cap \{1,...,n \}|}{n} = :d(A) $$ for $A \subseteq \mathbb{N}$.

It is not difficult to show

Proposition. (i) $d(\emptyset) = 0$ and $d(\mathbb{N})=1$. (ii) $d(\{n\})=0$ for all $n \in \mathbb{N}$. (iii) The set of numbers divisible by $m$ has natural density $1/m$. (NB: Some of this has been asserted in comments above, but I include it here for completeness.)

We then have the following theorem.

Theorem. There exists a finitely additive probability measure $P$ on $\mathscr{P}(\mathbb{N})$ that extends the natural density $d$.

Proof sketch. The proof relies on the existence of the Frechet ultrafilter $\mathcal{U}$ (the ultrafilter of cofinite sets) on $\mathbb{N}$, and is therefore non-constructive. We say a sequence $(x_{n})$ of real numbers is convergent in $\mathcal{U}$ with limit $x$ and write $x = \lim_{\mathcal{U}}x_{n}$ if for all $\epsilon > 0$ $$\{n: |x_{n} - x| < \epsilon \} \in \mathcal{U}.$$ It can be shown that every real sequence has a unique $\mathcal{U}$-limit. It can also be shown that $$P(A) = \lim_{\mathcal{U}}\frac{|A \cap \{1,...,n \}|}{n}$$ is a finitely additive probability on $\mathscr{P}(\mathbb{N})$ extending $d$. $\square$

By the Theorem and the Proposition, $P$ is a finitely additive probability measure that assigns measure $1/2$ to the set of odd numbers.

Now, you may object that I've changed the subject by invoking merely finitely additive "probabilities". In response, I would remind you that the concept of probability predates the Kolmogorovian theory, and that there are good arguments (due to DeFinetti and other subjectivists) in favor of relaxing countable additivity in some contexts.

  • $\begingroup$ Dear Teacher @Aduh I'm so sorry for this comment..I asked the question mathoverflow for help. But the question was downvoted. I had to delete the question. I really need help. But unfortunately, no one helped. If I ask you for help, can you take a look? If you have a few minutes. Then, I will delete this comment..Thank you very much.. mathoverflow.net/q/298997/123863 $\endgroup$ – Mathematics is Life Apr 30 '18 at 11:40

This is a great question that I as well don't know the answer to.

Also the probability cannot be 1. If the probability to choosing an odd number is 1, then the complement (the probability of choosing an even number is 0). However there are the same number of odd numbers and even numbers, therefore we can use the same proof to show that the probability choosing an even number is 1 leading to a contradiction.

I'm guessing the other approach is first defining our measure. We can use the normalized counting measure (density) as our probability measure on $(\mathbb{N}, 2^\mathbb{N})$ we just need the set to be finite. This measure would imply that the probability is the same for each natural number.

$$\mu(A) = \begin{cases} |A| & \text{if $A$ is finite} \\ \infty & \text{if $A$ is infinite} \end{cases}$$

The only problem that arises is that our set is infinite which will prevent us from having a our counting measure be a probability measure (we cannot divide by infinity). Maybe I'm mistaken, but it seems in order to solve this problem we can then cut up the natural numbers into a set of intervals, and prove it true for each interval. We then can extend it to projection maps.

We write the projection map as: $$\pi_k(\mathbb{N}) = \{k, k+1\} \text{ for any $k\in \mathbb{N}$ }$$ and define the new measure $\mu_k$ on $(\{k, k+1 \}, 2^{\{k, k+1\}})$ as $$\mu_k(A) = \mu(A \cap \pi_k(\mathbb{N})) = \mathbb{P}(A)$$ for any $A \in 2^\mathbb{N}$. Now we solve what happens when we add union two spaces together to our probability. It seems that we must prove the probability is then the average the measures together, i.e., if we union the interval $\{k, k+1 \} \cup \{k+2, k+3\} = B$, then our measure would be $\mu(B) = \frac{\mu_k(B) + \mu_{k+2}(B)}{2}$ assuming we normalize each density in order for it to be a probability measure.

Let $O = \{$ odd natural numbers$\}$. Then we can extend the measure to a limit after noticing $\mu_k(O) = \mu_{k+2}(O) = \dots = \mu_{k+2n}(O) = \frac12$ for any $n\in\mathbb{N}$. Our limit $$\mu(O) = \lim_{n\rightarrow\infty} \frac{\mu_1(O) + \mu_3(O) + \cdots + \mu_{1 + 2n}(O)}{n} $$ $$= \lim_{n\rightarrow\infty}\frac{\frac12 + \frac12 + \dots + \frac12}{n} = \lim_{n\rightarrow\infty} \frac{n\frac12}{n} = 1/2$$

Please correct me if you find any major errors.

  • $\begingroup$ Density is not a measure $\endgroup$ – Thomas Andrews Feb 26 '16 at 11:43
  • $\begingroup$ I suppose you have a good point. Without a weight it doesn't make much sense. $\endgroup$ – TeeJ Lockwood Nov 15 '16 at 17:23

I just realized the more clever solution that doesn't require all of this measure knowledge. Let $O$ be the set of odd natural numbers and $E$ the set of even natural numbers. We then notice that for our probability counting measure I will denote $\mathbb{P}$ on $(\mathbb{N}, 2^\mathbb{N})$ results in $$ \mathbb{P} (O) = \mathbb{P}(E) = \mathbb{P}(O^c).$$ Thus we have $$\mathbb{P}(\mathbb{N}) = \mathbb{P}(O\cup O^c) = \mathbb{P}(O) + \mathbb{P}(O^c) = 2\mathbb{P}(O),$$ on the other hand $$\mathbb{P}(\mathbb{N}) = 1.$$ This results in $\mathbb{P}(O) = \frac12$

  • $\begingroup$ ... "for our probability counting measure..." What "measure" is that? How do you know that $\mathbb P(O)=\mathbb P(E)$? Oh, I see this is in reference to another answer. Math.SE does not present the answers in the order they are written, so it is very hard to figure this out. Jus tack this to the end of your previous answer. $\endgroup$ – Thomas Andrews Feb 26 '16 at 11:41

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.