Problème du collectionneur de vignettes

Graphique qui donne, pour chaque nombre Modèle:Mvar de vignettes différentes (axe vertical), le nombre moyen Modèle:Math de paquets de céréales à acheter pour les posséder toutes (axe horizontal).

Le problème du collectionneur de vignettes ou du collectionneur de coupons (Modèle:En anglais, 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 Modèle:Mvar vignettes différentes, il faut acheter Modèle:Math 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 Modèle:Mvar 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 Modèle:Sfrac d'obtenir tout type de vignettes lors de l'achat d'une boîte.

Exemple d'une collection de 4 vignettes possibles : 1, 2, 3, 4. Sur l'exemple, à l'étape 1 on obtient la vignette 1, à l'étape 2, la vignette 4. à l'étape 3, la vignette 1 à nouveau, etc.

On note Modèle:Mvar 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 Modèle:Mvar que l'on note qui représente le nombre de paquets de céréales achetés avant d'obtenir Modèle:Mvar types de vignettes parmi les Modèle:Mvar 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 Modèle:Mvar d'obtention de la collection totale est donc Modèle:Mvar. On peut considérer que Modèle:Mvar est un temps : à chaque pas de temps, un paquet de céréales est acheté.

Soit Modèle:Mvar le temps supplémentaire pour obtenir la Modèle:Mvar-ème nouvelle vignette, sachant que l'on en a déjà Modèle:Math 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à Modèle:Math vignettes différentes, on en trouve une nouvelle en achetant une boîte de céréales si on tombe sur l'une des Modèle:Math vignettes nouvelles parmi les Modèle:Mvar possibles. Ainsi, la probabilité d'en trouver une nouvelle est Modèle:Sfrac. La variable Modèle:Mvar suit donc une loi géométrique de paramètre Modèle:Sfrac. D'où l'espérance :

$𝔼(t_{n,i})=\frac{1}{\text{paramètre}}=\frac{n}{n-(i-1)}$.

La variance, elle, vaut :

$𝕍(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éranceModèle:Sfn, le temps moyen pour obtenir Modèle:Mvar types de vignettes parmi les Modèle:Mvar types de vignettes de la collection vaut :

$\begin{array}{cc}𝔼(T_{n,k})& =𝔼(t_{n,1})+𝔼(t_{n,2})+\cdots +𝔼(t_{n,k})\\ & =\frac{n}{n}+\frac{n}{n-1}+\cdots +\frac{n}{n-k+1}\\ & =n\cdot (\frac{1}{n-k+1}+\frac{1}{n-k+2}+\cdots +\frac{1}{n})\\ & =n\cdot (H_n-H_{n-k}).\end{array}$

Pour $n=100$ vignettes à collectionner, ce graphique présente en abscisse le nombre moyen $𝔼(T_{100,k})$ de paquets nécessaires pour obtenir les $k$ vignettes situées en ordonnée, montrant combien les dernières vignettes sont les plus longues à obtenir.

où $H_n=\sum _{k=1}^n\frac{1}{k}$ est le Modèle:Mvar-ième nombre harmonique. Le temps moyen d'obtention de la collection totale est donc $𝔼(T_n)=𝔼(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 $𝔼(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 $𝔼(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 Modèle:Mvar, on obtient :

$𝔼(T_n)=n\cdot H_n=n\ln (n)+\gamma \cdot n+\frac{1}{2}+o(1),\text{pour}n\to \mathrm{\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 $𝔼(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 Modèle:Mvar, on obtientModèle:Sfn :

$\begin{array}{cc}𝕍(T_n)& =𝕍(t_{n,1})+𝕍(t_{n,2})+\cdots +𝕍(t_{n,n})\\ & =\frac{n^2}{n^2}+\frac{n^2}{(n-1{)}^2}+\cdots +\frac{n^2}{1^2}-𝔼(T_n)\\ & =n^2\left(\sum _{k=1}^n\frac{1}{k^2}\right)-n{H}_n\\ \end{array}$

En utilisant les développements asymptotiques de Modèle:Mvar et de $\sum _{k=1}^n\frac{1}{k^2}$, on obtient :

$𝕍(T_n)=\frac{{\pi }^2}{6}{n}^2-n\ln (n)-(\gamma +1)n+o(1),\text{pour}n\to \mathrm{\infty }.$

En utilisant la valeur au point 2 de la fonction zeta de Riemann, on obtient la majoration simple :

$\begin{array}{cc}𝕍(T_n)& ⩽n^2\left(\sum _{k=1}^n\frac{1}{k^2}\right)\\ & ⩽n^2\left(\sum _{k=1}^{\mathrm{\infty }}\frac{1}{k^2}\right)=\frac{{\pi }^2}{6}{n}^2<2n^2.\end{array}$

Un majoration simple de l’écart-type est donc $\sigma (T_n)⩽\frac{\pi }{\sqrt{6}}n⩽1,3n$.

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

• En utilisant l'inégalité de Bienaymé-Tchebychev , on a :

$\mathrm{\forall }\epsilon >0,\mathbb{P}(|T_n-n{H}_n|⩾\epsilon n)⩽\frac{2}{{\epsilon }^2}.$

• On peut aussi montrer le seuil suivant, en utilisant l'inégalité de Boole (Modèle:Lang)Modèle:Sfn :

$\mathrm{\forall }\epsilon >0,\underset{n\to \mathrm{\infty }}{\lim }\mathbb{P}(T_n>n\ln (n)+\epsilon n)=1-{\mathrm{e}}^{-{\mathrm{e}}^{-\epsilon }}.$

La première démonstration connue Modèle:Quoi, 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 1812Modèle:SfnModèle:Référence insuffisante. On cite aussi, souvent, un articleModèle:LequelModèle:, d’Erdös et Rényi de 1960Modèle:Référence nécessaire, où les auteurs semblentModèle:Quoi 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 Modèle:Nobr. Pour cela, on peut même supposer que les vignettes ne sont pas équiprobables, mais ont au contraire des probabilités respectives Modèle:Math d'être trouvées à chaque achat. Dans ces conditions, après Modèle:Nobr, le nombre moyen de vignettes différentes est $C_N=\sum _{k=1}^n(1-(1-p_k{)}^N)$.

Les fonctions $x⩾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 Modèle:Mvar est proche de Modèle:Math, on trouve une valeur de Modèle:Math proche de Modèle:Mvar, 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 doubleModèle:Sfn.
• Le collectionneur achète des pochettes de Modèle:Mvar vignettes différentes. On fait alors apparaître des coefficients binomiaux dans les formulesModèle:Sfn.

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éressantesModèle:Sfn. 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écessairesModèle:Référence nécessaire.
• Cette technique est aussi utilisée pour détecter des pannesModèle:Référence nécessaire.
• Dans le domaine de la diffusion de rumeur (Modèle:Lang) 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 contexteModèle:Référence nécessaire.
• 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 πModèle:Sfn.
• 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.

Bibliographie

Étude détaillée du problème

• Modèle:Ouvrage.
• Modèle:Ouvrage.

Vulgarisation et aspects généraux

• Modèle:Ouvrage.
• Modèle:Lien web.
• Modèle:Article.
• Modèle:Ouvrage.
• Modèle:Randomized Algorithms (Motwani et Raghavan).
• Modèle:Article.
• Modèle:Article.

Articles et ouvrages de recherche

• Modèle:Chapitre.
• Modèle:Ouvrage.
• Modèle:Article.

Voir aussi

Source de la traduction

Modèle:Traduction/Référence