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 $T n$ 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 $T n$ est un temps : à chaque pas de temps un paquet de céréales est acheté. Soit $t i$ 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 $T_{n}=\sum _{i=1}^{n}t_{i}$ .

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 $t i$ suit donc une loi géométrique de paramètre $n - i +1 / n$ . D'où l'espérance :

\mathbb {E} (t_{i})={\frac {n}{n-(i-1)}}

Espérance

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

{\begin{aligned}\mathbb {E} (T_{n})&=\mathbb {E} (t_{1})+\mathbb {E} (t_{2})+\cdots +\mathbb {E} (t_{n})\\&={\frac {n}{n}}+{\frac {n}{n-1}}+\cdots +{\frac {n}{1}}\\&=n\cdot \left({\frac {1}{1}}+{\frac {1}{2}}+\cdots +{\frac {1}{n}}\right)\\&=\,n\cdot H_{n}.\end{aligned}}

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

\mathbb {E} (T_{n})=n\cdot H_{n}=n\ln(n)+\gamma n+{\frac {1}{2}}+o(1),\ \ {\text{pour}}\ n\to \infty ,

où $\gamma \approx 0,5772156649$ est la constante d'Euler-Mascheroni.

Variance

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

{\begin{aligned}\operatorname {Var} (T_{n})&=\operatorname {Var} (t_{1})+\operatorname {Var} (t_{2})+\cdots +\operatorname {Var} (t_{n})\\&\leq {\frac {n^{2}}{n^{2}}}+{\frac {n^{2}}{(n-1)^{2}}}+\cdots +{\frac {n^{2}}{1^{2}}}\\&\leq n^{2}\cdot \left({\frac {1}{1^{2}}}+{\frac {1}{2^{2}}}+\cdots \right)={\frac {\pi ^{2}}{6}}n^{2}<2n^{2},\end{aligned}}

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

Grâce au calcul de la variance on peut obtenir l'inégalité suivante en utilisant l'inégalité de Bienaymé-Tchebychev :

\forall \varepsilon >0,\mathbb {P} \left(|T_{n}-nH_{n}|\geq \varepsilon \,n\right)\leq {\frac {2}{\varepsilon ^{2}}}.

On peut aussi montrer le seuil suivant, en utilisant l'inégalité de Boole (union bound)[4] :

\forall \varepsilon >0,\ \lim _{n\rightarrow \infty }\mathbb {P} (T_{n}>n\ln(n)+\varepsilon n)=1-e^{-e^{-\varepsilon }}.

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 $N$ achats. Pour cela, on peut même supposer que les vignettes ne sont pas équiprobables, mais ont au contraire des probabilités respectives $p_{1},\dots ,p_{n}$ d'être trouvées à chaque achat. Dans ces conditions, après $N$ achats, le nombre moyen de vignettes différentes est $C_{N}=\sum _{k=1}^{n}{\big (}1-(1-p_{k})^{N}{\big )}$ .

Les fonctions $x\geqslant 0\mapsto x^{N}$ é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 $N$ est proche de $n\ln n$ , on trouve une valeur de $C_{N}$ proche de $n$ , 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

(de) George Pólya, « Eine Wahrscheinlichkeitsaufgabe in der Kundenwerbung », Zeitschrift für Angewandte Mathematik und Mechanik, vol. 10, n^o 1,‎ 1930, p. 96–97 (DOI 10.1002/zamm.19300100113).
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.
Gourdon 2021.
Motwani et Raghavan 1995.
Foata, Han et Lass 2001.
Sardy et Velenik 2010.
Certains exemples de cette partie proviennent de Boneh et Hofri 1997.
Boneh 1983.

Bibliographie

Étude détaillée du problème

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

Vulgarisation et aspects généraux

Pierre-Simon de Laplace, Théorie analytique des probabilités, 1812 sur Gallica.
Sylvain Sardy et Yvan Velenik, « Petite collection d’informations utiles pour collectionneur compulsif », Images des maths,‎ 11 août 2010 (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, n^o 1,‎ 1997, p. 39-66 (DOI 10.1080/15326349708807412, lire en ligne).
(en) William Feller, An Introduction to Probability Theory and Its Applications, vol. 2, Wiley, 1^er janvier 1991, 2^e éd., 669 p. (ISBN 0-471-25709-5 et 978-0471257097), p. 262-263.
(en) Rajeev Motwani et Prabhakar Raghavan, Randomized Algorithms, Cambridge ; New York, Cambridge University Press (réimpr. 1997, 2000) (1^re éd. 1995), 476 p. (ISBN 9780521474658), chap. 3.6 (« The Coupon Collector's Problem »), p. 57-63.

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, 1983, p. 108-134.
(en) Aimo Torn et Antanas Zilinskas, Global optimization, Springer-Verlag, 1989.
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,‎ 2001 (lire en ligne).

Voir aussi

Source de la traduction

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Coupon collector's problem » (voir la liste des auteurs).

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.

[1] (de) George Pólya, « Eine Wahrscheinlichkeitsaufgabe in der Kundenwerbung », Zeitschrift für Angewandte Mathematik und Mechanik, vol. 10, n^o 1,‎ 1930, 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.

[Gourdon2021-3] Gourdon 2021.

[MotwaniRaghavan1995Motwani_Raghavan_1995-4] Motwani et Raghavan 1995.

[FoataHanLass2001-5] Foata, Han et Lass 2001.

[SardyVelenik2010-6] Sardy et Velenik 2010.

[7] Certains exemples de cette partie proviennent de Boneh et Hofri 1997.

[Boneh1983-8] Boneh 1983.