Дуб мартингейл - Википедия - Doob martingale

Эта статья предоставляет недостаточный контекст для тех, кто не знаком с предметом. Пожалуйста помоги улучшить статью к обеспечение большего контекста для читателя. (Март 2011 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

А Дуб мартингейл (названный в честь Джозеф Л. Дуб,^[1] также известный как Леви Мартингейл) представляет собой математическую конструкцию случайный процесс что приблизительно соответствует данному случайная переменная и имеет мартингейл недвижимость по отношению к данному фильтрация. Его можно рассматривать как развивающуюся последовательность наилучших приближений к случайной величине на основе информации, накопленной к определенному моменту времени.

Анализируя суммы, случайные прогулки, или другие аддитивные функции независимые случайные величины, часто можно применить Центральная предельная теорема, закон больших чисел, Неравенство Чернова, Неравенство Чебышева или аналогичные инструменты. При анализе похожих объектов, где различия не являются независимыми, основными инструментами являются мартингалы и Неравенство Адзумы.^{[требуется разъяснение ]}

Определение

Позволять ${ displaystyle Y}$ быть любой случайной величиной с ${ Displaystyle mathbb {E} [| Y |] < infty}$. Предполагать ${ displaystyle left {{ mathcal {F}} _ {0}, { mathcal {F}} _ {1}, dots right }}$ это фильтрация, т.е. ${ Displaystyle { mathcal {F}} _ {s} subset { mathcal {F}} _ {т}}$ когда ${ displaystyle s$. Определять

${ displaystyle Z_ {t} = mathbb {E} [Y mid { mathcal {F}} _ {t}],}$

тогда ${ displaystyle left {Z_ {0}, Z_ {1}, dots right }}$ это мартингейл,^[2] а именно Дуб мартингейл, относительно фильтрации ${ displaystyle left {{ mathcal {F}} _ {0}, { mathcal {F}} _ {1}, dots right }}$.

Чтобы увидеть это, обратите внимание, что

• ${ 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_ { т-1}}$ в качестве ${ displaystyle { mathcal {F}} _ {t-1} subset { mathcal {F}} _ {t}}$.

В частности, для любой последовательности случайных величин ${ displaystyle left {X_ {1}, X_ {2}, dots, X_ {n} right }}$ на вероятностном пространстве ${ displaystyle ( Omega, { mathcal {F}}, { text {P}})}$ и функция ${ displaystyle f}$ такой, что ${ Displaystyle mathbb {E} [| е (X_ {1}, X_ {2}, точки, X_ {n}) |] < infty}$, можно было выбрать

${ displaystyle Y: = f (X_ {1}, X_ {2}, dots, X_ {n})}$

и фильтрация ${ displaystyle left {{ mathcal {F}} _ {0}, { mathcal {F}} _ {1}, dots right }}$ такой, что

${ displaystyle { begin {align} { mathcal {F}} _ {0} &: = left { phi, Omega right }, { mathcal {F}} _ {t} &: = sigma (X_ {1}, X_ {2}, dots, X_ {t}), forall t geq 1, end {align}}}$

т.е. ${ displaystyle sigma}$-алгебра, порожденная ${ displaystyle X_ {1}, X_ {2}, dots, X_ {t}}$. Тогда, по определению Мартингейла Дуба, процесс ${ displaystyle left {Z_ {0}, Z_ {1}, dots right }}$ куда

${ displaystyle { begin {align} Z_ {0} &: = mathbb {E} [f (X_ {1}, X_ {2}, dots, X_ {n}) mid { mathcal {F} } _ {0}] = mathbb {E} [f (X_ {1}, X_ {2}, dots, X_ {n})], Z_ {t} &: = mathbb {E} [ f (X_ {1}, X_ {2}, dots, X_ {n}) mid { mathcal {F}} _ {t}] = mathbb {E} [f (X_ {1}, X_ { 2}, dots, X_ {n}) mid X_ {1}, X_ {2}, dots, X_ {t}], forall t geq 1 end {выравнивается}}}$

образует мартингейл Дуба. Обратите внимание, что ${ displaystyle Z_ {n} = f (X_ {1}, X_ {2}, dots, X_ {n})}$. Этот мартингал можно использовать для доказательства Неравенство МакДиармида.

Неравенство МакДиармида

Заявление^[1]

Рассмотрим независимые случайные величины ${ displaystyle X_ {1}, X_ {2}, dots X_ {n}}$ на вероятностном пространстве ${ displaystyle ( Omega, { mathcal {F}}, { text {P}})}$ куда ${ Displaystyle X_ {я} in { mathcal {X}} _ {я}}$ для всех ${ displaystyle i}$ и отображение ${ displaystyle f: { mathcal {X}} _ {1} times { mathcal {X}} _ {2} times cdots times { mathcal {X}} _ {n} rightarrow mathbb {Р} }$. Предположим, что существует постоянная ${ displaystyle c_ {1}, c_ {2}, dots, c_ {n}}$ такой, что для всех ${ displaystyle i}$,

${ displaystyle { underset {x_ {1}, cdots, x_ {i-1}, x_ {i}, x_ {i} ', x_ {i + 1}, cdots, x_ {n}} { sup}} | f (x_ {1}, dots, x_ {i-1}, x_ {i}, x_ {i + 1}, cdots, x_ {n}) - f (x_ {1}, точки, x_ {i-1}, x_ {i} ', x_ {i + 1}, cdots, x_ {n}) | leq c_ {i}.}$

(Другими словами, изменение значения ${ displaystyle i}$я координата ${ displaystyle x_ {i}}$ меняет значение ${ displaystyle f}$ самое большее ${ displaystyle c_ {i}}$.) Тогда для любого ${ displaystyle epsilon> 0}$,

${ displaystyle { text {P}} (е (X_ {1}, X_ {2}, cdots, X_ {n}) - mathbb {E} [f (X_ {1}, X_ {2}, cdots, X_ {n})] geq epsilon) leq exp left (- { frac {2 epsilon ^ {2}} { sum _ {i = 1} ^ {n} c_ {i } ^ {2}}} right),}$

${ displaystyle { text {P}} (е (X_ {1}, X_ {2}, cdots, X_ {n}) - mathbb {E} [f (X_ {1}, X_ {2}, cdots, X_ {n})] leq - epsilon) leq exp left (- { frac {2 epsilon ^ {2}} { sum _ {i = 1} ^ {n} c_ { i} ^ {2}}} right),}$

и

${ displaystyle { text {P}} (| е (X_ {1}, X_ {2}, cdots, X_ {n}) - mathbb {E} [f (X_ {1}, X_ {2}) , cdots, X_ {n})] | geq epsilon) leq 2 exp left (- { frac {2 epsilon ^ {2}} { sum _ {i = 1} ^ {n} c_ {i} ^ {2}}} right).}$

Доказательство

Выберите любой ${ Displaystyle x_ {1} ', x_ {2}', cdots, x_ {n} '}$ так что значение ${ Displaystyle f (x_ {1} ', x_ {2}', cdots, x_ {n} ')}$ ограничен, то для любого ${ displaystyle x_ {1}, x_ {2}, cdots, x_ {n}}$, к неравенство треугольника,

${ displaystyle { begin {align} & | f (x_ {1}, x_ {2}, cdots, x_ {n}) - f (x_ {1} ', x_ {2}', cdots, x_ {n} ') | leq & | f (x_ {1}, x_ {2}, cdots, x_ {n}) - f (x_ {1}', x_ {2}, cdots, x_ {n}) | & + sum _ {i = 1} ^ {n-1} | f (x_ {1} ', cdots, x_ {i}', x_ {i + 1}, cdots , x_ {n}) - f (x_ {1} ', x_ {2}', cdots, x_ {i} ', x_ {i + 1}', x_ {i + 2}, cdots, x_ { n}) | leq & sum _ {i = 1} ^ {n} c_ {i}, end {align}}}$

таким образом ${ displaystyle f}$ ограничено.

Определять ${ displaystyle Z_ {i}: = mathbb {E} [f (X_ {1}, X_ {2}, cdots, X_ {n}) mid X_ {1}, X_ {2}, cdots, X_ {i}]}$ для всех ${ displaystyle i geq 1}$ и ${ displaystyle Z_ {0}: = mathbb {E} [f (X_ {1}, X_ {2}, cdots, X_ {n})]}$. Обратите внимание, что ${ Displaystyle Z_ {п} = е (X_ {1}, X_ {2}, cdots, X_ {n})}$. С ${ displaystyle f}$ ограничена по определению мартингала Дуба, ${ displaystyle left {Z_ {i} right }}$ образует мартингал. Теперь определим${ displaystyle { begin {align} U_ {i} & = { underset {x in { mathcal {X}} _ {i}} { sup}} mathbb {E} [f (X_ {1 }, cdots, X_ {n}) mid X_ {1}, cdots, X_ {i-1}, x] - mathbb {E} [f (X_ {1}, cdots, X_ {n} ) mid X_ {1}, cdots, X_ {i-1}], L_ {i} & = { underset {x in { mathcal {X}} _ {i}} { inf} } mathbb {E} [f (X_ {1}, cdots, X_ {n}) mid X_ {1}, cdots, X_ {i-1}, x] - mathbb {E} [f ( X_ {1}, cdots, X_ {n}) mid X_ {1}, cdots, X_ {i-1}]. End {выравнивается}}}$

Обратите внимание, что ${ displaystyle L_ {i} leq Z_ {i} -Z_ {i-1} leq U_ {i}}$ и ${ displaystyle U_ {i}, L_ {i}}$ оба ${ Displaystyle { mathcal {F}} _ {я-1}}$-измеримый. Кроме того,

${ displaystyle { begin {align} U_ {i} -L_ {i} & = { underset {x_ {u} in { mathcal {X}} _ {i}, x_ {l} in { mathcal {X}} _ {i}} { sup}} mathbb {E} [f (X_ {1}, cdots, X_ {n}) mid X_ {1}, cdots, X_ {i- 1}, x_ {u}] - mathbb {E} [f (X_ {1}, cdots, X_ {n}) mid X_ {1}, cdots, X_ {i-1}, x_ {l }] & = { underset {x_ {u} in { mathcal {X}} _ {i}, x_ {l} in { mathcal {X}} _ {i}} { sup} } int _ {{ mathcal {X}} _ {i + 1} times cdots times { mathcal {X}} _ {n}} f (X_ {1}, cdots, X_ {i- 1}, x_ {u}, x_ {i + 1}, cdots, x_ {n}) { text {d}} { text {P}} _ {X_ {i + 1}, cdots, X_ {n} mid X_ {1}, cdots, X_ {t-1}, x_ {u}} (x_ {i + 1}, cdots, x_ {n}) & quad - int _ {{ mathcal {X}} _ {i + 1} times cdots times { mathcal {X}} _ {n}} f (X_ {1}, cdots, X_ {i-1}, x_ {l}, x_ {i + 1}, cdots, x_ {n}) { text {d}} { text {P}} _ {X_ {i + 1}, cdots, X_ {n} середина X_ {1}, cdots, X_ {t-1}, x_ {l}} (x_ {i + 1}, cdots, x_ {n}) & = { underset {x_ {u} в { mathcal {X}} _ {i}, x_ {l} in { mathcal {X}} _ {i}} { sup}} int _ {{ mathcal {X}} _ {i +1} times cdots times { mathcal {X}} _ {n}} f (X_ {1}, cdots, X_ {i-1}, x_ {u}, x_ {i + 1}, cdots, x_ {n}) { text {d}} { text {P }} _ {X_ {i + 1}, cdots, X_ {n}} (x_ {i + 1}, cdots, x_ {n}) & quad - int _ {{ mathcal {X }} _ {i + 1} times cdots times { mathcal {X}} _ {n}} f (X_ {1}, cdots, X_ {i-1}, x_ {l}, x_ { i + 1}, cdots, x_ {n}) { text {d}} { text {P}} _ {X_ {i + 1}, cdots, X_ {n}} (x_ {i + 1 }, cdots, x_ {n}) & = { underset {x_ {u} in { mathcal {X}} _ {i}, x_ {l} in { mathcal {X}} _ {i}} { sup}} int _ {{ mathcal {X}} _ {i + 1} times cdots times { mathcal {X}} _ {n}} f (X_ {1} , cdots, X_ {i-1}, x_ {u}, x_ {i + 1}, cdots, x_ {n}) & quad -f (X_ {1}, cdots, X_ {i -1}, x_ {l}, x_ {i + 1}, cdots, x_ {n}) { text {d}} { text {P}} _ {X_ {i + 1}, cdots , X_ {n}} (x_ {i + 1}, cdots, x_ {n}) & leq { underset {x_ {u} in { mathcal {X}} _ {i}, x_ {l} in { mathcal {X}} _ {i}} { sup}} int _ {{ mathcal {X}} _ {i + 1} times cdots times { mathcal {X }} _ {n}} c_ {i} { text {d}} { text {P}} _ {X_ {i + 1}, cdots, X_ {n}} (x_ {i + 1} , cdots, x_ {n}) & leq c_ {i} end {выравнивается}}}$

где третье равенство выполняется в силу независимости ${ Displaystyle X_ {1}, X_ {2}, cdots, X_ {n}}$. Затем, применяя общая форма неравенства Адзумы к ${ Displaystyle влево {Z_ {я} вправо }}$, у нас есть

${ Displaystyle { текст {P}} (е (X_ {1}, cdots, X_ {n}) - mathbb {E} [f (X_ {1}, cdots, X_ {n})] geq epsilon) = { text {P}} (Z_ {n} -Z_ {0} geq epsilon) leq exp left (- { frac {2 epsilon ^ {2}} { sum _ {i = 1} ^ {n} c_ {i} ^ {2}}} right).}$

Односторонняя граница с другого направления получается применением неравенства Адзумы к ${ displaystyle left {- Z_ {i} right }}$ а двусторонняя оценка следует из связанный союз. ${ displaystyle square}$

Смотрите также

• Неравенство концентраций - краткое изложение неравенства МакДиармида и нескольких аналогичных неравенств.

Рекомендации