Chặn Chernoff

Chặn Chernoff cho biến ngẫu nhiên X là tổng của n biến ngẫu nhiên độc lập ${\displaystyle X_{1},X_{2},...,X_{n}}$ , được chứng minh bằng cách xem xét phân bố của e^tX với giá trị thích hợp của t. Phương pháp này được áp dụng đầu tiên bởi Sergei Bernstein để chứng minh bất đẳng thức Bernstein.

Theo bất đẳng thức Markov và tính chất độc lập, ta có bất đẳng thức sau:

Với mọi t > 0,

${\displaystyle \Pr \left[X\geq a\right]=\Pr \left[e^{tX}\geq e^{ta}\right]\leq {\frac {\mathbf {E} \left[e^{tX}\right]}{e^{ta}}}={\prod _{i}E[e^{tX_{i}}] \over e^{ta}}.}$

Do có thể chọn t tùy ý, ta có

${\displaystyle \Pr \left[X\geq a\right]\leq \min _{t>0}{\prod _{i}E[e^{tX_{i}}] \over e^{ta}}.\quad (+)}$

Tương tự như vậy,

${\displaystyle \Pr \left[X\leq a\right]=\Pr \left[e^{-tX}\geq e^{-ta}\right]}$

Do đó,

${\displaystyle \Pr \left[X\leq a\right]\leq \min _{t>0}e^{ta}\prod _{i}E[e^{-tX_{i}}].\quad (++)}$

Trường hợp sai số tuyệt đối

Định lý sau đây được chứng minh bởi Wassily Hoeffding và được gọi là định lý Chernoff-Hoeffding.

Giả sử các biến ${\displaystyle X_{1},X_{2},\ldots ,X_{m}}$ là độc lập và có cùng phân bố. Giả sử ${\displaystyle p=E\left[X_{i}\right]}$ , ${\displaystyle X_{i}\in \{0,1\}}$ , và ${\displaystyle \varepsilon >0}$ . Khi đó

${\displaystyle {\begin{aligned}&\Pr \left[{\frac {1}{m}}\sum X_{i}\geq p+\varepsilon \right]\\&\qquad \leq \left({\left({\frac {p}{p+\varepsilon }}\right)}^{p+\varepsilon }{\left({\frac {1-p}{1-p-\varepsilon }}\right)}^{1-p-\varepsilon }\right)^{m}=e^{-D(p+\varepsilon \|p)m}\end{aligned}}}$

và

${\displaystyle {\begin{aligned}&\Pr \left[{\frac {1}{m}}\sum X_{i}\leq p-\varepsilon \right]\\&\qquad \leq \left({\left({\frac {p}{p-\varepsilon }}\right)}^{p-\varepsilon }{\left({\frac {1-p}{1-p+\varepsilon }}\right)}^{1-p+\varepsilon }\right)^{m}=e^{-D(p-\varepsilon \|p)m},\end{aligned}}}$

trong đó

${\displaystyle D(x||y)=x\log {\frac {x}{y}}+(1-x)\log {\frac {1-x}{1-y}}}$

là khoảng cách Kullback-Leibler giữa các biến ngẫu nhiên Bernoulli với tham số ${\displaystyle x}$ và ${\displaystyle y}$ .

Chứng minh

Chứng minh xuất phát từ bất đẳng thức (+) ở trên. Đặt ${\displaystyle q=p+\varepsilon }$ . Chọn a = mq và thay vào (+), ta có:

${\displaystyle \Pr \left[{\frac {1}{m}}\sum X_{i}\geq q\right]\leq \inf _{t>0}{\frac {E\left[\prod e^{tX_{i}}\right]}{e^{tmq}}}=\inf _{t>0}\left[{\frac {E\left[e^{tX_{i}}\right]}{e^{tq}}}\right]^{m}.}$

Do ${\displaystyle \Pr[X_{i}=1]=p}$ , ${\displaystyle \Pr[X_{i}=0]=(1-p)}$ , ta có

${\displaystyle \left[{\frac {E\left[e^{tX_{i}}\right]}{e^{tq}}}\right]^{m}=\left[{\frac {pe^{t}+(1-p)}{e^{tq}}}\right]^{m}=[pe^{(1-q)t}+(1-p)e^{-qt}]^{m}.}$

Bằng cách lấy lôgarit và tính đạo hàm, ta có thể tính được giá trị infimum ở trên thông qua đạo hàm sau

