Préconditionnement

2.9. Préconditionnement#

Cette méthode est aussi connue sous le nom de méthode de Blackwell-Rao. Il s’agit de réduire la variance en utilisant un préconditionnement. Soit $X$ une variable aléatoire et $\mathcal{B}$ une tribu, on rappelle que l’espérance conditionnelle $\mathbf{E}[X | \mathcal{B}]$ est une variable aléatoire $\mathcal{B}$–mesurable. Si l’on sait simuler cette variable aléatoire avec le même coût que $X$ alors on a toujours intérêt à considérer l’estimateur Monte Carlo basé sur la moyenne de réalisations de $\mathbf{E}[X | \mathcal{B}]$ par rapport à l’estimateur MC standard (basé sur la moyenne de réalisations de $X$). La preuve repose sur la proposition suivante, appelée inégalité de Jensen (conditionnelle).

Proposition 2.6 (Inégalité de Jensen)

Soit $X$ une variable aléatoire et $f$ une fonction convexe telle que $\mathbf{E}\big[|f(X)|\big] < +\infty$. Alors pour toute tribu $\mathcal{B}$,

\[\begin{equation*} f\big(\mathbf{E}[X|\mathcal{B}] \big) \le \mathbf{E}[f(X) | \mathcal{B}] \quad p.s. \end{equation*}\]

Si la quantité à calculer est $I = \mathbf{E}[X]$ alors on peut considérer la représentation $I = \mathbf{E}\big[\mathbf{E}[X | \mathcal{B}]\big]$ et si $\mathbf{E}[X|\mathcal{B}]$ est simulable l’estimateur Monte Carlo

\[\begin{equation*} \bar I_n = \frac{1}{n} \sum_{k=1}^n Z_k \quad \text{avec $(Z_k)_{k \ge 1}$ suite i.i.d. de loi $\mathbf{E}[X|\mathcal{B}]$}. \end{equation*}\]

Pour comparer cet estimateur avec l’estimateur standard $I_n = \frac{1}{n} \sum_{k=1}^n X_k$ il suffit de comparer les variances $\operatorname{var}(X)$ et $\operatorname{var}(\mathbf{E}[X|\mathcal{B}])$ et d’après l’inégalité de Jensen on a $\mathbf{E}[X|\mathcal{B}]^2 \le \mathbf{E}[X^2|\mathcal{B}]$ d’où

\[\begin{equation*} \mathbf{E}\big[\mathbf{E}[X | \mathcal{B}]^2\big] \le \mathbf{E}[X^2]. \end{equation*}\]

Un cas classique est de considérer un préconditionnement par rapport à certaines dimensions du problème. Prenons l’exemple suivant: on pose $X = g(Z_1, Z_2)$ avec $Z_1$ et $Z_2$ variables aléatoires indépendantes. On veut calculer $I = \mathbf{E}\big[g(Z_1, Z_2)\big]$ et en préconditionnant par rapport à $Z_2$ on obtient

(2.16)#\[\begin{equation} I = \mathbf{E}\big[\mathbf{E}[g(Z_1, Z_2) | Z_2] \big] = \mathbf{E}[G(Z_2)], \end{equation}\]

avec $G(z) = \mathbf{E}[g(Z_1, z)]$. Si connait la fonction $G$ par une formule fermée ou une bonne approximation numérique alors on sait simuler $G(Z_2)$ et l’estimateur Monte Carlo préconditionné s’écrit alors

\[\begin{equation*} \frac{1}{n} \sum_{k=1}^n G(Z_2^{(k)}) \quad \text{avec $(Z_2^{(k)})_{k \ge 1}$ suite i.i.d. de loi $Z_2$}. \end{equation*}\]

2.10. Stratification#

C’est une méthode particulière de préconditionnement qui est par exemple utilisé dans la théorie des sondages. Soit $X$ une variable aléatoire dans $\mathbf{R}^d$ et $f:\mathbf{R}^d \to \mathbf{R}$ telle que $\mathbf{E}\big[f^2(X)\big] < +\infty$. On souhaite calculer $I = \mathbf{E}[f(X)]$. L’idée de la stratification est de découper $\mathbf{R}^d$ en une partition $(E_i)_{1 \le i \le K}$ de $K$ ensembles $E_i$ appelés strates, et de faire un estimateur Monte Carlo dans chaque strate $E_i$. On suppose donc

