✨Bất đẳng thức Hoeffding

Trong lý thuyết xác suất, bất đẳng thức Hoeffding cho một chặn trên của xác suất một tổng các biến ngẫu nhiên sai lệch với giá trị kỳ vọng. Bất đẳng thức Hoeffding được chứng minh bởi Wassily Hoeffding.

Giả sử

:$X\_1,\; \backslash dots,\; X\_n\; !$

là các biến ngẫu nhiên độc lập. Giả sử $X\_i$ gần như chắc chắn bị chặn; nghĩa là, với mọi $1\; \backslash leq\; i\; \backslash leq\; n$ ta có

:$\backslash Pr(X\_i\; \backslash in\; [a\_i,\; b\_i])\; =\; 1.\; !$

Giá trị trung bình thực nghiệm của các biến đó là

:$\backslash overline\{X\}\; =\; (X\_1\; +\; \backslash cdots\; +\; X\_n)/n\; !$

Ta có các bất đẳng thức sau (Hoeffding 1963, định lý 2 ):

:$\backslash Pr(\backslash overline\{X\}\; -\; \backslash mathrm\{E\}[\backslash overline\{X\}]\; \backslash geq\; t)\; \backslash leq\; \backslash exp\; \backslash left(-\; \backslash frac\{2t^2n^2\}\{\backslash sum\_\{i=1\}^n\; (b\_i\; -\; a$i)^2} \right),! :$\backslash Pr(|\backslash overline\{X\}\; -\; \backslash mathrm\{E\}[\backslash overline\{X\}]|\; \backslash geq\; t)\; \backslash leq\; 2\backslash exp\; \backslash left(-\; \backslash frac\{2t^2n^2\}\{\backslash sum${i=1}^n (b_i - a_i)^2} \right),!

cho mọi giá trị t dương. Ở đây $\backslash mathrm\{E\}[\backslash overline\{X\}]$ là giá trị kỳ vọng của $\backslash overline\{X\}$.

Các bất đẳng thức này là trường hợp đặc biệt của bất đẳng thức Azuma–Hoeffding và của một bất đẳng thức tổng quát hơn nữa là bất đẳng thức Bernstein trong lý thuyết xác suất, chứng minh bởi Sergei Bernstein năm 1923. Chúng cũng là trường hợp đặc biệt của bất đẳng thức McDiarmid.

Các bất đẳng thức này cũng đúng khi $X\_i$ được chọn không thay thế; trong trường hợp này chúng không còn độc lập. Bài báo của Hoeffding cũng chứa một chứng minh của mệnh đề này. Bài báo của Serfling chứa một chặn trên chặt hơn một chút trong trường hợp lấy mẫu không thay thế.