Problème du collectionneur de vignettes

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

Le problème du collectionneur de vignettes ou du collectionneur de coupons (coupon collector en anglais) est un phénomène étudié en théorie des probabilités et en combinatoire. Un collectionneur cherche à avoir toutes les vignettes d'une série mais à l'achat le numéro de la vignette est inconnu (comme les jouets dans les paquets de céréales par exemple) : il s’agit donc d’un tirage avec remise. La question est : combien faut-il faire d'achats pour avoir la collection complète ? L'étude de ce problème et de ses généralisations trouve des applications notamment en ingénierie des télécommunications.

En moyenne, il faut environ n ln(n) achats pour une collection de n vignettes.

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[modifier | modifier le code]

On considère la variable aléatoire, Tn qui représente le nombre de vignettes achetées avant d'obtenir les n vignettes de la collection. On peut considérer que Tn est un temps : à chaque pas de temps une nouvelle vignette est achetée. Soit ti le temps supplémentaire pour obtenir la i-ème nouvelle vignette, sachant que l'on en a i-1. On a donc .

Calculs de l'espérance et de la variance du temps pour finir la collection[modifier | modifier le code]

Lorsque l'on a i-1 vignettes, la probabilité d'en trouver une nouvelle est n-i+1/n. La variable Tn suit donc une loi géométrique de paramètre n-i+1/n. D'où l'espérance :

Espérance[modifier | modifier le code]

Par linéarité de l'espérance :

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

est la constante d'Euler-Mascheroni.

Variance[modifier | modifier le code]

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

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[modifier | modifier le code]

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.

Généralisations[modifier | modifier le code]

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[4].
  • Le collectionneur achète des pochettes de k vignettes différentes. On fait alors apparaître des coefficients binomiaux dans les formules[5].

Applications[modifier | modifier le code]

La plupart des applications du problème du collectionneur de vignette sont des systèmes où il y a une 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[6].

  • Certaines méthodes pour identifier les contraintes intéressantes en optimisation, consiste à faire un certain nombre de tests et à supposer qu'après cet examen on a trouvé toutes les contraintes intéressantes[7]. 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[modifier | modifier le code]

  1. George Pólya: Eine Wahrscheinlichkeitsaufgabe in der Kundenwerbung, ZAMM – Zeitschrift für Angewandte Mathematik und Mechanik, Band 10, Heft 1, 1930, S. 96–97
  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. Voir Motwani et Raghavan 1995.
  4. Voir à ce propos l'article (Foata, Han et Lass 2001)
  5. Voir l'article en ligne gratuit (Sardy et Velenik 2010), sur Images des maths
  6. Certains exemples de cette partie proviennent de (Boneh et Hofri 1997).
  7. (Boneh 1983)

Bibliographie[modifier | modifier le code]

Vulgarisation et aspects généraux[modifier | modifier le code]

Articles et ouvrages de recherche[modifier | modifier le code]

  • (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[modifier | modifier le code]

Source de la traduction[modifier | modifier le code]