Неравенство Азумы

Неравенство Азумы — оценка для плотности вероятности последней величины мартингала.

ФормулировкаПравить

Пусть $c={\mathrm{\xi <!--\; \xi \; -->}}_0,{\mathrm{\xi <!--\; \xi \; -->}}_1,...{\mathrm{\xi <!--\; \xi \; -->}}_m$$c=\xi _{0},\xi _{1},...\xi _{m}$  — мартингал и для всех допустимых $i$$i$  и для всех элементарных событий $\mathrm{\omega <!--\; \omega \; -->}\in <!--\; \in \; -->\mathrm{\Omega <!--\; \Omega \; -->}$$\omega \in \Omega$  выполняется условие $\mid <!--\; \mid \; -->{\mathrm{\xi <!--\; \xi \; -->}}_i-<!--\; -\; -->{\mathrm{\xi <!--\; \xi \; -->}}_{i-<!--\; -\; -->1}\mid <!--\; \mid \; -->⩽<!--\; ⩽\; -->1$$\mid \xi _{i}-\xi _{i-1}\mid \leqslant 1$ . Тогда для любого $a>0$$a>0$  выполняется неравенство $P({\mathrm{\xi <!--\; \xi \; -->}}_m-<!--\; -\; -->c⩾<!--\; ⩾\; -->a)⩽<!--\; ⩽\; -->e^{-<!--\; -\; -->\frac{a^2}{2m}}$$P(\xi _{m}-c\geqslant a)\leqslant e^{-{\frac {a^{2}}{2m}}}$ .

ДоказательствоПравить

Доказательство приведено в книге .

ЛитератураПравить

• А.М. Райгородский. Модели случайных графов. — М.: МЦНМО, 2011. — 136 с. — ISBN 978-5-94057-840-6.