✨Chặn Chernoff

Trong lý thuyết xác suất, chặn Chernoff, đặt tên theo Herman Chernoff, cho một chặn trên giảm theo hàm mũ của đuôi phân phối của tổng nhiều biến ngẫu nhiên độc lập. Nó thường mạnh hơn các bất đẳng thức sử dụng mômen bậc nhất hay bậc hai chẳng hạn như bất đẳng thức Markov hay bất đẳng thức Chebyshev.

Nó có liên hệ với bất đẳng thức Bernstein, và bất đẳng thức Hoeffding.

Sau đây là một ví dụ trường hợp đặc biệt của chặn Chernoff. Giả sử X₁,..., X_n là các biến ngẫu nhiên Bernoulli độc lập với xác suất p > 1/2. Khi đó, nếu gọi xác suất xảy ra ít nhất n/2 sự kiện $\{X\_k\; =\; 1\}$ là P, thì

:$P=\backslash sum\backslash limits\_\{i\; =\; \backslash lfloor\; \backslash frac\{n\}\{2\}\; \backslash rfloor\; +\; 1\}^n\; \backslash binom\{n\}\{i\}p^i\; (1\; -\; p)^\{n\; -\; i\}.$

Chặn Chernoff cho thấy P có chặn dưới như sau:

:$P\; \backslash ge\; 1\; -\; \backslash mathrm\{e\}^\{-\; 2n\; \backslash left(\{p\; -\; \backslash frac\{1\}\{2\; \backslash right)^2\}.$

Dưới đây, trường hợp này sẽ được tổng quát hóa theo nhiều hướng khác nhau. Có nhiều phiên bản khác nhau của chặn Chernoff: sai số có thể là sai số tuyệt đối hoặc sai số tương đối so với giá trị kỳ vọng.

Bước thứ nhất trong chứng minh của 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 $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,

: $\backslash Pr\backslash left[X\; \backslash ge\; a\backslash right]\; =\; \backslash Pr\backslash left[e^\{tX\}\; \backslash ge\; e^\{ta\}\backslash right]\; \backslash le\; \backslash frac\{\; \backslash mathbf\{E\}\; \backslash left[e^\{tX\}\; \backslash right]\}\{e^\{ta\; =\; \{\backslash prod\_i\; E[e^\{tX\_i\}]\backslash over\; e^\{ta.$

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

: $\backslash Pr\backslash left[X\; \backslash ge\; a\backslash right]\; \backslash leq\; \backslash min\_\{t>0\}\; \{\backslash prod\_i\; E[e^\{tX\_i\}]\; \backslash over\; e^\{ta.\; \backslash quad\; (+)$

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

: $\backslash Pr\backslash left[X\; \backslash le\; a\backslash right]\; =\; \backslash Pr\backslash left[e^\{-tX\}\; \backslash ge\; e^\{-ta\}\backslash right]$

Do đó,

: $\backslash Pr\backslash left[X\; \backslash le\; a\backslash right]\; \backslash leq\; \backslash min\_\{t>0\}\; e^\{ta\}\; \backslash prod\_i\; E[e^\{-tX\_i\}].\; \backslash quad\; (++)$

Phát biểu và chứng minh

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 $X\_1,\; X\_2,\; \backslash ldots,\; X\_m$ là độc lập và có cùng phân bố. Giả sử $p\; =\; E\; \backslash left\; [X\_i\; \backslash right\; ]$, $X\_i\; \backslash in\; \{0,1\}$, và $\backslash varepsilon\; >\; 0$. Khi đó

::

và :: trong đó ::$D(x||y)\; =\; x\; \backslash log\; \backslash frac\{x\}\{y\}\; +\; (1-x)\; \backslash log\; \backslash 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ố $x$ và $y$.

Chứng minh

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

::$\backslash Pr\backslash left[\; \backslash frac\{1\}\{m\}\; \backslash sum\; X$i \ge q\right] \le \inf{t>0} \frac{E \left[\prod e^{t Xi}\right]}{e^{tmq = \inf{t>0} \left[\frac{ E\left[e^{tX_i} \right] }{e^{tq\right]^m.

Do $\backslash Pr[X\_i\; =\; 1]\; =\; p$, $\backslash Pr[X\_i\; =\; 0]\; =\; (1-p)$, ta có ::$\backslash left[\backslash frac\{\; E\backslash left[e^\{tX\_i\}\; \backslash right]\; \}\{e^\{tq\backslash right]^m\; =\; \backslash left[\backslash frac\{p\; e^t\; +\; (1-p)\}\{e^\{tq\}\; \}\backslash 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 ::

Giải khi đạo hàm ở trên bằng 0 để tính infimum, ta có :: nên $e^t\; =\; (1-p)\backslash left(\backslash frac\{p\}\{q\}-p\backslash right)^\{-1\}$.

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

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

Tóm lại, ta thu được kết quả cần chứng minh như sau ::$\backslash Pr\backslash left[\backslash frac\{1\}\{m\}\backslash sum\; X\_i\; \backslash ge\; p\; +\; \backslash varepsilon\backslash right]\; \backslash le\; e^\{-D(p+\backslash varepsilon\backslash |p)\; m\}.$

Để có bất đẳng thức thứ hai, ta xét các biến $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

$D(p\; +\; x\; \backslash |\; p)\; \backslash geq\; 2\; x^2$. Mệnh đề này có thể được chứng minh bằng tính chất lồi của $D(p+x\backslash |\; p)$ và tính chất $\backslash frac\{d^2\}\{dx^2\}\; D(p+x\backslash |p)\; =\; \backslash 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 $D((1+x)\; p\; \backslash |\; p)\; \backslash geq\; x^2\; p/4$ cho $-1/2\; \backslash leq\; x\; \backslash leq\; 1/2$ cũng được sử dụng.

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

Giả sử $X\_1,\; X\_2,\; \backslash 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ử $\backslash Pr(X\_i\; =\; 1)\; =\; p$i. Khi đó, nếu đặt $X\; =\; \backslash sum${i=1}^n X_i và $\backslash mu$ là giá trị kỳ vọng của $X$, thì với mọi $\backslash delta\; >\; 0$ ::

Chứng minh

Theo (+), ::{t > 0} \frac{\mathbf{E}\left[\prod{i=1}^n\exp(tXi)\right]}{\exp(t(1+\delta)\mu)} \ & = \inf{t > 0} \frac{\prod_{i=1}^n\mathbf{E}[\exp(tXi)]}{\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{align}

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

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

::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{align}

Chọn $t\; =\; \backslash log(1+\backslash delta)$ nên $t\; >\; 0$ khi $\backslash delta\; >\; 0$. Thay giá trị của $t$ vào biểu thức trên, ta thu được ::$\backslash frac\{\backslash exp((e^t-1)\backslash mu)\}\{\backslash exp(t(1+\backslash delta)\backslash mu)\}\; =\; \backslash frac\{\backslash exp((1+\backslash delta\; -\; 1)\backslash mu)\}\{(1+\backslash delta)^\{(1+\backslash delta)\backslash mu\; =\; \backslash left[\backslash frac\{\backslash exp(\backslash delta)\}\{(1+\backslash delta)^\{(1+\backslash delta)\backslash right]^\backslash 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ó ::

Chặn Chernoff cho ma trận

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.