Théorème de De Moivre-Laplace

Menu

Théorème de De Moivre-Laplace.

Si $X_n\sim\mathcal{B}(n,p)$ pour $n\in\mathbb{N}^*$ et $p\in]0,1[$ alors on a : $$\forall [a,b]\subseteq\mathbb{R},\quad \lim_{n\to+\infty}\mathbb{P}\big(X_n\in[a,b]\big)=\frac{1}{\sqrt{2\pi}} \int_a^b{\rm e}^{-\frac{t^2}{2}}\,{\rm d}t$$ ce qui signifie que $\displaystyle \frac{X_n-np}{\sqrt{pqn}}\overset{(\mathcal{L})}{\longrightarrow}\mathcal{N}(0,1)$.
Remarque. C'est un cas particulier du théorème central limite en remplaçant $X_n$ par $\displaystyle\sum_{k=1}^n Y_k$ où $Y_1$, $\dots$, $Y_n$ sont i.i.d. de loi $\mathcal{B}(p)$.

Preuve niveau Licence dans le cas $\displaystyle p=\frac{1}{2}$.

Soit $\omega:\lc1,n\rc\ra\lc1,n\rc$ une permutation.
Pour $k\in\lc2,n\rc$, on dit que $\omega$ possède un record vers le haut au rang $k$ lorsque : $\forall i\in\lc1,k-1\rc$, $\omega(k)>\omega(i)$.
Par convention, on dira que toute permutation $\omega$ possède un record vers le haut au rang $1$.
Si on interprète l'expérience aléatoire comme $n$ tirages successifs sans remise dans une urne de $n$ boules numérotées de $1$ à $n$, un record vers le haut au $k$-ième signifie que le numéro obtenu est strictement plus grand que les numéros obtenus aux tirages précédents.
CORRECTION [ afficher/masquer ]

1. On note $A$ l'évènement "la permutation ne donne qu'un seul record vers le haut".
   $\omega\in A$ signifie que seul le premier rang donne un record vers le haut.
   Ceci équivaut à la condition $\omega(1)=n$ (le premier tirage donne la boule numéro $n$).
   On a donc $\hbox{Card}(A)=(n-1)!$ et : $$\p(A)=\dfrac{(n-1)!}{n!}=\dfrac{1}{n}$$ On note $B$ l'évènement "la permutation donne $n$ records vers le haut".
   $\omega\in B$ signifie que $\omega(1)<\omega(2)<\dots<\omega(n)$, et donc que $\omega$ est l'application identité.
   Ainsi $\hbox{Card}(B)=1$ et : $$\p(B)=\dfrac{1}{n!}$$
2. 1. On note $E_{j,k}$ l'évènement "la permutation donne un record vers le haut au rang $k$ avec la valeur $j$".
      Si $j<k$ il est clair que $E_{j,k}=\emptyset$, et donc que $\p(E_{j,k})=0$.
      Supposons $j\geq k$.
      Dénombrons les permutations $\omega$ qui appartiennent à $E_{j,k}$ :
      • la valeur de $\omega(k)$ est fixée égale à $j$ : $1$ seule possibilité
      • les valeurs de $\omega(1)$, $\omega(2)$, $\dots$, $\omega(k-1)$ doivent être prises entre $1$ et $j-1$ : le nombre de possibilités est égal au nombre d'arrangements de $k$ éléments de $\lc1,j-1\rc$, c'est-à-dire à $\displaystyle\binom{j-1}{k-1}\times (k-1)!$
      • les valeurs de $\omega(k+1)$, $\omega(k+2)$, $\dots$, $\omega(n)$ sont choisies quelconques (deux à deux distinctes) parmi les $n-k$ valeurs restantes: $(n-k)!$ possibilités.
      On en déduit que $\hbox{Card}(E_{j,k})=\displaystyle\binom{j-1}{k-1}\times(k-1)!\times(n-k)!$ puis que : $$\p(E_{j,k})=\dfrac{\displaystyle\binom{j-1}{k-1}\times(k-1)!\times(n-k)!}{n!}$$
   2. On note $R_k$ l'évènement "la permutation donne un record vers le haut au rang $k$".
      On remarque que $R_k=\displaystyle\bigcup_{j=k}^n E_{j,k}$ et que les $E_{j,k}$, pour $j\in\lc k,n\rc$, sont deux à deux incompatibles.
      L'additivité de $\p$ donne donc : $$\begin{array}{rcl} \p(R_k)&=&\displaystyle\sum_{j=k}^n \p(E_{j,k})\\ &=&\displaystyle\sum_{j=k}^n \dfrac{\displaystyle\binom{j-1}{k-1}\times(k-1)!\times(n-k)!}{n!} \\ &=&\displaystyle \dfrac{(k-1)!\times (n-k)!}{n!} \sum_{j=k}^n \displaystyle\binom{j-1}{k-1} \\ &=&\displaystyle\dfrac{1}{k\displaystyle\binom{n}{k}} \sum_{j=k}^n \displaystyle\binom{j-1}{k-1}\end{array}$$ Mais : $$ \sum_{j=k}^n \displaystyle\binom{j-1}{k-1} = \sum_{j=k-1}^{n-1} \displaystyle\binom{j}{k-1} = \sum_{j=k-1}^{n-1} \left(\displaystyle\binom{j+1}{k} - \displaystyle\binom{j}{k} \right) = \displaystyle\binom{n}{k} - \displaystyle\binom{k-1}{k}=\displaystyle\binom{n}{k} $$ grâce à la formule d'additivité de Pascal et aux propriétés des sommes télescopiques.
      Finalement : $$\p(R_k)=\dfrac{1}{k} $$ Remarquez que cette formule est encore valable pour $k=1$.
   3. On peut retrouver directement ce résultat grâce au raisonnement suivant.
      Pour avoir un record vers le haut au rang $k$ :
      • on choisit les $k$ premiers nombres puis on les ordonne de telle sorte que le $k$-ème soit le plus grand : $\displaystyle\binom{n}{k}\times (k-1)!$ possibilités
      • on choisit ensuite les $n-k$ nombres restants et on les ordonne de façon quelconque : $\displaystyle\binom{n-k}{n-k}\times (n-k)!=(n-k)!$ possibilités.
      Le nombre total de possibilité étants $n!$ on a donc : $$\p(R_k)=\dfrac{ \displaystyle\binom{n}{k} (k-1)! (n-k)! }{ n!} = \dfrac{1}{k} $$
3. 1. D'après la question 2.b, $Y_k\sim\mathcal{B}\left(\dfrac{1}{k}\right)$.
      Supposons $k< j$.
      Déterminons $\p(Y_k=1,Y_j=1)=\p(''\hbox{record au }k-\hbox{ième et au }j-\hbox{ième rangs}'')$.
      Avec la technique de dénombrement du 3.c, on compte le nombre de permutations qui donnent un record aux rangs $k$ et $j$ (au moins) :
      • on choisit les $j$ premiers nombres : $\displaystyle\binom{n}{j}$ possibilités
      • le plus grand prend la position $j$ : $1$ possibilité
      • on choisit parmi les $j-1$ restants les $k$ premiers nombres : $\displaystyle\binom{j-1}{k}$ possibilités
      • on les ordonne de telle sorte d'avoir un record au rang $k$ : $(k-1)!$ possibilités
      • sur les $j$ premiers nombres choisis, il en reste $j-k-1$ à répartir entre les tirages
        $k+1$, $k+2$, $\dots$, $j-1$ donc $(j-k-1)!$ possibilités
      • on choisit ensuite les $n-j$ nombres restants et on les répartit sur les tirages $j+1$, $j+2$, $\dots$, $n$ : $\displaystyle\binom{n-j}{n-j}\times (n-j)!=(n-j)!$ possibilités.
      On en déduit que : $$\begin{array}{rcl} \p(Y_k=1,Y_j=1)&=&\dfrac{ \displaystyle\binom{n}{j}\times 1\times\displaystyle\binom{j-1}{k} \times (k-1)!\times (j-k-1)!\times (n-j)!}{n!}\\ &=&\dfrac{1}{k\times j}\\ &=&\p(Y_k=1)\times\p(Y_j=1)\\ &=&1\end{array}$$ On vérifie facilement que cette formule est vraie pour tout $k\neq j$.
      Puisque les variables $Y_k$ et $Y_j$ suivent des lois de Bernoulli, il est classique d'en déduire leur indépendance.
   2. On remarque que $X_n=\displaystyle\sum_{k=1}^n Y_k$, et donc par linéarité de l'espérance : $$\mathbb{E}(X_n)=\sum_{k=1}^n \mathbb{E}(Y_k) =\sum_{k=1}^n \dfrac{1}{k} $$ D'autre part, comme les $Y_k$, pour $k\in\lc1,n\rc$, sont deux à deux indépendants : $$ V(X_n)=\sum_{k=1}^n V(Y_k) = \sum_{k=1}^n \dfrac{1}{k}\left(1-\dfrac{1}{k}\right) = \sum_{k=1}^n \dfrac{1}{k}-\sum_{k=1}^n\dfrac{1}{k^2}$$ Il est classique que $\mathbb{E}(X_n)\underset{n\to+\infty}{\sim} \ln(n)$ et que $V(X_n)\underset{n\to+\infty}{\sim}\ln(n)$.
   3. Toujours grâce à l'indépendance des $Y_k$, on a pour tout $t\in\mathbb{R}$ : $$ G_{X_n}(t) = \prod_{k=1}^n G_{Y_k}(t)=\prod_{k=1}^n \left(\dfrac{1}{k}t+1-\dfrac{1}{k}\right)=\dfrac{1}{n!} \prod_{k=0}^{n-1} (t+k) $$
   4. On a donc, pour tout $t\in\mathbb{R}$ : $$ G_{X_n}(t)= \dfrac{1}{n!}\prod_{k=1}^n \stir{n}{k} t^k $$ On en déduit que $X_n(\Omega)=\lc1,n\rc$ et : $$\forall k\in\lc1,n\rc,\quad \p(X_n=k)= \dfrac{\displaystyle\stir{n}{k}}{n!} $$
      Pour aller plus loin :
      • il est intéressant de remarquer que le théorème central limite (et le lemme de Slutsky) donne $\dfrac{X_n-\ln(n)}{\sqrt{\ln(n)}} \underset{n\to+\infty}{\overset{(\mathcal{L})}{\ra} }\mathcal{N}(0,1)$.
      • si on note $Z_n$ le nombre de record vers le bas (il y a record vers le bas au rang $k$ si $\omega(k)<\omega(i)$ pour tout $i\in\lc 1,k-1\rc$), alors $Z_n$ a la même loi que $X_n$.

MASQUER

3. Nombre de cyles (= orbites) d'une permutation aléatoire.

On note $X_n$ le nombre de cycles d'une permutation aléatoire de $\lc1,n\rc$ dans sa décomposition canonique (en comptant les cycles de longueur $1$).

1. Etablir la relation suivante : $$\forall k\in\lc1,n+1\rc,\quad (n+1)\p(X_{n+1}=k)=\p(X_n=k-1)+n\p(X_n=k)$$
2. En déduire $\E(X_n)$.
   Donner en un équivalent lorsque $n\to+\infty$.
3. Déterminer la fonction génératrice de $X_n$. Que peut-on en déduire sur sa loi?
4. En déduire $V(X_n)$. Donner en un équivalent lorsque $n\to+\infty$.

1. $X_n(\Omega)=\lc1,n\rc$.
   Pour $k\in\lc1,n\rc$, on note $c_n(k)$ le nombre de permutations de $\lc1,n\rc$ qui se décompose en exactement $k$ cycles à supports disjoints, c'est-à-dire le cardinal de l'évènement $[X_n=k]$.
   Considérons une permutation $\omega$ de $\lc1,n+1\rc$ qui se décompose en exactement $k$ cycles à supports disjoints.
   Deux cas se présentent :
   • $\omega(n+1)=n+1$. La restriction de $\omega$ à $\lc1;n\rc$ est une permutation qui se décompose en exactement $k-1$ cycles à supports disjoints. Ce cas présente donc $c_{n}(k-1)$ possibilités.
   • $\omega(n+1)\neq n+1$. Le cycle qui contient $n+1$ est donc de longueur supérieur ou égale à $2$. En effaçant $n+1$ de ce cycle, on obtient une permutation de $\lc1,n\rc$ qui se décompose en exactement $k$ cycles à support disjoints. Obtenir un permutation $\omega$ de $\lc1,n+1\rc$ qui se décompose en $k$ cycles à supports disjoints, et telle que $\omega(n+1)\neq n+1$, revient donc à choisir une valeur $j\in\lc1,n\rc$ et une permutation de $\lc1,n\rc$ dans laquelle on ajoute $n+1$ juste avant $j$ dans le cycle qui contient $j$. Ce cas présente donc $n\times c_n(k)$ possibilités.
   D'après le lemme des bergers on a donc la relation de récurrence : $$ c_{n+1}(k)=c_n(k-1)+n c_n(k)$$ En divisant par $(n+1)!$ on en déduit que : $$ \forall k\in\lc2;n\rc,\quad (n+1)\p(X_{n+1}=k) = \p(X_n=k-1)+n\p(X_n=k) $$ et cette formule est vraie aussi si $k=1$ ou $k=n+1$.
2. 1. Donc : $$\begin{array}{rcl} (n+1)\E(X_{n+1})&=&\displaystyle(n+1)\sum_{k=1}^{n+1} k\p(X_{n+1}=k) \\ &=& \displaystyle\sum_{k=0}^n (k+1)\p(X_n=k)+n\sum_{k=1}^{n+1}k\p(X_n=k)\\ &=&\displaystyle(n+1)\E(X_n) + 1\end{array}$$ Comme $\E(X_1)=1$, on en déduit facilement par récurrence que : $$\E(X_n)=\sum_{k=1}^n \frac{1}{k}\underset{n\to+\infty}{\sim}\ln(n)$$
   2. De même pour tout $t\in\R$ : $$\begin{array}{rcl} (n+1)\times G_{X_{n+1}}(t) &=&\displaystyle(n+1) \sum_{k=1}^{n+1} t^k \p(X_{n+1}=k) \\ & =& \displaystyle\sum_{k=0}^{n+1} t^{k+1} \p(X_n=k) + n \sum_{k=1}^{n+1} t^k \p(X_n=k) \\ & =& \displaystyle(t+n) \times G_{X_n}(t) \end{array}$$ Comme $G_{X_1}(t)=t$ on en déduit par récurrence que : $$\forall t\in\R,\quad G_{X_n}(t)=\dfrac{1}{n!}\prod_{k=0}^{n-1}(t+k)$$ On reconnaît la fonction génératrice du nombre de records (vers le haut ou vers le bas): le nombre de cycles d'une permutation aléatoire a la même loi que son nombre de records.
      C'est en fait une conséquence d'un résultat non probabiliste appelé correspondance fondamentale de Foata: http://fr.wikipedia.org/wiki/Correspondance_fondamentale_de_Foata
   3. On a pour tout $t\notin\{-n+1,\dots,-1,0\}$ : $$G_{X_n}'(t) = G_{X_n}(t)\times\left(\sum_{k=0}^{n-1} \dfrac{1}{t+k}\right)$$ donc : $$G_{X_n}''(t) = - G_{X_n}(t)\times\left(\sum_{k=0}^{n-1}\frac{1}{(t+k)^2}\right) +G_{X_n}'(t)\times\left(\sum_{k=0}^{n-1}\frac{1}{t+k}\right) $$ On en déduit que $\E(X_n)=G_{X_n}'(1)=\displaystyle\sum_{k=1}^n\dfrac{1}{k}$ puis que : $$V(X_n)=G_{X_n}''(1)+G_{X_n}'(1)-G_{X_n}'(1)^2=\sum_{k=1}^n\dfrac{1}{k} -\sum_{k=1}^n\dfrac{1}{k^2}\underset{n\to+\infty}{\sim}\ln(n)$$

MASQUER