9
$\begingroup$

Prove that there is no probability measure on $\mathbb{N}$ such that for any $n\geq 1$, the probability of the set of multiples of $n$ is $1/n$.

I'm trying to proof this by contradiction, but actually I have no clue so far. Much appreciated if someone can help.

$\endgroup$
2
  • 1
    $\begingroup$ Countably additive measure defined on a $\sigma$-algebra? If so, hint: what is the $\sigma$-algebra generated by the sets mentioned? $\endgroup$
    – GEdgar
    May 8 '20 at 21:28
  • $\begingroup$ See also math.stackexchange.com/questions/1545914. $\endgroup$
    – joriki
    May 8 '20 at 23:04
4
$\begingroup$

Suppose there were such a measure, $\mu$. $\newcommand\of[1]{\left({#1}\right)}\newcommand\N{\Bbb{N}}$

Let $X_n=\{m\in\Bbb{N} : n\mid m\}$ be the set of multiples of $n$. Certainly these sets must be measurable.

First let's deal with a simple case, computing $\mu(X_{p_1}\cup \cdots \cup X_{p_i})$, where the $p_i$ are all distinct primes. Since the primes are all distinct, we get that finite intersections of sets have measure the product of the measures of the individual sets. By PIE, we then get that $$ \mu(X_{p_1}\cup\cdots \cup X_{p_i}) = \sum_{j=1}^i \frac{1}{p_j} - \sum_{j_1<j_2} \frac{1}{p_{j_1}p_{j_2}} + \cdots + (-1)^{i+1} \frac{1}{p_1p_2\cdots p_i}. $$ Now, if we subtract both sides from 1, then the right hand side factors to give $$ 1-\mu(X_{p_1}\cup\cdots \cup X_{p_i}) = \prod_{j=1}^i \of{1-\frac{1}{p_j}}, $$ so $$\mu(X_{p_1}\cup\cdots \cup X_{p_i}) = 1- \prod_{j=1}^i \of{1-\frac{1}{p_j}} =1-\frac{\phi(p_1\cdots p_i)}{p_1\cdots p_i}.$$

Now we make an observation: For any sequence $n_1,\ldots,n_k,\ldots$ containing all but finitely many prime numbers, $$\mu\of{\bigcup_{k\in\N} X_{n_k}} = 1.$$

Proof.

We can assume that the $n_i$ are all prime, since adding extra sets only increases the measure. The result then follows from the previous result combined with the following fact: $$\prod_{p\text{ prime}} \of{1-\frac{1}{p}} = 0.$$

To prove this fact, take $-\log$ of a partial product across primes below some upper bound, $p<N$, which gives $$\sum_{p < N} -\log(1-1/p) = \sum_{p<N}\sum_{n=1}^\infty \frac{1}{p^nn} \ge \sum_{p<N} \frac{1}{p}.$$ The reciprocals of the primes are well known to be a divergent series. (Most proofs of this actually go the other direction and prove that this product diverges, but I'm just trying to get a quick reduction to a well known fact, since this is not the point of my answer). Thus $-\log$ of the partial products go to $\infty$, which implies that the partial products converge to $0$.

This completes the proof of this fact. $\blacksquare$

Now we can show that if all the $X_n$ are measurable and there is a measure with value $\mu(X_n)=1/n$, then for all naturals $m$, $\{m\}$ is measurable and has measure $0$, which contradicts the claim.

Proof.

Induct on $m$ by divisibility. First $\{1\}$ is the complement of $$\bigcup_{p\text{ prime}}X_p,$$ which we just showed has measure $1$, so our base case holds.

For $m>1$, assume the result for all divisors of $m$. Then $$\mu(\{ d : d\mid m\}) = \mu\of{\Bbb{N} \setminus \bigcup_{d\nmid m} X_d}=1-1=0.$$ By the inductive hypothesis, $\mu(\{d:d\mid m\}) = \mu(\{m\})$, so $\mu(\{m\})=0$, as claimed.

Finally, for $m=0$, since $\{0\}=\bigcap_{n\in\N} X_n$, we have $\{0\}$ is measurable and $\mu(\{0\}) < 1/n$ for all $n$, which implies $\mu(\{0\})=0$.

Thus the claim is proved. $\blacksquare$

$\endgroup$
3
$\begingroup$

Suppose our "measure" $\mu$ is countably additive on the sigma-algebra $\Sigma$. And suppose, for $n=1,2,3,\cdots$, the sets $$ A[n] := n\mathbb N = \{0,n,2n,3n,\dots\} $$ belong to $\Sigma$ and $\mu(A[n]) = \frac{1}{n}$.

Note, then $$ \mathbb N \setminus A[n] \in \Sigma,\qquad \mu(\mathbb N \setminus A[n]) = \frac{n-1}{n}. $$ Now if $p_1,p_2,\dots,p_k$ are any $k$ distinct primes, then $$ A[p_1]\cap A[p_2]\cap\dots\cap A[p_k] = A[p_1p_2\dots p_k] \\ \mu\big(A[p_1]\cap A[p_2]\cap\dots\cap A[p_k]\big) =\frac{1}{p_1 p_2\dots p_k} $$

The set of natural numbers not divisible by $p_j$ has measure $1-\frac{1}{p_j}$. By inclusion-exclusion, the set of natural numbers not divisible by any of $p_1,p_2,\dots, p_k$ has measure $$ \left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right) \dots\left(1-\frac{1}{p_k}\right) $$ Let $p_1, p_2, \dots$ be some infinite list of distinct primes. By countable additivity, the set not divisible by any of these primes is $$ \prod_{j=1}^\infty\left(1-\frac{1}{p_j}\right) $$


Now (changing notation) let $p_1, p_2, p_3, \dots$ enumerate all the primes in order. The set of natural numbers divisible by no prime is $Q_0:=\{1\}$ with measure $$ \prod_{j=1}^\infty\left(1-\frac{1}{p_j}\right) = 0 . $$ The set of natural numbers not divisible by any prime except possibly $2$ is $Q_1:=\{1, 2,4\dots\}$ with measure $$ \mu(Q_1) = \prod_{j=2}^\infty\left(1-\frac{1}{p_j}\right) = 0 $$ Given index $J \in \mathbb N$, the set $Q_J$ of natural numbers not divisible by any primes except possibly $p_1,p_2,\dots,p_J$ has measure $$ \mu(Q_J) = \prod_{j=J+1}^\infty\left(1-\frac{1}{p_j}\right) = 0 . $$ Note that $Q_0 \subset Q_1 \subset Q_2 \subset \dots$. But by countable additivity, the union $$ Z:=\bigcup_{J=1}^\infty Q_J $$ has measure $$ \mu(Z) = \lim_{J \to \infty} \mu(Q_J) = 0 . $$ Of course $Z$ is the set of natural numbers which have finitely many prime divisors. So $Z = \mathbb N$, and we get $\mu(\mathbb N) = 0$.

$\endgroup$
3
  • $\begingroup$ Sorry, accidentally skipped part of the proof. Nicely done $\endgroup$ May 8 '20 at 22:50
  • $\begingroup$ Minor nit: looks like you switched 1 for $j$ in $\frac{1}{p_1}$ in a few of the products. $\endgroup$
    – Alex R.
    May 8 '20 at 23:51
  • $\begingroup$ Thanks, fixed.. $\endgroup$
    – GEdgar
    May 9 '20 at 0:06
-3
$\begingroup$

I believe such a probability measure would need to be uniform, so we have two cases: either $P(X=n)=0$ for all $n \in \mathbb{N}$, or $P(X=n)=\epsilon>0$ for all $n \in \mathbb{N}$.

If $P(X=n)=0$, then $1=P(\mathbb{N})=\sum_{n=1}^{\infty} P(X=n)=0$, a contradiction.

If $P(X=n)=\epsilon>0$, then $1=P(\mathbb{N})=\sum_{n=1}^{\infty} P(X=n)=\sum_{n=1}^{\infty} \epsilon=+\infty$, another contradiction.

Therefore, $\mathbb{N}$ cannot have a uniform probability measure.

$\endgroup$
4
  • 5
    $\begingroup$ Now just prove the "I believe" part. $\endgroup$
    – GEdgar
    May 8 '20 at 21:29
  • $\begingroup$ @GEdgar Probability wasn't by strong suit, but I remembered the argument that one cannot define a uniform probability on a countable set. My class never even defined uniform probability, but I took it to mean $P(X=a)$ is constant for all $a$. $\endgroup$
    – JasonM
    May 8 '20 at 21:39
  • 1
    $\begingroup$ @JasonM It's true that there is no uniform probability measure (I'd define it like you did) on the natural numbers. But that's not what the question was about; the condition was not "uniform" but something more complicated. Going from that to uniform is quite a leap. $\endgroup$ May 9 '20 at 9:56
  • $\begingroup$ @JoonasIlmavirta I see, thank you for pointing this out. I didn't realize how much of a leap it was. $\endgroup$
    – JasonM
    May 9 '20 at 22:42

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.