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ĩaSửa đổi

Một martingale Doob (đặt theo tên của J. L. Doob)[cần dẫn nguồn] 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

 

nhận giá trị trong tập  . Đối tượng quan tâm là một hàm  . Định nghĩa:

 

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

 

 

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

 ,

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   tập trung xung quanh giá trị kì vọng

 

Bất đẳng thức McDiarmidSửa đổi

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.[cần dẫn nguồn] Giả sử   là độc lập và giả sử   thỏa mãn

 

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

Do đó

 

và theo bất đẳng thức Azuma, ta có bất đẳng thức McDiarmid cho mọi  :

 

 

 

Xem thêmSửa đổi

Tham khảoSửa đổi

  • McDiarmid, Colin (1989). “On the Method of Bounded Differences” (PDF). Surveys in Combinatorics. 141: 148–188. Bản gốc (PDF) lưu trữ ngày 27 tháng 9 năm 2011. Truy cập ngày 7 tháng 10 năm 2011.

Tham khảoSửa đổi