3.1 概率工具
以下集中不等式经常会有用. 我们以易于使用的形式而不是最强的形式陈述它们. (注:集中不等式:集中不等式是数学中的一类不等式,描述了一个随机变量是否集中在某个取值附近.例如大数定律说明了一系列独立同分布随机变量的平均值在概率上趋近于它们的数学期望,这表示随着变量数目增大,平均值会集中在数学期望附近.)
定理3.1(加法形式的切尔诺夫界限,又称切尔诺夫不等式)定义 X1,X2,...,XmX_1,X_2 ,...,X_mX1 ,X2 ,...,Xm  为独立随机变量,对任意,iii 有 0≤Xi≤10\leq X_i \leq 10≤Xi ≤1 .定义 S=1m∑i=1mXiS = \frac{1}{