$\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.


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$ – Hippalectryon Nov 27 '14 at 0:16
  • $\begingroup$ (that being said, $\frac{1}{52}-\frac{1}{448}\sim0.41443<\frac{1}{52}-\frac{1}{504}\sim0.41468$) $\endgroup$ – Hippalectryon Nov 27 '14 at 0:36
  • $\begingroup$ @Hippalectryon It was a typo, it should be $\displaystyle\frac1{2^{6k+3}}$. $\endgroup$ – Daniel R Nov 27 '14 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 '14 at 8:33

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.