mathématiques MPSI · Chapitre 19 · Exercice de TD

La méthode de Chernoff sur la marche aléatoire

Probabilités sur un univers fini · E. Inégalités et concentration · niveau 3 (difficile)

Énoncé

Un marcheur part de $0$ et fait $n$ pas indépendants $X_{1}, \dots, X_{n}$ , chacun valant $+ 1$ ou $- 1$ avec probabilité $\frac{1}{2}$ ; on note $S_{n} = X_{1} + \dots + X_{n}$ sa position finale. On rappelle que $ch$ désigne le cosinus hyperbolique, $ch λ = \frac{e ^{λ} + e ^{- λ}}{2}$ , et $th$ la tangente hyperbolique, $th = \frac{sh}{ch}$ .

1) Pour $λ \in R$ , calculer $E (e^{λ X_{1}})$ et montrer que $ch λ \leq e^{λ^{2} /2}$ (cosinus hyperbolique de $λ$ , majoré par l'exponentielle de $λ^{2} /2$ ). On pourra étudier $g : λ \mapsto \frac{λ ^{2}}{2} - ln ch λ$ .

2) Justifier que $E (e^{λ S_{n}}) = (ch λ)^{n} \leq e^{n λ^{2} /2}$ .

3) Soient $a > 0$ et $λ > 0$ . En appliquant l'inégalité de Markov à la variable positive $e^{λ S_{n}}$ , montrer que $P (S_{n} \geq a) \leq e^{- λa + n λ^{2} /2}$ ; choisir $λ$ pour obtenir $P (S_{n} \geq a) \leq e^{- a^{2} / (2 n)}$ , puis $P (∣ S_{n} ∣ \geq a) \leq 2 e^{- a^{2} / (2 n)}$ .

4) Comparer, pour $a = 10 n$ , à ce que donne l'inégalité de Bienaymé-Tchebychev. Pourquoi l'exponentielle fait-elle tellement mieux que le carré ?

Corrigé de la question 1

La stratégie. L'inégalité de Markov ne demande qu'une variable positive et son espérance. Au lieu de l'appliquer à $S_{n}^{2}$ , ce qui redonne Tchebychev, on l'applique à $e^{λ S_{n}}$ : l'exponentielle transforme la somme en produit, l'indépendance transforme l'espérance du produit en produit des espérances, et l'on garde un paramètre $λ$ libre que l'on optimise à la fin. C'est la méthode de Chernoff.

1) La transformée d'un pas, et son inégalité. Par la formule de transfert, $X_{1}$ prenant les valeurs $1$ et $- 1$ avec probabilité $\frac{1}{2}$ : $E (e^{λ X_{1}}) = \frac{1}{2} e^{λ} + \frac{1}{2} e^{- λ} = ch λ,$ le cosinus hyperbolique de $λ$ .

L'inégalité $ch λ \leq e^{λ^{2} /2}$ . Comme $ch λ > 0$ , elle équivaut, par croissance du logarithme, à $ln ch λ \leq \frac{λ ^{2}}{2}$ , c'est-à-dire à $g (λ) \geq 0$ où $g (λ) = \frac{λ ^{2}}{2} - ln ch λ$ . La fonction $g$ est dérivable sur $R$ , paire (car $ch$ est paire), et $g (0) = 0 - ln 1 = 0$ . Sa dérivée est $g^{'} (λ) = λ - \frac{sh λ}{ch λ} = λ - th λ .$ Il reste à montrer que $th λ \leq λ$ pour $λ \geq 0$ . Posons $h (λ) = λ - th λ$ : $h (0) = 0$ et $h^{'} (λ) = 1 - (1 - th^{2} λ) = th^{2} λ \geq 0$ (la dérivée de la tangente hyperbolique est $1 - th^{2}$ , vue au chapitre des fonctions usuelles). Donc $h$ est croissante sur $R_{+}$ et $h \geq h (0) = 0$ : $th λ \leq λ$ pour $λ \geq 0$ . Ainsi $g^{'} \geq 0$ sur $R_{+}$ , $g$ y est croissante, et $g (λ) \geq g (0) = 0$ pour $λ \geq 0$ . Par parité, $g \geq 0$ sur $R$ tout entier : $ch λ \leq e^{λ^{2} /2} pour tout λ \in R .$ Contrôle. En $λ = 1$ : $ch 1 \approx 1, 5431$ et $e^{1/2} \approx 1, 6487$ . En $λ = 2$ : $ch 2 \approx 3, 7622$ et $e^{2} \approx 7, 389$ . L'inégalité est serrée près de $0$ — les deux fonctions valent $1 + \frac{λ ^{2}}{2} + o (λ^{2})$ — et large ensuite.

Question 2 : comment l'IA t'aide

2) Justifier que $E (e^{λ S_{n}}) = (ch λ)^{n} \leq e^{n λ^{2} /2}$ .

Élève

$e^{λ S_{n}}$ est le produit des $e^{λ X_{i}}$ , donc son espérance est le produit des espérances, c'est-à-dire $(ch λ)^{n}$ . Ça me paraît presque trop rapide.

L'égalité « espérance du produit = produit des espérances » n'est pas gratuite : quelle hypothèse demande-t-elle, et sur quelles variables exactement doit-elle porter ici ?

Élève

Il faut l'indépendance. Les $X_{i}$ sont indépendantes par hypothèse, mais j'applique le résultat aux $e^{λ X_{i}}$ , pas aux $X_{i}$ .

Quel résultat du cours garantit que des fonctions de variables indépendantes restent indépendantes ? Ensuite, pour passer de l'inégalité du 1) à sa puissance $n$ -ième, quelle propriété de $t \mapsto t^{n}$ utilises-tu ?

L'IA ne donne pas la réponse : elle pose la question qui fait avancer. À toi de continuer.

Continue cet exercice avec l'IA

Reprends la question 2 là où le dialogue s'arrête, puis la suite de l'exercice.

Continuer avec l'IA — gratuit, sans inscription

Gratuit, sans inscription. L'IA te guide pas à pas, sans te donner la réponse.

Le cours du chapitre · Tous les exercices du chapitre

Continuer avec l'IA, gratuit →