143
правки
Изменения
Неравенство в стиле Чебышева
{{Лемма
|statement=Пусть <tex>G</tex> <tex>d</tex>-регулярный граф со вторым по величине собственным числом <tex>\lambda</tex>. Пусть <tex>F \subseteq E</tex> множество ребер. Вероятность <tex>p</tex> того, что случайный путь, начинающийся со случайного ребра из <tex>F</tex> на <tex>i+1</tex> шаге попадет <tex>F</tex> ограничена <tex>\frac {|F|} {|E|} + \left({\frac {|\lambda|} d}\right)^i</tex>.
|proof=TODO
}}
==Вероятности==
Следующее неравенство в стиле неравенства Чебышева удобно использовать, чтобы показать что для неотрицательной случайной величины <tex>X</tex>, <tex>Pr[X > 0] \approx \mathbb{E}[X]</tex> когда <tex>\mathbb{E}[X] \approx \mathbb{E}[X^2]</tex>.
{{Утверждение
|statement= Для любой неотрицательной случайной величины <tex>X</tex>, <tex>Pr[X>0] \ge \mathbb{E}[X^2] / \mathbb{E}[X]</tex>
|proof=TODO
}}
