Chernoff限界 (Chernoff bound)

\(|X_i|\le1,\;\mathrm{E}[X_i]=0,\;i=1,\ldots,n\) なる確率変数 \(X_1,\ldots,X_n\) について \(X=\sum_{i=1}^n X_i,\;\mathrm{Var}[X]=\sigma^2\) とする. \(0\le\lambda\le2\sigma\) を満たす \(\lambda\) について次式が成立 \[\Pr[|X|\ge\lambda\sigma]\le2\exp[-\lambda^2/4]\] これをChernoff限界またはChernoffの不等式という.

-- しましま

関連項目

リンク集

関連文献


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2010-02-11 (木) 16:10:55 (2494d)