# Problème du collectionneur de vignettes

Le problème du collectionneur de vignettes ou du collectionneur de coupons (en anglais : coupon collector's problem, CCP) est un problème de probabilités et de combinatoire qui consiste à estimer le nombre de paquets de céréales à acheter pour collectionner une série complète de vignettes, à raison d'une vignette offerte dans chaque paquet. La vignette contenue dans chaque paquet étant inconnue à l'achat, il s'agit d'un tirage avec remise. En moyenne, si la série compte n vignettes différentes, il faut acheter n (1 + 1/2 + 1/3 + ... + 1/n) paquets de céréales.
Le problème du collectionneur de vignettes était déjà mentionné en 1812 par Pierre-Simon de Laplace dans sa Théorie analytique des probabilités, où il donne, avant Erdős et Rényi, la convergence vers la loi de Gumbel. Il est aussi mentionné par George Pólya, et il est notamment cité par William Feller. L'étude de ce problème et de ses généralisations trouve des applications notamment en ingénierie des télécommunications.

## Définition et notations

L'objectif du collectionneur est de posséder une vignette pour chacun des n types de vignettes. Pour cela, il achète des boîtes de céréales. Comme le montre la figure ci-dessous, il y a une vignette dans chaque boîte. Dans l'exemple, il achète sa première boîte dans laquelle il obtient la vignette 1. Il achète la deuxième boîte et on obtient la vignette 4. Dans son troisième achat, il obtient la vignette 1 à nouveau : sa collection reste donc la même, à savoir il possède la vignette 1 et 4. Il continue à acheter des boîtes de céréales jusqu'à obtenir une vignette de chaque type. On suppose que toutes les vignettes sont équiprobables : on a une probabilité de 1/n d'obtenir tout type de vignettes lors de l'achat d'une boîte.
On note T$_n$ le nombre de paquets à acheter pour obtenir la collection complète. Pour l'exemple ci-dessus, $T_{4}=10$ car le collectionneur a acheté 10 boîtes de céréales avant d'obtenir les 4 vignettes. Intuitivement, les dernières vignettes sont plus difficiles à obtenir que les premières. Pour étudier ce phénomène plus précisément, on introduit également la variable aléatoire T$_{n,k}$ que l'on note qui représente le nombre de paquets de céréales achetés avant d'obtenir k types de vignettes parmi les n types de vignettes de la collection. Dans l'exemple, $T_{4,1}=1$ car avec un seul achat, on possède forcément une vignette ; $T_{4,2}=2$, $T_{4,3}=5$ et $T_{4,4}=10$. Le temps T$_n$ d'obtention de la collection totale est donc T$_{n,n}$. On peut considérer que T$_{n,k}$ est un temps : à chaque pas de temps, un paquet de céréales est acheté.
Soit t$_{n,i}$ le temps supplémentaire pour obtenir la i-ème nouvelle vignette, sachant que l'on en a déjà i – 1 différentes. On a donc $T_{n,k}=\sum _{i=1}^{k}t_{n,i}$. Pour l'exemple de la figure ci-dessus, on a $t_{4,1}=1$ ($t_{n,1}$ est toujours égal à 1), $t_{4,2}=1$, $t_{4,3}=3$ et $t_{4,4}=5$. On a ici $T_{4}=10$ : en effet, dans l'exemple, il y a 10 boîtes achetées pour obtenir la collection complète des 4 vignettes.

## Calculs de l'espérance et de la variance du temps pour finir la collection

Lorsque l'on possède déjà i - 1 vignettes différentes, on en trouve une nouvelle en achetant une boîte de céréales si on tombe sur l'une des n – i + 1 vignettes nouvelles parmi les n possibles. Ainsi, la probabilité d'en trouver une nouvelle est n – i + 1/n. La variable t$_{n,i}$ suit donc une loi géométrique de paramètre n – i + 1/n. D'où l'espérance :
    $\mathbb {E} (t_{n,i})={\frac {1}{\text{paramètre}}}={\frac {n}{n-(i-1)}}$.
La variance, elle, vaut :
    $\mathbb {V} (t_{n,i})={\frac {1-{\text{paramètre}}}{{\text{paramètre}}^{2}}}={\frac {n(i-1)}{(n-i+1)^{2}}}={\frac {n^{2}}{(n-i+1)^{2}}}-{\frac {n}{n-i+1}}$.

### Espérance

Par linéarité de l'espérance, le temps moyen pour obtenir k types de vignettes parmi les n types de vignettes de la collection vaut :
    ${\begin{aligned}\mathbb {E} (T_{n,k})&=\mathbb {E} (t_{n,1})+\mathbb {E} (t_{n,2})+\cdots +\mathbb {E} (t_{n,k})\\&={\frac {n}{n}}+{\frac {n}{n-1}}+\cdots +{\frac {n}{n-k+1}}\\&=n\cdot \left({\frac {1}{n-k+1}}+{\frac {1}{n-k+2}}+\cdots +{\frac {1}{n}}\right)\\&=\,n\cdot (H_{n}-H_{n-k}).\end{aligned}}$
où $H_{n}=\sum _{k=1}^{n}{\frac {1}{k}}$ est le n-ième nombre harmonique. Le temps moyen d'obtention de la collection totale est donc $\mathbb {E} (T_{n})=\mathbb {E} (T_{n,n})=n\cdot H_{n}$, puisque $H_{0}=0$.

#### Exemples

Le collectionneur de vignettes est une métaphore et se retrouve dans des situations qui n'ont rien à voir avec des boites de céréales et des vignettes. Par exemple :
* Le nombre moyen d'essais nécessaires pour obtenir la naissance d'une fille et d'un garçon est $\mathbb {E} (T_{2})=3$. Ici, chaque naissance correspond à un tirage uniforme entre la naissance d'un garçon ou d'une fille. Le processus s'arrête lorsque l'on a "collectionné" les deux genres.
* Le nombre moyen d'essais de lancers d'un dé à 6 faces pour obtenir tous les nombres de 1 à 6 est $\mathbb {E} (T_{6})=14,7$. Ici, chaque lancer correspond à un tirage uniforme d'un nombre entre 1 et 6. Le processus s'arrête lorsque l'on a "collectionné" tous les nombres entre 1 et 6.

#### Comportement à l'infini

En utilisant le développement asymptotique de H$_n$, on obtient :
    $\mathbb {E} (T_{n})=n\cdot H_{n}=n\ln(n)+\gamma \cdot n+{\frac {1}{2}}+o(1),\ \ {\text{pour}}\ n\to \infty ,$
où $\gamma \approx 0,5772156649$ est la constante d'Euler-Mascheroni.

#### Temps d'attente moyen de la moitié de la collection

Ce nombre est $\mathbb {E} (T_{n,n/2})=n(H_{n}-H_{n/2})=n\ln 2-{\frac {1}{2}}+o(1)$. Ainsi, le temps d'attente moyen pour obtenir la moitié de la collection est linéaire en la taille $n$ de la collection ; il est inférieur au temps d'attente total qui est linéarithmique (voir complexité en temps).

### Variance

En utilisant l'indépendance des variables t$_{n,i}$, on obtient :
    ${\begin{aligned}\mathbb {V} (T_{n})&=\mathbb {V} (t_{n,1})+\mathbb {V} (t_{n,2})+\cdots +\mathbb {V} (t_{n,n})\\&={\frac {n^{2}}{n^{2}}}+{\frac {n^{2}}{(n-1)^{2}}}+\cdots +{\frac {n^{2}}{1^{2}}}-\mathbb {E} (T_{n})\\&=n^{2}\left(\sum _{k=1}^{n}{\frac {1}{k^{2}}}\right)-nH_{n}\\\end{aligned}}$
En utilisant les développements asymptotiques de H$_n$ et de $\sum _{k=1}^{n}{\frac {1}{k^{2}}}$, on obtient :
    $\mathbb {V} (T_{n})={\frac {\pi ^{2}}{6}}n^{2}-n\ln(n)-(\gamma +1)n+o(1),\ \ {\text{pour}}\ n\to \infty .$
En utilisant la valeur au point 2 de la fonction zeta de Riemann, on obtient la majoration simple :
    ${\begin{aligned}\mathbb {V} (T_{n})&\leqslant n^{2}\left(\sum _{k=1}^{n}{\frac {1}{k^{2}}}\right)\\&\leqslant n^{2}\left(\sum _{k=1}^{\infty }{\frac {1}{k^{2}}}\right)={\frac {\pi ^{2}}{6}}n^{2}<2n^{2}.\end{aligned}}$
Un majoration simple de l’écart-type est donc $\sigma (T_{n})\leqslant {\frac {\pi }{\sqrt {6}}}n\leqslant 1,3n$.

## Estimations plus précises de l'écart à la moyenne

* En utilisant l'inégalité de Bienaymé-Tchebychev , on a :
    $\forall \varepsilon >0,\mathbb {P} \left(|T_{n}-nH_{n}|\geqslant \varepsilon \,n\right)\leqslant {\frac {2}{\varepsilon ^{2}}}.$
* On peut aussi montrer le seuil suivant, en utilisant l'inégalité de Boole (union bound) :
    $\forall \varepsilon >0,\ \lim _{n\rightarrow \infty }\mathbb {P} (T_{n}>n\ln(n)+\varepsilon n)=1-\mathrm {e} ^{-\mathrm {e} ^{-\varepsilon }}.$
La première démonstration connue, via l’analyse des séries génératrices, est celle de Pierre-Simon de Laplace, dans sa Théorie analytique des probabilités en 1812. On cite aussi, souvent, un article$^,$ d’Erdös et Rényi de 1960, où les auteurs semblent découvrir à l’occasion la loi de Gumbel, qui réapparaît dans leurs travaux la même année, dans le théorème double-exponentiel précisant le seuil de connexité des graphes aléatoires.

## Avancement de la collection

On peut souhaiter calculer le nombre moyen de vignettes différentes obtenues après N achats. Pour cela, on peut même supposer que les vignettes ne sont pas équiprobables, mais ont au contraire des probabilités respectives p$_1$, ... , p$_n$ d'être trouvées à chaque achat. Dans ces conditions, après N achats, le nombre moyen de vignettes différentes est $C_{N}=\sum _{k=1}^{n}\left(1-(1-p_{k})^{N}\right)$.
Les fonctions $x\geqslant 0\mapsto x^{N}$ étant convexes, cette espérance est toujours inférieure ou égale à celle correspondant à l'équirépartition des vignettes, ce que l'intuition ne dément pas.
En outre, dans ce cas d'équiprobabilité, lorsque N est proche de n ln n, on trouve une valeur de C$_N$ proche de n, ce qui est conforme aux résultats des paragraphes précédents. Pour des vignettes mal réparties, il faudra être encore plus riche.

## Généralisations

On peut généraliser le problème de plusieurs manières.
* Le collectionneur a un petit frère auquel il donne les vignettes en double.
* Le collectionneur achète des pochettes de k vignettes différentes. On fait alors apparaître des coefficients binomiaux dans les formules.

## Applications

La plupart des applications du problème du collectionneur de vignette sont des systèmes où il y a un certain nombre d'éléments à visiter et où la politique choisie est de tirer au hasard des éléments jusqu'à les avoir tous vus (au moins avec une bonne probabilité). Certains exemples sont donnés ci-dessous.
* Certaines méthodes pour identifier les contraintes intéressantes en optimisation, consistent à faire un certain nombre de tests et à supposer qu'après cet examen on a trouvé toutes les contraintes intéressantes. Le nombre de tests nécessaires est déterminé grâce aux calculs précédents.
* Certains algorithmes d'optimisation ont besoin d'un point de départ, et ce point de départ influe sur le résultat obtenu, par exemple dans la recherche d'un minimum local. En utilisant plusieurs points de départ tirés au hasard on augmente la probabilité de succès en allant chercher de nouveaux minima locaux, mais on peut obtenir deux fois le même. On peut faire le parallèle avec le collectionneur de vignettes pour estimer le nombre de départs nécessaires.
* Cette technique est aussi utilisée pour détecter des pannes.
* Dans le domaine de la diffusion de rumeur (rumor spreading) dans un graphe, un modèle classique est celui où la rumeur est présente dans un nœud au départ et à chaque pas de temps chaque nœud informé transmet l'information à l'un de ses voisins au hasard. Le problème du collectionneur apparaît naturellement dans ce contexte.
* Le problème du collectionneur de vignettes permet d'apporter un argument en faveur, mais non une preuve, de ce que le nombre π est un nombre normal. En effet si c'est bien le cas, on peut estimer le nombre de décimales à lire pour trouver les dix chiffres de 0 à 9, les cent séquences de 00 à 99 et ainsi de suite ; les estimations données par le problème du collectionneur de vignettes sont proches des valeurs obtenues en observant le développement décimal de π.
* Le problème du collectionneur de vignettes intervient dans l'étude de la complexité en moyenne de l'algorithme de Gale-Shapley. L'objectif de cet algorithme est de calculer un mariage stable. L'algorithme procède comme suit. Chaque homme propose un mariage à la femme qu'il préfère le plus parmi celles à qui il n'a pas encore fait de proposition. Lorsqu'une femme célibataire reçoit une proposition, elle l'accepte. Si elle est mariée, elle accepte une proposition uniquement si cette dernière lui convient mieux. L'analyse en moyenne écrite par Donald Knuth fait une analogie avec le problème du collectionneur de vignettes comme suit. Son analyse repose sur des hommes amnésiques qui font des propositions à des femmes aléatoires. L'algorithme termine alors lorsque les hommes ont fait des propositions à toutes les femmes. L'ensemble des hommes représente les collectionneurs ; les femmes sont les vignettes.