Дуб мартингейл

Случайный процесс

В математической теории вероятностей мартингал Дуба (названный в честь Джозефа Л. Дуба ^[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}}_{t}}$ ${\displaystyle s<t}$

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

то есть мартингал , ^[2] а именно мартингал Дуба , относительно фильтрации . ${\displaystyle \left\{Z_{0},Z_{1},\dots \right\}}$ ${\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_{t-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} [|f(X_{1},X_{2},\dots ,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{aligned}{\mathcal {F}}_{0}&:=\left\{\phi ,\Omega \right\},\\{\mathcal {F}}_{t}&:=\sigma (X_{1},X_{2},\dots ,X_{t}),\forall t\geq 1,\end{aligned}}}$

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

${\displaystyle {\begin{aligned}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{aligned}}}$

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

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

Мартингал Дуба был введен Джозефом Л. Дубом в 1940 году для установления неравенств концентрации , таких как неравенство Мак-Диармида, которое применяется к функциям, удовлетворяющим свойству ограниченной разности (определенному ниже), когда они оцениваются на случайных независимых аргументах функции.

Функция удовлетворяет свойству ограниченных разностей , если подстановка значения th-й координаты изменяет значение не более чем на . Более формально, если существуют константы такие, что для всех , и всех , ${\displaystyle f:{\mathcal {X}}_{1}\times {\mathcal {X}}_{2}\times \cdots \times {\mathcal {X}}_{n}\rightarrow \mathbb {R} }$ ${\displaystyle i}$ ${\displaystyle x_{i}}$ ${\displaystyle f}$ ${\displaystyle c_{i}}$ ${\displaystyle c_{1},c_{2},\dots ,c_{n}}$ ${\displaystyle i\in [n]}$ ${\displaystyle x_{1}\in {\mathcal {X}}_{1},\,x_{2}\in {\mathcal {X}}_{2},\,\ldots ,\,x_{n}\in {\mathcal {X}}_{n}}$

${\displaystyle \sup _{x_{i}'\in {\mathcal {X}}_{i}}\left|f(x_{1},\dots ,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})\right|\leq c_{i}.}$

Неравенство Мак-Диармида ^[1]  —  Пусть удовлетворяет свойству ограниченных разностей с границами . ${\displaystyle f:{\mathcal {X}}_{1}\times {\mathcal {X}}_{2}\times \cdots \times {\mathcal {X}}_{n}\rightarrow \mathbb {R} }$ ${\displaystyle c_{1},c_{2},\dots ,c_{n}}$

Рассмотрим независимые случайные величины, где для всех . Тогда для любого , ${\displaystyle X_{1},X_{2},\dots ,X_{n}}$ ${\displaystyle X_{i}\in {\mathcal {X}}_{i}}$ ${\displaystyle i}$ ${\displaystyle \varepsilon >0}$

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

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

и как непосредственное следствие,

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

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

• Каталог статей по теории вероятностей
• Неравенство концентрации – краткое изложение неравенства Мак-Диармида и нескольких подобных неравенств.
• Ожидаемое значение и дисперсия
• Нечеткая логика и теория нечеткой меры
• Глоссарий по вероятностям и статистике
• Список вероятностных тем
• Список публикаций по статистике
• Список статистических тем
• Обозначение в теории вероятности
• Распределение вероятностей

Ссылки

1. Doob, JL (1940). "Свойства регулярности некоторых семейств случайных величин" (PDF) . Transactions of the American Mathematical Society . 47 (3): 455–486. doi : 10.2307/1989964 . JSTOR  1989964.
2. Дуб, Дж. Л. (1953). Стохастические процессы . Т. 101. Нью-Йорк: Wiley. С. 293.