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ử X1,..., Xn 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  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 , được chứng minh bằng cách xem xét phân bố của etX 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,

 

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  là độc lập và có cùng phân bố. Giả sử , , và . 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ố  và .

Chứng minh 

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

Do , , 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 .

Do đó, .

Vì , ta có , nên giá trị của   là hợp lệ. Sau khi đã giải được , 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 , 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
. Mệnh đề này có thể được chứng minh bằng  tính chất lồi của  và tính chất . 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  cho  cũng được sử dụng.

Trường hợp sai số tương đối 
Giả sử  là các biến ngẫu nhiên độc lập nhận giá trị 0 hoặc 1. Giả sử . Khi đó, nếu đặt  và  là giá trị kỳ vọng của , thì với mọi

Chứng minh 

Theo (+),

Đẳng thức ở dòng thứ 3 là do  nhận giá trị  với xác suất  và giá trị  với xác suất .

Viết lại  là  và áp dụng  (với bất đẳng thức chặt khi ) cho , ta có

Chọn  nên  khi . Thay giá trị của  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.

Xem thêm
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

Ghi chú

Tham khảo
 
 
 
 
 
 
 

Bất đẳng thức xác suất
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ử X1 , ... , Xn là các biến ngẫu nhiên Bernoulli độc lập với xác suất p >2 . Khi đó , nếu gọi xác suất xảy ra ít nhất n/2 sự kiện 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 , được chứng minh bằng cách xem xét phân bố của etX 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 > 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 là độc lập và có cùng phân bố . Giả sử , , và \. 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ố và \. Chứng minh Chứng minh xuất phát từ bất đẳng thức (+) ở trên . Đặt \. Chọn a = mq và thay vào (+) , ta có : Do , , 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để tính infimum , ta có nên \. Do đó , \. Vì , ta có , nên giá trị của là hợp lệ . Sau khi đã giải được , 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 , 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 . Mệnh đề này có thể được chứng minh bằng tính chất lồi của và tính chất \. 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 cho cũng được sử dụng . Trường hợp sai số tương đối Giả sử là các biến ngẫu nhiên độc lập nhận giá trịhoặc Giả sử \. Khi đó , nếu đặt và là giá trị kỳ vọng của , thì với mọi Chứng minh Theo (+) , Đẳng thức ở dòng thứlà do nhận giá trị với xác suất và giá trị với xác suất \. Viết lại là và áp dụng (với bất đẳng thức chặt khi ) cho , ta có Chọn nên khi \. Thay giá trị của 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 . Xem thêm 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 Ghi chú Tham khảo Bất đẳng thức xác suất