Q. 4.11 - A First Course in Probability

Question

(a) An integer $N$ is to be selected at random from $\left\{1,2,\dots ,(10{)}^3\right\}$ in the sense that each integer has the same probability of being selected. What is the probability that $N$ will be divisible by $3$ ? by $5$ ? by $7$ ? by $15$ ? by $105$ ? How would your answer change if $(10{)}^3$ is replaced by $(10{)}^k$ as $k$ became larger and larger?

(b) An important function in number theory-one whose properties can be shown to be related to what is probably the most important unsolved problem of mathematics, the Riemann hypothesis - is the Möbius function $\mu \left(n\right)$, defined for all positive integral values $n$ as follows: Factor $n$ into its prime factors. If there is a repeated prime factor, as in $12=2·2·3$ or $49=7·7$, then $\mu \left(n\right)$ is defined to equal $0$ . Now let $N$ be chosen at random from $\left\{1,2,\dots (10{)}^k\right\}$, where $k$ is large. Determine $P\left\{\mu \right(N)=0\}$ as $k\to \infty$. Hint: To compute $P\left\{\mu \right(N)\ne 0\}$, use the identity

$\prod _{i=1}^{\infty }\frac{P_i^2-1}{P_i^2}=\left(\frac{3}{4}\right)\left(\frac{8}{9}\right)\left(\frac{24}{25}\right)\left(\frac{48}{49}\right)\cdots =\frac{6}{{\pi }^2}$

where $P_i$ is the $i$ th-smallest prime. (The number $1$ is not a prime.)

Step-by-Step Solution

Answer

1. The ratio of divisible numbers $i$ gets closer and closer on the limit    gets closer and closer $P(N\%i=0)\approx \frac{1}{i}$
2. The third equality is in fact an approximation since we have that $N$ is a very large number, so we can consider all primes, not only that are less or equal to $N$.

Step 1: Given information Part (a)

Each integer has the same probability of being selected.

We have to consider numbers $1,2,\dots ,{10}^3$. Every third number out of them is divisible by $3$ , so there exist $333$ numbers that are divisible by three. Hence

$P(N\%3=0)=\frac{333}{1000}$

Step 2: Calculation Part (a)

Using the similar argument, we have

$P(N\%5=0)=\frac{200}{1000}$

$P(N\%7=0)=\frac{142}{1000}$

$P(N\%15=0)=\frac{66}{1000}$

$P(N\%105=0)=\frac{9}{1000}$

Step 3: Final answer Part (a)

If we apply a limit to these probabilities as $k$ gets better and bigger, we could have

$P(N\%i=0)\to \frac{1}{i}$

since the ratio of divisible numbers  $i$ gets closer and closer on the limit gets closer and closer $1 / i$.

Step 4: Given information Part (b)

$\prod _{i=1}^{\infty }\frac{P_i^2-1}{P_i^2}=\left(\frac{3}{4}\right)\left(\frac{8}{9}\right)\left(\frac{24}{25}\right)\left(\frac{48}{49}\right)\cdots =\frac{6}{{\pi }^2}$

Step 5: Calculation Part (b)

Observe that number $N$ has not double primes in its factorization if and only if it is not divisible by any square of prime number. Hence

$P\left(\mu \right(N)=0)=P\left(N\%p_i^2\ne 0,\text{ for all }{p}_{-}i\text{ less or equal to }N\right)$

$=\prod _{p_i\le N}P\left(N\%p_i^2\ne 0\right)$

$=\prod _{p_i}\left[1-P\left(N\%p_i^2=0\right)\right]$

$=\prod _{p_i}\left(1-\frac{1}{p_i^2}\right)$

$=\prod _{p_i}\frac{p_i^2-1}{p_i^2}=\frac{6}{{\pi }^2}$

where the third equality is in fact an approximation since we have that $N$ is very large number, so we can consider all primes, not only that are less or equal to $N$.

Step 6: Final Answer Part (b)

The third equality is in fact an approximation since we have that $N$ is a very large number, so we can consider all primes, not only that are less or equal to $N.$$N$