chernoff_bound.md

Chernoff Bound

ステートメント

$X$を確率変数とする，任意の$t>0$と$\lambda \in \mathbb{R}$に対して $$ \mathbb{P}\{ |X - \mathbb{E}X| \geq t\} \leq e^{\psi_{X}(\lambda)-\lambda t}. $$ ここで，$\psi_{X}$は$X$の生成母関数の対数，$\psi_{X}(\lambda):=\log \mathbb{E}\left[e^{\lambda X} \right]$．

証明の概要

Markovの不等式から証明できる

コメント

この不等式により，期待値周りの確率集中は生成母関数の対数$\psi_X$を評価することに帰着される

出典

Boucheron et al. Concentration inequalities: A Nonasymptotic Theory of Independence (2013)