Thực đơn
Chặn Chernoff Bước thứ nhất trong chứng minh của chặn ChernoffChặ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 {\displaystyle X_{1},X_{2},...,X_{n}} , đượ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,
Pr [ X ≥ a ] = Pr [ e t X ≥ e t a ] ≤ E [ e t X ] e t a = ∏ i E [ e t X i ] e t a . {\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ó
Pr [ X ≥ a ] ≤ min t > 0 ∏ i E [ e t X i ] e t a . ( + ) {\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,
Pr [ X ≤ a ] = Pr [ e − t X ≥ e − t a ] {\displaystyle \Pr \left[X\leq a\right]=\Pr \left[e^{-tX}\geq e^{-ta}\right]}Do đó,
Pr [ X ≤ a ] ≤ min t > 0 e t a ∏ i E [ e − t X i ] . ( + + ) {\displaystyle \Pr \left[X\leq a\right]\leq \min _{t>0}e^{ta}\prod _{i}E[e^{-tX_{i}}].\quad (++)}Thực đơn
Chặn Chernoff Bước thứ nhất trong chứng minh của chặn ChernoffLiên quan
Chặn quảng cáo Chặng đua MotoGP Ý 2024 Chặn Chernoff Chặng đua MotoGP Ý Chặng đua MotoGP Đức Chặng đua GP Pháp 2022 Chặng đua GP Ý Chặng đường tôi đi Chặng đua GP Pháp Chặng đua GP Ý 2021Tài liệu tham khảo
WikiPedia: Chặn Chernoff http://books.google.com/books?id=0bAYl6d7hvkC //www.ams.org/mathscinet-getitem?mr=57518 //www.ams.org/mathscinet-getitem?mr=614640 //arxiv.org/abs/quant-ph/0012127 http://www.arxiv.org/abs/1102.2684 //dx.doi.org/10.1016%2F0020-0190(90)90214-I //dx.doi.org/10.1214%2Faoms%2F1177729330 //dx.doi.org/10.1214%2Faop%2F1176994428 //dx.doi.org/10.2307%2F2282952 //www.jstor.org/stable/2236576