Le problème du collectionneur
Un jour, j'avais acheté un nouveau paquet de gâteaux. Dans ce paquet, il y avait un magnet pays, de quoi joliment décoré mon frigo. Ma fille fut immédiatement conquise! "Papa, papa, la prochaine fois que tu vas chez Leclerc, je voudrais que tu achètes assez de gâteaux pour qu'on puisse faire la carte du monde sur le frigo."
Évidemment, j'avais envie de faire plaisir à ma fille. Une petite recherche Google m'informa qu'il y avait 80 magnets différents à collectionner. J'ai alors un peu réfléchi. Il allait falloir m'acheter au moins 80 paquets. Mais en réalité sans doute plus. Ce serait une chance incroyable d'avoir des pays tous différents dans ces 80 paquets. Par exemple, si j'ai déjà 40 pays différents et que j'achète un paquet, je n'ai qu'une chance sur deux d'avoir un nouveau pays...
Alors je me mis à réfléchir. Un peu de maths, quelques souvenirs de probabilités, des calculs... Et là je compris qu'il me fallait acheter en moyenne 397 paquets. Je dus à regret aller voir ma fille et dire que je renonçais...
Les paragraphes qui suivent nécessitent des connaissances mathématiques du niveau Terminale Spécialité.
On peut modéliser ce problème par les probabilités. On suppose que les magnets sont équitablement répartis entre les paquets et donc que, quand on achète un paquet, il y a la même probabilité de tomber sur chaque magnet. On note $S$ la variable aléatoire égale au nombre de paquets achetés pour avoir les 80 magnets. $S$ est une variable aléatoire : la valeur qu'elle prend dépend du déroulement de l'expérience. Si j'ai beaucoup de chances, $S$ peut prendre la valeur $80.$ Si je n'ai pas de chance, $S$ peut prendre des valeurs très grandes...
Notons aussi, pour $k=1,\dots,80,$ $T_k$ le nombre de paquets qu'il me faut acheter pour passer de la possession de $k-1$ magnets différents à la possession de $k$ magnets différents. À nouveau, les $T_k$ sont des variables aléatoires, et on a clairement $$S=T_1+\cdots+T_{80}.$$
On va établir la loi de chaque $T_k$, c'est-à-dire les valeurs possibles prises par $T_k,$ et la probabilité que chaque valeur soit prise. Pour $T_1$ c'est facile. Quand on achète le premier paquet, on est sûr d'avoir un nouveau pays puisqu'on part de zéro pays. Ainsi, on a toujours $T_1=1.$
Passons à $T_2$. On est dans la situation où on a déjà un pays et où on achète des paquets jusqu'à avoir un nouveau pays.
- on a $T_2=1$ si dès le premier paquet acheté, on obtient un nouveau pays. Comme il y a 80 pays et 79 différents du premier, l'hypothèse d'équiprobabilité nous dit que $$P(T_2=1)=\frac{79}{80}.$$
- on a $T_2=2$ si dans le premier paquet, on a le même magnet que celle que l'on possède déjà (cela se produit avec probabilité $1/80$) et si dans le second paquet on a un magnet différent (ceci se produit avec une probabilité $79/80$). Ces événements étant indépendants, on a $$P(T_2=2)=\frac{1}{80}\times \frac{79}{80}.$$
- pour $j\geq 3$, on a $T_2=j$ si dans les $j-1$ premiers paquets, on trouve le même magnet que celui que l'on possède déjà et si dans le $j$-ème on a un magnet différent. Finalement, $$P(T_2=j)=\frac{1}{80^{j-1}}\times\frac{79}{80}=\frac{79}{80^j}.$$
L'arbre de probabilité suivant illustre le comportement que l'on vient de décrire : l'événement $S$ désigne le succès (avoir un magnet différent) et $E$ désigne l'échec.
La variable aléatoire $T_2$ est donc à valeurs dans $\{1,2,\dots\}$ et sa loi est
| $T_2=$ | $1$ | $2$ | $\dots$ | $j$ | $\dots$ |
| $P(T_2=\cdots)=$ | $\frac 1{80}$ | $\frac{79}{80^2}$ | $\dots$ | $\frac{79}{80^j}$ | $\dots$ |
L'étude qu'on a faite avec $T_2$ peut être répétée avec $T_k$, pour $k=3,\dots,80.$ La différence maintenant est que la probabilité, lorsqu'on achète un paquet, d'obtenir un nouveau magnet est $\frac{80-(k-1)}{80}$ alors que la probabilité d'avoir un magnet que l'on a déjà est $\frac{k-1}{80}.$ On en déduit que $T_k$ est à valeurs dans $\{1,2,\dots\}$ et sa loi est
| $T_k=$ | $1$ | $2$ | $\dots$ | $j$ | $\dots$ |
| $P(T_k=\cdots)=$ | $\frac {80-k+1}{80}$ | $\frac{(k-1)(80-k+1)}{80}$ | $\dots$ | $\frac{(k-1)^{j-1}(80-k-1)}{80^j}$ | $\dots$ |
Avec du vocabulaire de probabilité, $T_k$ suit la une loi géométrique de paramètre $\frac{80-k+1}{80}.$
Ce qui nous intéresse, c'est de calculer le nombre moyen de paquets qu'il nous faudra acheter. Autrement dit, on cherche à calculer l'espérance de $S.$ Par linéarité de l'espérance, on sait que $$E(S)=E(T_1)+E(T_2)+\cdots+E(T_{80}).$$ Il est facile de voir que $E(T_1)=1.$ Un calcul, qui sera expliquée plus loin, donne $$E(T_k)=\frac{80}{80-k+1}.$$ Ainsi, \begin{align*} E(S)&=1+\frac{80}{79}+\frac{80}{78}+\cdots+\frac{80}2+\frac{80}1\\ &=\frac{80}{80}+\frac{80}{79}+\frac{80}{78}+\cdots+\frac{80}2+\frac{80}1\\ &=80\left(1+\frac 12+\cdots+\frac{1}{80}\right)\\ &=80\sum_{k=1}^{80}\frac 1k. \end{align*} On ne peut aller plus loin, et en utilisant sa calculatrice pour calculer la somme, on trouve bien $$E(S)\simeq 397\dots$$ C'est pourquoi il faut acheter $397$ paquets en moyenne pour achever la collection.
Le calcul de l'espérance de $T_k$ est un peu délicat avec des connaissances du lycée. Le premier problème est que, contrairement à ce que l'on voit d'habitude au lycée, $T_k$ prend une infinité de valeurs. L'espérance doit être définie comme une somme infinie, ou plutôt comme une limite de sommes finies : $$E(T_k)=\lim_{n\to+\infty}\sum_{j=1}^n jP(T_k=j)=\lim_{n\to+\infty}\sum_{j=1}^n j\frac{(k-1)^{j-1}(80-k+1)}{80^j}.$$ On va sortir ce qui ne dépend pas de $j$ de la somme et même, pour homogénéiser les puissances, on va écrire $$(k-1)^{j-1}=\frac{(k-1)^j}{k-1}.$$ Ainsi, on a $$E(T_k)=\frac{80-k+1}{k-1}\lim_{n\to+\infty}\sum_{j=1}^n j\frac{(k-1)^j}{80^j}.$$ Reste à calculer cette dernière somme ce qui est la seconde difficulté. On va utiliser une méthode étonnante. On va plutôt calculer $$F(x)=\sum_{j=1}^n j x^j$$ pour tout $x\in\mathbb R$ en faisant varier $x$. Pour cela, posons pour $x\in\mathbb R,$ $$f(x)=\sum_{j=1}^n x^j.$$ Alors $f$ est dérivable sur $\mathbb R$ et $$f'(x)=\sum_{j=1}^n j x^{j-1}=\frac{1}{x}\times F(x)$$ si $x\neq 0.$ D'autre part, d'après la formule donnant la somme d'une série géométrique, $$f(x)=\frac{x-x^{n+1}}{1-x}.$$ En dérivant, \begin{align*} f'(x)&=\frac{(1-(n+1)x^n)(1-x)+(x-x^{n+1}}{(1-x)^2}\\ &=\frac{1-(n+1)x^{n}-nx^n}{(1-x)^2}. \end{align*} Ainsi, $$F(x)=xf'(x)=\frac{x-(n+1)x^{n+1}-nx^{n+1}}{(1-x)^2}.$$ On s'intéresse à la limite, pour $x=(k-1)/80,$ de $$\sum_{j=1}^n j x^j=\frac{x-(n+1)x^{n+1}-nx^{n+1}}{(1-x)^2}.$$ Puisque $x\in [0,1[,$ la comparaison des suites géométriques et des polynômes (qui est aussi une conséquence de la croissance comparée des fonctions exponentielles et des polynômes), nous dit que $$\lim_{n\to+\infty}\frac{x-(n+1)x^{n+1}-nx^{n+1}}{(1-x)^2}=\frac{x}{(1-x)^2}.$$ Ainsi, avec $x=(k-1)/80,$ on trouve finalement \begin{align*} E(T_k)&=\frac{80-k+1}{k-1}\times \frac{k-1}{80}\times\frac{1}{\left(1-\frac{k-1}{80}\right)^2}\\ &=\frac{80-k+1}{80}\times\frac{80^2}{80-k+1}\\ &=\frac{80}{80-k+1}. \end{align*}