✨Martingale Doob

Một martingale Doob (còn gọi là martingale Levy) là một quá trình ngẫu nhiên tính giá trị của một biến ngẫu nhiên và có tính chất martingale theo một bộ lọc cho trước. Nó có thể được xem là giá trị xấp xỉ của một biến ngẫu nhiên dựa vào thông tin tích lũy được cho tới một thời điểm nhất định.

Định nghĩa

Một martingale Doob (đặt theo tên của J. L. Doob) là một cách xây dựng martingale nói chung như sau. Ta xét một dãy các biến ngẫu nhiên

:$\backslash vec\{X\}=X\_1,\; X\_2,...,\; X\_n$

nhận giá trị trong tập $A$. Đối tượng quan tâm là một hàm $f:A^n\; \backslash to\; \backslash mathbb\{R\}$. Định nghĩa:

:$B$i=E{X{i+1},X{i+2},...,X{n[f(\vec{X})|X{1},X{2},...X{i}]

trong đó giá trị kì vọng trên là một biến ngẫu nhiên do việc tính kì vọng chỉ dựa trên

:$X${i+1},X{i+2},...,X_{n},

và

:$X${1},X{2},...X_{i}

vẫn được xem là biến ngẫu nhiên. Có thể chứng minh rằng $B\_i$ là một martingale cho bất kì dãy $X\_i$ nào. Do đó nếu ta có thể chặn trên độ chênh lệch

:$|B\_\{i+1\}-B\_i|$,

thì có thể áp dụng bất đẳng thức Azuma và kết luận với xác suất cao rằng $f(\backslash vec\{X\})$ tập trung xung quanh giá trị kì vọng

:$E[f(\backslash vec\{X\})]=B\_0.$

Bất đẳng thức McDiarmid

Một phương pháp để chặn trên độ chênh lệch và áp dụng bất đẳng thức Azuma cho một martingale Doob là bất đẳng thức McDiarmid. Giả sử $X\_1,\; X\_2,\; \backslash dots,\; X\_n$ là độc lập và giả sử $f$ thỏa mãn

: $\backslash sup\_\{x\_1,x\_2,\backslash dots,x\_n,\; \backslash hat\; x\_i\}\; |f(x\_1,x\_2,\backslash dots,x\_n)\; -\; f(x\_1,x$2,\dots,x{i-1},\hat xi, x{i+1}, \dots, x_n)| \le c_i \qquad \text{khi} \quad 1 \le i \le n \;.

(Nói cách khác, việc thay đổi giá trị $x\_i$ của tọa độ thứ $i$ làm thay đổi giá trị của $f$ bởi một lượng không quá $c\_i$.)

Do đó

:$|B\_\{i+1\}-B\_i|\; \backslash le\; c\_i$

và theo bất đẳng thức Azuma, ta có bất đẳng thức McDiarmid cho mọi $\backslash varepsilon\; >\; 0$:

: $\backslash Pr\; \backslash left\{\; f(X\_1,\; X\_2,\; \backslash dots,\; X\_n)\; -\; E[f(X\_1,\; X\_2,\; \backslash dots,\; X$n)] \ge \varepsilon \right} \le \exp \left(- \frac{2 \varepsilon^2}{\sum{i=1}^n c_i^2} \right)

và

: $\backslash Pr\; \backslash left\{\; E[f(X\_1,\; X\_2,\; \backslash dots,\; X\_n)]\; -\; f(X\_1,\; X\_2,\; \backslash dots,\; X$n) \ge \varepsilon \right} \le \exp \left(- \frac{2 \varepsilon^2}{\sum{i=1}^n c_i^2} \right)

và

: $\backslash Pr\; \backslash left\{\; |E[f(X\_1,\; X\_2,\; \backslash dots,\; X\_n)]\; -\; f(X\_1,\; X\_2,\; \backslash dots,\; X$n)| \ge \varepsilon \right} \le 2 \exp \left(- \frac{2 \varepsilon^2}{\sum{i=1}^n c_i^2} \right). \;