\[\begin{equation*} \mathbf{R}^d = E_1 \cup \dots \cup E_K, \quad \forall i \neq j, \, E_i \cap E_j = \emptyset. \end{equation*}\]

Alors on a la représentation

\[\begin{equation*} \begin{split} \mathbf{E}[f(X)] & = \sum_{i=1}^K \mathbf{E}\big[f(X) \mathbf{1}_{X \in E_i}\big], \\ & = \sum_{i=1}^K \mathbf{E}\big[f(X) | X \in E_i\big] \mathbf{P}\big(X \in E_i\big). \end{split} \end{equation*}\]

Pour mettre en oeuvre l’estimateur stratifié, on suppose tout d’abord

on connait $p_i = \mathbf{P}\big(X \in E_i\big)$ pour tout $i \in \{1,\dots, K\}$,
on sait simuler la loi conditionnelle $X|X \in E_i$.

Alors l’estimateur stratifié s’écrit

\[\begin{equation*} \bar I_n = \sum_{i=1}^K I^{(i)}_n p_i \quad \text{avec} \quad I^{(i)}_n = \frac{1}{n_i} \sum_{k=1}^{n_i} f(X^{(i)}_k), \end{equation*}\]

où

les $n_i \ge 1$ représentent le nombre de réalisations par strate et sont à choisir (cf. étude ci-dessous),
pour tout $i \in \{1,\dots,K\}$ la suite $(X^{(i)}_k)_{k \ge 1}$ est i.i.d. de loi $X | X \in E_i$,
les suites $(X^{(i)}_k)_{k \ge 1}$ pour tout $i \in \{1,\dots,K\}$ sont indépendantes.

La variance d’un estimateur stratifié vérifie alors

\[\begin{equation*} \operatorname{var}(\bar I_n) = \sum_{i = 1}^K \frac{\sigma_i^2 p_i^2}{n_i} \quad \text{avec} \quad \sigma_i^2 = \operatorname{var}\big(f(X) | X \in E_i\big). \end{equation*}\]

Si on suppose que le coût de simulation de $X | X \in E_i$ est le même que celui de $X$, comparer l’effort de $I_n$ (estimateur standard) et l’effort de $\bar I_n$ (estimateur stratifié) revient à comparer les variances et à choisir le même nombre total d’itérations $n$ pour l’estimateur standard et $n_1 + \cdots + n_K = n$ pour l’estimateur stratifié. Etant donné $n \ge K$, on choisit alors les $n_i$ qui minimisent $\operatorname{var}(\bar I_n)$ sous la contrainte $\sum_{i=1}^K n_i = n$. Pour résoudre ce problème on considère les $n_i$ comme des variables continues c’est à dire qu’on cherche le vecteur $(n_1, \dots, n_K) \in \mathbf{R}_+^K$ solution de

\[\begin{equation*} \min_{(n_1,\dots, n_K) \in \mathbf{R}_+^K} \psi(n_1, \dots, n_K) \quad \text{sous la contrainte $\phi(n_1, \dots, n_K) = 0$}, \end{equation*}\]

avec $\psi(n_1, \dots, n_K) = \displaystyle \sum_{i=1}^K \frac{\sigma_i^2 p_i^2}{n_i}$ et $\phi(n_1, \dots, n_K) = \displaystyle \sum_{i=1}^K n_i - n$.

Proof. Optimisation via les multiplicateurs de Lagrange. Le vecteur optimal $(n_1^*,\dots, n_K^*)$ du problème de minimisation sous contrainte est le point où les gradients de $\psi$ et $\phi$ sont colinéaires (cf. cours d’optimisation). On calcule donc les gradients

