Mathématiques universitaires — Licence 2 · Bachelor Year 2

22Variables aléatoires discrètes

Les variables aléatoires organisent les calculs de probabilité autour de fonctions plutôt que d’événements. Sur les espaces dénombrables, la théorie repose sur les familles sommables du Chapitre 7 : l’espérance est la somme d’une famille indexée par l’univers, et toutes ses propriétés — linéarité, transfert, formule du produit pour les variables indépendantes — sont des théorèmes sur les familles sommables. Le chapitre démontre les inégalités clés de Markov, de Bienaymé–Tchebychev, de Cauchy–Schwarz et de Jensen, et s’achève sur les lois classiques et la loi faible des grands nombres, dont la preuve tient en deux lignes une fois Tchebychev disponible.

22.1 Variables aléatoires et leurs lois

Définition 22.1 (Variable aléatoire discrète ; loi)

Soit $(\Omega, \P)$ un espace probabilisé dénombrable. Une variable aléatoire est une application $X \colon \Omega \to E$ ( $E$ un ensemble quelconque ; variable aléatoire réelle lorsque $E = \R$ ). Sa loi (ou distribution) est la mesure de probabilité $\P_X$ sur l’ensemble dénombrable $X(\Omega)$ définie par

\P_X(\{x\}) = \P(X = x) = \P\bigl(\{\omega : X(\omega) = x\}\bigr) .

Exemple 22.2 (Les lois classiques)

Bernoulli $\mathcal{B}(p)$ : $X \in \{0, 1\}$ , $\P(X = 1) = p$ . Indicatrice d’un événement.
Binomiale $\mathcal{B}(n, p)$ : $\P(X = k) = \binom nk p^k(1-p)^{n-k}$ , $0 \leq k \leq n$ : nombre de succès dans $n$ épreuves de Bernoulli indépendantes (volume Lycée ; redémontrée plus bas via des sommes de variables indépendantes).
Géométrique $\mathcal{G}(p)$ : $\P(X = k) = (1-p)^{k-1}p$ , $k \in \N^*$ : rang du premier succès (Exemple 21.5).
Poisson $\mathcal{P}(\lambda)$ : $\P(X = k) = e^{-\lambda}\frac{\lambda^k}{k!}$ , $k \in \N$ — une mesure de probabilité par la série exponentielle. La loi des événements rares (Chapitre 23).

Remarque 22.3 (Quelle loi modélise quoi)

Les quatre lois répondent à quatre questions primitives : Bernoulli, « est-ce arrivé ? » ; binomiale, « combien de fois en $n$ essais ? » ; géométrique, « combien de temps jusqu’à la première fois ? » ; Poisson, « combien d’événements à un taux donné, quand les essais sont nombreux et individuellement peu probables ? ». Reconnaître la question, c’est neuf dixièmes de la modélisation : les sommes d’indicatrices désignent la binomiale, les temps d’attente la géométrique, les comptages d’événements rares la Poisson — le passage de la binomiale à la Poisson étant rendu précis par la loi des événements rares au Chapitre 23.

Proposition 22.4 (Absence de mémoire de la loi géométrique)

Si $X \sim \mathcal{G}(p)$ , alors pour tous $m, n \in \N$ :

\P(X > m + n \mid X > m) = \P(X > n) ,

et les lois géométriques sont les seules lois sur $\N^*$ possédant cette propriété.

Démonstration. En sommant les poids géométriques, $\P(X > n) = (1-p)^n$ . Donc

\P(X > m + n \mid X > m) = \frac{\P(X > m + n)}{\P(X > m)} = \frac{(1-p)^{m+n}}{(1-p)^m} = (1-p)^n = \P(X > n).

Réciproquement, si $G(n) = \P(X > n)$ vérifie $G(m + n) = G(m)G(n)$ avec $G(0) = 1$ , alors $G(n) = G(1)^n$ par récurrence ; $q = G(1) \in \intco{0}{1}$ , et $q = 0$ ou bien la loi est $\mathcal{G}(1 - q)$ : $\P(X = k) = G(k-1) - G(k) = q^{k-1}(1 - q)$ . ∎

Exemple 22.5 (Aucun nombre n’est jamais « dû »)

On lance un dé en attendant un six : le temps d’attente est $X \sim \mathcal G(1/6)$ . L’absence de mémoire dit qu’après $10$ lancers infructueux, l’attente restante $X - 10$ , sachant $X > 10$ , est de nouveau $\mathcal G(1/6)$ : l’attente conditionnelle espérée reste $6$ lancers, exactement comme au départ. Le dé ne se souvient pas, et aucun six n’est jamais « dû » — le sophisme du joueur est la croyance que la loi conditionnelle devrait s’être décalée. Réciproquement, la moitié « unicité » de la proposition dit que cette indifférence caractérise les temps d’attente géométriques : tout temps d’attente dont la prévision ne se met jamais à jour est géométrique. Les files d’attente et les durées de vie réelles se mettent généralement à jour, ce qui est précisément la façon de détecter qu’elles ne sont pas géométriques.

22.2 Espérance

Définition 22.6 (Espérance)

Une variable aléatoire réelle $X$ sur $(\Omega, \P)$ admet une espérance si la famille $\bigl(X(\omega)\,\P(\{\omega\})\bigr)_{\omega \in \Omega}$ est sommable (Chapitre 7) ; son espérance est alors

\E(X) = \sum_{\omega \in \Omega} X(\omega)\,\P(\{\omega\}) .

Théorème 22.7 (Théorème de transfert)

$X$ admet une espérance si et seulement si la famille $\bigl(x\,\P(X = x)\bigr)_{x \in X(\Omega)}$ est sommable, et alors

\E(X) = \sum_{x \in X(\Omega)} x\,\P(X = x) .

Plus généralement, pour $f \colon X(\Omega) \to \R$ , la variable $f(X)$ admet une espérance si et seulement si $\sum_x \abs{f(x)}\,\P(X = x) < \infty$ , et alors $\E(f(X)) = \sum_x f(x)\,\P(X = x)$ .

Démonstration. Partitionnons $\Omega$ selon les lignes de niveau $\Omega_x = \{X = x\}$ , $x \in X(\Omega)$ . Par le théorème de sommation par paquets pour les familles sommables (Chapitre 7), la famille $(X(\omega)\P(\{\omega\}))_\omega$ est sommable si et seulement si chaque paquet l’est (automatique : $\sum_{\omega \in \Omega_x}\abs{x}\P(\{\omega\}) = \abs x\,\P(X = x)$ ) et si la famille des sommes des paquets $\bigl(x\,\P(X = x)\bigr)_x$ est sommable — et alors les sommes totales coïncident. Pour $f(X)$ : on applique l’énoncé démontré à la variable $Y = f \circ X$ , dont les lignes de niveau sont $\{Y = y\} = \bigsqcup_{x : f(x) = y}\{X = x\}$ ; une seconde sommation par paquets convertit $\sum_y y\,\P(Y = y)$ en $\sum_x f(x)\,\P(X = x)$ , les paquets regroupant désormais les valeurs $x$ par leur image $f(x)$ , la sommabilité absolue d’une famille étant équivalente à celle de l’autre. ∎

Théorème 22.8 (Propriétés de l’espérance)

Sur l’ensemble des variables aléatoires admettant une espérance :

(Linéarité) $\E(aX + bY) = a\,\E(X) + b\,\E(Y)$ .
(Positivité et monotonie) $X \geq 0 \Rightarrow \E(X) \geq 0$ ; $X \leq Y \Rightarrow \E(X) \leq \E(Y)$ ; et $\abs{\E(X)} \leq \E(\abs X)$ .
(Domination) Si $\abs X \leq Z$ et $Z$ admet une espérance, alors $X$ aussi.

Démonstration. Ce sont toutes des propriétés des sommes de familles sommables (Chapitre 7) : linéarité de la somme, positivité terme à terme, et le critère de domination pour la sommabilité. (Notons que la linéarité est immédiate sur la définition sur $\Omega$ , alors qu’elle serait malaisée sur la formule de transfert — un bénéfice de définir $\E$ en amont.) ∎

Exemple 22.9

$X \sim \mathcal{B}(n, p)$ : en écrivant $X = X_1 + \dots + X_n$ comme somme d’indicatrices de Bernoulli et en utilisant la linéarité, $\E(X) = np$ — sans coefficient binomial. $X \sim \mathcal{G}(p)$ : $\E(X) = \sum_{k\geq1}k(1-p)^{k-1}p = p\cdot\frac{1}{(1 - (1-p))^2} = \frac1p$ , en dérivant la série géométrique à l’intérieur de son disque (Chapitre 11). $X \sim \mathcal{P}(\lambda)$ : $\E(X) = \sum_{k\geq1}k e^{-\lambda}\frac{\lambda^k}{k!} = \lambda e^{-\lambda}\sum_{j\geq0}\frac{\lambda^j}{j!} = \lambda$ .

Exemple 22.10 (Le transfert à l’œuvre)

Pour $X \sim \mathcal P(\lambda)$ , calculons $\E\bigl(\frac1{1+X}\bigr)$ — la loi de $\frac1{1+X}$ elle-même est malaisée, mais le transfert ne la demande jamais :

\E\Bigl(\frac1{1+X}\Bigr) = \sum_{k\geq0}\frac{1}{k+1}\,\eu^{-\lambda} \frac{\lambda^k}{k!} = \frac{\eu^{-\lambda}}{\lambda}\sum_{k\geq0} \frac{\lambda^{k+1}}{(k+1)!} = \frac{\eu^{-\lambda}}{\lambda}\bigl(\eu^\lambda - 1\bigr) = \frac{1 - \eu^{-\lambda}}{\lambda} .

Deux leçons. Sur le plan du calcul : reconnaître une série exponentielle décalée est tout le travail — le transfert réduit les espérances de $f(X)$ à des manipulations de séries. Sur le plan structurel : la valeur naïve par substitution serait $\frac1{1 + \E X} = \frac1{1 + \lambda}$ , et la vraie réponse est plus grande,

\frac{1 - \eu^{-\lambda}}{\lambda} \geq \frac{1}{1 + \lambda},

exactement comme l’exige l’inégalité de Jensen pour la fonction convexe $t \mapsto \frac1{1+t}$ . Les espérances des images convexes se situent au-dessus de la valeur naïve par substitution, et le transfert plus une vérification de série rend concrète l’inégalité abstraite.

Théorème 22.11 (Indépendance et produits)

Deux variables aléatoires $X, Y$ sont indépendantes si $\P(X = x, Y = y) = \P(X = x)\P(Y = y)$ pour tous $x, y$ — de manière équivalente, les événements $\{X \in A\}$ et $\{Y \in B\}$ sont indépendants pour tous $A, B$ . Si $X$ et $Y$ sont des variables réelles indépendantes admettant des espérances, alors $XY$ admet une espérance et

\E(XY) = \E(X)\,\E(Y) .

Démonstration. L’équivalence des deux formulations résulte de la sommation de l’identité ponctuelle sur $(x, y) \in A \times B$ ( $\sigma$ -additivité deux fois). Pour le produit : la famille double $\bigl(xy\,\P(X = x)\P(Y = y)\bigr)_{(x,y)}$ est sommable, car par Fubini pour les familles (Chapitre 7)

\sum_{x, y}\abs x \abs y\,\P(X{=}x)\P(Y{=}y) = \Bigl(\sum_x \abs x \P(X{=}x)\Bigr) \Bigl(\sum_y \abs y \P(Y{=}y)\Bigr) < \infty ;

par indépendance cette famille est exactement $\bigl(xy\,\P(X = x, Y = y)\bigr)$ , dont la somme est $\E(XY)$ par transfert appliqué à la variable $(X, Y) \mapsto xy$ ; Fubini évalue de nouveau la somme non signée comme le produit $\E(X)\E(Y)$ . ∎

Exemple 22.12 (Produits, avec et sans indépendance)

On lance deux dés équilibrés. Si $Y$ est le second dé (indépendant du premier), $\E(XY) = \E(X)\E(Y) = 3.5^2 = 12.25$ . Si au contraire $Y = X$ (le « produit » d’un dé avec lui-même),

\E(X^2) = \frac{1 + 4 + 9 + 16 + 25 + 36}{6} = \frac{91}{6} \approx 15.17 \neq 12.25 :

mêmes lois marginales dans les deux scénarios, lois jointes différentes, espérances des produits différentes. La morale, digne d’être gravée : $\E(XY)$ est une fonctionnelle du couple, non des deux marginales — et l’écart $\E(X^2) - \E(X)^2 \approx 2.92$ est, par König–Huygens, précisément la variance $\frac{35}{12}$ du dé.

22.3 Variance, covariance et les inégalités classiques

Définition 22.13 (Moments, variance)

$X$ admet un moment d’ordre 2 si $X^2$ admet une espérance (alors $X$ aussi, par domination : $\abs X \leq \frac{1 + X^2}{2}$ ). Sa variance et son écart-type sont alors

V(X) = \E\bigl((X - \E(X))^2\bigr) = \E(X^2) - \E(X)^2 , \qquad \sigma(X) = \sqrt{V(X)} ,

(la seconde forme — la formule de König–Huygens — en développant le carré et en utilisant la linéarité :

\E\bigl((X - \E X)^2\bigr) = \E\bigl(X^2 - 2X\,\E X + \E(X)^2\bigr) = \E(X^2) - 2\,\E(X)^2 + \E(X)^2 ,

le terme central utilisant que $\E X$ est une constante). Pour $X, Y$ admettant des moments d’ordre deux, la covariance est

\operatorname{Cov}(X, Y) = \E\bigl((X - \E X)(Y - \E Y)\bigr) = \E(XY) - \E(X)\E(Y) .

Théorème 22.14 (Boîte à outils de la variance)

Pour des variables admettant des moments d’ordre deux :

$V(aX + b) = a^2\,V(X)$ ;
$V(X + Y) = V(X) + V(Y) + 2\operatorname{Cov}(X, Y)$ , et plus généralement

$V\Bigl(\sum_{i=1}^n X_i\Bigr) = \sum_{i=1}^n V(X_i) + 2\sum_{i < j}\operatorname{Cov}(X_i, X_j) ;$
si $X, Y$ sont indépendantes, $\operatorname{Cov}(X, Y) = 0$ (la réciproque est fausse), de sorte que les variances de variables indépendantes s’ajoutent.

Démonstration. 1 et 2 sont des développements de carrés plus la linéarité ; les produits $X_iX_j$ admettent des espérances par Cauchy–Schwarz ci-dessous (ou par $\abs{X_iX_j} \leq \frac{X_i^2 + X_j^2}{2}$ ). 3 est le Théorème 22.11 appliqué aux variables centrées. Un contre-exemple standard à la réciproque : $X$ uniforme sur $\{-1, 0, 1\}$ et $Y = X^2$ sont non corrélées ( $\E(XY) = \E(X^3) = 0 = \E X \cdot \E Y$ ) mais manifestement dépendantes. ∎

Théorème 22.15 (Inégalités de Markov et de Bienaymé–Tchebychev)

(Markov) Si $X \geq 0$ admet une espérance, alors pour tout $a > 0$ :

$\P(X \geq a) \leq \frac{\E(X)}{a} .$
(Tchebychev) Si $X$ admet un moment d’ordre deux, alors pour tout $\varepsilon > 0$ :

$\P\bigl(\abs{X - \E(X)} \geq \varepsilon\bigr) \leq \frac{V(X)}{\varepsilon^2} .$

Démonstration. 1. Ponctuellement, $a\,\mathbf{1}_{X \geq a} \leq X$ (sur l’événement le membre de gauche vaut $a \leq X$ ; en dehors, $0 \leq X$ ). Prenons les espérances : $a\,\P(X \geq a) \leq \E(X)$ par monotonie et $\E(\mathbf{1}_A) = \P(A)$ . 2. Appliquons Markov à la variable positive $(X - \E X)^2$ au niveau $a = \varepsilon^2$ : l’événement $\{(X - \E X)^2 \geq \varepsilon^2\}$ est exactement $\{\abs{X - \E X} \geq \varepsilon\}$ . ∎

Exemple 22.16 (Non corrélées mais soudées ensemble)

On lance deux dés équilibrés, $X$ et $Y$ indépendants, et on pose $S = X + Y$ , $D = X - Y$ . Par bilinéarité de la covariance,

\operatorname{Cov}(S, D) = V(X) - V(Y) + \operatorname{Cov}(Y, X) - \operatorname{Cov}(X, Y) = V(X) - V(Y) = 0 :

somme et différence sont non corrélées. Indépendantes ? Certainement pas : $S = 12$ force $D = 0$ , tandis que $\P(D = 0) = \frac16$ sans conditionnement. La corrélation ne teste que la partie linéaire d’une dépendance ; ici la dépendance est portée par la contrainte que $S$ et $D$ ont la même parité, invisible à la covariance. (Pour ce couple, une covariance nulle a nécessité $V(X) = V(Y)$ : des lois identiques, non l’indépendance, ont fait le travail.)

Exemple 22.17 (Quand Markov est exacte)

L’inégalité de Markov est une égalité précisément lorsque rien n’est gaspillé dans la borne $a\,\mathbf 1_{X\geq a} \leq X$ : la variable doit ne prendre que les valeurs $0$ et $a$ . Concrètement, si $\P(X = a) = \pi$ et $\P(X = 0) = 1 - \pi$ , alors $\E(X) = a\pi$ et

\P(X \geq a) = \pi = \frac{\E(X)}{a} .

Une lecture réaliste : dans une population où la richesse moyenne est $100$ et la richesse vaut soit $0$ soit $10^6$ , la proportion de millionnaires est exactement $10^{-4}$ — la borne de Markov, atteinte exactement par une inégalité maximale. Chaque fois que $X$ s’étale sur des valeurs intermédiaires, la borne est stricte, souvent démesurément ; mais comme le montre le cas extrême, aucune meilleure inégalité ne peut être extraite de la seule moyenne.

Exemple 22.18 (Tchebychev est optimale — sans hypothèses supplémentaires)

Fixons $\varepsilon > 0$ , $q \in \intoc01$ , et soit $X$ prenant les valeurs $\pm\varepsilon$ avec probabilité $\frac q2$ chacune et $0$ avec probabilité $1 - q$ . Alors $\E(X) = 0$ , $V(X) = q\varepsilon^2$ , et

\P\bigl(\abs{X - \E X} \geq \varepsilon\bigr) = q = \frac{V(X)}{\varepsilon^2} :

égalité dans Tchebychev. Ainsi l’inégalité ne peut être améliorée en utilisant seulement la variance — la décroissance en $1/\varepsilon^2$ est le prix exact de l’information d’ordre deux. Une décroissance plus rapide requiert des hypothèses plus fortes : le caractère borné de la variable achète une concentration exponentielle, comme l’Exercice 22.7 le laisse entrevoir et comme le problème du week-end de ce chapitre le développe systématiquement.

Théorème 22.19 (Cauchy–Schwarz et Jensen)

(Cauchy–Schwarz) Si $X, Y$ admettent des moments d’ordre deux, $XY$ admet une espérance et $\E(XY)^2 \leq \E(X^2)\,\E(Y^2)$ ; par conséquent $\operatorname{Cov}(X,Y)^2 \leq V(X)V(Y)$ .
(Jensen) Si $\varphi \colon I \to \R$ est convexe sur un intervalle contenant $X(\Omega)$ , et si $X$ , $\varphi(X)$ admettent des espérances, alors

$\varphi\bigl(\E(X)\bigr) \leq \E\bigl(\varphi(X)\bigr) .$

Démonstration. 1. Sommabilité de $XY$ : $\abs{XY} \leq \frac{X^2 + Y^2}2$ . L’application $(X, Y) \mapsto \E(XY)$ est une forme bilinéaire symétrique positive sur l’espace des variables admettant des moments d’ordre deux, de sorte que l’inégalité de Cauchy–Schwarz abstraite du Chapitre 12 s’applique (positive semi-définie suffit pour l’inégalité). En l’appliquant aux variables centrées, on obtient la borne sur la covariance.

2. D’abord, $m = \E(X)$ appartient à $I$ : $I$ est un intervalle contenant toutes les valeurs de $X$ , et l’espérance est monotone, donc $m$ est compris entre $\inf X(\Omega)$ et $\sup X(\Omega)$ . Par le théorème de la droite d’appui pour les fonctions convexes (Chapitre 8), il existe $\alpha, \beta$ tels que $\varphi(t) \geq \alpha t + \beta$ pour tout $t \in I$ et $\varphi(m) = \alpha m + \beta$ . Alors, ponctuellement sur $\Omega$ , $\varphi(X) \geq \alpha X + \beta$ ; en prenant les espérances,

\E\bigl(\varphi(X)\bigr) \geq \alpha\,\E(X) + \beta = \varphi\bigl(\E(X)\bigr). \qedhere

∎

Exemple 22.20

Jensen avec $\varphi(t) = t^2$ donne $\E(X)^2 \leq \E(X^2)$ — la positivité de la variance ; avec $\varphi(t) = 1/t$ sur $\intoo{0}{\infty}$ : $\frac{1}{\E X} \leq \E\bigl(\frac1X\bigr)$ — la moyenne harmonique est en dessous de la moyenne arithmétique, désormais sous forme aléatoire.

Remarque 22.21 (Pièges courants)

(i) $\E(XY) = \E(X)\E(Y)$ requiert l’indépendance (ou au moins une covariance nulle) : en prenant $Y = X$ on obtient $\E(X^2) \neq \E(X)^2$ dès que $V(X) > 0$ . (ii) De même $V(X + X) = 4V(X)$ , non $2V(X)$ : les variances ne s’ajoutent qu’entre termes indépendants (ou non corrélés). (iii) $\E(f(X))$ n’est pas $f(\E(X))$ ; pour $f$ convexe, Jensen vous indique même la direction de l’erreur, comme à l’Exemple 22.10. (iv) L’existence est une véritable hypothèse : pour la variable de Saint-Pétersbourg $X = 2^K$ avec $\P(K = k) = 2^{-k}$ ( $k \geq 1$ ),

\sum_{k\geq1}2^k\cdot2^{-k} = \sum_{k\geq1}1 = \infty :

$X$ est finie presque sûrement mais n’admet aucune espérance, et aucun prix d’entrée équitable pour le jeu n’existe. La sommabilité dans la définition de $\E$ n’est pas un pédantisme de comptabilité — c’est là que les queues lourdes sont détectées. (v) Enfin, le théorème de transfert exige la sommabilité absolue avant tout réarrangement de la somme sur les valeurs (Chapitre 7).

Exemple 22.22 (Tchebychev sur cent lancers)

Pour $X \sim \mathcal B(100, \frac12)$ : $\E X = 50$ , $V(X) = 25$ . Tchebychev avec $\varepsilon = 6$ :

\P(45 \leq X \leq 55) = \P(\abs{X - 50} < 6) \geq 1 - \frac{25}{36} \approx 0.31 ,

tandis que la somme binomiale exacte donne $\approx 0.73$ . Les $31\%$ garantis sont loin de la vérité, mais ils n’ont requis que la moyenne et la variance — le même certificat s’applique mot pour mot à toute variable de $\E = 50$ , $V = 25$ , aussi exotique soit-elle, et l’Exemple 22.18 montre qu’une telle variable la sature. L’universalité a un prix ; lorsque la loi est authentiquement binomiale, les outils exponentiels du problème du week-end comblent l’essentiel de l’écart.

Exemple 22.23 (La corrélation d’une partie avec son tout)

Pour $X, Y$ indépendantes de même loi, de variance $\sigma^2 > 0$ , à quel point un terme est-il corrélé avec la somme $S = X + Y$ ? Calculons

\operatorname{Cov}(X, S) = \operatorname{Cov}(X, X) + \operatorname{Cov}(X, Y) = \sigma^2 + 0 = \sigma^2, \qquad V(S) = 2\sigma^2,

de sorte que le coefficient de corrélation est

\rho(X, S) = \frac{\operatorname{Cov}(X, S)}{\sigma(X)\,\sigma(S)} = \frac{\sigma^2}{\sigma\cdot\sigma\sqrt2} = \frac{1}{\sqrt2} \approx 0.707 ,

quelle que soit la loi commune — dés, pièces, comptages de Poisson. Avec $n$ termes le même calcul donne $\rho(X_1, S_n) = 1/\sqrt n$ : l’influence de chaque terme individuel sur le total se dilue comme une racine carrée, ce qui est l’ombre corrélationnelle de l’échelle $\sqrt n$ des fluctuations. Cauchy–Schwarz garantit $\abs\rho \leq 1$ toujours ; ici la borne est atteinte exactement dans le cas dégénéré $n = 1$ et décroît de façon prévisible ensuite.

Exemple 22.24 (Inégalité arithmético-géométrique pondérée à partir de Jensen)

Soit $Y$ prenant les valeurs positives $a_1, \dots, a_k$ avec probabilités $\lambda_1, \dots, \lambda_k$ . La fonction $-\ln$ est convexe sur $\intoo0\infty$ , donc Jensen donne $-\ln\E(Y) \leq \E(-\ln Y)$ , c’est-à-dire

a_1^{\lambda_1}a_2^{\lambda_2}\cdots a_k^{\lambda_k} \;\leq\; \lambda_1a_1 + \lambda_2a_2 + \dots + \lambda_ka_k :

l’inégalité arithmético-géométrique pondérée, avec égalité si et seulement si $Y$ est constante. Des poids égaux $\lambda_i = \frac1k$ redonnent l’inégalité arithmético-géométrique classique. La probabilité a discrètement démontré un théorème purement algébrique : choisir une loi de probabilité est juste un procédé comptable pour les combinaisons convexes — le point de vue barycentrique du Chapitre 17 une fois de plus, désormais avec Jensen pour moteur.

22.4 La loi faible des grands nombres

Théorème 22.25 (Loi faible des grands nombres)

Soit $(X_k)_{k \geq 1}$ des variables aléatoires deux à deux indépendantes de même loi, admettant un moment d’ordre deux ; posons $m = \E(X_1)$ et $S_n = X_1 + \dots + X_n$ . Alors pour tout $\varepsilon > 0$ :

\P\Bigl(\,\Bigl|\frac{S_n}{n} - m\Bigr| \geq \varepsilon\Bigr) \;\leq\; \frac{V(X_1)}{n\,\varepsilon^2} \xrightarrow[n \to \infty]{} 0 .

Démonstration. Par linéarité $\E(S_n/n) = m$ ; par le Théorème 22.14 (l’indépendance deux à deux annule les covariances) $V(S_n) = n\,V(X_1)$ , donc $V(S_n/n) = V(X_1)/n$ . L’inégalité de Tchebychev appliquée à $S_n/n$ donne la borne. ∎

Remarque 22.26

C’est le théorème qui relie la probabilité à la fréquence : pour $X_k$ l’indicatrice d’un événement $A$ dans des répétitions indépendantes, $S_n/n$ est la fréquence observée de $A$ , et la loi des grands nombres dit qu’elle se concentre autour de $\P(A)$ au taux $\frac{p(1-p)}{n\varepsilon^2}$ . La loi forte ( $S_n/n \to m$ presque sûrement) est un théorème de la troisième année — sa preuve pour les moments d’ordre quatre est cependant à portée : voir l’Exercice 22.9, qui déroule Borel–Cantelli sur la borne de type Tchebychev. La même estimation de Tchebychev a alimenté la preuve par polynômes de Bernstein du théorème d’approximation de Weierstrass au Chapitre 10 — le lemme de comptage là-bas était la loi faible des grands nombres déguisée.

Exemple 22.27 (Collectionner cinquante vignettes)

Le collectionneur de vignettes de l’Exercice 22.3 avec $n = 50$ jouets distincts : le total espéré est

\E(T_{50}) = 50\,H_{50} = 50\sum_{k=1}^{50}\frac1k \approx 50 \times 4.499 \approx 225

boîtes — quatre fois et demie l’estimation naïve $50$ . La croissance harmonique est toute l’histoire : les premiers $25$ jouets arrivent en environ $50\ln2 \approx 35$ boîtes, tandis que le dernier jouet à lui seul coûte $50$ boîtes en moyenne (une attente géométrique de paramètre $\frac1{50}$ ). Les problèmes de complétion sont dominés par leur fin de partie, ce qui explique pourquoi l’Exercice 22.12 trouve des fluctuations d’ordre $n$ — la taille de cette attente géométrique finale — autour de la moyenne $n\ln n$ .

Exemple 22.28 (Quelle taille doit avoir $n$ ?)

Pour fixer la fréquence observée à $\varepsilon = 0.01$ près de $\P(A)$ avec une confiance de $95\%$ , la borne de Tchebychev exige

