Lemme de symétrisation

Le lemme de symétrisation (ou lemme de symétrisation de Vapnik-Tchervonenkis) est un résultat en théorie de probabilités proposée par Vladimir Vapnik et Alexeï Tchervonenkis. Au lieu de comparer la mesure empirique avec la mesure théorique (qui est souvent non connue) ce lemme permet de comparer cette mesure avec une copie indépendante d'elle-même.

Énoncé

Il existe différents énoncés de ce lemme : Pollard utilise la version de la symétrisation avec des processus stochastiques mais il existe des versions faisant intervenir l'erreur de généralisation d'un échantillon. Soit $(X_{t})_{t\in T},(X_{t}')_{t\in T}$ des processus stochastiques indépendants indexés par un ensemble $T$. Supposons qu'il existe des constantes $\alpha >0,\beta >0$ tel que

$\forall t\in T,\quad \mathbb {P} \left(|X_{t}'|\leq \alpha \right)\geq \beta .$

Alors,

$\forall t\in T,\forall \varepsilon >0,\quad \mathbb {P} \left(\sup _{t\in T}|X_{t}|>\varepsilon \right)\leq \beta ^{-1}\mathbb {P} \left(\sup _{t\in T}|X_{t}-X_{t}'|>\varepsilon -\alpha \right).$

En particulier en posant

• $X_{t}=P_{n}(t)-P(t)$ où $P_{n}$ est la mesure empirique et $P$ la loi des variables aléatoires $(Y_{i})_{i\in \mathbb {N} ^{*}}$ indépendantes et identiquement distribuées sur laquelle la mesure empirique est basée, i.e. $P_{n}(t)={\frac {1}{n}}\sum _{i=1}^{n}\mathbf {1} _{\{Y_{i}\leq t\}}$ et $P(t)=F_{Y}(t)$ avec $F_{Y}$ la fonction de répartition de Y ;
• $X_{t}'=P_{n}'-P$ où $P_{n}'$ est la mesure empirique basée sur une copie des variables précédentes ;
• $\alpha =\varepsilon /2,\beta =1/2$,

on obtient que

$\forall n\geq 8\varepsilon ^{-2},\quad \mathbb {P} \left(\sup _{t\in \mathbb {R} }|P_{n}(t)-P(t)|>\varepsilon \right)\leq 2\mathbb {P} \left(\sup _{t\in \mathbb {R} }|P_{n}(t)-P_{n}'(t)|>{\frac {1}{2}}\varepsilon \right).$

Démonstration

On note $\tau =\tau (\omega )$ un élément de $T$ pour lequel $|X_{\tau }|>\varepsilon$ (i.e. $\omega \in \{\sup _{t\in T}|X_{t}|>\varepsilon \}$). Puisqu'il dépend de $X,\tau$ est indépendant de $X'$ et donc conditionnellement à $X$ il agit comme un élément de $T$ fixé :

$\mathbb {P} \left(|X_{t}'|\leq \alpha |X\right)\geq \beta .$

En intégrant :

${\begin{aligned}\beta \mathbb {P} \left(\sup _{t\in T}|X_{t}|>\varepsilon \right)&\leq \mathbb {P} \left(|X_{\tau }'|\leq \alpha \right)\mathbb {P} \left(|X_{\tau }|>\varepsilon \right)\leq \mathbb {P} \left(|X_{\tau }'|\leq \alpha ,|X_{\tau }|>\varepsilon \right)\\&\leq \mathbb {P} \left(|X_{\tau }-X_{\tau }'|>\varepsilon -\tau \right)\leq \mathbb {P} \left(\sup _{t\in T}|X_{t}-X_{t}'|>\varepsilon -\alpha \right).\end{aligned}}$