체르노프 부등식 (Chernoff Inequality)
임의의 확률변수 $ X $ 와 임의의 상수 $ c, t > 0 $ 에 대하여 다음이 성립한다.
$$ P(X \geq c) \leq \dfrac{E(e^{tX})}{e^{tc}} $$
이는 마르코프 부등식으로 증명 가능하다.
$ g(x) = e^{tx} $ 는 가역이며 $ g $ 는 강한 증가함수이다. 따라서 마르코프 부등식에 의해 다음이 성립한다.
$ P(X \geq c) = P(e^{tX} \geq e^{tc} \leq \dfrac{E(e^{tX})}{e^{tc}} $
더 정확하게 증명도 가능하지만, 너무 길기에 생략한다.
체르노프 부등식은 우변을 $ t $ 에 대해 최적화하여 코시-슈바르츠 부등식을 이용하는 것처럼 더 좁은 상계를 얻을 수 있다. 또한 $ X $ 의 적률생성함수(MGF)가 존재한다면 우변 상계값의 분자가 적률생성함수이다. 즉 적률생성함수의 유용한 성질을 이용할 수 있다.
이렇게 체르노프 부등식을 이용하여 유도된 상계를 체르노프 유계(Chernoff bound)라고도 하고, 혹은 체르노프 부등식 자체를 체르노프 유계라고도 한다.
