Probabilités et statistiquesNotion · Glossaire
Collectionneur (problème du)
Le problème du collectionneur est un problème classique de probabilités. On suppose qu'il existe n types de coupons distincts, distribués aléatoirement et uniformément à chaque tirage. La question est de déterminer le nombre moyen de tirages nécessaires pour obtenir au moins un coupon de chaque type. La réponse est n fois la somme harmonique H(n) = 1 + 1/2 + 1/3 + ... + 1/n, soit environ n ln(n) pour n grand. Ce problème a des applications en informatique pour l'analyse d'algorithmes de hachage et de couverture.
Sommaire
Ce que vous allez apprendre
- Identifier les hypothèses du modèle classique.
- Retrouver l'espérance nHₙ par addition des temps d'attente.
- Vérifier le calcul complet pour six types.
- Distinguer la valeur moyenne d'une garantie sur la durée.
En clair
Imaginez six images différentes cachées dans des pochettes, avec une chance égale de trouver chacune d'elles. Les premières nouveautés arrivent vite. Puis les doubles s'accumulent et la dernière image se fait attendre. Le problème du collectionneur mesure précisément cette attente : combien de pochettes faut-il ouvrir en moyenne pour compléter la collection ?
L'obstacle n'est donc pas d'obtenir six images, mais d'obtenir les six types. Plus la collection avance, plus un tirage risque de reproduire un type déjà présent.
Définition
Le problème du collectionneur étudie le nombre de tirages nécessaire pour observer au moins une fois chacun de n types distincts. Le modèle classique suppose des tirages indépendants, avec remise, et une même probabilité 1/n pour chaque type. Le nombre de tirages est aléatoire ; on cherche son espérance, c'est-à-dire sa valeur moyenne théorique sur un grand nombre de collections recommencées.
Après avoir obtenu k types différents, avec 0 ≤ k < n, il en manque n − k. La probabilité que le tirage suivant apporte un nouveau type vaut (n − k)/n. Le temps moyen d'attente de cette nouveauté vaut donc n/(n − k). En additionnant les attentes successives, on obtient :
La lettre Tn désigne le nombre total de tirages et Hn la n-ième somme harmonique. Quand n devient grand, cette espérance est équivalente à n ln(n) : le terme logarithmique traduit surtout l'attente des derniers types manquants.
Un exemple, pas à pas
Une collection comporte six images équiprobables. Les tirages sont indépendants et une image déjà obtenue peut revenir. Données : n = 6 types ; probabilité de chaque type = 1/6 ; objectif = posséder les six types.
1. La première image est forcément nouvelle : son attente vaut 1 tirage.
2. Pour passer de 1 à 2 types, 5 types sur 6 sont nouveaux : l'attente vaut 6/5 = 1,2 tirage.
3. Les attentes suivantes valent successivement 6/4 = 1,5 ; 6/3 = 2 ; 6/2 = 3 ; puis 6/1 = 6 tirages.
2. Pour passer de 1 à 2 types, 5 types sur 6 sont nouveaux : l'attente vaut 6/5 = 1,2 tirage.
3. Les attentes suivantes valent successivement 6/4 = 1,5 ; 6/3 = 2 ; 6/2 = 3 ; puis 6/1 = 6 tirages.
On additionne ces six durées moyennes :
Il faut donc 14,7 tirages en moyenne pour compléter la collection de six images. Ce résultat n'annonce pas la durée d'une partie particulière : celle-ci peut finir avant ou bien après.
Contrôle : 6H6 = 6 × (1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6) = 14,7. Le dernier type représente à lui seul 6 tirages d'attente moyenne, ce qui explique son poids dans le total.
En pratique
Pour une collection de vignettes ou d'objets distribués au hasard, le modèle estime le nombre moyen d'achats avant d'obtenir tous les types. Si certaines vignettes sont plus rares, il faut abandonner la formule nHn et utiliser leurs probabilités réelles.
En informatique, la même question apparaît lorsqu'un procédé aléatoire doit avoir visité toutes les catégories, cases ou valeurs possibles. La formule classique convient seulement si les tirages sont indépendants et les catégories équiprobables ; sinon, une analyse adaptée au mécanisme de hachage ou de couverture est nécessaire.
Pour évaluer une simulation, on peut répéter de nombreuses collections, noter leur durée et comparer la moyenne observée à nHn. Une moyenne encore éloignée après peu d'essais n'est pas une contradiction : l'attente de la dernière nouveauté est très variable.
À ne pas confondre
Avec le nombre de tirages pour obtenir n coupons. Obtenir n coupons ne garantit pas n types distincts : des doubles peuvent apparaître. Dans l'exemple à six types, six tirages suffisent en quantité, mais pas nécessairement pour compléter la collection.
Avec le temps d'attente d'un seul type fixé. Attendre une image précise correspond à un seul objectif. Le collectionneur doit au contraire atteindre tous les types ; l'identité du type encore absent change au fil des tirages.
Avec le problème des anniversaires. Celui-ci cherche l'apparition d'une coïncidence, tandis que le collectionneur cherche la couverture complète des catégories. Un premier doublon peut arriver alors que presque toute la collection manque encore.
Limites et pièges
Types non équiprobables. Si un type est plus rare, le symptôme est une attente dominée par ce type. La formule nHn ne s'applique plus ; il faut calculer avec la distribution réelle.
Tirages dépendants ou sans remise. Si le contenu d'un tirage modifie le suivant, la probabilité d'une nouveauté n'est plus simplement (n − k)/n. Il faut modéliser la règle de tirage au lieu d'additionner les attentes classiques.
Moyenne prise pour une garantie. Pour six types, 14,7 est une espérance, pas un délai maximal ni un nombre entier de tirages assuré. Il faut étudier une probabilité de dépassement si l'on veut fixer un seuil de réussite.
Approximation utilisée comme égalité. La valeur nHn est exacte dans le modèle classique, tandis que n ln(n) n'est qu'un équivalent pour n grand. Pour n = 6, conserver 14,7 évite une approximation trop grossière.
Pour aller plus loin
suite harmonique — Elle éclaire la somme des attentes successives et la croissance logarithmique du temps de collection.
variable aléatoire — Elle précise le statut du nombre de tirages, dont 14,7 est une moyenne et non une issue possible.
Temps d'attente — Cette notion permet de décomposer la collecte en attentes successives jusqu'à chaque nouveau type.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres