Problème du collectionneur de vignettes

Le problème du collectionneur de vignettes ou du collectionneur de coupons (en anglais : coupon collector's problem) est un problème de probabilités et de combinatoire qui consiste à estimer, si une marque de céréales offre une vignette dans chaque paquet qu'elle vend, et si la série compte n vignettes différentes, le nombre de paquets de céréales à acheter pour collectionner la série complète. La vignette contenue dans chaque paquet étant inconnue à l'achat, il s'agit d'un tirage avec remise. En moyenne, il faut acheter n.(1 + 1/2 + 1/3 + ... + 1/n) paquets de céréales.

Graphe qui donne, pour chaque nombre n de vignettes différentes, le nombre moyen E (T ) de paquets de céréales à acheter pour les posséder toutes.

L'étude de ce problème et de ses généralisations trouve des applications notamment en ingénierie des télécommunications. Le problème du collectionneur de vignettes était déjà mentionné en 1812 par Pierre-Simon de Laplace dans Théorie analytique des probabilités, page 195, 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], mais il est notamment cité par William Feller[2].

Définition formelle et notations

On considère la variable aléatoire Tn qui représente le nombre de paquets de céréales achetés avant d'obtenir toutes les n vignettes de la collection. On peut considérer que Tn est un temps : à chaque pas de temps un paquet de céréales est acheté. Soit ti 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 .

Calculs de l'espérance et de la variance du temps pour finir la collection

Lorsque l'on a déjà i-1 vignettes différentes, on trouve une nouvelle en achetant une boîte de céréale si on tombe sur l'une n-i+1 vignettes nouvelles parmi les n possibles. Ainsi, la probabilité d'en trouver une nouvelle est n-i+1/n. La variable ti suit donc une loi géométrique de paramètre n-i+1/n. D'où l'espérance :

Espérance

Par linéarité de l'espérance[3] :

Hn est n-ième nombre harmonique. En utilisant le développement asymptotique de Hn, on obtient :

est la constante d'Euler-Mascheroni.

Variance

En utilisant l'indépendance des variables ti, on obtient[3] :

où la dernière égalité vient du calcul d'une valeur de la fonction zeta de Riemann.

Estimations plus précises de la déviation

La première démonstration connue, via l’analyse des séries génératrices, est celle de Pierre-Simon de Laplace, page 195 de son traité de probabilités, édition de 1812. On cite aussi, souvent, un article d’Erdös et Rényi de 1960, où les auteurs semblent découvrir à l’occasion la loi de Gumbel, qui réapparaît dans leurs travaux la même année, dans le fameux 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 achats. Pour cela, on peut même supposer que les vignettes ne sont pas équiprobables, mais ont au contraire des probabilités respectives d'être trouvées à chaque achat. Dans ces conditions, après 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'équirépartition, lorsque est proche de , on trouve une valeur de proche de , 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 double[5].
  • Le collectionneur achète des pochettes de k vignettes différentes. On fait alors apparaître des coefficients binomiaux dans les formules[6].

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[7].

  • 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[8]. 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.
  • Cette technique est aussi utilisée pour détecter des pannes.
  • 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.

Notes et références

  1. (de) George Pólya, « Eine Wahrscheinlichkeitsaufgabe in der Kundenwerbung », Zeitschrift für Angewandte Mathematik und Mechanik, vol. 10, no 1, , p. 96–97 (DOI 10.1002/zamm.19300100113).
  2. L'ouvrage de Feller où il est question du problème est Feller 1991, et la remarque est faite par exemple par Foata, Han et Lass 2001.
  3. Gourdon 2021.
  4. Motwani et Raghavan 1995.
  5. Foata, Han et Lass 2001.
  6. Sardy et Velenik 2010.
  7. Certains exemples de cette partie proviennent de Boneh et Hofri 1997.
  8. Boneh 1983.

Bibliographie

Étude détaillée du problème

  • Xavier Gourdon, Les maths en tête, t. Algèbre - Probabilités, Éditions Ellipses, , 3e éd. (1re éd. 1994), 414 p. (ISBN 978-2-340-05676-3), chap. 6 (« Probabilités »), problème no 9 (Problème du collectionneur), p. 356-359.

Vulgarisation et aspects généraux

Articles et ouvrages de recherche

  • (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).

Voir aussi

Source de la traduction

  • Portail des probabilités et de la statistique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.