✨Bất đẳng thức Azuma

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 có gia số bị chặn.

Giả sử { X_k: 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 -X và X 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

Giả sử F_i là một dãy những lần tung đồng xu công bằng độc lập nhau (nghĩa là F_i 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_j khác). Đặt $X$i = \sum{j=1}^i F_j cho ta một martingale với |X_k − X_k−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ó

:$\backslash Pr[X\_N\; >\; t]\; \backslash leq\; \backslash exp\backslash left(\backslash frac\{-t^2\}\{8\; N\}\backslash 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 X_N 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.