Théorème de Weierstrass via la loi binomiale et l'inégalité de Bienaymé-Tchebychev
- Écrit par : Begyn Arnaud
Thèmes: Variables aléatoires - Loi binomiale - Moments - Indépendance - Inégalité de Bienaymé Tchebychev
- Définition. Si $n\in\mathbb{N}$ et $f:[0,1]\longrightarrow\mathbb{R}$ est continue, on appelle polynôme de Bernstein d'ordre $n$ associé à $f$, le polynôme:
Dans la suite $B_n(f)$ sera noté $B_n$ pour simplifier les notations.
- Convergence simple vers $f$ sur $[0,1]$. Pour tout $x\in[0,1]$, on a $\displaystyle \lim_{n\to+\infty} B_n(x)=f(x)$.
Preuve.Le résultat est évident si $x=0$ ou $1$ puisque $B_n(0)=f(0)$ et $B_n(1)=f(1)$.
On suppose $x\in]0,1[$ et on fixe $\varepsilon>0$. On se donne $S_n\hookrightarrow\mathcal{B}(n,x)$ et on remarque que d'après le théorème de transfert on a:
$$\mathbb{E}\left[f\left(\frac{S_n}{n}\right)\right]=\sum_{k=0}^n f\left(\frac{k}{n}\right)\mathbb{P}(S_n=k)=\sum_{k=0}^n f\left(\frac{k}{n}\right)\binom{n}{k}x^k(1-x)^{n-k}=B_n(x)$$
En remarquant que $\displaystyle\sum_{k=0}^n\binom{n}{k}x^k(1-x)^{n-k}=(x+1-x)^n=1$ on a donc:
$$|B_n(x)-f(x)|=\left|\sum_{k=0}^n\left[f\left(\frac{k}{n}\right)-f(x)\right]\binom{n}{k}x^k(1-x)^{n-k}\right|\leq \sum_{k=0}^n\left|f\left(\frac{k}{n}\right)-f(x)\right|\binom{n}{k}x^k(1-x)^{n-k}$$
Comme $f$ est continue en $x$, on sait qu'il existe $\delta>0$ tel que, pour tout $k\in[\![0;n]\!]$:
$$\left|\frac{k}{n}-x\right|<\delta\Longrightarrow \left|f\left(\frac{k}{n}\right)-f(x)\right|\leq\varepsilon$$
(définition de la limite lorsque $t\to x$ avec $t=k/n$).
On pose alors $\displaystyle I=\left\{k\in[\!0;n]\!] \,\Big/\, \left|\frac{k}{n}-x\right|<\delta \right\}$ et $\displaystyle J=\left\{k\in[\!0;n]\!] \,\Big/\, \left|\frac{k}{n}-x\right|\geq\delta \right\}$. On obtient:
$$ |B_n(x)-f(x)| \leq \sum_{k\in I} \left|f\left(\frac{k}{n}\right)-f(x)\right|\binom{n}{k}x^k(1-x)^{n-k} + \sum_{k\in J} \left|f\left(\frac{k}{n}\right)-f(x)\right|\binom{n}{k}x^k(1-x)^{n-k} $$
donc:
$$|B_n(x)-f(x)| \leq \varepsilon \sum_{k\in I}\binom{n}{k}x^k(1-x)^{n-k}+\sum_{k\in J}\left|f\left(\frac{k}{n}\right)-f(x)\right|\binom{n}{k}x^k(1-x)^{n-k} $$
On a $\displaystyle \sum_{k\in I}\binom{n}{k}x^k(1-x)^{n-k}\leq \sum_{k=0}^n\binom{n}{k}x^k(1-x)^{n-k}=1$.
Si on pose $\displaystyle \| f\|_{\infty}=\max_{t\in[0,1]} |f(t)|$ alors pour $k\in J$, $\displaystyle \left|f\left(\frac{k}{n}\right)-f(x)\right|\leq 2\|f\|_{\infty}$ donc:
$$|B_n(x)-f(x)|\leq \varepsilon +2\|f\|_{\infty}\sum_{k\in J}\binom{n}{k}x^k(1-x)^{n-k}$$
Reste à remarquer que $\displaystyle \left[\left|\frac{S_n}{n}-x\right|\geq\delta\right]=\bigcup_{k\in J} [S_n=k]$ et donc que: $\displaystyle \mathbb{P}\left(\left|\frac{S_n}{n}-x\right|\geq\delta\right)=\sum_{k\in J}\mathbb{P}(S_n=k)=\sum_{k\in J}\binom{n}{k}x^k(1-x)^{n-k}$.
Ainsi:
$$|B_n(x)-f(x)|\leq \varepsilon +2\|f\|_{\infty}\mathbb{P}\left(\left|\frac{S_n}{n}-x\right|\geq\delta\right)$$
Reste à appliquer l'inégalité de Bienaymé-Tchebychev:
$$ \mathbb{P}\left(\left|\frac{S_n}{n}-x\right|\geq\delta\right)\leq\frac{V\left(\frac{S_n}{n}\right)}{\delta^2}=\frac{x(1-x)}{n\delta^2}\leq\frac{1}{4n\delta^2}$$
puisqu'on montre facilement que $t(1-t)\leq\frac{1}{4}$ pour tout $t\in[0,1]$.
Finalement:
$$|B_n(x)-f(x)|\leq \varepsilon +2\|f\|_{\infty}\frac{1}{4n\delta^2}$$
Et comme $\displaystyle\lim_{n\to+\infty} 2\|f\|_{\infty}\frac{1}{4n\delta^2}=0$, il existe $n_0\in\mathbb{N}$ tel que $\forall n\geq n_0$, $\displaystyle 2\|f\|_{\infty}\frac{1}{4n\delta^2}\leq\varepsilon $.
On a donc montré qu'il existe $n_0\in\mathbb{N}$ tel que $\forall n\geq n_0$, $\displaystyle |B_n(x)-f(x)|\leq 2\varepsilon$ (on aurait du choisir $\varepsilon/2$ au départ la place de $\varepsilon$).
En conclusion: $\displaystyle \lim_{n\to+\infty} B_n(x)=f(x)$.
- Théorème de Weierstrass: convergence uniforme vers $f$. On a en fait $\displaystyle \lim_{n\to+\infty} \max_{x\in[0,1]}\big|B_n(x)-f(x)\big|=0$.
Il n'est pas nécessaire d'ajouter des hypothèses sur $f$ !
Preuve. On reprend les calculs et les notations de la démonstration précédente. Pour $\varepsilon>0$ fixé:
$$|B_n(x)-f(x)|\leq \varepsilon +2\|f\|_{\infty}\frac{1}{4n\delta^2}$$
pour $x\in]0,1[$. Le membre de gauche étant nul pour $x=0$ et $x=1$, l'inégalité est valable pour tout $x\in[0,1]$.
Dans le membre de droite seul $\delta$ peut dépendre de $x$ (en effet l'inégalité de Bienaymé-Tchebychev nous a fourni une majoration indépendante de $x$). Mais d'après le théorème de Heine, $f$ est uniformément continue sur $[0,1]$, ce qui assure qu'on peut supposer que $\delta$ ne dépend pas de $x$. On en déduit que:
$$\max_{x\in[0,1]}|B_n(x)-f(x)|\leq \varepsilon +2\|f\|_{\infty}\frac{1}{4n\delta^2}$$
et on conclut comme dans la démonstration précédente.
- Vitesse de convergence. Supposons $f$ lipschitzienne sur $[0,1]$. Alors $\displaystyle \max_{x\in [0,1] } | B_n(x)-f(x) | \underset{ n\to+\infty }{ = } \mathcal{O} \left( \frac{1}{n^{\frac{1}{3}}}\right)$.
Preuve. $f$ est lipschitzienne donc il existe $k>0$ telle que:
$$\forall (x,y)\in[0,1]^2,\quad [f(x)-f(y)|\leq k|x-y|$$
Dans la preuve précédente, on peut donc choisir $\displaystyle \delta=\frac{\varepsilon}{k}$:
$$\max_{x\in[0,1]}|B_n(x)-f(x)|\leq \varepsilon +2\|f\|_{\infty}\frac{k^2}{4n\varepsilon^2}$$
pour tout $\varepsilon>0$.
On choisit alors $\varepsilon$ de la forme $\displaystyle \frac{1}{n^{\alpha}}$ et de telle sorte que $\varepsilon$ et $\displaystyle\frac{1}{n\varepsilon ^2}$ soit du même ordre de grandeur, c'est-à-dire que $\alpha=1-2\alpha$, donc $\displaystyle \varepsilon=\frac{1}{n^{\frac{1}{3}}}$. On obtient:
$$\max_{x\in[0,1]}|B_n(x)-f(x)|\leq \left(1 +2\|f\|_{\infty}\frac{k^2}{4}\right)\frac{1}{n^{\frac{1}{3}}}$$
donc:
$$\max_{x\in [0,1] } | B_n(x)-f(x) | \underset{ n\to+\infty }{ = } \mathcal{O} \left( \frac{1}{n^{\frac{1}{3}}}\right)$$
- Vitesse de convergence. Supposons $f$ hölderienne d'exposant $\gamma\in]0,1]$ sur $[0,1]$. Alors $\displaystyle \max_{x\in [0,1] } | B_n(x)-f(x) | \underset{ n\to+\infty }{ = } \mathcal{O} \left( \frac{1}{n^{\frac{\gamma}{2+\gamma}}}\right)$.
Preuve. $f$ est hölderienne d'exposant $\gamma$ donc il existe $k>0$ telle que:
$$\forall (x,y)\in[0,1]^2,\quad [f(x)-f(y)|\leq k|x-y|^{\gamma}$$
Dans la preuve précédente de la convergence uniforme, on choisit $\displaystyle \delta=\left(\frac{\varepsilon}{k}\right)^{\frac{1}{\gamma}}$:
$$\max_{x\in[0,1]}|B_n(x)-f(x)|\leq \varepsilon +2\|f\|_{\infty}\frac{k^{\frac{2}{\gamma}}}{4n\varepsilon^{\frac{2}{\gamma}}}$$
pour tout $\varepsilon>0$.
On choisit alors $\varepsilon$ de la forme $\displaystyle \frac{1}{n^{\alpha}}$ et de telle sorte que $\varepsilon$ et $\displaystyle\frac{1}{n\varepsilon^{\frac{2}{\gamma}}}$ soit du même ordre de grandeur, c'est-à-dire que $\displaystyle \alpha=1-\frac{2\alpha}{\gamma}$, donc $\displaystyle \varepsilon=\frac{1}{n^{\frac{\gamma}{2+\gamma}}}$. On obtient:
$$\max_{x\in[0,1]}|B_n(x)-f(x)|\leq \left(1 +2\|f\|_{\infty}\frac{k^2}{4}\right)\frac{1}{n^{\frac{\gamma}{2+\gamma}}}$$
donc:
$$\max_{x\in [0,1] } | B_n(x)-f(x) | \underset{ n\to+\infty }{ = } \mathcal{O} \left( \frac{1}{n^{\frac{\gamma}{2+\gamma}}}\right)$$
Théorème de Moivre-Laplace
- Écrit par : Begyn Arnaud
Thèmes: Variables aléatoires - Loi binomiale
- Théorème de Moivre-Laplace. Si $X_n\hookrightarrow\mathcal{B}(n,p)$, pour $n\in\mathbb{N}^*$ et $p\in]0,1[$, alors:
ce qui signifie que $\displaystyle \frac{X_n-np}{\sqrt{pqn}}\overset{(\mathcal{L})}{\longrightarrow}\mathcal{N}(0,1)$.
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 dans le cas $\displaystyle p=\frac{1}{2}$.
On pose $Z_n=\displaystyle \frac{X_n-np}{\sqrt{\frac{n}{4}}}=\frac{2}{\sqrt{n}}\left(X_n-\frac{n}{2}\right)$.
Puisque $X_n(\Omega)=[\![0;n]\!]$, on a $Z_n(\Omega)=\displaystyle \bigg\{t_k=\frac{2}{\sqrt{n}}\left(k-\frac{n}{2}\right)\, \bigg/ \, k\in[\![0;n]\!] \bigg\}$.
Les réels $-\sqrt{n}=t_0<t_1<\dots<t_n=\sqrt{n}$ forment une subdivision régulière de l'intervalle $[-\sqrt{n},\sqrt{n}]$, de pas $\displaystyle\frac{2}{\sqrt{n}}$.
On définit une fonction en escalier $f_n:\mathbb{R}\longrightarrow\mathbb{R}$ par:
$$\forall t\in\mathbb{R},\quad f_n(t)= \sum_{k=0}^n \frac{\sqrt{n}}{2}\mathbb{P}(S_n=k)\mathbf{1}_{\big[t_k-\frac{1}{\sqrt{n}},t_k+\frac{1}{\sqrt{n}}\big]} (t)$$
|
Lemme 1. On pose $k_a=\displaystyle \min\big\{ k\in[\![0;n ]\!] \, \big/ \, t_k\in[a,b]\big\}$, $k_b=\displaystyle \max\big\{ k\in[\![0;n ]\!] \, \big/ \, t_k\in[a,b]\big\}$, $a_n=\displaystyle t_{k_a} -\frac{1}{\sqrt{n}}$ et $b_n=\displaystyle t_{k_b} +\frac{1}{\sqrt{n}}$. Alors:
$$\mathbb{P}\big(Z_n\in[a,b]\big)=\int_{a_n}^{b_n} f_n(t)\,{\rm d}t$$
Preuve du lemme 1. Il est clair que $\displaystyle \int_{t_k-\frac{1}{\sqrt{n}}}^{t_k+\frac{1}{\sqrt{n}}} f_n(t)\,{\rm d}t=\mathbb{P}(X_n=k)=\mathbb{P}(Z_n=t_k)$, puisque $[X_n=k]=[Z_n=t_k$.
D'autre part $\big[Z_n\in[a,b]\big]=\displaystyle\bigcup_{k=k_a}^{k_b}[Z_n=k]$, donc par additivité d'une probabilité:
$$\mathbb{P}\big(Z_n\in[a,b]\big)=\sum_{k=k_a}^{k_b} \mathbb{P}(Z_n=t_k)=\sum_{k=k_a}^{k_b}\int_{t_k-\frac{1}{\sqrt{n}}}^{t_k+\frac{1}{\sqrt{n}}} f_n(t)\,{\rm d}t=\int_{a_n}^{b_n} f_n(t)\,{\rm d}t$$
|
L'idée est alors de montrer que lorsque $n$ est grand, $\displaystyle\int_{a_n}^{b_n} f_n(t)\,{\rm d}t$ est proche de $\displaystyle\int_{a}^{b} \varphi(t)\,{\rm d}t$, où $\varphi(t)=\displaystyle \frac{1}{\sqrt{2\pi}}{\rm e}^{-\frac{t^2}{2}}$.
L'inégalité triangulaire et le lemme $1$ donnent:
$$\Bigg| \mathbb{P}\big(Z_n\in[a,b]\big)-\int_{a}^{b} \varphi(t)\,{\rm d}t\Bigg| \leq \Bigg| \int_{a_n}^{b_n} f_n(t)\,{\rm d}t-\int_{a_n}^{b_n} \varphi(t)\,{\rm d}t\Bigg|+\Bigg| \int_{a_n}^{b_n} \varphi(t)\,{\rm d}t-\int_{a}^{b} \varphi(t)\,{\rm d}t\Bigg|=M_1+M_2\qquad(1)$$
où la définition de $M_1$ et $M_2$ est évidente.
Pour continuer nous avons besoin de plusieurs lemmes techniques.
|
Lemme2. Estimations de $a_n$ et $b_n$. On pose $c=\max(|a|,|b|)$. Alors si $n>c^2$, on a $\displaystyle |a_n-a|\leq \frac{1}{\sqrt{n}}$ et $\displaystyle|b_n-b|\leq\frac{1}{\sqrt{n}}$.
Preuve du lemme 2. Si $n>c^2$, on a $t_0<a$ et $t_n>b$, donc $1\leq k_a\leq k_b\leq n-1$.
Or par définition de $k_a$, on a: $\displaystyle t_{k_a-1}=t_{k_a}-\frac{2}{\sqrt{n}} <a \leq t_{k_a}$.
Comme $a_n$ est le milieu de $[t_{k_a-1},t_{k_a}]$, intervalle de longueur $\displaystyle \frac{2}{\sqrt{n}}$, on a $\displaystyle|a_n-a|\leq \frac{1}{\sqrt{n}}$.
On obtient de même $\displaystyle|b_n-a|\leq \frac{1}{\sqrt{n}}$.
|
|
Lemme 3. Estimation de $f_n(t)$. Il existe $D>0$ telle que, si $n>4c^2$:
$$\forall t\in [a_n,b_n],\quad \big| f_n(t) - \varphi(t) \big|\leq \frac{D}{\sqrt{n}} $$
Preuve du lemme 3. Supposons que $n>4c^2$ et $t\in[a_n,b_n]=\displaystyle\bigcup_{k=k_a}^{k_b}\left[t_k-\frac{1}{\sqrt{n}},t_k+\frac{1}{\sqrt{n}}\right]$.
Il existe $k\in[\![k_a;k_b]\!]$ tel que $t\in\displaystyle \left[t_k-\frac{1}{\sqrt{n}},t_k+\frac{1}{\sqrt{n}}\right]$.
On a donc $f_n(t)=f_n(t_k)$.
De plus, $1\leq k\leq n-1$, donc $|t_k|\leq A$.
D'après l'inégalité triangulaire et la stricte positivité de $f_n$:
$$ \big| f_n(t)-\varphi(t) \big| = \big| f_n(t_k )-\varphi(t) \big| \leq \big| \varphi(t_k)-\varphi(t) \big| + \frac{ f_n(t_k) }{ f_n(0) } \bigg| f_n(0) - \frac{ 1 }{ \sqrt{2\pi} } \bigg| + \bigg| \frac{1}{\sqrt{2\pi}} \frac{ f_n(t_k) }{ f_n(0) } - \varphi(t_k) \big| \qquad (2)$$ Nous allons majorer un par un chacun des trois termes du membre de droite. $\star$ Premier terme. $t\in\displaystyle \left[t_k-\frac{1}{\sqrt{n}},t_k+\frac{1}{\sqrt{n}}\right] $ donne $\displaystyle|t-t_k|\leq\frac{1}{\sqrt{n}}$.
On vérifie ensuite facilement avec l'inégalité des accroissements finis que: $\forall (x,y)\in\mathbb{R}^2$, $\big|\varphi(x)-\varphi(y)\big|\leq |x-y|$.
On a donc:
$$ \big|\varphi(t_k)-\varphi(t)\big| \leq \frac{1}{\sqrt{n}}\qquad (3) $$ $\star$ Deuxième terme. La valeur de $f_n(0)$ dépend de la parité de $n$. On suppose donc dans la suite que $n$ est pair: $n=2m$ où $m\in\mathbb{N}^*$.
Puisque $n=2m$, on a $t_{m}= 0$ et donc $\displaystyle f_{2m}(0)=f_{2m}(t_m)=\frac{\sqrt{2m}}{2}\binom{2m}{m}=\frac{\sqrt{2m}}{2}\frac{(2m)!}{2^{2m}(m!)^2}$.
Utilisons un peu de calcul intégral. On pose $\displaystyle I_m = \int_0^1 (1-t^2)^{\frac{m}{2}}\,{\rm d}t$. On montre facilement que la suite $(I_m)_{m\geq1}$ est décroissante et strictement positive, de premiers termes $I_0=1$ et $\displaystyle I_1=\frac{\pi}{4}$ (via le changement de variables $t=\cos(\theta)$), et qu'elle vérifie la relation de récurrence $\displaystyle I_m=\frac{m}{m+1} I_{m-2}$.
On en déduit les formules:
$$I_{2m}=\frac{2^{2m}(m!)^2}{(2m+1)!}=\frac{\sqrt{2m}}{2}\frac{1}{2m+1}\frac{1}{f_{2m}(0)}\quad\hbox{et}\quad I_{2m-1}=\frac{(2m)!}{2^{2m+1}(m!)^2}\pi=\frac{2}{\sqrt{2m}}\frac{\pi}{2}f_{2m}(0)$$ Donc $\;\displaystyle f_{2m}(0) ^2= \frac{m}{\pi(2m+1)} \frac{I_{2m-1}}{I_{2m}} $.
D'où par décroissance de $(I_m)_{m\geq1}$, on obtient: $\displaystyle \left(1-\frac{1}{2m}\right)^2\leq \frac{1}{1+\frac{1}{2m}}\leq 2\pi f_{2m}(0)^2\leq 1$
et donc:
$$ \left(1-\frac{1}{2m}\right)\leq \sqrt{2\pi}\, f_{2m}(0)\leq 1\qquad (4.1)$$
De plus:
$$ \frac{f_{2m}(t_k)}{f_{2m}(0) }=\frac{\binom{2m}{k} }{ \binom{2m}{m} }=\frac{ (2m-k+1)(2m-k+2)\dots m}{(m+1)(m+2)\dots k }$$
Comme $\displaystyle\binom{ 2m }{k} =\binom{2m }{2m- k}$, on peut se ramener au cas $k\geq m$, et l'égalité précedente donne alors que:
$$ 0\leq \frac{f_{2m}(t_k)}{f_{2m}(0) } \leq1\qquad (4.2)$$
Les inégalités $(4.1)$ et $(4.2)$ donnent que:
$$\frac{ f_n(t_k) }{ f_n(0) } \bigg| f_n(0) - \frac{ 1 }{ \sqrt{2\pi} } \bigg|\leq \frac{1}{2m\,\sqrt{2\pi} } \qquad (4) $$
$\star$ Troisième terme. On vient de voir que $\displaystyle \frac{ f_{2m}(t_k) }{ f_{2m}(0) } = \frac{m}{k} v_{k-m} $ où on peut supposer $k\geq m$ et $\displaystyle v_{\ell}=\frac{\displaystyle\prod_{i=1}^{\ell-1}\left(1-\frac{i}{m}\right) }{\displaystyle\prod_{i=1}^{\ell-1}\left(1+\frac{i}{m}\right) }$ pour $\ell\in\mathbb{N}^*$ et $v_0=1$.
De plus, d'après l'inégalité triangulaire:
$$ \left| \frac{ f_{2m}(t_k) }{ f_{2m}(0) } - \varphi(t_k) \right|\leq \left| \frac{ f_{2m}(t_k) }{ f_{2m}(0) } - v_{k-m} \right| + \left| v_{k-m} - {\rm e}^{-\frac{t_k^2}{2}}\right|=N_1+N_2 $$
On en déduit que $v_\ell=\displaystyle \exp\left(-\frac{\ell^2}{m}+\frac{\ell}{m}+\sum_{i=1}^{\ell-1} \varepsilon\left(\frac{i}{m}\right)\right)$ et pour $\displaystyle 1\leq\ell\leq\frac{m}{2}$, on a $ \displaystyle\left|\varepsilon\left(\frac{i}{m}\right)\right|\leq\frac{i^3}{m^3}$ donc $\displaystyle \left|\sum_{i=1}^{\ell-1}\varepsilon\left(\frac{i}{m}\right)\right|\leq\frac{1}{m^3}\sum_{i=1}^{\ell-1} i^3\leq\frac{\ell^4}{4m^3} $.
Ainsi si $k>m$, on a: $\displaystyle v_{k-m}={\rm e}^{-\frac{t_k^2}{2}}{\rm e}^{\frac{t_k}{\sqrt{2m}}+\varepsilon_k}$ où $\displaystyle|\varepsilon_k|\leq\frac{(k-m)^4}{4m^3}=\frac{t_k^4}{16m}\leq \frac{t_k^2}{8\sqrt{2m}}$. Ceci reste vrai si $k=m$.
On a donc:
$$ N_2={\rm e}^{-\frac{ t_k^2 }{ 2 } } \left| {\rm e}^{ \frac{ t_k }{ \sqrt{2m} }+\varepsilon_k }-1\right|\leq {\rm e}^{ \frac{ t_k+\frac{ t_k^4 }{ 8 } }{ \sqrt{2m} }+\varepsilon_k }-1 \leq {\rm e}^{\frac{K_1}{\sqrt{2m}}}-1$$
où $\displaystyle K_1=c+\frac{c^4}{8}>0$. L'inégalité ${\rm e}^x-1\leq x{\rm e^x}$ pour $x>0$ donne alors:
$$N_2\leq \frac{K_2}{\sqrt{2m}}\qquad(5.1)$$
où $K_2=K_1{\rm e}^{K_1}>0$.
D'autre part:
$$N_1= \left| \frac{ f_{2m}(t_k) }{ f_{2m}(0) } - v_{k-m} \right| = \frac{k-m}{k}v_{k-m}\leq \frac{k-m}{m} =\frac{t_k}{\sqrt{2m}}\leq \frac{c}{\sqrt{2m}}\qquad (5.2)$$
Les inégalités $(5.1)$ et $(5.2)$ donnent alors:
$$\left| \frac{ f_{2m}(t_k) }{ f_{2m}(0) } - \varphi(t_k) \right|\leq \frac{K_2}{\sqrt{2m}}+\frac{c}{\sqrt{2m}}=\frac{K_3}{\sqrt{2m}}\qquad$$
où $K_3=K_2+c>0$.
$\star$ Les inégalités $(2)$, $(3)$, $(4)$ et $(5)$ donnent finalement:
$$ \big| f_n(t)-\varphi(t) \big| \leq \frac{1}{\sqrt{2m}} + \frac{1}{2m\,\sqrt{2\pi} } + \frac{K_3}{\sqrt{2m}} \leq \frac{D_1}{\sqrt{2m}}=\frac{D_1}{\sqrt{n}}\qquad(6) $$ $\star$ Il reste à prouver la même inégalité lorsque $n$ est impair. Puisque $n-1$ est pair, on va pouvoir utiliser les résultats précédents au rang $n-1$.
On note $(\tau_0,\tau_1,\dots,\tau_{n-1})$ la subdivision associée au rang $n-1$: $\displaystyle\tau_k=\frac{2}{\sqrt{n-1}}(k-n+1)$.
On remarque que pour $1\leq k\leq n-1$, $\tau_{k-1}\leq t_k\leq\tau_k$, et donc $\displaystyle |\tau_k-t_k|\leq \frac{2}{\sqrt{n-1}} $.
Puisqu'on a pris $k$ tel que $t\in\displaystyle \left[t_k-\frac{1}{\sqrt{n}},t_k+\frac{1}{\sqrt{n}}\right]$, on a $f_n(t)=f_n(t_k)$ et $\displaystyle |t-t_k|\leq \frac{1}{\sqrt{n}} $.
Ainsi $\displaystyle |t-\tau_k|\leq |t-t_k|+|t_k-\tau_k|\leq\frac{1}{\sqrt{n}}+\frac{2}{\sqrt{n-1}}\leq \frac{K_4 }{\sqrt{n}} $. De plus, la formule de Pascal donne que:
$$f_n(t)=f_n(t_k)=\frac{\sqrt{n}}{2^{n+1}}\binom{n}{k}=\frac{\sqrt{n}}{2^{n+1}}\left[\binom{n-1}{k-1}+\binom{n-1}{k}\right]=\frac{1}{2\sqrt{1-\frac{1}{n}}}\big[f_{n-1}(\tau_{k-1})+f_{n-1}(\tau_k)\big]$$
On a $\displaystyle\frac{1}{\sqrt{1-\frac{1}{n}}}-1\leq \frac{1}{n}$ et d'après $(4.1)$, $\sqrt{2\pi}f_{n-1}(\tau_k)\leq 1$ et $\sqrt{2\pi}f_{n-1}(\tau_{k-1})\leq 1$, donc en déduit que $\displaystyle 0\leq\sqrt{2\pi}\big(2f_n(t)-f_{n-1}(\tau_k)-f_{n-1}(\tau_{k-1})\big)\leq \frac{2}{n}$.
D'après l'inégalité triangulaire:
$$2\big|f_n(t)-\varphi(t)|\leq \frac{2}{n\,\sqrt{2\pi}} +\big| f_{n-1}(\tau_k)-\varphi(\tau_k)\big|+\big| f_{n-1}(\tau_{k-1})-\varphi(\tau_{k-1})\big|+\big| \varphi(\tau_k)-\varphi(t)\big|+\big| \varphi(\tau_{k-1})-\varphi(t)\big|$$
L'inégalité $(6)$ donne $\displaystyle\big| f_{n-1}(\tau_k)-\varphi(\tau_k)\big|\leq\frac{D_1}{\sqrt{n}}$ et $\displaystyle\big| f_{n-1}(\tau_{k})-\varphi(\tau_k)\big|\leq\frac{D_1}{\sqrt{n}}$.
On a aussi $\displaystyle\big| \varphi(\tau_k)-\varphi(t)\big|\leq|\tau_k-t|\leq \frac{K_4 }{\sqrt{n}} $ et $\displaystyle\big| \varphi(\tau_{k-1})-\varphi(t)\big|\leq|\tau_{k-1}-t|\leq \frac{K_4 }{\sqrt{n}} $.
Il existe donc une constante $D_2>0$ telle que:
$$\big| f_n(t)-\varphi(t) \big|\leq \frac{D_1}{\sqrt{n}}\qquad(7) $$
$\star$ $(6)$ et $(7)$ donnent que pour tout $n>4c^2$:
$$\forall t\in [a_n,b_n],\quad \big| f_n(t) - \varphi(t) \big|\leq \frac{D}{\sqrt{n}} $$
où $D=\max(D_1,D_2)$. |
Nous pouvons maintenant revenir à l'inégalité $(1)$. Le lemme $3$ donne que:
$$ M_1 \leq \int_{a_n}^{b_n}\big|f_n(t) - \varphi(t)\big| {\rm d}t\leq \int_{a_n}^{b_n} \frac{D}{\sqrt{n}}\,{\rm d}t\leq \frac{D(b-a+2)}{\sqrt{n}}$$
et, en utilisant que, $\forall t\in\mathbb{R}$, $\displaystyle |\varphi(t)|\leq\frac{1}{2}$:
$$M_2\leq \int_{a_n}^{b_n} \big|\varphi(t)\big|\,{\rm d}t+\int_{a}^{b} \big|\varphi(t)\big|\,{\rm d}t\leq \frac{|a-a_n|}{2}+\frac{|b-b_n|}{2}$$
et donc d'après le lemme $2$:
$$M_2\leq\frac{1}{2\sqrt{n}}+\frac{1}{2\sqrt{n}}=\frac{1}{\sqrt{n}}$$
On a donc:
$$\Bigg| \mathbb{P}\big(Z_n\in[a,b]\big)-\int_{a}^{b} \varphi(t)\,{\rm d}t\Bigg| \leq \frac{D(b-a+2)+1}{\sqrt{n}}$$
Le théorème des gendarmes permet alors de conclure que:
$$\lim_{n\to+\infty} \mathbb{P}\big(Z_n\in[a,b]\big)=\int_{a}^{b} \varphi(t)\,{\rm d}t$$
Sur les permutations aléatoires
- Écrit par : Begyn Arnaud
Thèmes: Espaces probabilisés finis - Vecteurs aléatoires - Espérance et variance - Covariance - Fonctions génératrices
On choisit comme univers l'ensemble des permutations de $[\![ 1;n ]\!]$. L'expérience aléatoire consiste donc à choisir au hasard une permutation. On munit cet espace de la probabilité uniforme, c'est-à-dire que chaque permutation peut être choisie avec la même probabilité $\displaystyle \frac{1}{ n! }$.
Remarquons que cette expérience peut être décrite avec une urne: on dispose d'une urne de $n$ boules numérotées de $1$ à $n$, et on tire toutes les boules successivement une par une et sans remise. La succession de tirages donne une permutation des chiffres de $1$ à $n$, et chaque issue de l'espérience se produit avec probabilité $\dfrac{1}{n!}$. On est donc ramené au choix équiprobable d'une permutation aléatoire.
- Nombre de points fixes. On tire au hasard une permutation aléatoire $\omega$, et on s'intéresse à ses points fixes (c'est-à-dire aux
éléments $i \in [\![ 1;n ]\!]$ vérifiant $\omega(i)=i$ ). On note $X$ la variables aléatoire égale au nombre de ses points fixes.
a) Quelle est la probabilité de l'évènement $[X=n]$?
b) Quelle est la probabilité de l'évènement $[X=n-1]$?
c) Quelle est la probabilité de l'évènement $[X=n-2]$?
d) Pour tout $i \in [\![ 1;n ]\!]$, on note $Y_i$ la variable aléatoire égale à $1$ si le point $i$ est fixe et $0$ sinon.
Déterminer la loi de $Y_i$. Pour $i\neq j$, les variables $Y_i$ et $Y_j$ sont-elles indépendantes?
e) Relier $X$ aux $Y_i$, $1\leq i\leq n$, et en déduire l'espérance et la variance du nombre de points fixes d'une permutation aléatoire.
f) Calculer la probabilité qu'une permutation aléatoire soit un dérangement, c'est-à-dire que l'évènement $[X=0]$ soit réalisé.
g) Donner alors la loi de $X$.
h) La variable $X$ dépend en fait de $n$; on la note donc $X_n$. Pour $k\in \mathbb{N}$, déterminer $\displaystyle \lim_{ n \rightarrow +\infty } \mathbb{P} ( X_n = k )$.
Solution. a) $X=n$ signifie que tous les points sont fixes, la permutation $\omega$ est donc l'identité. Il n'y a qu'une seule façon de l'obtenir, donc la probabilité cherchée est:
$$ \mathbb{ P} ( X=n ) = \frac{ 1}{ n! } $$
b) $X= n-1$ est impossible: en effet, un point qui n'est pas fixe prend nécessairement la position d'un autre point, ce qui fait au minimum deux points non fixes; une permutation ne peut donc pas laisser un seul point non fixe. La probabilité cherchée est donc:
$$ \mathbb{P} ( X=n-1 ) = 0 $$
c) $X=n-2$ signifie que la permutation $\omega$ laisse seulement deux points non fixes.
On choisit les deux points qui ne seront pas fixes: $\displaystyle \binom{n}{2}$ possibilités.
On les permute: $1$ seule possibilité.
Les autres points sont fixes: $1$ seule possibilité pour chaque.
La probabilité cherchée est donc:
$$ \mathbb{ P } ( X=n-2 ) = \frac{ \displaystyle \binom{n}{2} }{ n! } $$
On aurait pu aussi utiliser le fait que $S_n$ comporte $\displaystyle \binom{n}{2}$ transpositions (qui sont les permutations ayant exactement $n-2$ points fixes).
d) $Y_i( \Omega ) = \{ 0;1 \}$ donc $Y_i$ suit une loi de Bernoulli de paramètre $\mathbb{ P } ( Y_i = 1 )$.
$Y_i=1$ signifie que le point $i$ est fixe; les $n-1$ autres peuvent l'être ou ne pas l'être. Cela revient à permuter de manière quelconque ces $n-1$ autres points, donc:
$$\mathbb{ P} ( Y_i=1 ) = \frac { (n-1)! }{ n! } = \frac{1}{n} $$
Ainsi $\displaystyle Y_i \hookrightarrow \mathcal{ B } \left( \frac{ 1 }{ n } \right)$.
De même, $\big[ Y_i = 1 \big] \cap \big[ Y_j = 1 \big]$ signifie que les points $i$ et $j$ sont fixes. Comme cela revient à permuter de manière quelconque les $n-2$ autres points:
$$ \mathbb{ P } ( Y_i=1 , Y_j=1 ) = \frac{ (n-2) ! }{ n ! } = \frac{ 1 }{ n(n-1) } \neq \mathbb{P} ( Y_i=1) \times \mathbb{P} ( Y_j=1 ) $$
Ceci prouve que $Y_i$ et $Y_j$ ne sont pas indépendantes.
e) Comme les $Y_i$ ne prennent comme valeurs que $0$ ou $1$, la variable $\displaystyle \sum_{ i=1 }^n Y_i$ compte le nombre d'indice $i$ pour lesquels $Y_i$ prend la valeur $1$, et donc elle est égale au nombre de points fixes de la permutation aléatoire:
$$ X = \sum_{ i=1 }^n Y_i $$
Par linéarité de l'espérance:
$$ \mathbb{ E } (X) = \sum_{i=1}^n \mathbb{E} ( Y_i ) = \sum_{ i=1 }^n \frac{1}{n} = 1$$
(Le lecteur cultivé aura remarqué que ce résultat est une conséquence directe de la formule de Burnside, puisque le groupe symétrique agit transitivement sur $[\![ 1;n ]\!]$: http://fr.wikipedia.org/wiki/Action_de_groupe_%28math%C3%A9matiques%29#Formule_des_classes.2C_formule_de_Burnside )
D'autre part, par propriété de la variance:
$$ V (X) = \sum_{i=1}^n V( X_i ) + 2 \sum_{ 1\leq i<j \leq n} \hbox{Cov} ( Y_i,Y_j ) $$
On sait que $V ( Y_i ) = \displaystyle \frac{1}{n} \left( 1 - \frac{1}{n} \right)$.
De plus $Y_i Y_j$ ne prend que les valeurs $0$ ou $1$, et suit donc une loi de Bernoulli de paramètre $\mathbb{ P } ( Y_iY_j = 1 )$.
Mais $\big[ Y_iY_j = 1 \big] = \big[ Y_i=1 \big] \cap \big[ Y_j=1 \big]$, donc d'après le calcul de la question d), $Y_i Y_j$ suit la loi de Bernoulli de paramètre $\displaystyle \frac{1}{ n(n-1) }$. On en déduit que $\mathbb{E} ( Y_i Y_j ) = \displaystyle \frac{1}{ n(n-1) } $, puis que:
$$ \hbox{Cov} ( Y_i, Y_j ) = \mathbb{E} ( Y_i Y_j ) - \mathbb{E} ( Y_i) \mathbb{[E} ( Y_j) = \frac{1}{ n(n-1) } - \frac{1}{n^2} = \frac{1}{ n^2 (n-1) } $$
En remarquant que ce résultat ne dépend pas des valeurs de $i$ et $j$, et que la somme $\displaystyle \sum_{ 1\leq i<j \leq n } $ dispose de $ \displaystyle \binom{n}{2} $ termes, on obtient:
$$ V(X) = n\times\frac{1}{n} \left( 1 - \frac{1}{n} \right) + 2 \binom{n}{2} \times \frac{1}{ n^2(n-1) } = 1 $$
f) On remarque que $ \displaystyle [X=0] = \bigcap_{i=1}^n \big[ Y_i=0 \big]$. Donc:
$$ \mathbb{P} ( X=0 ) =1 - \mathbb{P} \left( \bigcup_{i=1}^n \big[Y_i = 1 \big] \right) = 1 - \sum_{k=1}^{n} (-1)^{k-1} \left( \sum_{ 1 \leq i_1 < i_2 < \dots < i_k \leq n } \mathbb{P} \big( [Y_{i_1} =1 ] \cap [ Y_{i_2} = 1 ] \cap \dots \cap [ Y_{i_k} = 1 ] \big) \right) $$
d'après la formule du crible de Poincaré.
Or si $1\leq i_1 < \dots < i_k \leq n$, l'évènement $ [Y_{i_1} =1 ] \cap [ Y_{i_2} = 1 ] \cap \dots \cap [ Y_{i_k} = 1 ] $ correspond aux permutations qui laisse fixes les points $i_1$, $\dots$, $i_k$, les $n-k$ autre points pouvant être fixes ou ne pas l'être. Ceci revient à permuter ces $n-k$ autres points, donc:
$$ \mathbb{P} \big( [Y_{i_1} =1 ] \cap [ Y_{i_2} = 1 ] \cap \dots \cap [ Y_{i_k} = 1 ] \big) = \frac{ ( n - k ) ! }{ n ! } $$
Comme cette quantité ne dépend pas des valeurs de $i_1$, $\dots$, $i_k$ (mais seulement de $k$), et comme la somme $\displaystyle \sum_{ 1 \leq i_1 < \dots < i_k \leq n } $ comporte $\displaystyle \binom{ n }{ k }$ termes, on a:
$$ \sum_{1\leq i_1 < \dots < i_k \leq n } \mathbb{P} \big( [ Y_{i_1} = 1 ] \cap \dots \cap [ Y_{i_k} = 1 ] \big) = \binom{n}{k} \frac{ ( n-k ) ! }{ n ! } = \frac{ 1 }{ k ! } $$
Ainsi:
$$ \mathbb{P} ( X=0 ) = 1 - \sum_{k=1}^n (-1)^{k-1} \frac{1}{ k! } = \sum_{k=0}^n \frac{ (-1)^k }{ k ! } $$
(Il est classique que cette quantité a pour limite $\displaystyle \frac{1}{ \hbox{e} } $ lorsque $ n \rightarrow +\infty$. )
g) Pour commencer, remarquons que $X ( \Omega ) = [\![ 0;n ]\!] $. En effet: une permutation a au minimum $0$ point fixe (c'est un dérangement), et au maximum $n$ points fixes (c'est l'identité).
D'autre part si $k\in [\![ 0;n ]\!]$ , l'évènement $[X=k]$ correspond aux permutations qui ont exactement $k$ points fixes. Pour les dénombrer, on compte le nombre de possibilités de choisir les $k$ points qui seront fixes et on multiplie par le nombre façons de permuter les $n-k$ autres points de telle sorte qu'ils soient tous non fixes.
On a $\displaystyle \binom{n}{k} $ choix des $k$ points qui seront fixes.
D'après f), $n! \mathbb{P} (X = 0 ) =n ! \displaystyle \sum_{k=0}^n \frac{ (-1)^k }{ k ! }$ corresponds au nombre de permutations de $ [\![ 1;n ]\!] $ qui ne laissent aucun point fixe. Donc le nombre de façons de permuter $n-k$ points de telle sorte qu'aucun ne soit fixe est: $ \displaystyle ( n-k ) ! \sum_{ i=0 }^{n-k} \frac{ (-1)^i }{ i ! } $.
On en déduit que:
$$ \mathbb{P} ( X=k ) = \frac{1}{ n ! } \binom{n}{k} ( n-k ) ! \sum_{ i=0 }^{n-k} \frac{ (-1)^i }{ i ! } = \frac{1}{ k ! } \sum_{i=0}^{ n-k } \frac{ (-1)^i }{ i ! } $$
h) Soit $ k \in \mathbb{N} $. On a:
$$ \forall n \geq k, \quad \mathbb{P} ( X_n =k ) = \frac{1}{ k ! } \sum_{i=0}^{n-k} \frac{ (-1)^i }{ i ! } $$
donc:
$$ \forall k\in\mathbb{N},\quad \lim_{n\rightarrow +\infty} \mathbb{P} ( X_n = k ) = \frac{ {\rm e}^{-1} }{ k ! } $$
On vient en fait de montrer que $ X_n \underset{ n\rightarrow +\infty}{ \overset{ ( \mathcal{L} ) }{ \longrightarrow } } \mathcal{P} ( 1 ) $.
- Records vers le haut. 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.
1. Quelle est la probabilité qu'une permutation donne un seul record vers le haut? qu'elle donne $n$ records vers le haut?
2.(a) Pour $(k,j)\in\lc2;n\rc^2$, quelle est la probabilité qu'une permutation donne un record vers le haut au rang $k$ avec $\omega(k)=j$?
(C'est-à-dire que les $n$ tirages sans remise donne le numéro $j$ au $k$-ième tirage et que les tirages précédents ont donné un numéro strictement inférieur à $j$).
2.(b) Pour $k\in\lc2;n\rc$, déterminer la probabilité qu'une permutation donne un record vers le haut au rang $k$.
2.(c) Comment aurait-on pu procéder pour trouver ce résultat directement?
3. On note $X_n$ le nombre de records obtenus. Pour tout $k\in\lc1;n\rc$, on note aussi $Y_k$ = $1$ si on a obtenu un record au rang $k$ et $0$ sinon.
3.(a) Pour $k\in\lc1;n\rc$, quelle est la loi de $Y_k$? Pour $k\neq j$, montrer que $Y_k$ et $Y_j$ sont indépendantes.
3.(b) En déduire $\mathbb{E}(X_n)$ et $V(X_n)$. Donner en un équivalent lorsque $n\to+\infty$.
3.(c) Déterminer la fonction génératrice de $X_n$.
$$ \newcommand{\stir}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}} $$
3.(d) On définit les nombres de Stirling non signés de première espéce, notés $\stir{n}{k}$, par la formule: $X(X+1)\dots(X+n-1)=\dsum_{k=1}^n \stir{n}{k} X^k$.
Donner la loi de $X_n$ en fonction des $\stir{n}{k}$, pour $k\in\lc1;n\rc$.
Solution. 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 nuémro $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.(a) 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 permutation $\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 à $\dbin{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})=\dbin{j-1}{k-1}\times(k-1)!\times(n-k)!$ puis que:
$$\p(E_{j,k})=\dfrac{\dbin{j-1}{k-1}\times(k-1)!\times(n-k)!}{n!}$$
2.(b) On note $R_k$ l'évènement "la permutation donne un record vers le haut au rang $k$".
On remarque que $R_k=\dbigcup_{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;
$$\p(R_k)=\sum_{j=k}^n \p(E_{j,k})=\sum_{j=k}^n \dfrac{\dbin{j-1}{k-1}\times(k-1)!\times(n-k)!}{n!} = \dfrac{(k-1)!\times (n-k)!}{n!} \sum_{j=k}^n \dbin{j-1}{k-1} =\dfrac{1}{k\dbin{n}{k}} \sum_{j=k}^n \dbin{j-1}{k-1}$$
Mais:
$$ \sum_{j=k}^n \dbin{j-1}{k-1} = \sum_{j=k-1}^{n-1} \dbin{j}{k-1} = \sum_{j=k-1}^{n-1} \left(\dbin{j+1}{k} - \dbin{j}{k} \right) = \dbin{n}{k} - \dbin{k-1}{k}=\dbin{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$.
2.(c) 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: $\dbin{n}{k}\times (k-1)!$ possibilités;
- on choisit ensuite les $n-k$ nombres restants et on les ordonne de façon quelconque: $\dbin{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{ \dbin{n}{k} (k-1)! (n-k)! }{ n!} = \dfrac{1}{k} $$
3.(a) D'après la question 2.(b), $Y_k\hookrightarrow\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 a compte le nombre de permutations qui donnent un record au rangs $k$ et $j$ (au moins):
- on choisit les $j$ premiers nombres; $\dbin{n}{j}$ possibilités;
- le plus grand prend la position $j$: $1$ possibilité;
- on choisit parmi les $j-1$ restants les $k$ premiers nombres: $\dbin{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$: $(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$: $\dbin{n-j}{n-j}\times (n-j)!=(n-j)!$.
On en déduit que:
$$\p(Y_k=1,Y_j=1)=\dfrac{ \dbin{n}{j}\times 1\times\dbin{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$$
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.
3.(b) On remarque que $X_n=\dsum_{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}-\dsum_{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.(c) Toujours grâce à l'indépendance des $Y_k$, on a pour tout $t\in\mathbb{R}$:
$$ G_{X_n}(t) = \dprod_{k=1}^n G_{Y_k}(t)=\dprod_{k=1}^n \left(\dfrac{1}{k}t+1-\dfrac{1}{k}\right)=\dfrac{1}{n!} \dprod_{k=0}^{n-1} (t+k) $$
3.(d) On a donc, pour tout $t\in\mathbb{R}$:
$$ G_{X_n}(t)= \dfrac{1}{n!}\dprod_{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)}} \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$.
- 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.(a) Etablir la relation suivant:
$$\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)$$
1.(b) En déduire $\E(X_n)$. Donner en un équivalent lorsque $n\to+\infty$.
1.(c) Déterminer la fonction génératrice de $X_n$. Que peut-on en déduire sur sa loi?
1.(d) En déduire $V(X_n)$. Donner en un équivalenr lorsque $n\to+\infty$.
Solution. 1.(a) $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 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$.
1.(b) Donc:
$$(n+1)\E(X_{n+1})=(n+1)\sum_{k=1}^{n+1} k\p(X_{n+1}=k) = \sum_{k=0}^n (k+1)\p(X_n=k)+n\sum_{k=1}^{n+1}k\p(X_n=k)=(n+1)\E(X_n) + 1$$
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)$$
1.(c) De même, pour tout $t\in\R$:
$$(n+1)\times G_{X_{n+1}}(t)=(n+1) \sum_{k=1}^{n+1} t^k \p(X_{n+1}=k) = \sum_{k=0}^{n+1} t^{k+1} \p(X_n=k) + n \sum_{k=1}^{n+1} t^k \p(X_n=k) = (t+n) \times G_{X_n}(t) $$
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.
1.(d) 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)=\dsum_{k=1}^n\dfrac{1}{k}$ (ce qu'on savait déjà), puis que:
$$V(X_n)=G_{X_n}''(1)+G_{X_n}'(1)-G_{X_n}'(1)^2=\dsum_{k=1}^n\dfrac{1}{k}-\dsum_{k=1}^n\dfrac{1}{k^2}\underset{n\to+\infty}{\sim}\ln(n)$$
Sur la loi uniforme
- Écrit par : Begyn Arnaud
Thèmes: Variables aléatoires - Loi - Moments
On dit qu'une variable aléatoire $X$ suit la loi uniforme sur une partie $A$ de $\mathbb{R}$ finie et non vide, lorsque:
$$X(\Omega)=A\qquad\hbox{et}\qquad \forall a\in A,\;\mathbb{P}(X=a)=\frac{1}{|A|}$$
où $|A|$ désigne le cardinal de $A$.
On le note $X\hookrightarrow\mathcal{U}(A)$.
- Modélisation1. On tire au hasard un élément de $A$ et on le note $X$, Alors $X\hookrightarrow\mathcal{U}(A)$.
La preuve est évidente!
- Modélisation2. On distingue un élément de $A$ des autres, qu'on note $a_0$.
On tire ensuite un par un et sans remise les éléments de $A$, jusqu'à avoir obtenu l'élément $a_0$. On note $X$ le nombre de tirages effectués.
Alors $X\hookrightarrow\mathcal{U}\big([\![1;n]\!]\big)$, où $n=|A|$.
Preuve: Il est clair que $X(\Omega)=[\![ 1;n]\!]$.
Pour $k\in[\![ 1;n]\!]$: $[X=k]=\overline{E_1}\cap\overline{E_2}\cap\dots\cap\overline{E_{k-1}}\cap E_k$ où $E_i$ est l'événement " le $i$-ième tirage a donné $a_0$". Les événements $E_i$, $i\in[\![1;k]\!]$, ne sont pas indépendants (car ils sont incompatibles), mais on peut faire le calcul grâce à la formule des probabilités composées:
\begin{equation*} \mathbb{P}(X=k) = \mathbb{P} \big( \overline{E_1} \big) \times \mathbb{P} \big( \overline{E_2} \big| \overline{E_1} \big) \times \dots \times \mathbb{P} \left( \overline{E_{k-1}} \Bigg| \bigcap_{i=1}^{k-2} \overline{E_i} \right) \times \mathbb{P} \left(E_{k} \Bigg| \bigcap_{i=1}^{k-1} \overline{E_i} \right) \end{equation*}
mais $ \mathbb{P}(E_i)=\frac{1}{n-i+1} $ et $ \mathbb{P}\big(\overline{E_i}\big)=\frac{n-i}{n-i+1} $ car lorsque le $i$-ième tirage commence il ne reste que $n-i+1$ éléments dans $A$.
On a donc:
$$\mathbb{P}(X=k)=\frac{n-1}{n}\times\frac{n-2}{n-1}\times\dots\times\frac{n-k}{n-k+1}\times\frac{1}{n-k}=\frac{1}{n}$$
Par exemple, on tire une a une et sans remise les cartes d'un jeu de 32 cartes et on note $X$ le numéro obtenu. Alors $X\hookrightarrow\mathcal{U}\big([\![1;32]\!]\big)$.
- Espérance et variance. Lorsque $X\hookrightarrow\mathcal{U}\big([\![1;n]\!]\big)$, on a $\mathbb{E}(X)=\displaystyle \frac{n+1}{2}$ et $V(X)= \displaystyle \frac{n^2-1}{12}$.
Preuve: Par définition $\mathbb{E}(X)=\displaystyle\sum_{k=1}^n k\frac{1}{n} = \frac{n+1}{2}$.
Par le théorème de transfert: $\mathbb{E}\big(X^2\big)=\displaystyle \sum_{k=1}^n\frac{k}{n^2}=\frac{(n+1)(2n+1)}{6}$
La formule de Koenig-Huyghens donne alors que: $ V(X) = \displaystyle \frac{n^2-1}{12}$.
- Fonction génératrice. $\forall t\in\mathbb{R}$, $G_X(t) = \displaystyle \frac{1}{n} \sum_{k=1}^n t^k$.
Preuve: c'est une simple application du théorème de transfert.
Sur la loi multinomiale
- Écrit par : Begyn Arnaud
Thèmes: Vecteurs aléatoires - Lois marginales - Espérance et variance - Covariance
On dit qu'un vecteur aléatoire $Z=(X_1,X_2,\dots,X_r)$ suit la loi multinomiale de paramètres $n\in\mathbb{N}^*$ et $(p_1,p_2,\dots,p_r)\in]0,1[^r$, avec $r\geq2$ et $p_1+p_2+\dots+p_r=1$, lorsque:
$$ Z(\Omega) \subseteq [\![ 0;n ]\!]^r \qquad \hbox{et} \qquad \forall (k_1,k_2,\dots,k_r) \in [\![ 0;n ]\!]^r , \; \mathbb{P} \big( Z=(k_1,k_2,\dots,k_r) \big) = \Bigg\{ \begin{array}{cl} \frac{ n ! }{ {k_1} ! {k_2} ! \dots {k_r} ! } {p_1}^{k_1} {p_2}^{k_2} \dots {p_r}^{k_r} & \hbox{ si } {k_1}+{k_2}+\dots{k_r}=1 \\\\ 0 & \hbox{ sinon} \end{array} $$
On le note $Z\hookrightarrow\mathcal{M}(n;p_1,p_2,\dots,p_r)$.
- Remarque. On a donc $X_1+X_2+\dots+X_r=n$ presque sûrement. Les variables $X_1$, $X_2$, $\dots$, $X_r$ ne sont donc pas indépendantes.
- Formule du multinôme. On peut en déduire la formule du multinôme dans un cas particulier. En effet, si $n\in\mathbb{N}^*$ et $(a_1,a_2,\dots,a_r)\in\big(\mathbb{R}^*_+\big)^r$,
on se donne $Z=(X_1,X_2,\dots,X_r)\hookrightarrow\mathcal{M}(n;p_1,p_2,\dots,p_r)$ où $p_i= \displaystyle \frac{a_i}{a_1+a_2+\dots+a_r}$, $1\leq i\leq r$, et dans ce cas la propriété $\displaystyle\sum_{ k_1+k_2+\dots +k_r=n} \mathbb{P}\big(Z=(k_1,k_2,\dots,k_r)\big) = 1$ s'écrit:
$$ \sum_{ k_1+k_2+\dots +k_r=n}\frac{ n ! }{ {k_1} ! {k_2} ! \dots {k_r} ! } {a_1}^{k_1} {a_2}^{k_2} \dots {a_r}^{k_r}=(a_1+a_2+\dots+a_r)^n$$
- Modélisation. On se donne une système complet d'évènements $(A_1,A_2,\dots,A_r)$ associé à une expérience aléatoire. Pour $i\in[\![1;r]\!]$, on note $p_i=\mathbb{P}(A_i)$ et
$X_i$ le nombre de fois où $A_i$ s'est réalisé au cours de $n$ répétitions indépendantes de l'expérience aléatoire.
Alors $Z=(X_1,X_2,\dots,X_r)\hookrightarrow\mathcal{M}(n;p_1,p_2,\dots,p_r)$.
Alors $Z=(X_1,X_2,\dots,X_r)\hookrightarrow\mathcal{M}(n;p_1,p_2,\dots,p_r)$.
Preuve: Il est clair que $Z(\Omega)\subseteq[\![ 0;n]\!]^r$.
D'autre part, pour $k=(k_1,\dots,k_r)\in[\![ 0;n]\!]^r$ avec $k_1+k_2+\dots+k_r=n$, on raisonne comme dans le cas de la loi binomiale: si on représente la situation par un arbre $r$-naire (chaque parent a $r$ fils) l'évènement $[X=k]$ correspond à $\frac{ n ! }{ {k_1} ! {k_2} ! \dots {k_r} ! }$ branches toutes de même probabilité ${p_1}^{k_1} {p_2}^{k_2} \dots {p_r}^{k_r}$. On en déduit que:
$$\mathbb{P} \big( Z=(k_1,k_2,\dots,k_r) \big) = \frac{ n ! }{ {k_1} ! {k_2} ! \dots {k_r} ! } {p_1}^{k_1} {p_2}^{k_2} \dots {p_r}^{k_r}$$
Par exemple: on dispose d'une urne de $n$ boules, chacune coloriée avec une couleur prise parmi $r$, et on effectue $n$ tirages avec remise d'une boule dans cette urne. Si on note $X_i$ = nombre de boules obtenues de la couleur $i$, pour $i\in[\![1;r]\!]$, alors $Z=(X_1,X_2,\dots,X_r)\hookrightarrow\mathcal{M}(n;p_1,p_2,\dots,p_r)$ où $p_i=\displaystyle \frac{n_i}{n}$ avec $n_i$ = nombre de boules de la couleur $i$ dans l'urne.
Autre exemple: dans la modélisation du processus de population de Galton-Watson, chaque individus a un nombre d'enfants entre $0$ et $r$, choisi aléatoirement selon une loi finie $(p_0,p_1,\dots,p_r)$. Si on note $Z_n$ le nombre d'individus de la $n$-ième génération, et, pour $i\in[\![0;r]\;]$, $A_{i}^{(n)}$ le nombre d'individus de la $n$-ième génération qui ont exactement $i$ enfants, alors, pour $k\in\mathbb{N}$, la loi du vecteur $(A_0^{(n)},A_1^{(n)},\dots,A_r^{(n)})$ sachant que $Z_n=k$ est la loi multinomiale $\mathcal{M}(k;p_0,p_1,\dots,p_r)$.
- Lien avec la loi binomiale: cas du schéma de Bernoulli. Si on se place dans le cadre du schéma de Bernoulli ($n$ répétitions indépendantes d'une expérience
succès/échec) et si note $X$ le nombre de succès obtenus, $Y$ le nombre d'échecs obtenus, alors $Z=(X,Y)\hookrightarrow\mathcal{M}(n;p,1-p)$ où $p$ est la probabilité que l'expérience aléatoire donne un succès.
D'autre part, on sait aussi que $X\hookrightarrow\mathcal{B}(n,p)$ et $Y\hookrightarrow\mathcal{B}(n;1-p)$. Comme le montre, le résultat suivant c'est en fait une propriété plus générale.
- Lois marginales. On suppose que $Z=(X_1,\dots,X_r)\hookrightarrow\mathcal{M}(n;p_1,\dots,p_r)$. Alors, si $i[\![1;r]\!]$, $X_i\hookrightarrow\mathcal{B}(n,p_i)$.
Preuve. Par modélisation (le calcul est lourd!).
On fixe $i\in[\![1;r]\!]$. Il est clair que $X_i(\Omega)\subseteq[\![ 0;n]\!]$.
D'autre part, si on se place dans le cadre de la modélisation ci-dessus, $X_i$ compte le nombre de fois où l'évènement $A_i$ s'est réalisé lors de $n$ répétitions indépendantes. On est donc le cadre d'un schéma de Bernoulli, où $A_i$ représente le "succès" et $\overline{A_i}$ représente l' "échec". Comme $p_i=\mathbb{P}(A_i)$, on peut donc dire que $X_i\hookrightarrow\mathcal{B}(n,p_i)$.
Preuve. De même $\displaystyle\sum_{i\in I} X_i$ compte le nombre de succès dans un schéma de Bernoulli où les "succès" sont donnés par l'évènement $\displaystyle \bigcup_{i\in I} A_i$, qui est de probabilité $\displaystyle \sum_{i\in I} p_i$.
- Espérance, variance et covariance. Pour $(i,j)\in[\![1;r]\!]^2$ avec $i\neq j$: $\mathbb{E}(X_i)=p_i$, $V(X_i)=np_I(1-p_i)$ et $\hbox{Cov}(X_i,X_j)=-np_ip_j$.
Preuve. Les deux premiers résultats sont déduits de $X_i\hookrightarrow\mathcal{B}(n,p_i)$.
D'autre part on sait que $X_i+X_j\hookrightarrow\mathcal{B}(n,p_i+p_j)$ donc que $V(X_i+X_j)=n(p_i+p_j)(1-p_i-p_j)$. Mais on aussi $V(X_i+X_j)=V(X_i)+V(X_j)+2\hbox{Cov}(X_i,X_j)$. On en déduit que: $\displaystyle \hbox{Cov}(X_i,X_j)=\frac{1}{2}\big( n(p_i+p_j)(1-p_i-p_j)-np_i(1-p_i)-np_j(1-p_j) \big)=-np_ip_j$.