\(|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の不等式という.
-- しましま