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"1..., "X""n" là các biến ngẫu nhiên Bernoulli độc lập với xác suất "p" &gt; 1/2. Khi đó, nếu gọi xác suất xảy ra ít nhất "n"/2 sự kiện formula_1 là "P", thì
Chặn Chernoff cho thấy "P" có chặn dưới như sau:
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 formula_4, đượ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" &gt; 0,
Do có thể chọn "t" tùy ý, ta có
Tương tự như vậy,
Do đó,
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 formula_9 là độc lập và có cùng phân bố. Giả sử formula_10, formula_11, và formula_12. Khi đó
và
trong đó
là khoảng cách Kullback-Leibler giữa các biến ngẫu nhiên Bernoulli với tham số formula_16 và formula_17.
Chứng minh.
Chứng minh xuất phát từ bất đẳng thức (+) ở trên. Đặt formula_18. Chọn "a = mq" và thay vào (+), ta có:
Do formula_20, formula_21, ta có
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 formula_25.
Do đó, formula_26.
Vì formula_27, ta có formula_28, nên giá trị của formula_29 là hợp lệ. Sau khi đã giải được formula_29, 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
Để có bất đẳng thức thứ hai, ta xét các biến formula_33, 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
formula_34. Mệnh đề này có thể được chứng minh bằng tính chất lồi của formula_35 và tính chất formula_36. 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 formula_37 cho formula_38 cũng được sử dụng.
Trường hợp sai số tương đối.
Giả sử formula_39 là các biến ngẫu nhiên độc lập nhận giá trị 0 hoặc 1. Giả sử formula_40. Khi đó, nếu đặt formula_41 và formula_42 là giá trị kỳ vọng của formula_43, thì với mọi formula_44
Chứng minh.
Theo (+),
Đẳng thức ở dòng thứ 3 là do formula_47 nhận giá trị formula_48 với xác suất formula_49 và giá trị formula_50 với xác suất formula_51.
Viết lại formula_52 là formula_53 và áp dụng formula_54 (với bất đẳng thức chặt khi formula_55) cho formula_56, ta có
Chọn formula_58 nên formula_59 khi formula_44. Thay giá trị của formula_29 vào biểu thức trên, ta thu được
Đâ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.