『確率と計算』 第4章

4. Chernoff and Hoeffding Bounds

4.1 Moment Generating Functions

確率変数 $X$ の moment generating function

\[ M_X(t) = \mathbf{E}[e^{tX}] \]

定理4.1

$X$ を確率変数とし、そのMGFを $M_X(t)$とする。 期待値演算と微分演算の交換をゆるすと、任意の $n>1$について

\[ \mathbf{E}[X^n] = M_X^{(n)}(0) \]

これは $M_X(t)$ の $n$次導関数の $t=0$ のときの値である

4.2 Deriving and Applying Chernoff Bounds

4.3 Better Bounds for Some Special Cases

4.4 Application: Set Balancing

4.5 The Hoeffding Bound

4.6 Application: Packet Routing in Sparse Networks