====== Algorytmy probabilistyczne - Lista 4. ======

===== Zadanie 2 =====
Prawdopodobieństwo tego, że nie będzie kolizji przy B kulach i n pudełkach:

$\displaystyle (1 - \frac 1 n) \cdot(1 - \frac 2 n) \cdot(1 - \frac 3 n) \cdot\dots\cdot(1 - \frac {B-1} n) = 
\prod^{B-1}_{j=1} (1 - \frac j n)$

$\displaystyle  \prod^{B-1}_{j=1} (1 - \frac j n) \approx
\prod^{B-1}_{j=1} e^{- \frac j n} =
\exp\{-\sum^{B-1}_{j=1}\frac j n\} =
\exp\{-B\cdot(B-1)/2n\}\approx \exp\{-B^2/2n\}$

$\displaystyle \frac 1 2 = e^{-\ln 2}$

Jak 0.5 to prawdopodobieństwo tego, że nie ma kolizji, to 1-0.5 = 0.5 to prawdopodobieństwo, że ta kolizja zajdzie.

$\ln 2 = \frac {B^2} {2n}$

$B = \sqrt { 2n \ln n}$
===== Zadanie 3 =====
$\displaystyle P(X \geq (1 + \delta)\mu) \leq exp\{-\mu \cdot \delta^{2} \cdot \frac 1 3\}$

$\displaystyle P(X \geq (1.5)\frac n 3) \leq exp\{-\frac n 3\cdot \frac 1 4\cdot \frac 1 3 \} = e^{-\frac n {36}}$
===== Zadanie 4 =====
$ \displaystyle P(X \leq (1 - \delta)\mu) \leq exp\{-\mu \cdot \delta^{2} \cdot \frac 1 2 \}$

$\displaystyle P(X \leq (1 - \frac 1 3) \cdot \frac {3n} 4) \leq exp\{-\frac {3n} 4\cdot \frac 1 9\cdot \frac 1 2 \} = e^{-\frac n {24}}$

===== Zadanie 5 =====
$ \displaystyle P(X \leq (1 - \delta)\mu) \leq exp\{-\mu \cdot \delta^{2} \cdot \frac 1 2 \}$

$ \displaystyle P(X \leq (1 - \delta)\frac {3n} 4) \leq
 exp\{-\frac {3n} 8 \cdot \delta^{2}\} =
 \frac 1 {n^5}$

$5 \ln n = \frac {3n} 8 \delta^2$

$\sqrt {\frac {40  \ln n} {3n}}=\delta$

$f(n) =  (1 - \sqrt {\frac {40  \ln n} {3n}})\cdot \frac {3n} 4$


$ \displaystyle P(X \leq (1 - \delta)\frac {3n} 4) \leq
 exp\{-\frac {3n} 8 \cdot \delta^{2}\} =
 \frac 1 {e^{1.5n}}$

$1.5n = \frac {3n} 8 \cdot \delta^{2}$

$4 = \delta^{2}$

$\delta = 2$

Zły bound, bo $\delta$ powinna być $(0,1)$.

===== Zadanie 6 =====
$\displaystyle P(X \geq (1 + \delta)\mu) \leq exp\{-\mu \cdot \delta^{2} \cdot \frac 1 3\}$

$\displaystyle P(X \geq (1+\delta)1) \leq exp\{-\delta^2\cdot \frac 1 3 \}$

Co by tu zrobić, aby z $exp\{-\delta^2\cdot \frac 1 3 \}$ zrobić $\frac 1 {n^2}$. Podstawiamy $\delta = \sqrt {6\log n}$

$\displaystyle P(X \geq (1+\sqrt{6\ln n})1) \leq
exp\{-6\ln n\cdot \frac 1 3 \}= 
\frac 1 {e^{\ln n^2}} = \frac 1 {n^2}$

$ m = 1 + \sqrt{6 \ln n}$

Zły bound, bo $\delta$ powinna być $(0,1)$.