$\Omega=\mathbb{N}^*,P(\omega=n)=\dfrac{1}{2^n}$, let $A_k$ be the event $k\mid\omega$.

1) Find $P(A_k)$

2) Let B be the event "$\omega$ is prime", show that $\frac{13}{32}<P(B)<\frac{209}{504}$

One can see easily that $P(A_k)=\dfrac{1}{2^k-1}$

To find $P(B)$, I did the following :

$$\begin{align} P(B)&=\displaystyle\sum_{n\in\mathbb{N}^*}P(\omega=n)P\left(\bigcap_{k=2}^{\lfloor\sqrt{n}\rfloor}\overline{A_k}\right) \\&=\sum_{n\in\mathbb{N}^*}\dfrac{1}{2^n}\left(1-P\left(\bigcup_{k=2}^{‌​\lfloor\sqrt{n}\rfloor}{A_k}\right)\right) \\&\le\sum_{n\in\mathbb{N}^*}\dfrac{1}{2^n}\left(1-\sum_{k=2}^{\lfloor\sqrt{n}\rfloor}P\left(A_k\right)‌​\right) \\&=\sum_{n\in\mathbb{N}^*}\dfrac{1}{2^n}\left(1-\sum_{k=2}^{\lfloor\sqrt{n}\rfloor}\dfrac{1}{2^k-1}\right)\end{align}$$

However, I cannot find a good simplification of that bound.


1 Answer 1


For the lower bound, note that the probability of selecting the first three primes is

$$P\left(\omega \in \{2,3,5\}\right) = \frac14 + \frac18 + \frac1{32}=\frac{13}{32}$$

and the desired probability is obviously higher than that.

To get an upper bound, consider the probability of choosing $2$ or an odd number $> 2$.

$$P\left(\omega \in \{2\} \cup \{2k+1, k \in \Bbb{Z^+} \} \right)= \frac14+\sum_{k=1}^{\infty}\frac1{2^{2k+1}} = \frac14+\frac16=\frac5{12} > \frac{209}{504}$$ Because of the last inequality, this bound is not tight enough. So let's try to remove the first non-primes among our odd numbers, i.e. $\{9,15,21\dots\}$.

$$\begin{align} P\left(\omega \in \{2\} \cup \{2k+1, k \in \Bbb{Z^+} \}\setminus\{6k+3, k \in \Bbb{Z^+} \}\right)&=\frac5{12}-\sum_{k=1}^{\infty}\frac1{2^{6k+3}}\\\\ &=\frac5{12}-\frac1{504}\\\\ &=\frac{209}{504} \end{align}$$

The desired probability is obviously lower than this. Hence, $$\large\boxed{\frac{13}{32} < P\left(\omega \text{ is prime}\right) < \frac{209}{504}}$$

Calculation of one of the sums: $$\begin{align} \sum_{k=1}^\infty \frac1{2^{6k+3}} &= \sum_{k=1}^\infty \frac1{2^3 2^{6k}}\\ &= \frac1{2^3} \sum_{k=1}^\infty \left(\frac1{2^6}\right)^k\\ &= \frac18 \left( \sum_{k=0}^\infty \left(\frac1{64}\right)^k -1\right)\\ &= \frac18 \left( \frac1{1-\frac1{64}} - 1 \right) \\ &= \frac18 \left( \frac{64}{63} - 1 \right) \\ &= \frac18 \left(\frac1{63}\right)\\ &= \frac1{504} \end{align}$$

  • $\begingroup$ $\displaystyle\sum_{k=1}^{\infty}\frac1{2^{3k+6}}=\frac{1}{448}\neq\frac{1}{504}$ $\endgroup$ Nov 27, 2014 at 0:16
  • $\begingroup$ (that being said, $\frac{1}{52}-\frac{1}{448}\sim0.41443<\frac{1}{52}-\frac{1}{504}\sim0.41468$) $\endgroup$ Nov 27, 2014 at 0:36
  • $\begingroup$ @Hippalectryon It was a typo, it should be $\displaystyle\frac1{2^{6k+3}}$. $\endgroup$
    – Daniel R
    Nov 27, 2014 at 8:31
  • $\begingroup$ I noticed the typo right after I added the step-by-step calculation of the sum, but I'll let it stand. $\endgroup$
    – Daniel R
    Nov 27, 2014 at 8:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .