Problème du collectionneur de vignettes

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 achats pour une collection de vignettes.

Le problème du collectionneur de vignettes était déjà connu dans les années 30, Il est d'abord 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, qui représente le nombre de vignettes achetées avant d'obtenir les vignettes de la collection. On peut considérer que est un temps : à chaque pas de temps une nouvelle vignette est achetée. Soit 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 suit donc une loi géométrique de paramètre . 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]

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]

  • Sylvain Sardy et Yvan Velenik, « Petite collection d’informations utiles pour collectionneur compulsif », Images des maths,‎ (lire en ligne)
  • (en) Arnon Boneh et Micha Hofri, « The coupon-collector problem revisited—a survey of engineering problems and computational methods », Stochastic Models, Taylor and Francis, vol. 13, no 1,‎ , p. 39-66 (lire en ligne)
  • (en) William Feller, An Introduction to Probability Theory and Its Applications, vol. 2, Wiley, , 2e éd., 669 p. (ISBN 0471257095 et 978-0471257097), p. 262-263.

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]