Le dernier autocollant coûte le plus cher

Compléter un ensemble de N objets de collection prend beaucoup plus de temps que N essais — les quelques derniers éléments se cachent derrière un mur de doublons, et le nombre attendu de paquets est d'environ N·ln N.

Les doublons font des dégâts : une fois que tu possèdes la majeure partie de l'ensemble, presque chaque paquet répète quelque chose que tu as déjà, de sorte que les derniers autocollants coûtent plus cher que tout le début de l'album.

Par l'équipe de rédaction de Math Says Yes

Examiné par des humains selon nos normes en matière de sources et de corrections.

Comment nous évaluons le contenu

LE PIÈGE

Nous prévoyons « N éléments, donc un peu plus de N essais » et ignorons la vitesse à laquelle les doublons s'accumulent vers la fin.

Une grille presque complète d'emplacements de collection avec un seul emplacement vide et un tas de doublons.

Ce que cela montre

Collecter chaque élément d'un ensemble de N, où chaque essai te donne un élément uniformément aléatoire, ne prend pas environ N essais. Il faut grosso modo N fois le logarithme népérien de N, plus un petit terme supplémentaire d'environ 0,577 fois N. Pour un ensemble de 50 éléments, cela donne environ 225 essais en , soit plus de quatre fois la taille de l'ensemble lui-même. Le manque provient entièrement des doublons : une fois que tu possèdes la plus grande partie de l'ensemble, l'écrasante majorité des tirages répète quelque chose que tu as déjà, de sorte que chaque nouvel élément unique arrive de plus en plus lentement.

Ce que montrent les chiffres

100

200

400

autocollants uniques

tirages d'un seul autocollant →

Pour un ensemble de 50 éléments avec 1 élément par tirage, la moitié arrive en environ 34 tirages ; l'achèvement prend en moyenne environ 225.

Pourquoi la fin est brutale

Imagine que tu aies N moins un des N éléments, avec un seul vide restant. Chaque paquet est désormais celui dont tu as besoin avec une de tout juste 1 sur N, et tout le reste est un doublon — le coût est concentré tout à la fin. Une chance sur N signifie que le nombre attendu d'essais pour enfin obtenir cet élément est d'environ N à lui seul. Ainsi, le dernier élément peut coûter autant d'essais que l'ensemble compte de membres. L'avant-dernier coûte environ N sur deux, celui d'avant environ N sur trois, et ainsi de suite, ce qui explique exactement d'où vient le logarithme dans le total.

Pourquoi l'intuition échoue

La plupart des gens prévoient mentalement un nombre de tentatives proche de N, ou un peu plus, car l'ensemble comporte N emplacements et chaque essai en remplit un. Cette idée suppose implicitement que chaque tirage est utile, mais les tirages cessent de l'être à mesure que l'album se remplit. Nous remarquons l'élan du début, où presque chaque sachet ajoute une vignette, et nous oublions que ce même hasard nous servira des doubles par la suite. L'écart entre le N attendu et le N·ln N que nous payons réellement constitue toute la surprise, et il grandit avec la taille de l'ensemble.

Exemple concret

Prends un album de vignettes avec 50 vignettes distinctes, chaque sachet en contenant une de façon uniformément aléatoire. En , il faut environ 225 sachets pour remplir tout l'album. La première moitié, soit les 25 premières vignettes, arrive étonnamment vite, en environ 34 sachets. Après cela, le rythme s'effondre. La dernière vignette demande à elle seule environ 50 sachets en moyenne, et les toutes dernières réunies représentent une grande part du total. Le graphique le montre : la ligne monte en flèche au début, puis s'aplatit pour s'étirer lentement vers le dernier emplacement.

Comment l'utiliser

Chaque fois que tu dois récupérer chaque élément d'un ensemble fixe et que ceux-ci arrivent au hasard, prévois la fin plutôt que le compte. Fixe ton budget plus près de N·ln N que de N, et attends-toi à ce que les derniers éléments demandent le plus d'efforts. Mieux encore, échange. Échanger des doubles avec un autre collectionneur élimine cette fin laborieuse, car ton surplus correspond exactement au manque de quelqu'un d'autre. C'est pourquoi la culture de l'échange de vignettes existe : un marché d'échange transforme une fin individuelle brutale en une fin collective rapide, et c'est le moyen le moins cher de battre les mathématiques.

Ce que les gens comprennent mal

Un collectionneur qui possède 40 des 50 vignettes d'un album a l'impression d'avoir fait 80 % du chemin, alors qu'il n'a dépensé qu'environ un tiers des sachets attendus. Prévoir trop peu de tentatives est le réflexe initial ; cette erreur survient plus tard, au milieu de la collection : assimiler la part d'éléments possédés à la part d'efforts fournis. La collecte aléatoire est intensive au début — les premiers progrès sont faciles car de nombreux résultats conviennent, tandis que les progrès tardifs sont lents car peu d'entre eux le font. Un même nombre d'éléments restants peut cacher une attente prévue beaucoup plus longue.

Quand cela s'applique

Le problème du collectionneur de coupons apparaît dans les albums de vignettes, les boîtes de tirage aléatoire, la recherche de bugs rares, le recensement de toutes les catégories dans des journaux de bord, la collecte de réponses d'enquête auprès de chaque segment, ou l'observation de toutes les variantes dans des systèmes aléatoires. Il s'applique au mieux lorsque les résultats sont échantillonnés au hasard avec remise. L'échange, le ciblage ou des probabilités inégales modifient l'attente.

Note sur la source

L'étude de référence sur le problème du collectionneur de coupons est celle de Wolfram MathWorld. La page utilise le résultat formel comme intuition : le temps attendu est dicté par la recherche de plus en plus lente des dernières catégories non vues.

Essaie

Collectionneur de coupons

Ouvre des paquets et regarde les toute dernière vignettes stagner.

% complété

paquets ouverts

estimé pour finir

Les premières vignettes arrivent vite, mais vers la fin, presque chaque paquet est un doublon — le dernier article à lui seul demande à peu près autant de paquets que la collection entière compte d'articles.

FAQ

Pourquoi le dernier élément d'une collection est-il si difficile à obtenir ?

Parce qu'une fois qu'un seul élément manque dans un ensemble de N, chaque tirage aléatoire n'a qu'une probabilité de 1 sur N d'être celui dont tu as besoin. Cette faible chance signifie que l'attente prévue pour ce dernier élément est d'environ N essais à elle seule.

Combien de sachets faut-il pour terminer un ensemble de N éléments ?

En moyenne, environ N fois le logarithme népérien de N, et non N. Pour un ensemble de 50 éléments, cela fait environ 225 sachets, soit plus de quatre fois la taille de l'ensemble, car les doubles dominent les derniers tirages.