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}
\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}}
\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}}
\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).
\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).