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.
Graphique qui donne, pour chaque nombre n de vignettes différentes (axe vertical), le nombre moyen E(T) de paquets de céréales à acheter pour les posséder toutes (axe horizontal).
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[1], et il est notamment cité par William Feller[2]. L'étude de ce problème et de ses généralisations trouve des applications notamment en ingénierie des télécommunications.
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.
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 Tn le nombre de paquets à acheter pour obtenir la collection complète. Pour l'exemple ci-dessus, 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éatoireTn,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, car avec un seul achat, on possède forcément une vignette; , et . Le temps Tn d'obtention de la collection totale est donc Tn,n. On peut considérer que Tn,k est un temps: à chaque pas de temps, un paquet de céréales est acheté.
Soit tn,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 . Pour l'exemple de la figure ci-dessus, on a ( est toujours égal à 1), , et . On a ici : en effet, dans l'exemple, il y a 10 boîtes achetées pour obtenir la collection complète des 4 vignettes.
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 tn,i suit donc une loi géométrique de paramètre n – i + 1/n. D'où l'espérance:
Par linéarité de l'espérance[3], le temps moyen pour obtenir k types de vignettes parmi les n types de vignettes de la collection vaut:
Pour vignettes à collectionner, ce graphique présente en abscisse le nombre moyen de paquets nécessaires pour obtenir les vignettes situées en ordonnée, montrant combien les dernières vignettes sont les plus longues à obtenir.
où est le n-ième nombre harmonique. Le temps moyen d'obtention de la collection totale est donc , puisque .
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 . 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 . 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.
Temps d'attente moyen de la moitié de la collection
Ce nombre est . Ainsi, le temps d'attente moyen pour obtenir la moitié de la collection est linéaire en la taille 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 tn,i, on obtient[3]:
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 p1, ... , pn d'être trouvées à chaque achat. Dans ces conditions, après N achats, le nombre moyen de vignettes différentes est .
Les fonctions é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 CN 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.
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[8].
Le collectionneur achète des pochettes de k vignettes différentes. On fait alors apparaître des coefficients binomiaux dans les formules[9].
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[10].
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[11]. 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[réf.nécessaire].
Cette technique est aussi utilisée pour détecter des pannes[réf.nécessaire].
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[réf.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 π[12].
Le problème du collectionneur de vignettes intervient dans l'étude de la complexité en moyenne de l'algorithme de Gale-Shapley[13]. 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[13] 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.
(en) P. Erdös et A. Rényi, «On the Evolution of Random Graphs», Publications of the Mathematical Institute of the Hungarian Academy of Sciences, , p.343-347 (lire en ligne)
. Donald Knuth, Mariages Stables et leurs relations avec d'autres problèmes combinatoires, Montréal, Les Presses de l'Université de Montréal, , 106p. (ISBN978-2-7606-0529-9, présentation en ligne).
Étude détaillée du problème
Xavier Gourdon, Les maths en tête, t.Algèbre - Probabilités, Paris, Ellipses, , 3eéd. (1reéd. 1994), 414p. (ISBN978-2-340-05676-3), chap.6 («Probabilités»), problème no9 (Problème du collectionneur), p.356–359 [lire en ligne].
Gilles Pagès et Claude Bouzitat (ill.Yves Guézou, avec le concours de Fabrice Carrance et Frédérique Petit), En passant par hasard: Les probabilités de tous les jours, Paris, Vuibert, , 268p. (ISBN2-7117-5258-5), «Pour quelques images de plus».
(en) Arnon Boneh et Micha Hofri, «The coupon-collector problem revisited—a survey of engineering problems and computational methods», Stochastic Models(en), Taylor & Francis, vol.13, no1, , p.39–66 (DOI10.1080/15326349708807412, lire en ligne).
(en) William Feller, An Introduction to Probability Theory and Its Applications, vol.1, New York, Wiley, , 3eéd., p.225.
(en) Arnon Boneh, «Preduce—A probabilistic algorithm identifying redundancy by a random feasible point generator (RFPG)», dans Redundancy in Mathematical Programming, Springer, , p.108–134.
(en) Aimo Torn et Antanas Zilinskas, Global optimization, Springer-Verlag, .
Dominique Foata, Guo-Niu Han et Bodo Lass, «Les nombres hyperharmoniques et la fratrie du collectionneur de vignettes», Séminaire Lotharingien de Combinatoire, vol.47, (lire en ligne).