\[\begin{equation*} \nabla \psi(n_1, \dots, n_K) = \begin{pmatrix} \vdots \\ - \frac{p_i^2 \sigma_i^2}{n_i^2} \\ \vdots \end{pmatrix} \quad \text{et} \quad \nabla \phi(n_1, \dots, n_K) = \begin{pmatrix} \vdots \\ 1 \\ \vdots \end{pmatrix}, \end{equation*}\]

et on en déduit la relation de proportionnalité $\exists \lambda > 0$, $n_i^* = \lambda p_i \sigma_i$. Comme $\sum_{i = 1}^K n_i^* = n$ on a $\lambda = n \frac{1}{\sum_{j=1}^K p_j \sigma_j}$.

Proof. Optimisation via Cauchy-Schwartz. Une alternative est d’utiliser l’inégalité de Cauchy-Schwartz en remarquant que

\[\begin{equation*} \Big(\sum_{i=1}^K p_i \sigma_i \Big)^2 = \Big(\sum_{i=1}^K \frac{p_i \sigma_i}{\sqrt{n_i}} \sqrt{n_i}\Big)^2 \le \Big(\sum_{i=1}^K \frac{p_i^2 \sigma_i^2}{n_i}\Big) \Big(\sum_{i=1}^K n_i \Big), \end{equation*}\]

d’où, en utilisant $\sum_{i=1}^K n_i = n$,

\[\begin{equation*} \frac{1}{n} \Big(\sum_{i=1}^K p_i \sigma_i\Big)^2 \le \sum_{i=1}^K \frac{p_i^2 \sigma_i^2}{n_i}. \end{equation*}\]

La variance optimale $\psi(n_1^*, \dots, n_K^*)$ est donc toujours supérieure à $\frac{1}{n} \Big(\sum_{i=1}^K p_i \sigma_i \Big)^2$ et minimale dans le cas d’égalité de l’inégalité de Cauchy-Schwartz c’est à dire lorsque les vecteurs $a_i = \frac{p_i \sigma_i}{\sqrt{n_i^*}}$ et $b_i = \sqrt{n_i^*}$ sont colinéaires.

Remark 2.2 (Choix optimal)

Ainsi le choix optimal $n_i^*$ de réalisations dans la strate $E_i$ dépend du poids relatif de la strate, ce poids étant la probabilité $p_i$ de tomber dans la strate $E_i$ et la variabilité (mesurée via l’écart-type) de $f$ dans cette strate $\sigma_i = \sqrt{\operatorname{var}\big(f(X)|X \in E_i\big)}$. Si on note $\bar I^*_n$ l’estimateur stratifié construit avec ce choix optimal $n_i^*$ on a

(2.17)#\[ n_i^* = \left\lceil n \frac{p_i \sigma_i}{\sum_{j=1}^K p_j \sigma_j} \right\rceil \quad \text{et} \quad \operatorname{var}(\bar I^*_n) \simeq \frac{1}{n} \Big(\sum_{i=1}^K p_i \sigma_i \Big)^2.\]

Remark 2.3 (Choix proportionnel)

