Dejar
ser cualquier variable aleatoria con
. Suponer
es una filtración , es decir
Cuándo
. Definir
![{\displaystyle Z_{t}=\mathbb {E} [Y\mid {\mathcal {F}}_{t}],}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
luego
es una martingala , [2] a saber, Doob martingala , con respecto a la filtración
.
Para ver esto, tenga en cuenta que
;
como
.
En particular, para cualquier secuencia de variables aleatorias
en el espacio de probabilidad
y función
tal que
, uno podría elegir
![{\displaystyle Y:=f(X_{1},X_{2},\dots ,X_{n})}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
y filtración
tal que
![{\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}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
es decir
-álgebra generada por
. Entonces, por definición de Doob martingale, proceso
dónde
![{\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}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
forma una martingala Doob. Tenga en cuenta que
. Esta martingala se puede utilizar para probar la desigualdad de McDiarmid .
Declaración [1]
Considere variables aleatorias independientes
en el espacio de probabilidad
dónde
para todos
y un mapeo
. Suponga que existen constantes
tal que para todos
,
![{\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},\dots ,x_{i-1},x_{i}',x_{i+1},\cdots ,x_{n})|\leq c_{i}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
(En otras palabras, cambiar el valor de la
th coordenada
cambia el valor de
por como máximo
.) Entonces, para cualquier
,
![{\displaystyle {\text{P}}(f(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),}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\text{P}}(f(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),}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
y
![{\displaystyle {\text{P}}(|f(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).}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Prueba
Elija cualquiera
tal que el valor de
está acotado, entonces, para cualquier
, por desigualdad triangular ,
![{\displaystyle {\begin{aligned}&|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{aligned}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
por lo tanto
está ligado.
Definir
para todos
y
. Tenga en cuenta que
. Desde
está limitado, por la definición de Doob martingala,
forma una martingala. Ahora define
Tenga en cuenta que
y
son ambos
- medible . Además,
![{\displaystyle {\begin{aligned}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}\mid X_{1},\cdots ,X_{t-1},x_{l}}(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}){\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{aligned}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
donde la tercera igualdad se mantiene debido a la independencia de
. Luego, aplicando la forma general de la desigualdad de Azuma a
, tenemos
![{\displaystyle {\text{P}}(f(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).}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
La cota unilateral de la otra dirección se obtiene aplicando la desigualdad de Azuma a
y el límite de dos caras se sigue del límite de unión .