Doob martyngał

W matematycznej teorii prawdopodobieństwa martyngał Dooba (nazwany na cześć Josepha L. Dooba , znanego również jako martyngał Levy'ego ) jest procesem stochastycznym , który przybliża daną zmienną losową i ma właściwość martyngału w odniesieniu do danej filtracji . Można to traktować jako ewoluującą sekwencję najlepszych przybliżeń zmiennej losowej na podstawie informacji zgromadzonych do pewnego czasu.

Analizując sumy, spacery losowe lub inne addytywne funkcje niezależnych zmiennych losowych , często można zastosować centralne twierdzenie graniczne , prawo wielkich liczb , nierówność Chernoffa , nierówność Czebyszewa lub podobne narzędzia. Podczas analizy podobnych obiektów, w których różnice nie są niezależne, głównymi narzędziami są martyngały i nierówność Azumy . ^{[ wymagane wyjaśnienie ]}

Definicja

Niech $będzie$ dowolną zmienną losową z ${\ Displaystyle \ mathbb {E} [| Y |] <\ infty}$ . Załóżmy, że ${\ Displaystyle \ lewo \ {{\ mathcal {F}} _ {0}, {\ mathcal {F}} _ {1}, \ kropki \ po prawej \}}$ jest filtracją fa $podzbiór {\ mathcal {F}} _ {t}} kiedy s$ < $displaystyle s <t}$ . Definiować

{\ Displaystyle Z_ {t} = \ mathbb {E} [Y \ mid {\ mathcal {F}} _ {t}]}

wtedy ${\ Displaystyle \ lewo \ {Z_ {0}, Z_ {1}, \ kropki \ prawo \}}$ jest martyngałem , a mianowicie martyngałem Dooba , w odniesieniu do filtracji ${\ Displaystyle \ lewo \ {{\ mathcal {F}} _ {0}, {\ mathcal {F}} _ {1}, \ kropki \ prawo \}}$ .

Aby to zobaczyć, zauważ to

${\ Displaystyle \ mathbb {E} [| Z_ {t} |] = \ mathbb {E} [|\ mathbb {E} [Y \ mid {\ mathcal {F}} _ {t}] |] \leq \mathbb {E} [\mathbb {E} [|Y|\mid {\mathcal {F}}_{t}]]=\mathbb {E} [|Y|]<\infty }$ ;
${\ Displaystyle \ mathbb {E} [ Z_{t}\mid {\mathcal {F}}_{t-1}]=\mathbb {E} [\mathbb {E} [Y\mid {\mathcal {F}}_{t}]\mid {\mathcal {F}}_{t-1}]=\mathbb {E} [Y\mid {\mathcal {F}}_{t-1}]=Z_{t-1}}$ jako ${\ Displaystyle {\ mathcal {F}} _ {t-1} \ podzbiór {\ mathcal {F}} _ {t}}$ .

W szczególności dla dowolnej sekwencji zmiennych losowych ${\ Displaystyle \ lewo \ {X_ {1}, X_ {2}, \ kropki, X_ {n} \ prawo \}}$ na $($ i $[$ _ ${\ Displaystyle \ mathbb {E} [| f (X_ {1}, X_ {2} \ kropki, X_ {n}) |] <\ infty} , można$ wybrać

{\ Displaystyle Y: = f (X_ {1}, X_ {2}, \ kropki, X_ {n})}

i filtracja taka, że ${\ Displaystyle \ lewo \ {{\ mathcal {F}} _ {0}, {\ mathcal {F}} _ {1}, \ kropki \ po prawej \}}$

{\ Displaystyle {\ rozpocząć {wyrównane} {\ mathcal {F}} _ { 0}&:=\left\{\phi ,\Omega \right\},\\{\mathcal {F}}_{t}&:=\sigma (X_{1},X_{2},\kropki ,X_{t}),\forall t\geq 1,\end{wyrównane}}}

tj. ${\ Displaystyle \ sigma}$ -algebra generowana przez ${\ Displaystyle X_ {1}, X_ {2}, \ kropki, X_ {t}}$ . $_$ zgodnie definicją

{\ Displaystyle {\ rozpocząć{wyrównane}Z_{0}&:=\mathbb {E} [f(X_{1},X_{2},\kropki ,X_{n})\mid {\mathcal {F}}_{0} ]=\mathbb {E} [f(X_{1},X_{2},\kropki ,X_{n})],\\Z_{t}&:=\mathbb {E} [f(X_{1 },X_{2},\kropki ,X_{n})\mid {\mathcal {F}}_{t}]=\mathbb {E} [f(X_{1},X_{2},\kropki ,X_{n})\mid X_{1},X_{2},\kropki ,X_{t}],\forall t\geq 1\end{wyrównane}}}

tworzy martyngał Dooba. Zauważ, że ${\ Displaystyle Z_ {n} = f (X_ {1}, X_ {2}, \ kropki, X_ {n})}$ . Ten martyngał może być użyty do udowodnienia nierówności McDiarmida .

Nierówność McDiarmida

Martyngał Doob został wprowadzony przez Josepha L. Dooba w 1940 r. W celu ustalenia nierówności koncentracji , takich jak nierówność McDiarmida , która ma zastosowanie do funkcji, które spełniają właściwość ograniczonych różnic (zdefiniowaną poniżej), gdy są oceniane na podstawie losowych niezależnych argumentów funkcji.

Funkcja ${\ Displaystyle f: {\ mathcal {X}} _ {1} \ razy {\ mathcal {X}} _ {2} \ razy \ cdots \ razy {\ mathcal {X}} _ {n} \ rightarrow \ mathbb {R}}$ spełnia właściwość ograniczonych różnic , jeśli zastępuje się wartość współrzędnej ${\ displaystyle i}$ zmienia się ${\ displaystyle x_ {i}}$ wartość co najwyżej $displaystyle c_ {i}}$ $\$ . $n$ istnieją dla $Displaystyle ja \ w [n]}$ i wszystkie ${\ Displaystyle x_ {1} \ w {\ mathcal {X}} _ {1}, \,x_{2}\in {\mathcal {X}}_{2},\,\ldots,\,x_{n}\in {\mathcal {X}}_{n}}$ ,

{\ Displaystyle \ sup _ {x_ {i} '\ w {\ mathcal {X}} _ {i}} \ lewo | f (x_ {1}, \ kropki, x_ {i-1}, x_ {i} ,x_{i+1},\ldots ,x_{n})-f(x_{1},\dots ,x_{i-1},x_{i}',x_{i+1},\ldots , x_{n})\prawo|\równoważnik c_{i}.}

Nierówność McDiarmida - Niech ${\ Displaystyle f: {\ mathcal {X}} _ {1} \ razy {\ mathcal {X}} _ {2} \ razy \ cdots \times {\ mathcal {X}} _ {n} \ rightarrow \ mathbb {R}}$ spełniają właściwość ograniczonych różnic z granicami ${\ Displaystyle c_ {1}, c_ {2 },\kropki ,c_{n}}$ .

$in {\ mathcal {X}} _ {i}}$ niezależne $i$ gdzie dla wszystkich ${\ displaystyle i}$ . Następnie, dla dowolnego , ${\ displaystyle \ varepsilon > 0$ }