264
правки
Изменения
→Анализ сепараторов
== Анализ сепараторов ==
лемма 6.3
<tex> p = \dfrac{1}{kn}\sum\limits _{i=1}^k r_i </tex>
<tex>\sum\limits_{i=1}^k|R_i\cap S| \ge (p+t)ks </tex>
<tex> \Bigg( \bigg( \dfrac{p}{p+t} \bigg) ^{p+t} \bigg(\dfrac{1-p}{1-p-t}\bigg)^{1-p-t}\Bigg)^{ks} </tex>
<tex> \bigg( \dfrac{p}{p+t} \bigg) ^{p+t} \bigg(\dfrac{1-p}{1-p-t}\bigg)^{1-p-t} < \exp(-2t^2) </tex>
<tex> \bigg( \dfrac{p}{p+t} \bigg) ^{p+t} \bigg(\dfrac{1-p}{1-p-t}\bigg)^{1-p-t} < \bigg(\dfrac{ep}{p+t}\bigg) ^{p+t} </tex>
<tex> \exp(-2t^2ms) \le (em)^{-n^2/s} \le (em)^{-n} </tex>
<tex> \dfrac{1 + e^{-5}}{1 - e^{-5}} \Bigg(\bigg(\dfrac{efn}{2\varepsilon_Fj}\bigg)^{2/f}\dfrac{2ej}{fn}\Bigg)^{\varepsilon_Fj}</tex>
<tex> p(s) \le \dbinom{n}{s} \bigg(\dfrac{ejs}{(\tfrac{1}{2}fs + \varepsilon_Fj)n}\bigg)^{\tfrac{1}{2}fs+\varepsilon_Fj} </tex>
== Доказательство ==