\frac{p(1-p)}{n\varepsilon^2} \leq \frac{1}{4n\varepsilon^2} \leq 0.05, \qquad\text{c'est-à-dire}\qquad n \geq \frac{1}{4\cdot0.05\cdot(0.01)^2} = 50\,000 .

La dépendance est brutale en $\varepsilon$ (quadratique) et douce en la confiance (linéaire en $1/\alpha$ ). Ces deux caractéristiques sont des propriétés de la borne, non de la vérité : les inégalités exponentielles du problème du week-end abaissent le prix de la confiance de $1/\alpha$ à $\ln(1/\alpha)$ — la même spécification coûtera environ $18\,500$ échantillons là-bas — tandis que l’échelle $1/\varepsilon^2$ est authentique et inaméliorable. Savoir quelle partie d’une borne est lâche est aussi utile que la borne elle-même.

La loi des grands nombres en image : la loi de S_n/n (dessinée schématiquement) garde son centre m mais se resserre à mesure que n grandit, de sorte que la probabilité en dehors de la bande [m- , m+ ] — les deux queues — tend vers zéro. Tchebychev borne les queues par V(X_1)/(n 2) ; le problème du week-end montre qu’elles sont en fait exponentiellement petites. — La loi des grands nombres en image : la loi de $S_n/n$ (dessinée schématiquement) garde son centre $m$ mais se resserre à mesure que $n$ grandit, de sorte que la probabilité en dehors de la bande $\intcc{m-\varepsilon}{m+\varepsilon}$ — les deux queues — tend vers zéro. Tchebychev borne les queues par $V(X_1)/(n\varepsilon^2)$ ; le problème du week-end montre qu’elles sont en fait exponentiellement petites.

Remarque 22.29 (Perspectives au sein de ce volume)

En aval, tout ce qui précède alimente le Chapitre 23 : l’espérance $\E(t^X)$ d’une fonction astucieuse de $X$ condense la loi entière en une série entière, les moments deviennent des dérivées en $1$ , et des identités de type Wald pour les sommes aléatoires portent la théorie des processus de branchement ; le théorème du produit pour les variables indépendantes devient la multiplicativité des fonctions génératrices. En amont, l’espérance est un barycentre à poids de probabilité (Chapitre 17), l’inégalité de Jensen est la géométrie de la droite d’appui des fonctions convexes (Chapitre 8), et la méthode des moments exponentiels du problème du week-end de ce chapitre est Markov appliquée à $\eu^{tX}$ — une inégalité, améliorée par un bon changement de variable, couvrant trois chapitres.

22.5 Exercices

Exercice 22.1 ★

Calculer $\E(X)$ et $V(X)$ pour $X \sim \mathcal{B}(n, p)$ (via des indicatrices), $X \sim \mathcal{P}(\lambda)$ (montrer $V(X) = \lambda$ ), et $X \sim \mathcal{G}(p)$ (montrer $V(X) = \frac{1-p}{p^2}$ ; utiliser $\E(X(X-1))$ et la dérivée seconde de la série géométrique).

Solution

Solution de Exercice 22.1.

Binomiale : $X = \sum_{i=1}^n X_i$ avec des $X_i$ de Bernoulli indépendantes ; $V(X_i) = \E(X_i^2) - \E(X_i)^2 = p - p^2$ , et les variances de variables indépendantes s’ajoutent (Théorème 22.14) :

\E(X) = np, \qquad V(X) = np(1-p) .

Poisson : $\E\bigl(X(X-1)\bigr) = \sum_{k\geq2}k(k-1)e^{-\lambda}\frac{\lambda^k}{k!} = \lambda^2 e^{-\lambda}\sum_{j\geq0}\frac{\lambda^j}{j!} = \lambda^2$ , donc

V(X) = \E(X^2) - \E(X)^2 = \lambda^2 + \lambda - \lambda^2 = \lambda .

Géométrique ( $q = 1 - p$ ) : en dérivant deux fois $\sum_{k\geq0}q^k = \frac{1}{1-q}$ à l’intérieur du disque (Chapitre 11), $\sum_{k\geq2}k(k-1)q^{k-2} = \frac{2}{(1-q)^3}$ , donc

\E\bigl(X(X-1)\bigr) = pq\sum_{k\geq2}k(k-1)q^{k-2} = \frac{2q}{p^2}, \qquad V(X) = \frac{2q}{p^2} + \frac1p - \frac{1}{p^2} = \frac{q}{p^2} = \frac{1-p}{p^2} .

Exercice 22.2 ★

Soient $X \sim \mathcal{P}(\lambda)$ et $Y \sim \mathcal{P}(\mu)$ indépendantes. Montrer que $X + Y \sim \mathcal{P}(\lambda + \mu)$ (convolution des poids ; formule du binôme), et que la loi conditionnelle de $X$ sachant $X + Y = n$ est binomiale $\mathcal{B}\bigl(n, \frac{\lambda}{\lambda + \mu}\bigr)$ .

Solution

Solution de Exercice 22.2.

Somme : pour $n \in \N$ , par disjonction et indépendance,

\P(X + Y = n) = \sum_{k=0}^n \P(X = k)\P(Y = n - k) = e^{-(\lambda + \mu)}\frac{1}{n!} \sum_{k=0}^n \binom nk \lambda^k\mu^{n-k} = e^{-(\lambda+\mu)}\frac{(\lambda + \mu)^n}{n!}

par la formule du binôme : $X + Y \sim \mathcal{P}(\lambda + \mu)$ . Loi conditionnelle : pour $0 \leq k \leq n$ ,

\P(X = k \mid X + Y = n) = \frac{\P(X = k)\P(Y = n - k)}{\P(X + Y = n)} = \binom nk \Bigl(\frac{\lambda}{\lambda+\mu}\Bigr)^{k} \Bigl(\frac{\mu}{\lambda+\mu}\Bigr)^{n-k} ,

la loi binomiale $\mathcal{B}\bigl(n, \frac{\lambda}{\lambda+\mu}\bigr)$ : étant donné le comptage total, chaque événement « choisit » indépendamment la première source avec probabilité proportionnelle à son taux.

Exercice 22.3 ★

(Collectionneur de vignettes, espérance) Une marque de céréales cache l’un de $n$ jouets distincts, uniformément, dans chaque boîte. Soit $T_n$ le nombre de boîtes nécessaires pour collectionner les $n$ jouets. En écrivant $T_n$ comme une somme de variables géométriques indépendantes (temps pour voir un nouveau jouet quand $k$ manquent encore), montrer

\E(T_n) = n\sum_{k=1}^{n}\frac{1}{k} \sim n\ln n

(équivalent par la comparaison série–intégrale du Chapitre 6).

Solution

Solution de Exercice 22.3.

Lorsque $k$ jouets manquent encore, chaque nouvelle boîte apporte un nouveau jouet avec probabilité $\frac kn$ , indépendamment du passé : le temps d’attente $W_k$ du prochain nouveau jouet est géométrique $\mathcal{G}\bigl(\frac kn\bigr)$ , avec $\E(W_k) = \frac nk$ , et $T_n = W_n + W_{n-1} + \dots + W_1$ (la première boîte donne toujours un nouveau jouet : $W_n = 1$ , cohérent avec $\E = n/n$ ). Par linéarité,

\E(T_n) = \sum_{k=1}^n \frac nk = n\sum_{k=1}^n\frac1k \sim n\ln n ,

en utilisant $\sum_{k\leq n}\frac1k = \ln n + \gamma + o(1)$ (Chapitre 6). Collectionner les derniers jouets est ce qui coûte : la moitié des boîtes va à la dernière poignée.

Exercice 22.4 ★★

Soit $X \geq 0$ à valeurs entières. Démontrer la formule des queues

\E(X) = \sum_{n=1}^{\infty} \P(X \geq n)

(lorsque l’un des deux membres est fini), en écrivant $X = \sum_{n\geq1}\mathbf{1}_{X \geq n}$ et en échangeant les sommations (Fubini pour les familles positives). Retrouver $\E(X) = \frac1p$ pour la loi géométrique.

Solution

Solution de Exercice 22.4.

Ponctuellement, $X(\omega) = \#\{n \geq 1 : X(\omega) \geq n\} = \sum_{n\geq1}\mathbf{1}_{X \geq n}(\omega)$ . La famille double $\bigl(\mathbf{1}_{X \geq n}(\omega)\,\P(\{\omega\})\bigr)_{n, \omega}$ est positive, donc Fubini pour les familles (Chapitre 7) s’applique inconditionnellement : en sommant d’abord en $n$ on obtient $\E(X)$ , en sommant d’abord en $\omega$ on obtient $\sum_n \P(X \geq n)$ ; les deux sont simultanément finies et égales. Pour $X \sim \mathcal{G}(p)$ : $\P(X \geq n) = q^{n-1}$ ( $q = 1-p$ ), donc $\E(X) = \sum_{n\geq1}q^{n-1} = \frac{1}{1 - q} = \frac1p$ .

Exercice 22.5 ★★

(L’échantillonnage sans remise est plus concentré) Une urne contient $N$ boules, dont $M$ blanches. On tire $n \leq N$ boules sans remise et soit $X$ le nombre de blanches (loi hypergéométrique). En utilisant les indicatrices $X = \sum_{i=1}^n Y_i$ avec $Y_i$ le $i$ -ème tirage : montrer que chaque $Y_i$ est de Bernoulli de paramètre $p = M/N$ (symétrie !), en déduire $\E(X) = np$ exactement comme avec remise, et montrer $\operatorname{Cov}(Y_i, Y_j) = -\frac{p(1-p)}{N-1} < 0$ pour $i \neq j$ , d’où $V(X) = np(1-p)\frac{N - n}{N - 1} \leq np(1-p)$ .

Solution

Solution de Exercice 22.5.

Symétrie : la $i$ -ème boule tirée est une boule uniformément aléatoire de l’urne (chacune des $N$ boules a la même probabilité d’atterrir en position $i$ de l’ordre de tirage), donc $\P(Y_i = 1) = \frac MN = p$ et $\E(X) = np$ par linéarité — aucune indépendance nécessaire.

Covariance : pour $i \neq j$ , $\E(Y_iY_j) = \P(\text{les tirages } i, j \text{ sont tous deux blancs}) = \frac{M(M-1)}{N(N-1)}$ (les couples ordonnés de positions distinctes reçoivent un couple ordonné de boules distinctes, uniformément). Donc

\operatorname{Cov}(Y_i, Y_j) = \frac{M(M-1)}{N(N-1)} - \frac{M^2}{N^2} = \frac{M(N - M)}{N^2}\cdot\frac{-1}{N-1} = -\frac{p(1-p)}{N-1} < 0 :

tirer une boule blanche raréfie les blanches pour les autres tirages. Par le Théorème 22.14,

V(X) = np(1-p) + n(n-1)\Bigl(-\frac{p(1-p)}{N-1}\Bigr) = np(1-p)\,\frac{N - n}{N - 1} \leq np(1-p) :

l’échantillonnage sans remise a la même moyenne mais une variance plus petite qu’avec remise (égalité seulement pour $n = 1$ ), les corrélations négatives agissant comme un stabilisateur. Pour $n = N$ la variance s’annule : le comptage est alors déterministe.

Exercice 22.6 ★★

Soit $X$ admettant un moment d’ordre deux. Montrer que $c \mapsto \E\bigl((X - c)^2\bigr)$ est minimale exactement en $c = \E(X)$ , de minimum $V(X)$ . Puis montrer que $\P(X = \E(X)) = 1$ si et seulement si $V(X) = 0$ . (Pour le second point : si $V(X) = 0$ , utiliser Tchebychev avec $\varepsilon = 1/n$ et la continuité monotone, Théorème 21.6.)

Solution

Solution de Exercice 22.6.

En développant autour de $m = \E(X)$ :

\E\bigl((X - c)^2\bigr) = \E\bigl((X - m)^2\bigr) + 2(m - c)\,\E(X - m) + (m - c)^2 = V(X) + (m - c)^2 ,

minimale exactement en $c = m$ de valeur $V(X)$ — l’espérance est le meilleur prédicteur constant en moyenne quadratique.

Si $\P(X = m) = 1$ alors $(X - m)^2$ s’annule avec probabilité $1$ , donc $V(X) = 0$ (la famille définissante a des termes nuls sauf sur un ensemble négligeable). Réciproquement, si $V(X) = 0$ , Tchebychev (Théorème 22.15) donne $\P\bigl(\abs{X - m} \geq \frac1n\bigr) \leq n^2\,V(X) = 0$ pour tout $n$ ; les événements $\bigl\{\abs{X - m} \geq \frac1n\bigr\}$ croissent vers $\{X \neq m\}$ , donc la continuité monotone (Théorème 21.6) donne $\P(X \neq m) = 0$ .

Exercice 22.7 ★★★

(La concentration bat Markov) Soit $S_n \sim \mathcal{B}(n, \frac12)$ (nombre de piles en $n$ lancers équilibrés). Comparer les bornes données par Markov ( $\P(S_n \geq \frac{3n}{4})$ ), par Tchebychev, et par la méthode exponentielle (Chernoff) :

\P\Bigl(S_n \geq \frac{3n}4\Bigr) \leq \E\bigl(e^{tS_n}\bigr)e^{-3nt/4} = \Bigl(\frac{1 + e^t}{2}\Bigr)^n e^{-3nt/4} \quad (t > 0),

et optimiser $t$ pour obtenir une borne exponentiellement petite. (En $t = \ln 3$ : borne $\bigl(2\cdot 3^{-3/4}\bigr)^n \approx (0.877)^n$ .)

Solution

Solution de Exercice 22.7.

$\E(S_n) = \frac n2$ et $V(S_n) = \frac n4$ . Markov : $\P\bigl(S_n \geq \frac{3n}4\bigr) \leq \frac{n/2}{3n/4} = \frac23$ — une borne constante, inutile pour $n$ grand. Tchebychev : l’événement implique $\abs{S_n - \frac n2} \geq \frac n4$ , donc la probabilité est $\leq \frac{n/4}{(n/4)^2} = \frac4n$ — décroît, mais seulement polynomialement. Chernoff : par indépendance, $\E(e^{tS_n}) = \prod_{i=1}^n\E(e^{tX_i}) = \bigl(\frac{1 + e^t}{2}\bigr)^n$ , et Markov appliquée à $e^{tS_n} \geq e^{3nt/4}$ donne, pour tout $t > 0$ ,

\P\Bigl(S_n \geq \frac{3n}4\Bigr) \leq \Bigl(\frac{1 + e^t}{2}\Bigr)^n e^{-3nt/4} = \exp\Bigl(n\bigl(\ln\tfrac{1 + e^t}{2} - \tfrac{3t}4\bigr)\Bigr).

Minimisons l’exposant : $\frac{\dd}{\dd t}\ln\frac{1+e^t}{2} = \frac{e^t}{1 + e^t} = \frac34$ en $e^t = 3$ , c’est-à-dire $t = \ln 3$ , donnant

\P\Bigl(S_n \geq \frac{3n}4\Bigr) \leq \Bigl(\frac{4}{2}\Bigr)^n 3^{-3n/4} = \bigl(2 \cdot 3^{-3/4}\bigr)^n \approx (0.877)^n ,

exponentiellement petite. La hiérarchie Markov $\to$ Tchebychev $\to$ Chernoff est l’échelle standard : chaque barreau applique Markov à une fonction de la variable à croissance plus rapide.

Exercice 22.8 ★★★

(Weierstrass à nouveau, de façon probabiliste) Soit $f \colon [0,1] \to \R$ continue et $S_n \sim \mathcal{B}(n, x)$ . Montrer que le polynôme de Bernstein $B_nf(x) = \sum_{k=0}^n f\bigl(\frac kn\bigr)\binom nk x^k(1-x)^{n-k}$ vaut $\E\bigl[f\bigl(\frac{S_n}{n}\bigr)\bigr]$ , et redémontrer l’estimation $\abs{B_nf(x) - f(x)} \leq \omega_f(\delta) + \frac{2\norm f_\infty}{4n\delta^2}$ du Chapitre 10 dans ce langage probabiliste (découper selon $\bigl|\frac{S_n}{n} - x\bigr| \geq \delta$ et utiliser Tchebychev).

Solution

Solution de Exercice 22.8.

Par le théorème de transfert (Théorème 22.7) appliqué à $f\bigl(\frac{S_n}{n}\bigr)$ avec $S_n \sim \mathcal{B}(n, x)$ :

\E\Bigl[f\Bigl(\frac{S_n}{n}\Bigr)\Bigr] = \sum_{k=0}^n f\Bigl(\frac kn\Bigr)\binom nk x^k(1-x)^{n-k} = B_nf(x) .

Fixons $\delta > 0$ et découpons $\abs{f(S_n/n) - f(x)}$ selon l’événement $D = \bigl\{\abs{\frac{S_n}{n} - x} \geq \delta\bigr\}$ : en dehors de $D$ , la différence est au plus le module de continuité $\omega_f(\delta) = \sup_{\abs{s - t}\leq\delta}\abs{f(s) - f(t)}$ ; sur $D$ , au plus $2\norm f_\infty$ . En prenant les espérances et en utilisant Tchebychev avec $V\bigl(\frac{S_n}{n}\bigr) = \frac{x(1-x)}{n} \leq \frac{1}{4n}$ :

\abs{B_nf(x) - f(x)} \leq \E\,\abs{f(S_n/n) - f(x)} \leq \omega_f(\delta) + 2\norm f_\infty\,\P(D) \leq \omega_f(\delta) + \frac{2\norm f_\infty}{4n\delta^2} .

La continuité uniforme de $f$ sur $[0, 1]$ rend $\omega_f(\delta) \to 0$ : choisir $\delta$ puis $n$ , et $B_nf \to f$ uniformément — le théorème d’approximation de Weierstrass du Chapitre 10, dont le « lemme de comptage » est désormais reconnaissable comme l’inégalité de Tchebychev pour la loi binomiale.

Exercice 22.9 ★★★

(Loi forte sous moments d’ordre quatre) Soit $(X_k)$ indépendantes, identiquement distribuées, centrées ( $\E X_1 = 0$ ), avec $\E(X_1^4) < \infty$ . En développant $\E(S_n^4)$ et en dénombrant les termes survivants (seuls les termes $\E(X_i^4)$ et $\E(X_i^2X_j^2)$ , $i \neq j$ ), montrer $\E(S_n^4) \leq C n^2$ pour une constante $C$ . En déduire $\sum_n \P\bigl(\abs{S_n/n} \geq \varepsilon\bigr) < \infty$ pour tout $\varepsilon > 0$ (Markov à l’ordre 4) et conclure avec Borel–Cantelli (Théorème 21.25) que $S_n/n \to 0$ presque sûrement selon une formulation adéquate : l’événement $\bigcap_{j}\bigcup_N\bigcap_{n \geq N}\{\abs{S_n/n} < \frac1j\}$ a pour probabilité $1$ .

Solution

Solution de Exercice 22.9.

Développons $S_n^4 = \sum_{i,j,k,l}X_iX_jX_kX_l$ et prenons les espérances. Par indépendance et centrage, tout terme contenant un indice apparaissant exactement une fois s’annule ( $\E(X_i) = 0$ se factorise). Termes survivants : les $n$ termes diagonaux $\E(X_i^4)$ , et les termes appariant deux paires d’indices égaux, $\E(X_i^2X_j^2) = \E(X_1^2)^2$ pour $i \neq j$ , apparaissant $3n(n-1)$ fois : choisir la paire non ordonnée de valeurs ( $\binom n2$ façons), puis les $\frac{4!}{2!\,2!} = 6$ façons de les placer dans les quatre emplacements — $6\binom n2 = 3n(n-1)$ . Donc, avec $\E(X_1^2)^2 \leq \E(X_1^4)$ (Jensen ou Cauchy–Schwarz),

\E(S_n^4) = n\,\E(X_1^4) + 3n(n-1)\,\E(X_1^2)^2 \leq C n^2, \qquad C = 4\,\E(X_1^4) .

Markov à l’ordre 4 :

\P\Bigl(\Bigl|\frac{S_n}{n}\Bigr| \geq \varepsilon\Bigr) = \P\bigl(S_n^4 \geq n^4\varepsilon^4\bigr) \leq \frac{Cn^2}{n^4\varepsilon^4} = \frac{C}{n^2\varepsilon^4} ,

une série sommable. Par Borel–Cantelli 1 (Théorème 21.25), pour chaque $j$ l’événement $B_j = \limsup_n\bigl\{\abs{S_n/n} \geq \frac1j\bigr\}$ a pour probabilité $0$ , donc $\P\bigl(\bigcup_j B_j\bigr) = 0$ par sous-additivité dénombrable. Sur le complémentaire — de probabilité $1$ — pour tout $j$ il existe $N$ tel que $\abs{S_n/n} < \frac1j$ pour tout $n \geq N$ : précisément $S_n/n \to 0$ . La loi forte des grands nombres est vraie sous un moment d’ordre quatre ; en retirer cette hypothèse (théorème de Kolmogorov) relève de la troisième année.

Exercice 22.10 ★

On lance deux dés équilibrés ; soit $M$ le plus grand des deux résultats. En utilisant la formule des queues de l’Exercice 22.4 (version finie), montrer

\E(M) = \sum_{k=1}^{6}\P(M \geq k) = 6 - \sum_{j=0}^5\Bigl(\frac j6\Bigr)^2 = \frac{161}{36} \approx 4.47 .

Solution

Solution de Exercice 22.10.

$\P(M \leq k) = \bigl(\frac k6\bigr)^2$ (les deux dés valent au plus $k$ , indépendamment), donc $\P(M \geq k) = 1 - \bigl(\frac{k-1}6\bigr)^2$ et

\E(M) = \sum_{k=1}^6\P(M \geq k) = 6 - \frac{0 + 1 + 4 + 9 + 16 + 25}{36} = 6 - \frac{55}{36} = \frac{161}{36} \approx 4.47 ,

confortablement au-dessus de la moyenne $3.5$ d’un seul dé, comme un maximum se doit de l’être.

Exercice 22.11 ★★

Soit $F_n$ le nombre de points fixes d’une permutation uniformément aléatoire de $\{1, \dots, n\}$ ( $n \geq 2$ ). En écrivant $F_n = \sum_i\mathbf 1_{\sigma(i) = i}$ , calculer $\E(F_n) = 1$ , $\operatorname{Cov}(\mathbf 1_{\sigma(i)=i}, \mathbf 1_{\sigma(j)=j}) = \frac1{n^2(n-1)}$ pour $i \neq j$ , et conclure $V(F_n) = 1$ : en moyenne une lettre est fixée, avec une variance exactement égale à $1$ , quel que soit $n$ .

Solution

Solution de Exercice 22.11.

Avec $I_i = \mathbf 1_{\sigma(i) = i}$ : $\P(\sigma(i) = i) = \frac{(n-1)!}{n!} = \frac1n$ , donc $\E(F_n) = n\cdot\frac1n = 1$ . Pour $i \neq j$ : $\P(\sigma(i) = i, \sigma(j) = j) = \frac{(n-2)!}{n!} = \frac1{n(n-1)}$ , d’où

\operatorname{Cov}(I_i, I_j) = \frac1{n(n-1)} - \frac1{n^2} = \frac{1}{n^2(n-1)} .

Par la boîte à outils de la variance (Théorème 22.14),

V(F_n) = n\cdot\frac1n\Bigl(1 - \frac1n\Bigr) + n(n-1)\cdot\frac1{n^2(n-1)} = 1 - \frac1n + \frac1n = 1 .

Moyenne $1$ , variance $1$ , indépendantes de $n$ — cohérent avec la limite de Poisson du problème des rencontres (Exercice 21.5).

Exercice 22.12 ★★★

(Collectionneur de vignettes, concentration) Dans le cadre de l’Exercice 22.3, montrer

V(T_n) = \sum_{k=1}^n\frac{1 - k/n}{(k/n)^2} \leq n^2\sum_{k=1}^n\frac{1}{k^2} \leq \frac{\pi^2}{6}n^2,

en utilisant l’indépendance des étapes géométriques et $V(\mathcal G(p)) = \frac{1-p}{p^2}$ (Exercice 22.1 ; la valeur $\pi^2/6$ est l’Exemple 14.12). En déduire avec Tchebychev que $\dfrac{T_n}{n\ln n} \to 1$ en probabilité : le temps total du collectionneur est $n\ln n$ à des fluctuations d’ordre $n$ près.

Solution

Solution de Exercice 22.12.

$T_n = \sum_{k=1}^nG_k$ où $G_k \sim \mathcal G(k/n)$ est le temps pour voir un nouveau jouet quand $k$ manquent, les étapes étant indépendantes. Donc

V(T_n) = \sum_{k=1}^n\frac{1 - k/n}{(k/n)^2} \leq \sum_{k=1}^n\frac{n^2}{k^2} \leq \frac{\pi^2}6\,n^2 ,

par l’Exemple 14.12. Avec $\E(T_n) = nH_n$ , $H_n = \sum_1^n\frac1k$ (Exercice 22.3), Tchebychev donne, pour $\varepsilon > 0$ ,

\P\bigl(\abs{T_n - nH_n} \geq \varepsilon\,n\ln n\bigr) \leq \frac{\pi^2n^2/6}{\varepsilon^2n^2\ln^2 n} = \frac{\pi^2}{6\,\varepsilon^2\ln^2n} \xrightarrow[n\to\infty]{} 0 .

Puisque $H_n \sim \ln n$ , diviser par $n\ln n$ montre que $T_n/(n\ln n) \to 1$ en probabilité : les fluctuations de $T_n$ sont d’ordre $n$ , négligeables devant la moyenne $n\ln n$ .

22.6 Problème : la boîte à outils de la concentration, de Markov à Hoeffding

Problème 22.1

Problème du week-end — la concentration exponentielle à la main, et combien de personnes un sondage doit interroger

L’inégalité de Markov coûte un moment et achète une décroissance en $1/a$ ; Tchebychev coûte deux moments et achète $1/\varepsilon^2$ — et l’Exemple 22.18 montre que c’est tout ce que ces moments peuvent acheter. Ce problème gravit le reste de l’échelle : la méthode exponentielle (Chernoff) avec son taux exact pour les lancers de pièce, l’inégalité de Hoeffding pour toutes les variables bornées, et le gain — des tailles d’échantillon explicites et honnêtes pour les sondages, les annonces d’élections et les tests de pièce. Tout au long, $S_n \sim \mathcal B(n, p)$ est une somme de $n$ variables de Bernoulli indépendantes et $\widehat p_n = S_n/n$ la fréquence empirique.

Partie I — Calibrage sur la pièce équilibrée. Ici $p = \frac12$ et $a \in \intoo{\frac12}{1}$ .

Markov au niveau $an$ : montrer $\P(S_n \geq an) \leq \frac1{2a}$ , une borne qui ne tend même pas vers $0$ . Où Markov perd-il autant ?
Tchebychev : en utilisant la symétrie de la binomiale équilibrée autour de $n/2$ , montrer

$\P(S_n \geq an) = \tfrac12\, \P\bigl(\abs{S_n - \tfrac n2} \geq n(a - \tfrac12)\bigr) \leq \frac{1}{8n(a - 1/2)^2},$

c’est-à-dire $\frac2n$ en $a = \frac34$ : une décroissance polynomiale enfin.
(Chernoff, niveau général) Calculer $\E(\eu^{tS_n}) = \bigl(\frac{1 + \eu^t}2\bigr)^n$ et optimiser $\P(S_n \geq an) \leq \E(\eu^{tS_n})\eu^{-tan}$ sur $t > 0$ : montrer que le $t$ optimal est $\ln\frac{a}{1-a}$ et

$\P(S_n \geq an) \leq \eu^{-n\,I(a)}, \qquad I(a) = \ln 2 + a\ln a + (1-a)\ln(1-a) > 0 .$

Vérifier que $a = \frac34$ redonne la borne $\bigl(2\cdot3^{-3/4}\bigr)^n$ de l’Exercice 22.7.
(L’exposant est exact) Soit $k = an$ un entier. À partir du fait que $\binom nk a^k(1-a)^{n-k}$ est le plus grand des $n + 1$ termes d’une loi de probabilité, démontrer $\binom nk \geq \frac{\eu^{nH(a)}}{n+1}$ avec $H(a) = -a\ln a - (1-a)\ln(1-a)$ , et en déduire la borne inférieure correspondante

$\P(S_n \geq an) \geq \binom{n}{an}2^{-n} \geq \frac{\eu^{-n\,I(a)}}{n + 1} .$
Tabuler les trois bornes en $n = 100$ , $a = \frac34$ : Markov $\frac23$ , Tchebychev $0.02$ , Chernoff $\approx 2.1\cdot10^{-6}$ (la vraie valeur est $\approx 2.8\cdot10^{-7}$ ). Morale, en une phrase ?

Partie II — L’inégalité de Hoeffding.

(Cas de Rademacher) Pour $\varepsilon = \pm1$ avec probabilité $\frac12$ chacune, démontrer

$\E(\eu^{t\varepsilon}) = \cosh t \leq \eu^{t^2/2} \qquad (t \in \R)$

en comparant les deux séries terme à terme ( $(2k)! \geq 2^kk!$ ).
En déduire, pour des variables de Rademacher indépendantes $\varepsilon_1, \dots, \varepsilon_n$ et tout $s > 0$ :

$\P\Bigl(\sum_{i=1}^n\varepsilon_i \geq s\Bigr) \leq \eu^{-s^2/(2n)} .$
Traduire pour des pièces équilibrées ( $X_i = \frac{1+\varepsilon_i}2$ ) : $\P\bigl(\widehat p_n - \tfrac12 \geq \delta\bigr) \leq \eu^{-2n\delta^2}$ , et la version bilatérale avec un facteur $2$ .
(Lemme de Hoeffding) Soit $X \in \intcc01$ avec $\E X = p$ , et $\psi(t) = \ln\E(\eu^{tX})$ . Justifier que $\psi$ est deux fois dérivable avec

$\psi''(t) = \E_t(X^2) - \E_t(X)^2, \qquad \E_t(Y) := \frac{\E(Y\eu^{tX})}{\E(\eu^{tX})},$

une variance d’une variable repondérée prenant toujours ses valeurs dans $\intcc01$ ; la borner par $\frac14$ (argument de minimalité de l’Exercice 22.6) et conclure par Taylor :

$\E\bigl(\eu^{t(X - p)}\bigr) \leq \eu^{t^2/8} .$
(Inégalité de Hoeffding) Pour des $X_i \in \intcc01$ indépendantes de moyenne commune $p$ , en déduire

$\P\bigl(\abs{\widehat p_n - p} \geq \delta\bigr) \leq 2\,\eu^{-2n\delta^2} \qquad (\delta > 0).$
Comparer le taux de Tchebychev $\frac{p(1-p)}{n\delta^2}$ avec celui de Hoeffding $2\eu^{-2n\delta^2}$ : quelle hypothèse chacun requiert-il, et à partir de quel $n$ (approximativement) la borne exponentielle l’emporte-t-elle en $\delta = 0.03$ , $p = \frac12$ ?

Partie III — Combien de personnes un sondage doit-il interroger ? Un sondage interroge $n$ électeurs indépendants, choisis uniformément ; chacun répond honnêtement ; $p$ est le vrai score, $\widehat p_n$ le chiffre du sondage.

Montrer que le sondage est précis à $\pm\delta$ près avec confiance $1 - \alpha$ (c’est-à-dire $\P(\abs{\widehat p_n - p} \geq \delta) \leq \alpha$ ) dès que

$n \;\geq\; \frac{\ln(2/\alpha)}{2\,\delta^2} .$
Calculer le $n$ requis pour la spécification standard « trois points, quatre-vingt-quinze pour cent » ( $\delta = 0.03$ , $\alpha = 0.05$ ) : $n \geq 2050$ ; et pour un point : $n \geq 18\,445$ . Observer — et expliquer — le fait frappant que la réponse ne fait pas intervenir la taille de la population.
Refaire la question 13 avec Tchebychev ( $V(X_1) = p(1-p) \leq \frac14$ ) : $n \geq \frac1{4\alpha\delta^2} = 5556$ à trois points. Noter que l’échantillonnage sans remise ne fait qu’aider (Exercice 22.5 : la variance se réduit d’un facteur $\frac{N-n}{N-1}$ ).
(Annoncer une élection) Le vrai score d’un candidat est $p = 0.52$ . Combien d’électeurs doit-on sonder pour que $\P(\widehat p_n \leq \tfrac12) \leq 0.01$ ? Montrer $n \geq \frac{\ln 100}{2\cdot(0.02)^2} \approx 5757$ — annoncer une course serrée coûte bien plus que d’estimer un score.
Ce que les mathématiques ne couvrent pas : énumérer les hypothèses de modélisation utilisées (échantillonnage uniforme indépendant, réponses honnêtes, $p$ fixe), et expliquer en un court paragraphe pourquoi les erreurs réelles de sondage sont dominées par le biais (échantillonnage non uniforme, non-réponse), qu’aucune augmentation de $n$ ne réduit.

Partie IV — Plus fin et moins cher.

(Médiane des moyennes : décroissance exponentielle à partir de deux moments) Répartir un budget de $km$ échantillons en $k$ groupes indépendants de $m$ ; soient $\widehat p^{(1)}, \dots, \widehat p^{(k)}$ les moyennes de groupe et $M$ leur médiane. Choisir $m$ pour que chaque groupe satisfasse $\P(\abs{\widehat p^{(i)} - p} \geq \delta) \leq \frac18$ (Tchebychev : $m \geq \frac2{\delta^2}$ suffit). Montrer que si $\abs{M - p} \geq \delta$ alors au moins $k/2$ groupes se trompent, et en déduire

$\P(\abs{M - p} \geq \delta) \leq \binom{k}{\lceil k/2\rceil}\Bigl(\frac18 \Bigr)^{k/2} \leq 2^k\cdot 8^{-k/2} = 2^{-k/2} :$

une concentration exponentielle n’utilisant rien de plus que des variances.
(Paley–Zygmund) Pour $X \geq 0$ admettant un moment d’ordre deux, démontrer $\P(X > 0) \geq \dfrac{\E(X)^2}{\E(X^2)}$ (Cauchy–Schwarz sur $X\mathbf 1_{X>0}$ ) : l’outil de sens inverse — les moments peuvent aussi forcer des événements à se produire.
(Pinsker allégée) Montrer $I(a) \geq 2\bigl(a - \tfrac12\bigr)^2$ sur $\intoo{\frac12}1$ (la différence s’annule à l’ordre deux en $\frac12$ et sa dérivée seconde est $\frac1{a(1-a)} - 4 \geq 0$ ) : l’exposant exact de Chernoff bat toujours celui, quadratique, de Hoeffding.
Développer $I\bigl(\tfrac12 + \delta\bigr) = 2\delta^2 + O(\delta^4)$ et combiner avec la question 4 : pour de petites déviations l’exposant de Hoeffding $2n\delta^2$ est asymptotiquement exact — aucune méthode ne peut le battre de plus que des facteurs polynomiaux.
Dresser le tableau de la boîte à outils : pour Markov, Tchebychev, la borne d’ordre quatre de l’Exercice 22.9, Hoeffding, et Chernoff avec exposant $I$ , énoncer en une ligne chacun : hypothèse requise, décroissance obtenue, et la question de ce problème où elle a été la plus fine.

Partie V — Dividendes.

(Tester une pièce) Une pièce est soit équilibrée, soit biaisée avec $p = 0.55$ . On la lance $n$ fois et on déclare « biaisée » quand $\widehat p_n > 0.525$ . Montrer que les deux probabilités d’erreur sont au plus $\eu^{-2n(0.025)^2}$ , et que $n \geq 3685$ lancers garantissent qu’elles sont toutes deux sous $1\%$ .
(Les événements rares ont besoin d’une borne consciente de la variance) Soit $p = 0.01$ et prenons la spécification relative $\delta = p/2 = 0.005$ , $\alpha = 0.05$ . Comparer les tailles d’échantillon exigées par Hoeffding ( $n \approx 74\,000$ ) et par Tchebychev avec la vraie variance $p(1-p)$ ( $n \approx 7920$ ) : la borne exponentielle aveugle à la variance perd face au humble moment d’ordre deux. Énoncer la morale, et d’où viendra l’outil manquant (une borne exponentielle consciente de la variance ; l’approximation de Poisson du Chapitre 23).
(Loi forte pour les pièces) À partir de $\sum_n 2\eu^{-2n\delta^2} < \infty$ et de Borel–Cantelli (Théorème 21.25), démontrer que $\widehat p_n \to p$ presque sûrement pour des lancers de pièce indépendants : formuler l’événement presque sûr comme $\bigcap_j\bigcup_N\bigcap_{n\geq N} \{\abs{\widehat p_n - p} < \tfrac1j\}$ comme à l’Exercice 22.9, et conclure. (Le caractère borné remplace le moment d’ordre quatre utilisé là-bas.)
Synthèse. En cinq phrases : ce que chaque barreau de l’échelle (moments un, deux, quatre ; exponentielle bornée ; exposant exact) coûte et achète ; pourquoi sonder $2050$ personnes suffit pour un pays de n’importe quelle taille ; et laquelle de ces bornes le volume de troisième année affinera en les constantes exactes du théorème central limite.

Solution

Solution de Problème 22.1.

1. $\E(S_n) = \frac n2$ et Markov (Théorème 22.15) donnent $\P(S_n \geq an) \leq \frac{n/2}{an} = \frac1{2a}$ . Markov ne connaît que la moyenne : il ne peut distinguer une variable concentrée en $n/2$ d’une variable étalée entre $0$ et $n$ , de sorte qu’il tarife la queue comme si toute la masse pouvait s’y trouver.

2. La binomiale équilibrée est symétrique autour de $n/2$ ( $S_n$ et $n - S_n$ ont la même loi), donc avec $x = n(a - \frac12) > 0$ les deux événements $\{S_n - \frac n2 \geq x\}$ et $\{S_n - \frac n2 \leq -x\}$ sont disjoints et équiprobables : $\P(S_n \geq an) = \frac12\P(\abs{S_n - \frac n2} \geq x)$ . Tchebychev avec $V(S_n) = \frac n4$ :

\P(S_n \geq an) \leq \frac12\cdot\frac{n/4}{n^2(a - 1/2)^2} = \frac1{8n(a - 1/2)^2},

soit $\frac2n$ en $a = \frac34$ .

3. Par indépendance et le théorème du produit, $\E(\eu^{tS_n}) = \bigl(\E \eu^{tX_1}\bigr)^n = \bigl(\frac{1 + \eu^t}2\bigr)^n$ . Markov appliquée à $\eu^{tS_n}$ :

\P(S_n \geq an) \leq \eu^{-tan}\Bigl(\frac{1 + \eu^t}2\Bigr)^{\!n} = \exp\Bigl(n\bigl(\ln\tfrac{1 + \eu^t}2 - ta\bigr)\Bigr).

La dérivée de l’exposant en $t$ est $\frac{\eu^t}{1 + \eu^t} - a$ , s’annulant en $\eu^t = \frac a{1-a}$ , c’est-à-dire $t^* = \ln\frac a{1-a} > 0$ ; là $\frac{1 + \eu^{t^*}}2 = \frac1{2(1-a)}$ et l’exposant vaut

n\Bigl(-\ln 2 - \ln(1-a) - a\ln\frac a{1-a}\Bigr) = -n\bigl(\ln2 + a\ln a + (1-a)\ln(1-a)\bigr) = -n\,I(a),

avec $I(\frac12) = 0$ et $I'(a) = \ln\frac a{1-a} > 0$ sur $\intoo{\frac12}1$ : $I(a) > 0$ . En $a = \frac34$ : $\eu^{-I(3/4)} = \frac12(\tfrac34)^{-3/4}(\tfrac14)^{-1/4} = 2\cdot3^{-3/4}$ , la borne de l’Exercice 22.7.

4. Les $n + 1$ nombres $\binom nja^j(1-a)^{n-j}$ somment à $1$ , et le plus grand est celui en $j = k = an$ (le mode de $\mathcal B(n, a)$ est $\floor{(n+1)a} = k$ ici). Un maximum de $n + 1$ nombres sommant à $1$ vaut au moins $\frac1{n+1}$ :

\binom nk a^k(1-a)^{n-k} \geq \frac1{n+1} \quad\Longrightarrow\quad \binom nk \geq \frac{a^{-an}(1-a)^{-n(1-a)}}{n+1} = \frac{\eu^{nH(a)}}{n+1}.

Donc $\P(S_n \geq an) \geq \binom{n}{an}2^{-n} \geq \eu^{n(H(a) - \ln2)}/(n+1) = \eu^{-nI(a)}/(n+1)$ : à un facteur polynomial $n + 1$ près, l’exposant de Chernoff est la vérité.

5. $n = 100$ , $a = \frac34$ : Markov $\frac23$ ; Tchebychev $\frac2{100} = 0.02$ ; Chernoff $(2\cdot3^{-3/4})^{100} = \eu^{-100\,I(3/4)} \approx 2.1\cdot10^{-6}$ , contre l’exact $2.8\cdot10^{-7}$ . Morale : chaque moment d’information divise la borne polynomialement ; le moment exponentiel change sa nature.

6. $\cosh t = \sum_{k\geq0}\frac{t^{2k}}{(2k)!}$ et $\eu^{t^2/2} = \sum_{k\geq0}\frac{t^{2k}}{2^kk!}$ ; la propriété résulte terme à terme de $(2k)! \geq 2^kk!$ , qui est vraie par récurrence : $(2k)! = 2k(2k-1)\cdot(2k-2)! \geq 2k\cdot 2^{k-1}(k-1)! = 2^kk!\cdot(2k-1) \geq 2^kk!$ .

7. Par indépendance, $\E\bigl(\eu^{t\sum\varepsilon_i} \bigr) = (\cosh t)^n \leq \eu^{nt^2/2}$ , donc Markov donne $\P(\sum\varepsilon_i \geq s) \leq \eu^{nt^2/2 - ts}$ ; en minimisant en $t = s/n$ on obtient $\eu^{-s^2/(2n)}$ .

8. Avec $X_i = \frac{1 + \varepsilon_i}2$ , $\widehat p_n - \frac12 = \frac1{2n}\sum\varepsilon_i$ , donc $\{\widehat p_n - \frac12 \geq \delta\} = \{\sum\varepsilon_i \geq 2n\delta\}$ et la question 7 donne la borne $\eu^{-(2n\delta)^2/(2n)} = \eu^{-2n\delta^2}$ . L’événement symétrique a la même borne, d’où le facteur $2$ pour $\abs{\widehat p_n - \frac12} \geq \delta$ .

9. $\E(\eu^{tX}) = \sum_x\eu^{tx}\P(X = x)$ est une série de fonctions lisses de $t$ dont les dérivées terme à terme sont dominées, sur tout intervalle compact en $t$ , par $\eu^{\abs t}\P(X = x)$ (car $0 \leq x \leq 1$ ) : par le théorème de dérivation pour les séries normalement convergentes (Théorème 10.7) elle est deux fois dérivable, et la règle du quotient donne $\psi' = \E_t(X)$ et $\psi'' = \E_t(X^2) - \E_t(X)^2$ , où $\E_t$ est l’espérance pour les poids repondérés $\eu^{tx}\P(X{=}x)/\E(\eu^{tX})$ — positifs, sommant à $1$ , portés par les mêmes valeurs $x \in \intcc01$ . Une variance d’une variable à valeurs dans $\intcc01$ est au plus $\frac14$ : par l’Exercice 22.6, elle vaut $\min_c\E_t((X - c)^2) \leq \E_t\bigl((X - \tfrac12)^2\bigr) \leq \tfrac14$ . Taylor avec reste intégral, en utilisant $\psi(0) = 0$ , $\psi'(0) = p$ :

\psi(t) = tp + \int_0^t(t - s)\,\psi''(s)\,\dd s \leq tp + \frac{t^2}2\cdot\frac14,

c’est-à-dire $\E(\eu^{t(X - p)}) \leq \eu^{t^2/8}$ pour tout $t$ réel.

10. Par indépendance, $\E\bigl(\eu^{t(S_n - np)}\bigr) \leq \eu^{nt^2/8}$ ; Markov et l’optimisation $t = 4\delta$ donnent

\P(\widehat p_n - p \geq \delta) \leq \eu^{nt^2/8 - tn\delta}\Big|_{t = 4\delta} = \eu^{-2n\delta^2};

en appliquant ceci aux variables $1 - X_i$ (également dans $\intcc01$ ) on borne l’autre queue, d’où le $2\eu^{-2n\delta^2}$ bilatéral.

11. Tchebychev ne requiert qu’un moment d’ordre deux et donne $\frac{p(1-p)}{n\delta^2}$ ; Hoeffding requiert le caractère borné et donne $2\eu^{-2n\delta^2}$ . En $p = \frac12$ , $\delta = 0.03$ : les bornes sont $\frac{278}{n}$ (approximativement) contre $2\eu^{-0.0018n}$ ; elles se croisent vers $n \approx 1200$ , après quoi la borne exponentielle l’emporte, et démesurément ( $n = 5000$ : $0.056$ contre $2.5\cdot10^{-4}$ ).

12. Par Hoeffding (question 10), $\P(\abs{\widehat p_n - p} \geq \delta) \leq 2\eu^{-2n\delta^2} \leq \alpha$ dès que $2n\delta^2 \geq \ln\frac2\alpha$ , c’est-à-dire $n \geq \frac{\ln(2/\alpha)}{2\delta^2}$ .

13. $\delta = 0.03$ , $\alpha = 0.05$ : $n \geq \frac{\ln 40}{2\cdot0.0009} \approx 2049.4$ : $2050$ personnes. Pour $\delta = 0.01$ : $n \geq \frac{\ln40}{0.0002} \approx 18\,445$ . La taille de la population n’apparaît jamais parce que chaque électeur échantillonné est modélisé comme un nouveau tirage Bernoulli $(p)$ : la difficulté du sondage est la variance d’une pièce, non la taille du pays. Diviser la marge par deux coûte quatre fois l’échantillon — la loi en $1/\delta^2$ .

14. Tchebychev : $\P(\abs{\widehat p_n - p} \geq \delta) \leq \frac{p(1-p)}{n\delta^2} \leq \frac1{4n\delta^2} \leq \alpha$ pour $n \geq \frac1{4\alpha\delta^2}$ , c’est-à-dire $5556$ à trois points — environ $2.7$ fois l’exigence de Hoeffding. Sans remise, la variance est multipliée par $\frac{N - n}{N-1} < 1$ (Exercice 22.5), donc le même $n$ ne peut que faire mieux : le calcul avec remise est le conservateur.

15. $\{\widehat p_n \leq \frac12\} \subseteq \{\widehat p_n - 0.52 \leq -0.02\}$ , donc par la borne de Hoeffding unilatérale $\P(\widehat p_n \leq \tfrac12) \leq \eu^{-2n(0.02)^2} \leq 0.01$ dès que $n \geq \frac{\ln 100}{2\cdot0.0004} \approx 5756.5$ : $5757$ électeurs. Le coût varie comme l’inverse du carré de l’avance, non de la précision désirée : les courses serrées sont chères.

16. Utilisé : l’échantillon est tiré uniformément et indépendamment de l’électorat ; toute personne échantillonnée répond, honnêtement, et $p$ ne bouge pas pendant le sondage. Les vrais sondages violent les trois : les répondants joignables et disposés ne sont pas un échantillon uniforme (biais de sélection et de non-réponse), et les réponses peuvent être mensongères ou instables. Ce sont des erreurs de biais : elles décalent $\E(\widehat p_n)$ loin de $p$ d’une quantité indépendante de $n$ , de sorte qu’aucune taille d’échantillon ne les réduit — les mathématiques de cette partie ne contrôlent que le terme de fluctuation.

17. Tchebychev pour un groupe de taille $m$ : $\P(\abs{ \widehat p^{(i)} - p} \geq \delta) \leq \frac{1}{4m\delta^2} \leq \frac18$ pour $m \geq \frac2{\delta^2}$ . Si moins de $k/2$ groupes se trompent, alors plus de $k/2$ des valeurs $\widehat p^{(i)}$ se situent dans l’intervalle ouvert $\intoo{p - \delta}{p + \delta}$ , et leur médiane aussi ; donc $\{\abs{M - p} \geq \delta\}$ force au moins $\lceil k/2\rceil$ erreurs parmi $k$ groupes indépendants. La borne de l’union sur les $\binom k{\lceil k/2\rceil}$ ensembles possibles de groupes fautifs donne

\P(\abs{M - p} \geq \delta) \leq \binom{k}{\lceil k/2\rceil} \Bigl(\frac18\Bigr)^{k/2} \leq 2^k\,8^{-k/2} = 2^{-k/2} :

décroissance exponentielle en le nombre de groupes, achetée avec rien d’autre que des variances — utile précisément quand les termes sont non bornés et que Hoeffding est indisponible.

18. Cauchy–Schwarz (Théorème 22.19) :

\E(X) = \E(X\,\mathbf 1_{X>0}) \leq \sqrt{\E(X^2)}\sqrt{\E(\mathbf 1_{X>0}^2)} = \sqrt{\E(X^2)\,\P(X > 0)} ;

élever au carré et diviser.

19. Soit $h(a) = I(a) - 2(a - \tfrac12)^2$ . Alors $h(\tfrac12) = 0$ , $h'(a) = \ln\frac a{1-a} - 4(a - \tfrac12)$ s’annule en $\tfrac12$ , et

h''(a) = \frac1a + \frac1{1-a} - 4 = \frac{1}{a(1-a)} - 4 \geq 0

puisque $a(1-a) \leq \frac14$ . Donc $h'$ croît depuis $0$ sur $\intco{\frac12}1$ , d’où $h' \geq 0$ et $h \geq 0$ : $I(a) \geq 2(a - \tfrac12)^2$ .

20. $I(\tfrac12) = I'(\tfrac12) = 0$ , $I''(a) = \frac1{a(1-a)}$ donne $I''(\tfrac12) = 4$ , et $I'''(\tfrac12) = 0$ (la fonction est symétrique autour de $\tfrac12$ ), donc $I(\tfrac12 + \delta) = 2\delta^2 + O(\delta^4)$ . La question 4 borne alors la vraie queue en dessous par $\eu^{-n(2\delta^2 + O(\delta^4))}/(n+1)$ : pour $\delta$ petit l’exposant de Hoeffding $2n\delta^2$ est asymptotiquement exact — seules des améliorations polynomiales en $n$ sont possibles.

21. Markov : un moment, décroissance $1/a$ , utile seulement comme moteur derrière les autres (la question 1 le montre plat). Tchebychev : deux moments, décroissance $\frac{V}{n\delta^2}$ , optimale sans hypothèses supplémentaires (Exemple 22.18), et le meilleur outil à la question 23. Moment d’ordre quatre (Exercice 22.9) : décroissance $C/n^2$ , juste assez de sommabilité pour une loi forte. Hoeffding : variables bornées, décroissance $2\eu^{-2n\delta^2}$ , le cheval de trait de la partie III. Chernoff avec le taux exact $I(a)$ : moments exponentiels complets, exposant imbattable (questions 4, 20), le point de référence pour tout le reste.

22. Si la pièce est équilibrée : $\P(\widehat p_n > 0.525) \leq \P(\widehat p_n - \tfrac12 \geq 0.025) \leq \eu^{-2n(0.025)^2}$ . Si $p = 0.55$ : $\P(\widehat p_n \leq 0.525) \leq \P(\widehat p_n - 0.55 \leq -0.025) \leq \eu^{-2n(0.025)^2}$ . Les deux erreurs sont sous $0.01$ lorsque $2n(0.025)^2 \geq \ln 100$ , c’est-à-dire $n \geq 3684.2$ : $3685$ lancers. (Distinguer des hypothèses distantes de $2.5$ points coûte ce qu’estimer à $\pm2.5$ points coûte.)

23. Hoeffding : $n \geq \frac{\ln 40}{2(0.005)^2} \approx 73\,778$ . Tchebychev avec la vraie variance $p(1-p) = 0.0099$ : $n \geq \frac{0.0099}{0.05\cdot(0.005)^2} = 7920$ — neuf fois moins cher. L’exposant de Hoeffding $2n\delta^2$ tarife la variance à son pire cas $\frac14$ , absurdement pessimiste quand $p = 0.01$ ; le humble moment d’ordre deux sait mieux. L’outil manquant est une borne exponentielle consciente de la variance (inégalité de Bernstein, troisième année) — ou, pour les événements rares, l’approximation de Poisson démontrée au Chapitre 23, qui opère sur l’échelle relative naturelle.

24. Fixons $\delta > 0$ : $\sum_n 2\eu^{-2n\delta^2} < \infty$ (série de type géométrique), donc Borel–Cantelli 1 (Théorème 21.25) donne $\P(\abs{\widehat p_n - p} \geq \delta \text{ infiniment souvent}) = 0$ , c’est-à-dire l’événement $E_j = \bigcup_N\bigcap_{n\geq N}\{\abs{\widehat p_n - p} < \tfrac1j\}$ a pour probabilité $1$ pour chaque $j$ . L’intersection dénombrable $\bigcap_jE_j$ a encore probabilité $1$ (sous-additivité sur les complémentaires), et dessus $\widehat p_n \to p$ : la loi forte des grands nombres pour les lancers de pièce, le caractère borné jouant le rôle que le moment d’ordre quatre a joué à l’Exercice 22.9.

25. Un moment achète une borne plate ; deux achètent $1/(n\delta^2)$ , et rien de plus (l’exemple d’optimalité) ; quatre achètent $1/n^2$ , assez pour se télescoper en une loi presque sûre ; le caractère borné achète $\eu^{-2n\delta^2}$ ; et le moment exponentiel complet achète le taux exact $I$ , qu’aucune méthode ne bat. Sonder $2050$ personnes suffit pour n’importe quel pays parce que la fluctuation de l’échantillon est régie par la variance de la pièce, non par la taille de la population — les étiquettes de prix en $1/\delta^2$ et $\ln(1/\alpha)$ sont universelles. Le théorème central limite du volume de troisième année remplace ces inégalités, sur l’échelle $\sqrt n$ , par une loi limite exacte à constantes explicites — transformant chaque borne de ce problème en une égalité asymptotique.