Xem mã nguồn của Bất đẳng thức Azuma

{{chú thích trong bài}} 
Trong [[lý thuyết xác suất]], '''bất đẳng thức Azuma–Hoeffding''' (đặt tên theo [[Kazuoki Azuma]] và [[Wassily Hoeffding]]) là một bất đẳng thức về sự tập trung của giá trị một [[martingale (lý thuyết xác suất)|martingale]] có gia số bị chặn.

Giả sử { ''X''<sub>''k''</sub>: ''k'' = 0, 1, 2, 3,... } là một [[Martingale (lý thuyết xác suất)|martingale]] (hoặc [[Martingale (lý thuyết xác suất)|super-martingale]]) và

:<math>|X_k - X_{k-1}| < c_k, \, </math>

[[gần như chắc chắn]]. Khi đó, với mọi số nguyên dương ''N'' và mọi [[số thực]] dương ''t'',

:<math>P(X_N - X_0 \geq t) \leq \exp\left ({-t^2 \over 2 \sum_{k=1}^N c_k^2} \right). </math>

Nếu ''X'' là một martingale, thì bằng cách áp dụng bất đẳng thức Azuma cho cả martingale ''-X'' và ''X'' ta có bất đẳng thức sau:

:<math>P(|X_N - X_0| \geq t) \leq 2\exp\left ({-t^2 \over 2 \sum_{k=1}^N c_k^2} \right). </math>

Bất đẳng thức Azuma áp dụng cho [[martingale Doob]] chính là [[phương pháp gia số bị chặn]] thường được dùng để phân tích [[thuật toán ngẫu nhiên]].

==Một ví dụ sử dụng bất đẳng thức Azuma==
Giả sử ''F''<sub>''i''</sub> là một dãy những lần tung đồng xu công bằng độc lập nhau (nghĩa là ''F''<sub>''i''</sub> có cùng xác suất nhận giá trị -1 cũng như 1 và độc lập với những giá trị ''F''<sub>''j''</sub> khác).  Đặt <math>X_i = \sum_{j=1}^i F_j</math> cho ta một [[Martingale (lý thuyết xác suất)|martingale]] với |''X''<sub>''k''</sub>&nbsp;&minus;&nbsp;''X''<sub>''k''&minus;1</sub>|&nbsp;≤&nbsp;2. Nói cách khác, <math>X_i</math> chính là chênh lệch giữa số lần nhận giá trị 1 so với số lần nhận giá trị -1 trong ''i'' lần tung đầu tiên. Áp dụng bất đẳng thức Azuma, ta có

:<math> \Pr[X_N > t] \leq \exp\left(\frac{-t^2}{8 N}\right).</math>

Ví dụ, nếu chọn ''t'' tỉ lệ với ''N'', ta nhận thấy giá trị ''lớn nhất'' có thể của ''X''<sub>''N''</sub> là tỉ lệ với ''N'', và ''xác suất'' nó tỉ lệ với ''N'' giảm với tỉ lệ lũy thừa theo&nbsp;''N''.

==Ghi chú==

Một [[Bất đẳng thức Bernstein (lý thuyết xác suất)|bất đẳng thức tương tự]] sử dụng giả thiết yếu hơn được chứng minh bởi {{harvtxt|Bernstein|1937}}.

Hoeffding chứng minh bất đẳng thức này cho các biến độc lập thay vì cho gia số của martingale, và cũng đã nhận thấy rằng chỉ với một vài thay đổi nhỏ là chứng minh cũng áp dụng cho trường hợp martingale (xem trang 18 trong {{harvtxt|Hoeffding|1963}}).

==Xem thêm==
* [[Martingale Doob#Bất đẳng thức McDiarmid|Bất đẳng thức McDiarmid]]
* [[Bất đẳng thức Markov]]
* [[Bất đẳng thức Hoeffding]]
* [[Bất đẳng thức Chebyshev]]
* [[Bất đẳng thức Bernstein (lý thuyết xác suất)]]
* [[Bất đẳng thức Bennett]]

==Tham khảo==

* {{chú thích sách|first1=N. |last1=Alon |first2= J. |last2=Spencer|title=The Probabilistic Method|publisher= Wiley|location=New York|year= 1992}}
* {{chú thích tạp chí|doi=10.2748/tmj/1178243286|first=K. |last=Azuma|title=Weighted Sums of Certain Dependent Random Variables|journal=Tôhoku Math. Journ.|volume=19|pages= 357–367 |year=1967}}
* {{chú thích tạp chí| last=Bernstein | first=Sergei N. | authorlink=Sergei Natanovich Bernstein | year=1937 | trans_title=On certain modifications of Chebyshev's inequality|language=tiếng Nga| journal=Doklady Akademii Nauk SSSR | volume=17 | issue=6 | pages=275–277}} (quyển 4, mục 22 trong tuyển tập)
* {{chú thích sách| first=C. |last=McDiarmid|chapter= On the method of bounded differences|title=Surveys in Combinatorics|series= London Math. Soc. Lectures Notes 141|publisher= Cambridge Univ. Press|location= Cambridge |year=1989|pages=148–188}}
* {{chú thích tạp chí|doi=10.2307/2282952|first1=W. |last1=Hoeffding|title=Probability inequalities for sums of bounded random variables|journal=J. Amer. Statist. Assoc.|volume=58|issue=301|pages= 13–30|year= 1963|mr=  0144363  }}
* {{chú thích tạp chí|first1=A. P. |last1=Godbole |first2= P. |last2=Hitczenko|title=Beyond the method of bounded differences|journal=DIMACS Ser. Discrete Math. Theoret. Comput. Sci.|volume= 41|pages=43–58|year= 1998 |mr=1630408  }}

==Tham khảo==
{{tham khảo}}

[[Thể loại:Bất đẳng thức xác suất]]
[[Thể loại:Lý thuyết martingale]]