Hoeffdingの不等式 (Hoeffding's inequality)

\(n\)個の独立な確率変数\(X_1,\cdots,X_n\)の値域は\([a_i,b_i]\)とする.\(S_n=X_1+\ldots+X_n\) とし,ある正数 \(\epsilon\) について次のHoeffdingの不等式が成立. \[\Pr[S_n - \mathrm{E}[S_n]\ge n\epsilon]\le \exp\biggl(-\frac{2n^2\epsilon^2}{\sum_{i=1}^n(b_i-a_i)^2}\biggr)\] ただし,\(\mathrm{E}[\cdot]\) は期待値確率分布に依存せずに成立する点が便利.

-- しましま

関連項目

リンク集

関連文献


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