En pratique on n’a pas accès aux quantités $\sigma_i$ qui dépendent de la loi $X$ mais aussi de la fonction $f$ (à la différence des $p_i$ qui ne dépendent pas de $f$). Si on suppose que $\sigma_i$ est le même pour toute strate $E_i$ i.e. $\sigma_i = \sigma$ alors le choix optimal vaut $n_i^* = n p_i$. Même si cette hypothèse $\sigma_i = \sigma$ n’est pas vérifiée on peut tout de même considérer ce choix proportionnel $n_i^{\#} = n p_i$ et l’estimateur MC stratifié associé $\bar I^{\#}_n$,

(2.18)#\[ n_i^{\#} = \left\lceil n p_i \right\rceil \quad \text{et} \quad \operatorname{var}(\bar I^{\#}_n) \simeq \frac{1}{n} \sum_{i=1}^K \sigma_i^2 p_i.\]

Proposition 2.7

Les estimateurs stratifiés, l’optimal $\bar I^*_n$ défini en (2.17), et le proportionnel $\bar I^{\#}_n$ défini en (2.18), sont plus efficaces que l’estimateur standard et on a

\[\begin{equation*} \forall n \ge K, \quad \operatorname{var}(\bar I_n^*) \le \operatorname{var}(\bar I_n^{\#}) \le \operatorname{var}(I_n). \end{equation*}\]

Proof. Encore une fois, pour simplifier (sans changer la nature du résultat) on considère les nombres $n_i$ comme des quantités réelles i.e. $n_i^* = n \frac{p_i \sigma_i}{\sum_j p_j \sigma_j}$ et $n_i^{\#} = n p_i$. On vérifie la première inégalité $\operatorname{var}(\bar I_n^*) \le \operatorname{var}(\bar I_n^{\#})$ (vraie car par définition $I_n^*$ est optimal…) en utilisant par exemple l’inégalité de Jensen avec la fonction $x \mapsto x^2$ convexe et $(p_i)_{1 \le i \le K}$ la probabilité discrète.

On vérifie la seconde inégalité. On a $\operatorname{var}(I_n) = \frac{1}{n} \operatorname{var}i\big(f(X)\big)$ et

\[\begin{equation*} \begin{split} \operatorname{var}\big(f(X)\big) &= \mathbf{E}[f^2(X)] - \mathbf{E}[f(X)]^2, \\ & = \sum_{i=1}^K p_i \mathbf{E}[f^2(X)|X \in E_i] - \Big(\sum_{i=1}^K p_i \mathbf{E}[f(X)|X \in E_i] \Big)^2, \\ & = \sum_{i=1}^K p_i \big(\sigma_i^2 + \mathbf{E}[f(X)|X \in E_i]^2\big) - \Big(\sum_{i=1}^K p_i \mathbf{E}[f(X)|X\in E_i] \Big)^2, \\ & \ge \sum_{i=1}^K p_i \sigma_i^2, \end{split} \end{equation*}\]

car $\sum_{i=1}^K p_i m(i)^2 \ge \Big(\sum_{i=1}^K p_i m(i)\Big)^2$ avec $m(i) = \mathbf{E}[f(X)|X \in E_i]$. On a donc prouvé $\operatorname{var}(I_n) \ge \operatorname{var}(\bar I_n^{\#})$.

En résumé, il est toujours efficace de faire une méthode de stratification (que l’on peut voir aussi comme un préconditionnement par rapport à une loi discrète) mais il faut connaitre les $p_i = \mathbf{P}(X \in E_i)$ et savoir simuler selon la loi conditionnelle $X|X \in E_i$ avec le même coût que $X$ (donc sans utiliser de rejet…).

Example 2.1 (Dimension 1.)

Soit $X$ variable aléatoire réelle de fonction de répartition $F$ continue. Etant donné $K \ge 1$, $(p_1, \dots, p_K) \in ]0,1[^K$ avec $p_1 + \cdots + p_K = 1$, on construit les strates $E_i$ de la façon suivante

\[\begin{equation*} E_i = ]a_{i-1}, a_i] \quad \text{avec $a_0 = -\infty$, et pour $1 \le i \le K$, $a_i = F^{-1}\Big(\sum_{j=1}^i p_j \Big)$}. \end{equation*}\]

Il est facile de vérifier que $\mathbf{P}(X \in E_i) = F(a_i) - F(a_{i-1}) = p_i$. Un choix standard est de fixer $p_i = \frac{1}{K}$ et dans ce cas $a_i = F^{-1}\big(\frac{i}{K}\big)$.

La deuxième étape est de simuler selon la loi conditionnelle $X|X\in E_i$ et cela peut se faire par l’inverse de la fonction de répartition. En effet on a

\[\begin{equation*} \forall x \in \mathbf{R}, \quad F_{X|X\in E_i}(x) = \mathbf{P}\big(X \le x | X \in E_i\big) = \begin{cases} 1 & \text{si $x \ge a_i$} \\ 0 & \text{si $x < a_{i-1}$} \\ \frac{F(x) - F(a_{i-1})}{F(a_i) - F(a_{i-1})} & \text{si $a_{i-1} \le x < a_i$}, \end{cases} \end{equation*}\]

et on inverse facilement (à faire !).

Préconditionnement

Contents

2.9. Préconditionnement#

2.10. Stratification#