${\displaystyle {\begin{aligned}&{\frac {d}{dt}}\log(pe^{(1-q)t}+(1-p)e^{-qt})\\&\qquad ={\frac {1}{pe^{(1-q)t}+(1-p)e^{-qt}}}((1-q)pe^{(1-q)t}-q(1-p)e^{-qt})\\&\qquad =-q+{\frac {pe^{(1-q)t}}{pe^{(1-q)t}+(1-p)e^{-qt}}}\end{aligned}}}$

Giải khi đạo hàm ở trên bằng 0 để tính infimum, ta có

${\displaystyle {\begin{aligned}q&={\frac {pe^{(1-q)t}}{pe^{(1-q)t}+(1-p)e^{-qt}}}={\frac {pe^{(1-q)t}}{e^{-qt}(pe^{t}+(1-p))}}\\pe^{(1-q)t}&=pe^{-qt}e^{t}=qe^{-qt}(pe^{t}+1-p)\\{\frac {p}{q}}e^{t}&=pe^{t}+1-p\end{aligned}}}$

nên ${\displaystyle e^{t}=(1-p)\left({\frac {p}{q}}-p\right)^{-1}}$ .

Do đó, ${\displaystyle t=\log \left({\frac {(1-p)q}{(1-q)p}}\right)}$ .

Vì ${\displaystyle q=p+\varepsilon >p}$ , ta có ${\displaystyle t>0}$ , nên giá trị của ${\displaystyle t}$ là hợp lệ. Sau khi đã giải được ${\displaystyle t}$ , ta thay giá trị này vào phương trình ở trên và thu được

${\displaystyle {\begin{aligned}&\log(pe^{(1-q)t}+(1-p)e^{-qt})=\log[e^{-qt}(1-p+pe^{t})]\\&\qquad =\log \left[e^{-q\log \left({\frac {(1-p)q}{(1-q)p}}\right)}\right]+\log \left[1-p+pe^{\log \left({\frac {1-p}{1-q}}\right)}e^{\log {\frac {q}{p}}}\right]\\&\qquad =-q\log {\frac {1-p}{1-q}}-q\log {\frac {q}{p}}+\log \left[1-p+p\left({\frac {1-p}{1-q}}\right){\frac {q}{p}}\right]\\&\qquad =-q\log {\frac {1-p}{1-q}}-q\log {\frac {q}{p}}+\log \left[{\frac {(1-p)(1-q)}{1-q}}+{\frac {(1-p)q}{1-q}}\right]\\&\qquad =-q\log {\frac {q}{p}}+(1-q)\log {\frac {1-p}{1-q}}=-D(q\|p).\end{aligned}}}$

Tóm lại, ta thu được kết quả cần chứng minh như sau

${\displaystyle \Pr \left[{\frac {1}{m}}\sum X_{i}\geq p+\varepsilon \right]\leq e^{-D(p+\varepsilon \|p)m}.}$

Để có bất đẳng thức thứ hai, ta xét các biến ${\displaystyle Y_{i}=1-X_{i}}$ , và áp dụng chứng minh tương tự.

Chặn đơn giản hơn

Có thể thu được một chặn đơn giản hơn bằng cách áp dụng${\displaystyle D(p+x\|p)\geq 2x^{2}}$ . Mệnh đề này có thể được chứng minh bằng tính chất lồi của ${\displaystyle D(p+x\|p)}$ và tính chất ${\displaystyle {\frac {d^{2}}{dx^{2}}}D(p+x\|p)={\frac {1}{(p+x)(1-p-x)}}}$ . Chặn này là một trường hợp đặc biệt của bất đẳng thức Hoeffding.Đôi khi chặn ${\displaystyle D((1+x)p\|p)\geq x^{2}p/4}$ cho ${\displaystyle -1/2\leq x\leq 1/2}$ cũng được sử dụng.

Trường hợp sai số tương đối

Giả sử ${\displaystyle X_{1},X_{2},\ldots ,X_{n}}$ là các biến ngẫu nhiên độc lập nhận giá trị 0 hoặc 1. Giả sử ${\displaystyle \Pr(X_{i}=1)=p_{i}}$ . Khi đó, nếu đặt ${\displaystyle X=\sum _{i=1}^{n}X_{i}}$ và ${\displaystyle \mu }$ là giá trị kỳ vọng của ${\displaystyle X}$ , thì với mọi ${\displaystyle \delta >0}$

${\displaystyle \Pr \left[X>(1+\delta )\mu \right]<\left({\frac {e^{\delta }}{(1+\delta )^{(1+\delta )}}}\right)^{\mu }.}$

Chứng minh

