Bất đẳng thức Azuma

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

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

Giả sử { Xk: k = 0, 1, 2, 3,... } là một martingale (hoặc super-martingale) và

|X_k - X_{k-1}| < c_k, \,

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,

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

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

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

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[sửa | sửa mã nguồn]

Giả sử Fi là một dãy những lần tung đồng xu công bằng độc lập nhau (nghĩa là Fi 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ị Fj khác). Đặt X_i = \sum_{j=1}^i F_j cho ta một martingale với |Xk − Xk−1| ≤ 2. Nói cách khác, X_i 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ó

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

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 XN 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 N.

Ghi chú[sửa | sửa mã nguồn]

Mộ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 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 Hoeffding (1963)).

Xem thêm[sửa | sửa mã nguồn]

Tài liệu tham khảo[sửa | sửa mã nguồn]

  • Alon, N.; Spencer, J. (1992). The Probabilistic Method. New York: Wiley. 
  • Azuma, K. (1967). “Weighted Sums of Certain Dependent Random Variables”. Tôhoku Math. Journ. 19: 357–367. doi:10.2748/tmj/1178243286. 
  • Bernstein, Sergei N. (1937). [On certain modifications of Chebyshev's inequality] |dịch tựa đề= cần |tựa đề= (trợ giúp). Doklady Akademii Nauk SSSR (bằng tiếng Nga) 17 (6): 275–277.  (quyển 4, mục 22 trong tuyển tập)
  • McDiarmid, C. (1989). “On the method of bounded differences”. Surveys in Combinatorics. London Math. Soc. Lectures Notes 141. Cambridge: Cambridge Univ. Press. tr. 148–188. 
  • Hoeffding, W. (1963). “Probability inequalities for sums of bounded random variables”. J. Amer. Statist. Assoc. 58 (301): 13–30. doi:10.2307/2282952. MR 0144363. 
  • Godbole, A. P.; Hitczenko, P. (1998). “Beyond the method of bounded differences”. DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 41: 43–58. MR 1630408.