动机
独立指示变量之和记录了重复随机试验中的成功次数。其期望值给出了一个有用的中心位置,但本身并不能说明较大偏离出现的可能性有多小。马尔可夫(Markov)不等式利用期望值为非负随机变量设界;直接把它用于成功次数,得到的结果往往很弱。这里的关键想法是对和的指数函数应用马尔可夫不等式。独立性随后把乘积的期望化为期望的乘积,从而得到随指数下降的尾界。
即使各指示变量的成功概率互不相同,这些界仍然有用。它们是上界,而不是精确概率,并且独立性假设在其中起着实质作用。我们先推导精确的表达式,再给出便于使用的简化形式和具体的样本量估计。
定义
设 X 1 , … , X n X_1,\dots,X_n X 1 , … , X n 为独立的伯努利(Bernoulli)变量,其中 Pr ( X i = 1 ) = p i \Pr(X_i=1)=p_i Pr ( X i = 1 ) = p i ,Pr ( X i = 0 ) = 1 − p i \Pr(X_i=0)=1-p_i Pr ( X i = 0 ) = 1 − p i 。令 X = ∑ i X i X=\sum\limits_i X_i X = i ∑ X i ,μ = E [ X ] = ∑ i p i \mu=\mathbb E[X]=\sum\limits_i p_i μ = E [ X ] = i ∑ p i 。这些变量不必同分布。对于 δ > 0 \delta>0 δ > 0 ,乘性上尾 是事件 X ≥ ( 1 + δ ) μ X\ge(1+\delta)\mu X ≥ ( 1 + δ ) μ ;对于 0 < δ < 1 0<\delta<1 0 < δ < 1 ,乘性下尾 是事件 X ≤ ( 1 − δ ) μ X\le(1-\delta)\mu X ≤ ( 1 − δ ) μ 。尽管 X X X 取整数值,这些阈值仍是实数;不等式按通常的含义理解。
对于 λ ∈ R \lambda\in\mathbb R λ ∈ R ,矩生成函数表达式为 E [ e λ X ] \mathbb E[e^{\lambda X}] E [ e λ X ] 。由于 0 ≤ X ≤ n 0\le X\le n 0 ≤ X ≤ n ,这里所有的期望都是有限的。结果在 μ > 0 \mu>0 μ > 0 时才有意义;若 μ = 0 \mu=0 μ = 0 ,则所有 p i = 0 p_i=0 p i = 0 ,X = 0 X=0 X = 0 几乎必然成立,因此乘性偏离需要另行解释。
定理
对于均值之和为 μ > 0 \mu>0 μ > 0 的独立伯努利变量,以及 δ > 0 \delta>0 δ > 0 ,
Pr ( X ≥ ( 1 + δ ) μ ) ≤ ( e δ ( 1 + δ ) 1 + δ ) μ . \Pr(X\ge(1+\delta)\mu)\le\left(\frac{e^\delta}{(1+\delta)^{1+\delta}}\right)^\mu. Pr ( X ≥ ( 1 + δ ) μ ) ≤ ( ( 1 + δ ) 1 + δ e δ ) μ . 对于 0 < δ < 1 0<\delta<1 0 < δ < 1 ,
Pr ( X ≤ ( 1 − δ ) μ ) ≤ ( e − δ ( 1 − δ ) 1 − δ ) μ . \Pr(X\le(1-\delta)\mu)\le\left(\frac{e^{-\delta}}{(1-\delta)^{1-\delta}}\right)^\mu. Pr ( X ≤ ( 1 − δ ) μ ) ≤ ( ( 1 − δ ) 1 − δ e − δ ) μ .
在相同假设下,对于 0 < δ ≤ 1 0<\delta\le1 0 < δ ≤ 1 ,
Pr ( X ≥ ( 1 + δ ) μ ) ≤ e − μ δ 2 / 3 , Pr ( X ≤ ( 1 − δ ) μ ) ≤ e − μ δ 2 / 2 . \Pr(X\ge(1+\delta)\mu)\le e^{-\mu\delta^2/3},\qquad
\Pr(X\le(1-\delta)\mu)\le e^{-\mu\delta^2/2}. Pr ( X ≥ ( 1 + δ ) μ ) ≤ e − μ δ 2 /3 , Pr ( X ≤ ( 1 − δ ) μ ) ≤ e − μ δ 2 /2 . 因此,对于 0 < δ < 1 0<\delta<1 0 < δ < 1 ,有 Pr ( ∣ X − μ ∣ ≥ δ μ ) ≤ 2 e − μ δ 2 / 3 \Pr(|X-\mu|\ge\delta\mu)\le2e^{-\mu\delta^2/3} Pr ( ∣ X − μ ∣ ≥ δ μ ) ≤ 2 e − μ δ 2 /3 。
证明思路或证明
对任意实数 λ \lambda λ ,由独立性及 1 + y ≤ e y 1+y\le e^y 1 + y ≤ e y 得
E [ e λ X ] = ∏ i ( 1 − p i + p i e λ ) ≤ exp ( μ ( e λ − 1 ) ) . \mathbb E[e^{\lambda X}]=\prod_i(1-p_i+p_i e^\lambda)
\le\exp\bigl(\mu(e^\lambda-1)\bigr). E [ e λ X ] = i ∏ ( 1 − p i + p i e λ ) ≤ exp ( μ ( e λ − 1 ) ) . 对于 λ > 0 \lambda>0 λ > 0 ,对 e λ X e^{\lambda X} e λ X 应用马尔可夫不等式,得
Pr ( X ≥ ( 1 + δ ) μ ) ≤ exp ( μ ( e λ − 1 ) − λ ( 1 + δ ) μ ) . \Pr(X\ge(1+\delta)\mu)\le
\exp\bigl(\mu(e^\lambda-1)-\lambda(1+\delta)\mu\bigr). Pr ( X ≥ ( 1 + δ ) μ ) ≤ exp ( μ ( e λ − 1 ) − λ ( 1 + δ ) μ ) . 取 λ = ln ( 1 + δ ) \lambda=\ln(1+\delta) λ = ln ( 1 + δ ) ,即得上尾表达式。这一选择使上面的指数界最小,因为其指数部分的导数为 μ ( e λ − ( 1 + δ ) ) \mu(e^\lambda-(1+\delta)) μ ( e λ − ( 1 + δ )) ,且二阶导数为正。
对于下尾,取 λ < 0 \lambda<0 λ < 0 。取指数会反转事件的方向:X ≤ ( 1 − δ ) μ X\le(1-\delta)\mu X ≤ ( 1 − δ ) μ 蕴含 e λ X ≥ e λ ( 1 − δ ) μ e^{\lambda X}\ge e^{\lambda(1-\delta)\mu} e λ X ≥ e λ ( 1 − δ ) μ 。再次应用马尔可夫不等式,得到形式相同、但 λ \lambda λ 为负的表达式。取 λ = ln ( 1 − δ ) \lambda=\ln(1-\delta) λ = ln ( 1 − δ ) ,即得所述的下界。这一反转至关重要;若在此步使用正的指数,所界定的将是错误的事件。
对于简化的上界,令 h ( δ ) = ( 1 + δ ) ln ( 1 + δ ) − δ − δ 2 / 3 h(\delta)=(1+\delta)\ln(1+\delta)-\delta-\delta^2/3 h ( δ ) = ( 1 + δ ) ln ( 1 + δ ) − δ − δ 2 /3 。则 h ( 0 ) = h ′ ( 0 ) = 0 h(0)=h'(0)=0 h ( 0 ) = h ′ ( 0 ) = 0 ,而 h ′ ′ ( δ ) = 1 / ( 1 + δ ) − 2 / 3 ≥ − 1 / 6 h''(\delta)=1/(1+\delta)-2/3\ge-1/6 h ′′ ( δ ) = 1/ ( 1 + δ ) − 2/3 ≥ − 1/6 并非处处非负,所以仅凭这一观察不足以证明结论。换一种方式:h ′ ( δ ) = ln ( 1 + δ ) − 2 δ / 3 h'(\delta)=\ln(1+\delta)-2\delta/3 h ′ ( δ ) = ln ( 1 + δ ) − 2 δ /3 在 [ 0 , 1 ] [0,1] [ 0 , 1 ] 上是凹函数,在 0 0 0 处为零,在 1 1 1 处为正(因为 ln 2 > 2 / 3 \ln2>2/3 ln 2 > 2/3 )。凹函数位于其弦的上方,所以 h ′ h' h ′ 在整个区间上 ≥ 0 \ge0 ≥ 0 ,从而 h ≥ 0 h\ge0 h ≥ 0 。为说明 ln 2 > 2 / 3 \ln2>2/3 ln 2 > 2/3 ,在 [ 0 , 1 ] [0,1] [ 0 , 1 ] 上对逐点恒等式 1 / ( 1 + x ) − ( 8 / 9 − 4 x / 9 ) = ( 2 x − 1 ) 2 / [ 9 ( 1 + x ) ] 1/(1+x)-(8/9-4x/9)=(2x-1)^2/[9(1+x)] 1/ ( 1 + x ) − ( 8/9 − 4 x /9 ) = ( 2 x − 1 ) 2 / [ 9 ( 1 + x )] 积分;右边非负,且除一点外为正,而线性项的积分为 2 / 3 2/3 2/3 。
对于下界,令 g ( δ ) = δ + ( 1 − δ ) ln ( 1 − δ ) − δ 2 / 2 g(\delta)=\delta+(1-\delta)\ln(1-\delta)-\delta^2/2 g ( δ ) = δ + ( 1 − δ ) ln ( 1 − δ ) − δ 2 /2 。此时 g ( 0 ) = g ′ ( 0 ) = 0 g(0)=g'(0)=0 g ( 0 ) = g ′ ( 0 ) = 0 ,且当 0 ≤ δ < 1 0\le\delta<1 0 ≤ δ < 1 时 g ′ ′ ( δ ) = δ / ( 1 − δ ) ≥ 0 g''(\delta)=\delta/(1-\delta)\ge0 g ′′ ( δ ) = δ / ( 1 − δ ) ≥ 0 。因此 g ≥ 0 g\ge0 g ≥ 0 ,由此得到下尾的二次型估计。在端点 δ = 1 \delta=1 δ = 1 ,由独立性可得 Pr ( X = 0 ) = ∏ i ( 1 − p i ) ≤ e − μ ≤ e − μ / 2 \Pr(X=0)=\prod\limits_i(1-p_i)\le e^{-\mu}\le e^{-\mu/2} Pr ( X = 0 ) = i ∏ ( 1 − p i ) ≤ e − μ ≤ e − μ /2 ,从而完成所述下尾范围的证明。最后,对上尾事件与下尾事件应用并集界;这两个事件之间无需独立。
证明透视
独立性在何处起作用 各假设用在哪里:独立性恰好只用一次,就是把 E [ e λ X ] \mathbb E[e^{\lambda X}] E [ e λ X ] 写成乘积 ∏ i ( 1 − p i + p i e λ ) \prod\limits_i(1-p_i+p_ie^\lambda) i ∏ ( 1 − p i + p i e λ ) ;马尔可夫不等式只需要非负性。关键一步是取指数,它把和变成积,并把参数 λ \lambda λ 留作事后再优化的自由量。不等式 1 + y ≤ e y 1+y\le e^y 1 + y ≤ e y 再把每个因子化为 e p i ( e λ − 1 ) e^{p_i(e^\lambda-1)} e p i ( e λ − 1 ) ,于是只剩下 μ \mu μ 。对下尾,取负的 λ \lambda λ 使事件的包含方向反转。简化形式靠 [ 0 , 1 ] [0,1] [ 0 , 1 ] 上的微积分比较收尾,所以只在该范围内陈述。没有独立性,分解便不成立,后面“各变量全相同”的反例说明了这一点。
例题详解
将一枚均匀硬币抛 100 100 100 次,令 X X X 为正面的次数。则 μ = 50 \mu=50 μ = 50 。取 δ = 0.4 \delta=0.4 δ = 0.4 ,得 Pr ( X ≥ 70 ) ≤ e − 50 ( 0.4 ) 2 / 3 = e − 8 / 3 ≈ 0.0695 \Pr(X\ge70)\le e^{-50(0.4)^2/3}=e^{-8/3}\approx0.0695 Pr ( X ≥ 70 ) ≤ e − 50 ( 0.4 ) 2 /3 = e − 8/3 ≈ 0.0695 。更精细的表达式为 ( e 0.4 / 1.4 1.4 ) 50 ≈ 0.029 (e^{0.4}/1.4^{1.4})^{50}\approx0.029 ( e 0.4 /1. 4 1.4 ) 50 ≈ 0.029 。这两个数都不是二项分布的精确概率。
设 200 200 200 次独立试验的成功概率均为 0.3 0.3 0.3 ,故 μ = 60 \mu=60 μ = 60 。取 δ = 1 / 2 \delta=1/2 δ = 1/2 ,成功次数至多为 30 30 30 的概率被界定为 e − 60 / 8 = e − 7.5 < 0.00056 e^{-60/8}=e^{-7.5}<0.00056 e − 60/8 = e − 7.5 < 0.00056 。这是对成功次数不足的机会的保证,而不是断言恰好总有 60 60 60 次成功。
设独立的伯努利样本具有共同的未知成功概率 p > 0 p>0 p > 0 ,并以 p ^ = X / n \widehat p=X/n p = X / n 估计它。若已知下界 p ≥ p 0 > 0 p\ge p_0>0 p ≥ p 0 > 0 ,则对于 0 < ε < 1 0<\varepsilon<1 0 < ε < 1 ,由定理得
Pr ( ∣ p ^ − p ∣ ≥ ε p ) ≤ 2 e − n p 0 ε 2 / 3 . \Pr(|\widehat p-p|\ge\varepsilon p)\le2e^{-np_0\varepsilon^2/3}. Pr ( ∣ p − p ∣ ≥ εp ) ≤ 2 e − n p 0 ε 2 /3 . 要使它至多为 α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) ,只需取 n ≥ 3 ln ( 2 / α ) / ( p 0 ε 2 ) n\ge3\ln(2/\alpha)/(p_0\varepsilon^2) n ≥ 3 ln ( 2/ α ) / ( p 0 ε 2 ) 并向上取整为整数。要事先选定这一相对误差的样本量,就需要下界 p 0 p_0 p 0 。
常见错误
反例模式
均值相同并不能取代独立性 设 Y Y Y 为均匀伯努利变量,并取每个 X i = Y X_i=Y X i = Y 。则 μ = n / 2 \mu=n/2 μ = n /2 ,但 Pr ( X = n ) = 1 / 2 \Pr(X=n)=1/2 Pr ( X = n ) = 1/2 。独立变量情形下 δ = 1 \delta=1 δ = 1 的上界却随 n n n 以指数速度趋于零。因此,仅有相同的边缘分布是不够的;这里所有变量是完全相依的。
不要不经换算就把绝对误差代入相对误差的界。事件 ∣ X − μ ∣ ≥ a |X-\mu|\ge a ∣ X − μ ∣ ≥ a 只有在 μ > 0 \mu>0 μ > 0 时才对应于 δ = a / μ \delta=a/\mu δ = a / μ ,而上面便于使用的二次型上界还额外假设 δ ≤ 1 \delta\le1 δ ≤ 1 。对于更大的偏离,应使用第一个定理,或另行证明在自己所述范围内成立的界。大于一的界是有效的,但没有信息量;它总可以与平凡的上界一结合使用。
选择指数参数
证明中的参数并不是随机试验本身的性质。它是我们手头的一个可调旋钮,因为马尔可夫不等式对每个正阈值、每个非负随机变量都成立。对于上尾,我们可以取任意正的 λ \lambda λ ,推出一个有效的界,然后选取使右边最小的那个。使其最小的取值取决于偏离的阈值。如果选了一个方便但并非最优的参数,结果仍然有效,只是可能较弱。
概念视角 分析
把这个界看成速率函数的指数 对 x = ( 1 + δ ) μ x=(1+\delta)\mu x = ( 1 + δ ) μ ,在 λ > 0 \lambda>0 λ > 0 上最好的界是 exp ( − sup λ [ λ x − μ ( e λ − 1 ) ] ) \exp(-\sup\limits_\lambda[\lambda x-\mu(e^\lambda-1)]) exp ( − λ sup [ λ x − μ ( e λ − 1 )]) 。这个上确界是 μ ( e λ − 1 ) \mu(e^\lambda-1) μ ( e λ − 1 ) 的勒让德(Legendre)变换,等于 μ [ ( 1 + δ ) ln ( 1 + δ ) − δ ] \mu[(1+\delta)\ln(1+\delta)-\delta] μ [( 1 + δ ) ln ( 1 + δ ) − δ ] 。所以第一个定理说的是:尾概率至多为 e − I ( x ) e^{-I(x)} e − I ( x ) ,其中 I I I 是均值为 μ \mu μ 的泊松(Poisson)变量的速率函数。
对于下尾,指数的方向同样重要。当 λ \lambda λ 为负时,X X X 增大会使 e λ X e^{\lambda X} e λ X 减小。于是 X X X 的一个较小值被转化为非负变量的一个较大值,而这正是马尔可夫不等式所能控制的事件。两个论证使用的矩界相同,但指数函数的符号与单调性区分了这两个事件。在应用马尔可夫不等式之前先写下事件的包含关系,是防止符号错误的可靠办法。
乘积估计利用了均值,却丢弃了其他信息。具体而言,1 − p i + p i e λ ≤ e p i ( e λ − 1 ) 1-p_i+p_i e^\lambda\le e^{p_i(e^\lambda-1)} 1 − p i + p i e λ ≤ e p i ( e λ − 1 ) 可能相当松,把这些不等式相乘后只保留了 p i p_i p i 之和。若精确的概率已知,可以保留乘积,并对其马尔可夫界做数值优化。对于概率相等的情形,精确分布是二项分布,也可以改为对相应的二项概率求和。这些简单的界之所以有价值,是因为它们给出了无需这些精确计算的通用保证。
设 100 100 100 个计数器中,每一个都是均值为 60 60 60 的独立指示变量之和。独立性只要求在每个计数器内部成立,不同的计数器可以共享随机性。对每个计数器,其降到至多 30 30 30 的下尾概率至多为 e − 7.5 e^{-7.5} e − 7.5 。因此,至少有一个计数器降到这么低的概率至多为 100 e − 7.5 ≈ 0.0553 100e^{-7.5}\approx0.0553 100 e − 7.5 ≈ 0.0553 。即使各计数器之间共享随机性,并集界仍然有效。而在没有证明失败事件相互独立的情况下,把各自的失败概率相乘是不正确的。
乘性估计与加性估计的比较
配套的集中不等式笔记证明了独立伯努利变量的加性 Hoeffding 不等式,并用它来放大多数表决。它对向上偏离 a a a 的界为 e − 2 a 2 / n e^{-2a^2/n} e − 2 a 2 / n ;而这里的乘性界则随均值而变化。两者在各自所述的假设下都成立,但在没有比较实际指数之前,不应宣称其中某一个普遍更好。当成功很稀少时,μ \mu μ 可以远小于 n n n ,乘性估计便能反映这种稀疏性。
例如,设 n = 1000 n=1000 n = 1000 个独立指示变量的成功概率均为 0.01 0.01 0.01 ,故 μ = 10 \mu=10 μ = 10 。要界定至少 20 20 20 次成功的概率,取 δ = 1 \delta=1 δ = 1 。二次型乘性估计给出 e − 10 / 3 ≈ 0.0357 e^{-10/3}\approx0.0357 e − 10/3 ≈ 0.0357 ;取 a = 10 a=10 a = 10 的加性 Hoeffding 估计给出 e − 0.2 ≈ 0.819 e^{-0.2}\approx0.819 e − 0.2 ≈ 0.819 。更精细的乘性公式给出 ( e / 4 ) 10 ≈ 0.0210 (e/4)^{10}\approx0.0210 ( e /4 ) 10 ≈ 0.0210 。三者都是同一事件的上界,人们可以自由使用其中最小的有效界。对于这个概率相等的例子,如有需要,精确概率可以由二项分布计算得到。
不同的分母解释了这一差别。Hoeffding 的界只用到有界独立变量的个数和加性位移。乘性论证则利用成功概率之和来界定矩生成函数。较小的均值提供了额外的信息,但这一优势取决于事件和参数。在另一些参数范围内,Hoeffding 的界可能更精细。比较数值估计是一个数学步骤;不核对其假设和尺度就选用某个有名字的不等式,是不够的。
与均值无关的阈值
有时设计目标给出的是绝对阈值 t t t ,而我们只知道均值的一个上界 m ≥ μ m\ge\mu m ≥ μ 。若 t > m > 0 t>m>0 t > m > 0 ,上尾的证明仍能给出有用的保证,而无需假装 m m m 就是真正的均值。对每个 λ > 0 \lambda>0 λ > 0 ,
Pr ( X ≥ t ) ≤ exp ( μ ( e λ − 1 ) − λ t ) ≤ exp ( m ( e λ − 1 ) − λ t ) , \Pr(X\ge t)\le\exp\bigl(\mu(e^\lambda-1)-\lambda t\bigr)
\le\exp\bigl(m(e^\lambda-1)-\lambda t\bigr), Pr ( X ≥ t ) ≤ exp ( μ ( e λ − 1 ) − λ t ) ≤ exp ( m ( e λ − 1 ) − λ t ) ,
这是因为 e λ − 1 > 0 e^\lambda-1>0 e λ − 1 > 0 。取 λ = ln ( t / m ) \lambda=\ln(t/m) λ = ln ( t / m ) ,得
Pr ( X ≥ t ) ≤ exp ( t − m ) ( m t ) t . \Pr(X\ge t)\le \exp(t-m)\left(\frac{m}{t}\right)^t. Pr ( X ≥ t ) ≤ exp ( t − m ) ( t m ) t .
这一计算在正确的方向上使用了上界。对于下尾,e λ − 1 e^\lambda-1 e λ − 1 的符号为负,若以同样的方式代入 μ \mu μ 的上界,会使相关不等式反向;那里有用的信息是 μ \mu μ 的下界。
作为说明,设独立指示变量的均值之和至多为 5 5 5 ,而不希望出现的阈值为 t = 15 t=15 t = 15 。则上面的结果把该事件的概率界定为 e 10 / 3 15 ≈ 0.00154 e^{10}/3^{15}\approx0.00154 e 10 / 3 15 ≈ 0.00154 。无需断言均值等于五。若上界为零,则每个指示变量的均值都为零,和几乎必然为零,所以正阈值的概率直接就是零。
上界阈值的论证也说明了如何安全地使用经过舍入的数值估计。经过证明的均值上界,可以通过上面的不等式代替实际均值进行上尾计算。而没有确定方向的近似估计则不能自动代入。在代码中,应当记录一个计算出的量是上界还是下界,以及其使用的严格条件。
相对精度与绝对精度
对于样本比例,相对误差与未知的 p p p 成比例。当 p p p 很小时,即使很小的绝对误差也可能是很大的相对误差。例题中的下界 p 0 p_0 p 0 保证了期望成功次数足够多,使乘性估计对所有允许的 p p p 一致地具有信息量。若没有正的下界,则仅由 ε \varepsilon ε 和 α \alpha α 选定的任何有限样本量,都无法对所有正的 p p p 一致地给出上面的相对保证:可以把 p p p 取得如此之小,使得观察不到任何成功的可能性非常大。
要直接看出这一点,固定 n n n 并选取足够小的正数 p p p 。观察不到任何成功的概率为 ( 1 − p ) n (1-p)^n ( 1 − p ) n ,当 p ↓ 0 p\downarrow0 p ↓ 0 时它趋于一。在这个事件上 p ^ = 0 \widehat p=0 p = 0 ,其相对误差为一。因此,对于任何 0 < ε < 1 0<\varepsilon<1 0 < ε < 1 ,该事件都违背了所要求的相对精度。这一论证并不是说在 p p p 已知,或自适应程序带有额外假设时估计是不可能的;它说明的是对所有正概率一致成立的固定样本量所受的限制。
绝对误差的保证则要求对某个固定的 a > 0 a>0 a > 0 有 ∣ p ^ − p ∣ < a |\widehat p-p|<a ∣ p − p ∣ < a 。其适当的样本复杂度可以借助无需已知 p p p 下界的其他集中界来研究。切不可悄悄地以其中一个问题取代另一个:例如,当 p = 0.5 p=0.5 p = 0.5 时 0.01 0.01 0.01 的绝对误差很小,但当 p = 0.001 p=0.001 p = 0.001 时它却是 p p p 的十倍。所估计的量决定了数学应当界定哪一个失败事件。
在算法中解读该界
概率陈述描述的是由指定算法与输入所诱导的分布。它并不指明哪些具体的执行会成功。若算法能够验证自己的输出,验证失败时也许可以重试;此时必须分析重试的代价与独立性。若无法进行这样的验证,尾部估计仍然界定了答案不准确的概率,但并不能使算法事后辨认出该答案。
区分尾界与对期望的保证也很有用。均值为 60 60 60 并不排除结果为 30 30 30 ,而出现这种结果的概率极小,也不意味着它不可能发生。当设计要求失败概率至多为 α \alpha α 时,计算必须表明数值上界不大于 α \alpha α 。例如,若界为 0.0553 0.0553 0.0553 ,那么即使精确概率恰好更小,它也不能证明 0.05 0.05 0.05 的目标。可以增加试验次数,使用更精细的表达式,或者在模型允许时计算精确概率。
所述的上尾与下尾不等式在阈值处包含等号。对于整数值的计数,实数阈值如 27.4 27.4 27.4 在上尾事件中可实现为 X ≥ 28 X\ge28 X ≥ 28 ,在下尾事件中可实现为 X ≤ 27 X\le27 X ≤ 27 。概率不等式按所写的形式仍然有效;若把阈值向错误的方向取整,就改变了事件,并可能得出无效的数值结论。明确指出这一整数事件,对于对照分析界检查代码尤其有用。
可选 独立性究竟用在哪里? 证明只通过指数矩的一个不等式用到独立性。
通往推广的路径
独立性究竟用在哪里? 证明只通过指数矩的一个不等式用到独立性。
独立性只用了一次,就是把 E [ e λ X ] \mathbb E[e^{\lambda X}] E [ e λ X ] 写成 ∏ i E [ e λ X i ] \prod\limits_i\mathbb E[e^{\lambda X_i}] i ∏ E [ e λ X i ] 。若对相应符号的 λ \lambda λ 有 E [ e λ X ] ≤ ∏ i ( 1 − p i + p i e λ ) \mathbb E[e^{\lambda X}]\le\prod\limits_i(1-p_i+p_ie^\lambda) E [ e λ X ] ≤ i ∏ ( 1 − p i + p i e λ ) ,证明其余部分原样适用。已知某些相依的族也满足这个不等式,例如负相关联的指示变量,把球独立投入箱子时“各箱是否为空”的指示变量就属于这一类。验证它是另一个论证,本节没有给出。
关闭
总结
对计数取指数,使独立性能够分解期望,而马尔可夫不等式再把这个期望转化为上尾和下尾的估计。对于均值固定比例的偏离,失败概率随均值以指数速度下降。样本量的应用需要独立性,以及成功概率的一个已知正下界。
练习
快速检查
(对于 n = 80 n=80 n = 80 次独立的均匀硬币抛掷,用二次型界估计至少 60 60 60 次正面的机会。)
先算 μ \mu μ ,再求满足 ( 1 + δ ) μ = 60 (1+\delta)\mu=60 ( 1 + δ ) μ = 60 的 δ \delta δ 。
解答 · 答案 此处 μ = 40 \mu=40 μ = 40 ,δ = 1 / 2 \delta=1/2 δ = 1/2 ,所以概率至多为 e − 40 / 12 = e − 10 / 3 ≈ 0.0357 e^{-40/12}=e^{-10/3}\approx0.0357 e − 40/12 = e − 10/3 ≈ 0.0357 。
快速检查
(设 X X X 计数 100 100 100 次独立试验的成功次数,每次成功概率为 0.2 0.2 0.2 。界定 Pr ( X ≤ 10 ) \Pr(X\le10) Pr ( X ≤ 10 ) 。)
求满足 ( 1 − δ ) μ = 10 (1-\delta)\mu=10 ( 1 − δ ) μ = 10 的 δ \delta δ ,再用下尾界。
解答 · 答案 此处 μ = 20 \mu=20 μ = 20 ,δ = 1 / 2 \delta=1/2 δ = 1/2 ,得 Pr ( X ≤ 10 ) ≤ e − 20 / 8 = e − 2.5 ≈ 0.0821 \Pr(X\le10)\le e^{-20/8}=e^{-2.5}\approx0.0821 Pr ( X ≤ 10 ) ≤ e − 20/8 = e − 2.5 ≈ 0.0821 。
快速检查
(为什么当对所有 i i i 都有 X i = Y X_i=Y X i = Y (其中 Y Y Y 是成功概率为 1 / 2 1/2 1/2 的单个伯努利变量)时,该定理不适用?)
比较 Pr ( X 1 = 1 , X 2 = 1 ) \Pr(X_1=1,X_2=1) Pr ( X 1 = 1 , X 2 = 1 ) 与边际概率之积。
解答 · 答案 这些变量并不独立:例如 Pr ( X 1 = 1 , X 2 = 1 ) = 1 / 2 \Pr(X_1=1,X_2=1)=1/2 Pr ( X 1 = 1 , X 2 = 1 ) = 1/2 ,而它们边缘概率的乘积为 1 / 4 1/4 1/4 。因此,指数期望所需的分解是无效的。
快速检查
(对于相对误差 ε = 1 / 2 \varepsilon=1/2 ε = 1/2 、已知 p ≥ 0.1 p\ge0.1 p ≥ 0.1 及失败目标 α = 0.05 \alpha=0.05 α = 0.05 ,由上面给出的公式给出一个充分的整数样本量。)
计算 3 ln ( 2 / α ) / ( p 0 ε 2 ) 3\ln(2/\alpha)/(p_0\varepsilon^2) 3 ln ( 2/ α ) / ( p 0 ε 2 ) 并向上取整。
解答 · 答案 公式给出 n ≥ 3 ln 40 / ( 0.1 ⋅ 0.25 ) ≈ 442.665 n\ge3\ln40/(0.1\cdot0.25)\approx442.665 n ≥ 3 ln 40/ ( 0.1 ⋅ 0.25 ) ≈ 442.665 ,所以 n = 443 n=443 n = 443 已经足够。这一结果是上界保证,并不声称它是可能的最小样本量。