Chernoff Boundsで遊んでみよう！

確率不等式

179

Markov's Inequality

$X$ を任意の確率変数とし、 $a > 0$ とする。

$Pr (| X | \geq a) \leq \frac{E [X]}{a}$

Chernoff Bounds

Markov's Inequalityより、Chernoff Boundsが得られる。

任意の $t > 0$ について、

$Pr (X \geq a) = Pr (e^{t X} \geq e^{t a}) \leq \frac{E [e^{t X}]}{e^{t a}}$

同様に、任意の $t < 0$ について、
$Pr (X \leq a) = Pr (e^{t X} \geq e^{t a}) \leq \frac{E [e^{t X}]}{e^{t a}}$

Chernoff Boundsの応用

$X_{1}, \dots, X_{n}$ を独立な確率変数とする。
$Pr (X_{i} = 1) = Pr (X_{i} = - 1) = 1 / 2$ とする。

このとき、 $X = \sum_{i = 1}^{n} X_{i}$ とする。

任意の $a > 0$ について、
$Pr (| X | \geq a) \leq 2 e^{- a^{2} / 2 n}$

任意のt>0について、
$E [e^{t X_{i}}] = \frac{1}{2} e^{t} + \frac{1}{2} e^{- t}$

$e^{t}$ と $e^{- t}$ をマクローリン展開をして、

$e^{t} = 1 + t + t^{2} / 2! + \dots + t^{i} / i! + \dots$

$e^{- t} = 1 - t + t^{2} / 2! + \dots + (- 1)^{i} t^{i} / i! + \dots$

$(2 i)! = 2 i (2 i - 1) (2 i - 2) \dots \geq 2^{i} i (i - 1) (i - 2) \dots = 2^{i} (i)!$ に注意して、

$\begin{array}{rcl} E [e^{t X_{i}}] & = & \frac{1}{2} e^{t} + \frac{1}{2} e^{- t} \\ = & \sum_{i \geq 0} t^{2 i} / (2 i)! \\ \leq & \sum_{i \geq 0} (t / 2)^{i} / i! \\ = & e^{t^{2} / 2} \end{array}$

$E [e^{t X}] = E [e^{t \sum_{i} X_{i}}] = \prod_{i = 1}^{n} E [e^{t X_{i}}] \leq e^{n t^{2} / 2}$

それゆえ、
$Pr (X \geq a) = Pr (e^{t X} \geq e^{t} a) \leq E [e^{t} X] / e^{t a} \leq e^{t^{2} n / 2 - t a}$

$t = a / n$ とおけば、
$Pr (X \geq a) \leq e^{- a^{2} / 2 n}$

同様にして、
$Pr (X \leq - a) \leq e^{- a^{2} / 2 n}$

よって、任意の $a > 0$ について、
$Pr (| X | \geq a) \leq 2 e^{- a^{2} / 2 n}$

参考文献

[1]

Michael Mitzenmacher and Eli Upfal, Probability and Computing

投稿日：2024年3月27日

更新日：2024年3月27日

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

hdk105

15082

計測・制御・情報に興味があります. 備忘録として残していきます.

他の人のコメント

コメントはありません。

読み込み中

hdk105

Chernoff Boundsで遊んでみよう！

Markov's Inequality
Chernoff Bounds
Chernoff Boundsの応用
参考文献