Bách khoa toàn thư mở Wikipedia
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.
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
X
→
=
X
1
,
X
2
,
.
.
.
,
X
n
{\displaystyle {\vec {X}}=X_{1},X_{2},...,X_{n}}
nhận giá trị trong tập
A
{\displaystyle A}
f
:
A
n
→
R
{\displaystyle f:A^{n}\to \mathbb {R} }
B
i
=
E
X
i
+
1
,
X
i
+
2
,
.
.
.
,
X
n
[
f
(
X
→
)
|
X
1
,
X
2
,
.
.
.
X
i
]
{\displaystyle 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
,
{\displaystyle X_{i+1},X_{i+2},...,X_{n},}
và
X
1
,
X
2
,
.
.
.
X
i
{\displaystyle 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
{\displaystyle B_{i}}
X
i
{\displaystyle X_{i}}
|
B
i
+
1
−
B
i
|
{\displaystyle |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
(
X
→
)
{\displaystyle f({\vec {X}})}
E
[
f
(
X
→
)
]
=
B
0
.
{\displaystyle E[f({\vec {X}})]=B_{0}.}
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ử
X
1
,
X
2
,
…
,
X
n
{\displaystyle X_{1},X_{2},\dots ,X_{n}}
f
{\displaystyle f}
sup
x
1
,
x
2
,
…
,
x
n
,
x
^
i
|
f
(
x
1
,
x
2
,
…
,
x
n
)
−
f
(
x
1
,
x
2
,
…
,
x
i
−
1
,
x
^
i
,
x
i
+
1
,
…
,
x
n
)
|
≤
c
i
khi
1
≤
i
≤
n
.
{\displaystyle \sup _{x_{1},x_{2},\dots ,x_{n},{\hat {x}}_{i}}|f(x_{1},x_{2},\dots ,x_{n})-f(x_{1},x_{2},\dots ,x_{i-1},{\hat {x}}_{i},x_{i+1},\dots ,x_{n})|\leq c_{i}\qquad {\text{khi}}\quad 1\leq i\leq n\;.}
(Nói cách khác, việc thay đổi giá trị
x
i
{\displaystyle x_{i}}
i
{\displaystyle i}
f
{\displaystyle f}
c
i
{\displaystyle c_{i}}
Do đó
|
B
i
+
1
−
B
i
|
≤
c
i
{\displaystyle |B_{i+1}-B_{i}|\leq c_{i}}
và theo bất đẳng thức Azuma , ta có bất đẳng thức McDiarmid cho mọi
ε
>
0
{\displaystyle \varepsilon >0}
Pr
{
f
(
X
1
,
X
2
,
…
,
X
n
)
−
E
[
f
(
X
1
,
X
2
,
…
,
X
n
)
]
≥
ε
}
≤
exp
(
−
2
ε
2
∑
i
=
1
n
c
i
2
)
{\displaystyle \Pr \left\{f(X_{1},X_{2},\dots ,X_{n})-E[f(X_{1},X_{2},\dots ,X_{n})]\geq \varepsilon \right\}\leq \exp \left(-{\frac {2\varepsilon ^{2}}{\sum _{i=1}^{n}c_{i}^{2}}}\right)}
và
Pr
{
E
[
f
(
X
1
,
X
2
,
…
,
X
n
)
]
−
f
(
X
1
,
X
2
,
…
,
X
n
)
≥
ε
}
≤
exp
(
−
2
ε
2
∑
i
=
1
n
c
i
2
)
{\displaystyle \Pr \left\{E[f(X_{1},X_{2},\dots ,X_{n})]-f(X_{1},X_{2},\dots ,X_{n})\geq \varepsilon \right\}\leq \exp \left(-{\frac {2\varepsilon ^{2}}{\sum _{i=1}^{n}c_{i}^{2}}}\right)}
và
Pr
{
|
E
[
f
(
X
1
,
X
2
,
…
,
X
n
)
]
−
f
(
X
1
,
X
2
,
…
,
X
n
)
|
≥
ε
}
≤
2
exp
(
−
2
ε
2
∑
i
=
1
n
c
i
2
)
.
{\displaystyle \Pr \left\{|E[f(X_{1},X_{2},\dots ,X_{n})]-f(X_{1},X_{2},\dots ,X_{n})|\geq \varepsilon \right\}\leq 2\exp \left(-{\frac {2\varepsilon ^{2}}{\sum _{i=1}^{n}c_{i}^{2}}}\right).\;}
![{\displaystyle B_{i}=E_{X_{i+1},X_{i+2},...,X_{n}}[f({\vec {X}})|X_{1},X_{2},...X_{i}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3f6ec3a7576e56b6ffc994c9b4b8793a7e32089c)
![{\displaystyle E[f({\vec {X}})]=B_{0}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d6ef3f74b5041f6b60b4b9bcf52fa4b911c91a09)
![{\displaystyle \Pr \left\{f(X_{1},X_{2},\dots ,X_{n})-E[f(X_{1},X_{2},\dots ,X_{n})]\geq \varepsilon \right\}\leq \exp \left(-{\frac {2\varepsilon ^{2}}{\sum _{i=1}^{n}c_{i}^{2}}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/004475c6361355d80884da4c2c2245593187c728)
![{\displaystyle \Pr \left\{E[f(X_{1},X_{2},\dots ,X_{n})]-f(X_{1},X_{2},\dots ,X_{n})\geq \varepsilon \right\}\leq \exp \left(-{\frac {2\varepsilon ^{2}}{\sum _{i=1}^{n}c_{i}^{2}}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cdd975b6fc5307a0b2ca8136050fbe6a1aa7387a)
![{\displaystyle \Pr \left\{|E[f(X_{1},X_{2},\dots ,X_{n})]-f(X_{1},X_{2},\dots ,X_{n})|\geq \varepsilon \right\}\leq 2\exp \left(-{\frac {2\varepsilon ^{2}}{\sum _{i=1}^{n}c_{i}^{2}}}\right).\;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ef2bac8be3049d02f5000162fcc0e25c81cb821f)