🎟️ Problème du collectionneur de coupons — Nombre de tirages attendu pour tout collectionner

La dérivation utilise la linéarité de l'espérance. Après avoir collecté k coupons distincts, le temps d'attente jusqu'au prochain nouveau coupon suit une loi géométrique de probabilité de succès p = (N − k) / N, donc sa moyenne est N / (N − k). En sommant pour k = 0, 1, …, N−1, on obtient E[T] = N/N + N/(N−1) + … + N/1 = N · (1 + 1/2 + … + 1/N) = N · H_N. La variance est également connue : Var[T] = N² · Σ(1/k²) ≈ N² · π²/6 pour N grand.

Les albums d'autocollants Panini en sont l'exemple le plus connu : un album de la Coupe du monde 2018 comptait 682 autocollants, et les collectionneurs devaient acheter en moyenne environ 4 832 pochettes pour le compléter (à raison de 5 autocollants par pochette). En génie logiciel, le test aléatoire (fuzzing) doit générer suffisamment de données de test pour atteindre chaque branche ; avec N branches, l'effort attendu croît comme N · ln(N). Les protocoles réseau qui attribuent des identifiants aléatoires font face au même problème dual du paradoxe des anniversaires : la rapidité d'apparition d'une collision contre le nombre d'identifiants nécessaires pour couvrir un ensemble.

Oui — cela ne serait vrai que si l'on pouvait garantir l'absence de répétitions, comme lors d'un tirage sans remise. Avec remise (tirages aléatoires indépendants), les doublons sont inévitables. Le total attendu croît comme N · ln(N), et non comme N, car les derniers coupons nécessitent chacun de nombreux tirages répétés avant que le type manquant n'apparaisse. Pour N = 50, le nombre de tirages attendu est d'environ 225, et non 50. L'histogramme révèle également une longue queue à droite, ce qui signifie qu'il faut parfois bien plus que la moyenne.

Le problème trouve ses racines dans la combinatoire du XVIIIe siècle. Abraham de Moivre a étudié des problèmes d'occupation apparentés dans son ouvrage de 1718, La Doctrine des chances. La formulation moderne et la solution par le nombre harmonique sont devenues connues grâce aux manuels de théorie des probabilités du milieu du XXe siècle. Le nom « collectionneur de coupons » s'est popularisé lorsque les jeux de coupons physiques et les cartes à collectionner sont devenus des produits de consommation courants au début du XXe siècle, offrant une analogie naturelle au problème abstrait d'occupation.

Le problème du collectionneur de coupons est étroitement lié au problème des anniversaires (qui demande quand survient la première collision plutôt que quand toutes les places sont remplies), aux problèmes d'occupation en combinatoire et à l'analyse des fonctions de hachage aléatoires. C'est le dual du collectionnement de coupons : l'un demande la première répétition, l'autre la couverture complète. Les simulations connexes incluent le paradoxe des anniversaires, les problèmes de couverture de marche aléatoire et l'intégration par la méthode de Monte-Carlo, qui impliquent tous des temps d'attente dans des processus aléatoires.

En test logiciel, le problème quantifie le nombre de données de test aléatoires nécessaires pour atteindre une couverture complète des chemins de code — un étalon pour comparer les tests aléatoires (fuzzing) aux tests systématiques. Dans les systèmes distribués, il modélise le nombre de messages de diffusion nécessaires avant que chaque nœud du réseau en ait reçu au moins un. Les équilibreurs de charge et les tables de hachage utilisent une analyse d'occupation similaire pour prédire quand tous les compartiments seront non vides. La borne N · ln(N) apparaît également dans les algorithmes randomisés pour les problèmes de couverture d'ensembles.

Lorsque les types de coupons ont des probabilités inégales, la formule du nombre harmonique ne s'applique plus. Le temps de complétion attendu est alors déterminé par le coupon le plus rare : si le type le moins probable a une probabilité p_min, le nombre attendu de tirages croît au moins aussi vite que 1/p_min. Ceci est étudié sous le nom de « collectionneur de coupons non uniforme » et peut être bien pire que le cas uniforme. Lorsque les coupons arrivent par pochettes (comme dans les albums d'autocollants), le problème devient une variante à tirages corrélés, analysée par des fonctions génératrices et des simulations, qui révèle que la structure des pochettes peut légèrement augmenter ou diminuer le coût total attendu selon la taille des pochettes et les règles de chevauchement.