Formule du crible/Exemple d'application

Début de la boite de navigation du chapitre

Nous allons traiter dans ce chapitre un exemple de problème que l’on résout avec la formule du crible. Le lecteur est invité, après avoir bien compris cet exemple, à faire l'exercice 1 qui est similaire.

fin de la boite de navigation du chapitre

Énoncé.

Une urne contient n boules numérotées de 1 à n. On tire indéfiniment dans cette urne avec remise. Soit X la variable aléatoire qui prend pour valeur le numéro du tirage où pour la première fois toutes les boules ont été obtenues au moins une fois. Donner la loi de X.

Corrigé.

Soit r ∈ ℕ, nous devons calculer p(X=r).

Si r < n, nous avons de façon évidente p(X=r) = 0. On ne peut pas obtenir toutes les boules si on fait moins de n tirages.

Supposons maintenant r ≥ n.

Soit B_i l’événement : « La boule numéro i n’est pas apparue au cours des r premiers tirages. »

B_i ∩ B_j représentera l’événement : « Les boules numérotées i et j ne sont pas sorties dans les r premiers tirages. »

B_i ∪ B_j représentera l’événement : « Au moins une des deux boules numérotées i ou j n’est pas apparue au cours des r premiers tirages. »

Nous avons donc :

${\begin{aligned}p(X>r)&=p\left(\bigcup _{i=1}^{n}B_{i}\right)\\&=\sum _{k=1}^{n}\left((-1)^{k+1}\sum _{1\leqslant i_{1}<i_{2}<\cdots <i_{k}\leqslant n}p\left(\bigcap _{j=1}^{k}B_{i_{j}}\right)\right)\end{aligned}}$

$\scriptstyle {p\left(\bigcap _{j=1}^{k}B_{i_{j}}\right)}$ représente la probabilité que les k boules :

$B_{i_{1}},B_{i_{2}},\cdots ,B_{i_{k}}$

ne soient pas sorties au cours des r premiers tirages (les autres peuvent être sorties ou non).

Par conséquent :

$p\left(\bigcap _{j=1}^{k}B_{i_{j}}\right)=\left({\frac {n-k}{n}}\right)^{r}$

Et donc :

$p(X>r)=\sum _{k=1}^{n}\left((-1)^{k+1}\sum _{1\leqslant i_{1}<i_{2}<\cdots <i_{k}\leqslant n}\left({\frac {n-k}{n}}\right)^{r}\right)$

$\scriptstyle {\sum _{1\leqslant i_{1}<i_{2}<\cdots <i_{k}\leqslant n}\left({\frac {n-k}{n}}\right)^{r}}$ est une somme de termes constants. Il y en a autant que ce qu’il y a de façon de choisir k nombres dans l’intervalle [1;n], c’est-à-dire $\scriptstyle {n \choose k}$.

On a donc :

$\sum _{1\leqslant i_{1}<i_{2}<\cdots <i_{k}\leqslant n}\left({\frac {n-k}{n}}\right)^{r}={n \choose k}\left({\frac {n-k}{n}}\right)^{r}$

Par conséquent :

$p(X>r)=\sum _{k=1}^{n}\left((-1)^{k+1}{n \choose k}\left({\frac {n-k}{n}}\right)^{r}\right)$

Nous avons alors :

${\begin{aligned}p(X=r)&=p(X>r-1)-p(X>r)\\&=\sum _{k=1}^{n}\left((-1)^{k+1}{n \choose k}\left({\frac {n-k}{n}}\right)^{r-1}\right)-\sum _{k=1}^{n}\left((-1)^{k+1}{n \choose k}\left({\frac {n-k}{n}}\right)^{r}\right)\\&=\sum _{k=1}^{n}\left((-1)^{k+1}{n \choose k}\left[\left({\frac {n-k}{n}}\right)^{r-1}-\left({\frac {n-k}{n}}\right)^{r}\right]\right)\\&=\sum _{k=1}^{n}\left((-1)^{k+1}{n \choose k}\left({\frac {n-k}{n}}\right)^{r-1}\left[1-\left({\frac {n-k}{n}}\right)\right]\right)\\&=\sum _{k=1}^{n}\left((-1)^{k+1}{n \choose k}\left({\frac {n-k}{n}}\right)^{r-1}\left({\frac {k}{n}}\right)\right)\\&=\sum _{k=1}^{n}\left((-1)^{k+1}{n-1 \choose k-1}\left({\frac {n-k}{n}}\right)^{r-1}\right)\end{aligned}}$

Remarque

Une autre façon de calculer la loi de X est de remarquer que $p(X\leq r)$ est la probabilité pour qu'une application de $\{1,\dots ,r\}$ dans $\{1,\dots ,n\}$ soit surjective, c'est-à-dire $p(X\leq r)={\frac {S_{r,n}}{n^{r}}}$, où $S_{r,n}$ (nombre de surjections de $\{1,\dots ,r\}$ dans $\{1,\dots ,n\}$, évidemment nul si r < n) est calculé au chapitre suivant. On retrouve ainsi (pour r ≥ n) :

$p(X\leq r)=\sum _{j=0}^{n}(-1)^{n-j}{\binom {n}{j}}\left({\frac {j}{n}}\right)^{r}$.