Theo (+),

${\displaystyle {\begin{aligned}\Pr[X>(1+\delta )\mu )]&\leq \inf _{t>0}{\frac {\mathbf {E} \left[\prod _{i=1}^{n}\exp(tX_{i})\right]}{\exp(t(1+\delta )\mu )}}\\&=\inf _{t>0}{\frac {\prod _{i=1}^{n}\mathbf {E} [\exp(tX_{i})]}{\exp(t(1+\delta )\mu )}}\\&=\inf _{t>0}{\frac {\prod _{i=1}^{n}\left[p_{i}\exp(t)+(1-p_{i})\right]}{\exp(t(1+\delta )\mu )}}\end{aligned}}}$

Đẳng thức ở dòng thứ 3 là do ${\displaystyle e^{tX_{i}}}$ nhận giá trị ${\displaystyle e^{t}}$ với xác suất ${\displaystyle p_{i}}$ và giá trị ${\displaystyle 1}$ với xác suất ${\displaystyle 1-p_{i}}$ .

Viết lại ${\displaystyle p_{i}e^{t}+(1-p_{i})}$ là ${\displaystyle p_{i}(e^{t}-1)+1}$ và áp dụng ${\displaystyle 1+x\leq e^{x}}$ (với bất đẳng thức chặt khi ${\displaystyle x>0}$ ) cho ${\displaystyle x=p_{i}(e^{t}-1)}$ , ta có

${\displaystyle {\begin{aligned}&\Pr[X>(1+\delta )\mu ]<{\frac {\prod _{i=1}^{n}\exp(p_{i}(e^{t}-1))}{\exp(t(1+\delta )\mu )}}\\&\qquad ={\frac {\exp \left((e^{t}-1)\sum _{i=1}^{n}p_{i}\right)}{\exp(t(1+\delta )\mu )}}={\frac {\exp((e^{t}-1)\mu )}{\exp(t(1+\delta )\mu )}}.\end{aligned}}}$

Chọn ${\displaystyle t=\log(1+\delta )}$ nên ${\displaystyle t>0}$ khi ${\displaystyle \delta >0}$ . Thay giá trị của ${\displaystyle t}$ vào biểu thức trên, ta thu được

${\displaystyle {\frac {\exp((e^{t}-1)\mu )}{\exp(t(1+\delta )\mu )}}={\frac {\exp((1+\delta -1)\mu )}{(1+\delta )^{(1+\delta )\mu }}}=\left[{\frac {\exp(\delta )}{(1+\delta )^{(1+\delta )}}}\right]^{\mu }}$

Đây chính là bất đẳng thức cần chứng minh. Bằng một chứng minh tương tự, ta có

${\displaystyle \Pr[X<(1-\delta )\mu ]<\exp(-\mu \delta ^{2}/2).}$

Rudolf Ahlswede và Andreas Winter đã chứng minh một phiên bản của chặn Chernoff cho các biến ngẫu nhiên nhận giá trị ma trận.^[1]

• Bất đẳng thức Bernstein (lý thuyết xác suất)
• Bất đẳng thức Hoeffding
• Bất đẳng thức Markov
• Bất đẳng thức Chebyshev

• Ahlswede, R.; Winter, A. (2003). “Strong Converse for Identification via Quantum Channels”. IEEE Transactions on Information Theory. 48 (3): 569–579. arXiv:quant-ph/0012127.
• Chernoff, H. (1952). “A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations”. Annals of Mathematical Statistics. 23 (4): 493–507. doi:10.1214/aoms/1177729330. JSTOR 2236576. MR 0057518. Zbl 0048.11804.
• Hoeffding, W. (1963). “Probability Inequalities for Sums of Bounded Random Variables”. Journal of the American Statistical Association. 58 (301): 13–30. doi:10.2307/2282952. JSTOR 2282952.
• Chernoff, H. (1981). “A Note on an Inequality Involving the Normal Distribution”. The Annals of Probability. 9 (3): 533. doi:10.1214/aop/1176994428. JSTOR 2243541. MR 0614640. Zbl 0457.60014.
• Hagerup, T. (1990). “A guided tour of Chernoff bounds”. Information Processing Letters. 33 (6): 305. doi:10.1016/0020-0190(90)90214-I.
• Mitzenmacher, M.; Upfal, E. (2005). Probability and Computing: Randomized Algorithms and Probabilistic Analysis. ISBN 9780521835404.
• Nielsen, F. (2011). "Chernoff information of exponential families". arΧiv:1102.2684 [cs.IT].