Voir la source de Problème du collectionneur de vignettes

{{Voir homonymes|CCP}}[[Fichier:Coupon collector problem.svg|vignette|Graphique qui donne, pour chaque nombre {{mvar|n}} de vignettes différentes (axe vertical), le nombre moyen {{math|''E''(''T'')}} de paquets de céréales à acheter pour les posséder toutes (axe horizontal).]]

Le '''problème du collectionneur de vignettes''' ou du '''collectionneur de coupons''' ({{en anglais|coupon collector's problem}}, '''CCP''') est un problème de [[théorie des probabilités|probabilités]] et de [[combinatoire]] qui consiste à estimer le nombre de [[Céréales de petit déjeuner|paquets de céréales]] à acheter pour [[Collection (activité)|collectionner]] une série complète de vignettes, à raison d'une vignette [[Cereal box prize|offerte dans chaque paquet]]. La vignette contenue dans chaque paquet étant inconnue à l'achat, il s'agit d'un [[tirage avec remise]]. En moyenne, si la série compte {{mvar|n}} vignettes différentes, il faut acheter {{math|''n'' (1 + {{sfrac|1|2}} + {{sfrac|1|3}} + ... + {{sfrac|1|''n''}})}} paquets de céréales.

Le problème du collectionneur de vignettes était déjà mentionné en 1812 par [[Pierre-Simon de Laplace]] dans sa ''[[Théorie analytique des probabilités]]'', où il donne, avant [[Paul Erdős|Erdős]] et [[Alfréd Rényi|Rényi]], la convergence vers la [[loi de Gumbel]]. Il est aussi mentionné par [[George Pólya]]<ref>{{article|langue=de|auteur1=George Pólya|titre=Eine Wahrscheinlichkeitsaufgabe in der Kundenwerbung|périodique=[[Journal of Applied Mathematics and Mechanics|Zeitschrift für Angewandte Mathematik und Mechanik]]|volume=10|numéro=1|année=1930|pages=96–97|doi=10.1002/zamm.19300100113}}.</ref>, et il est notamment cité par [[William Feller]]<ref>L'ouvrage de Feller où il est question du problème est {{harvsp|Feller|1968}}, et la remarque est faite par exemple par {{harvsp|Foata|Han|Lass|2001}}.</ref>. L'étude de ce problème et de ses généralisations trouve des applications notamment en ingénierie des [[télécommunications]].

== Définition et notations ==

L'objectif du collectionneur est de posséder une vignette pour chacun des {{mvar|n}} types de vignettes. Pour cela, il achète des boîtes de céréales. Comme le montre la figure ci-dessous, il y a une vignette dans chaque boîte. Dans l'exemple, il achète sa première boîte dans laquelle il obtient la vignette 1. Il achète la deuxième boîte et on obtient la vignette 4. Dans son troisième achat, il obtient la vignette 1 à nouveau : sa collection reste donc la même, à savoir il possède la vignette 1 et 4. Il continue à acheter des boîtes de céréales jusqu'à obtenir une vignette de chaque type. On suppose que toutes les vignettes sont [[Équiprobabilité|équiprobables]] : on a une probabilité de {{sfrac|1|''n''}} d'obtenir tout type de vignettes lors de l'achat d'une boîte.
[[Fichier:Coupon collectors problem example.svg|centré|vignette|860x860px|Exemple d'une collection de 4 vignettes possibles : 1, 2, 3, 4. Sur l'exemple, à l'étape 1 on obtient la vignette 1, à l'étape 2, la vignette 4. à l'étape 3, la vignette 1 à nouveau, etc.]]On note {{mvar|T{{ind|n}}}} le nombre de paquets à acheter pour obtenir la collection complète. Pour l'exemple ci-dessus, <math>T_4=10</math> car le collectionneur a acheté 10 boîtes de céréales avant d'obtenir les 4 vignettes. Intuitivement, les dernières vignettes sont plus difficiles à obtenir que les premières. Pour étudier ce phénomène plus précisément, on introduit également la [[variable aléatoire]] {{mvar|T{{ind|n,k}}}} que l'on note qui représente le nombre de paquets de céréales achetés avant d'obtenir {{Mvar|k}} types de vignettes parmi les {{mvar|n}} types de vignettes de la collection. Dans l'exemple, <math>T_{4, 1}=1</math> car avec un seul achat, on possède forcément une vignette ; <math>T_{4, 2}=2</math>, <math>T_{4, 3}=5</math> et <math>T_{4, 4}=10</math>. Le temps {{mvar|T{{ind|n}}}} d'obtention de la collection totale est donc {{mvar|T{{ind|n,n}}}}. On peut considérer que {{mvar|T{{ind|n,k}}}} est un [[Temps d'arrêt|temps]] : à chaque pas de temps, un paquet de céréales est acheté.

Soit {{mvar|t{{ind|n,i}}}} le temps supplémentaire pour obtenir la {{mvar|i}}-ème nouvelle vignette, sachant que l'on en a déjà {{math|''i'' – 1}} différentes. On a donc <math>T_{n,k}=\sum_{i=1}^k t_{n,i}</math>. Pour l'exemple de la figure ci-dessus, on a <math>t_{4,1} = 1</math> (<math>t_{n,1}</math> est toujours égal à 1), <math>t_{4,2} = 1</math>, <math>t_{4,3} = 3</math> et <math>t_{4,4} = 5</math>. On a ici <math>T_4=10</math> : en effet, dans l'exemple, il y a 10 boîtes achetées pour obtenir la collection complète des 4 vignettes.

== Calculs de l'espérance et de la variance du temps pour finir la collection ==
Lorsque l'on possède déjà {{math|''i'' - 1}} vignettes différentes, on en trouve une nouvelle en achetant une boîte de céréales si on tombe sur l'une des {{math|''n'' – ''i'' + 1}} vignettes nouvelles parmi les {{mvar|n}} possibles. Ainsi, la probabilité d'en trouver une nouvelle est {{sfrac|''n'' – ''i'' + 1|''n''}}. La variable {{mvar|t{{ind|n,i}}}} suit donc une [[loi géométrique]] de paramètre {{sfrac|''n'' – ''i'' + 1|''n''}}. D'où l'[[Espérance mathématique|espérance]] : 

:<math>\mathbb{E}(t_{n,i}) = \frac{1}{\text{paramètre}} =  \frac{n}{n-(i-1)}</math>.

La [[Variance (mathématiques)|variance]], elle, vaut :
:<math>\mathbb V(t_{n,i}) = \frac{1-\text{paramètre}}{\text{paramètre}^2} =\frac{n(i-1)}{(n-i+1)^2}=  \frac{n^2}{(n-i+1)^2} -\frac{n}{n-i+1}</math>.

=== Espérance ===
Par linéarité de l'espérance{{sfn|Gourdon|2021}}, le temps moyen pour obtenir {{Mvar|k}} types de vignettes parmi les {{mvar|n}} types de vignettes de la collection vaut : 

:<math>
\begin{align}
\mathbb{E}(T_{n,k})& = \mathbb{E}(t_{n,1}) + \mathbb{E}(t_{n,2}) + \cdots + \mathbb{E}(t_{n,k}) \\
& = \frac{n}{n} + \frac{n}{n-1} +  \cdots + \frac{n}{n-k+1}\\  
& = n \cdot \left(\frac{1}{n-k+1} + \frac{1}{n-k+2} + \cdots + \frac{1}{n}\right)\\ 
& = \, n \cdot (H_n-H_{n-k}).
\end{align}
</math>
[[Fichier:Collectionneur.gif|vignette|350x350px|Pour <math>n=100</math> vignettes à collectionner, ce graphique présente en abscisse le nombre moyen <math>
\mathbb{E}(T_{100,k})
</math> de paquets nécessaires pour obtenir les <math>k</math> vignettes situées en ordonnée, montrant combien les dernières vignettes sont les plus longues à obtenir.]]
où <math>
H_n=\sum_{k=1}^n\frac1k
</math> est le {{mvar|n}}-ième [[nombre harmonique]]. Le temps moyen d'obtention de la collection totale est donc <math>
\mathbb{E}(T_{n})=\mathbb{E}(T_{n,n})=n\cdot H_n
</math>, puisque <math>
H_0=0
</math>.

==== Exemples ====
Le collectionneur de vignettes est une [[métaphore]] et se retrouve dans des situations qui n'ont rien à voir avec des boites de céréales et des vignettes. Par exemple :
* Le nombre moyen d'essais nécessaires pour obtenir la naissance d'une fille et d'un garçon est <math>\mathbb E(T_2)=3</math>. Ici, chaque naissance correspond à un tirage uniforme entre la naissance d'un garçon ou d'une fille. Le processus s'arrête lorsque l'on a "collectionné" les deux genres.
* Le nombre moyen d'essais de lancers d'un dé à 6 faces pour obtenir tous les nombres de 1 à 6 est <math>\mathbb E(T_6)=14,7</math>. Ici, chaque lancer correspond à un tirage uniforme d'un nombre entre 1 et 6. Le processus s'arrête lorsque l'on a "collectionné" tous les nombres entre 1 et 6.

==== Comportement à l'infini ====
En utilisant le [[développement asymptotique]] de {{mvar|H{{ind|n}}}}, on obtient :

:<math>
\mathbb{E}(T_n)  = n \cdot H_n = n \ln(n) + \gamma \cdot n + \frac1{2} + o(1), \ \ 
\text{pour}  \ n \to \infty,
</math>
où <math>\gamma \approx 0,5772156649</math> est la [[constante d'Euler-Mascheroni]].

==== Temps d'attente moyen de la moitié de la collection ====
Ce nombre est <math>
\mathbb{E}(T_{n,n/2})=n(H_n-H_{n/2})=n\ln2-\frac12+o(1)
</math>. Ainsi, le temps d'attente moyen pour obtenir la moitié de la collection est linéaire en la taille <math>n</math> de la collection ; il est inférieur au temps d'attente total qui est linéarithmique (voir [[complexité en temps]]).

=== Variance ===
En utilisant l'indépendance des variables {{mvar|t{{ind|n,i}}}}, on obtient{{sfn|Gourdon|2021}} :
:<math>
\begin{align}
\mathbb{V}(T_n)& = \mathbb{V}(t_{n,1}) + \mathbb{V}(t_{n,2}) + \cdots + \mathbb{V}(t_{n,n}) \\ 
& =\frac{n^2}{n^2} + \frac{n^2}{(n-1)^2} +  \cdots + \frac{n^2}{1^2} -\mathbb{E}(T_n)\\
& =n^2\left(\sum_{k=1}^n\frac1{k^2}\right) -nH_n\\
\end{align}
</math>
En utilisant les [[développement asymptotique|développements asymptotiques]] de {{mvar|H{{ind|n}}}} et de <math>
\sum_{k=1}^n\frac1{k^2}
</math>, on obtient :
:<math>
\mathbb{V}(T_n)  =\frac{\pi^2}6n^2 - n \ln(n) -( \gamma+1) n + o(1), \ \ 
\text{pour}  \ n \to \infty.
</math>

En utilisant la valeur au point 2 de la [[fonction zeta de Riemann]], on obtient la majoration simple :
:<math>
\begin{align}
\mathbb{V}(T_n)
& \leqslant n^2\left(\sum_{k=1}^n\frac1{k^2}\right) \\
& \leqslant n^2\left(\sum_{k=1}^\infty\frac1{k^2}\right) = \frac{\pi^2}{6} n^2 < 2 n^2.
\end{align}
</math>

Un majoration simple de l’[[Écart type|écart-type]] est donc <math>
\sigma(T_n)\leqslant\frac{\pi}{\sqrt6}n\leqslant1,3 n
</math>.

== Estimations plus précises de l'écart à la moyenne ==

* En utilisant l'[[inégalité de Bienaymé-Tchebychev]] , on a :

:<math>\forall \varepsilon>0,
\mathbb{P}\left(
|T_n- n H_n| \geqslant \varepsilon \, n
\right) \leqslant \frac{2}{\varepsilon^2}.</math>

* On peut aussi montrer le seuil suivant, en utilisant l'[[inégalité de Boole]] (''{{lang|en|union bound}}''){{sfn|Motwani|Raghavan|1995}} :

:<math>\forall \varepsilon>0,\ \lim_{n\rightarrow \infty}\mathbb{P}(T_n>n\ln(n)+\varepsilon n) = 1 - \mathrm{e}^{-\mathrm{e}^{-\varepsilon}}.</math>
La première démonstration connue {{Quoi|date=18 juin 2023}}, via l’analyse des [[Série génératrice|séries génératrices]], est celle de [[Pierre-Simon de Laplace]], dans sa ''[[Théorie analytique des probabilités]]'' en 1812{{sfn|Laplace|1812}}{{référence insuffisante|date=18 juin 2023}}. On cite aussi, souvent, un article{{Lequel|date=18 juin 2023}}<ref>{{article |langue=en |titre=On the Evolution of Random Graphs |auteur1=P. Erdös |auteur2= A. Rényi |périodique=Publications of the Mathematical Institute of the Hungarian Academy of Sciences |date=1960 |passage=343-347 |lire en ligne=https://snap.stanford.edu/class/cs224w-readings/erdos60random.pdf}}</ref>{{,}}<ref>{{article |lang=en |auteur1=B. Bollobás |année=1984 |titre=The Evolution of Random Graphs |périodique=Transactions of the American Mathematical Society |volume=286 |numéro=1 |pages=257–274 |doi=10.2307/1999405}}</ref> d’Erdös et Rényi de 1960{{Référence nécessaire|date=18 juin 2023}}, où les auteurs semblent{{Quoi|date=18 juin 2023}} découvrir à l’occasion la [[loi de Gumbel]], qui réapparaît dans leurs travaux la même année, dans le théorème double-exponentiel précisant le seuil de connexité des [[Graphe aléatoire|graphes aléatoires]].

== Avancement de la collection ==

On peut souhaiter calculer le nombre moyen de vignettes différentes obtenues après {{nobr|{{mvar|N}} achats}}. Pour cela, on peut même supposer que les vignettes ne sont pas équiprobables, mais ont au contraire des probabilités respectives {{math|''p''{{ind|1}}, ... , ''p''{{ind|''n''}}}} d'être trouvées à chaque achat. Dans ces conditions, après {{nobr|{{mvar|N}} achats}}, le nombre moyen de vignettes différentes est <math>C_N=\sum_{k=1}^n\left(1-(1-p_k)^N\right)</math>.

Les fonctions <math>x\geqslant0\mapsto x^N</math> étant [[Fonction convexe|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'équiprobabilité, lorsque {{mvar|N}} est proche de {{math|''n'' ln ''n''}}, on trouve une valeur de {{math|''C''{{ind|''N''}}}} proche de {{mvar|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{{sfn|Foata|Han|Lass|2001}}.
* Le collectionneur achète des pochettes de {{mvar|k}} vignettes différentes. On fait alors apparaître des [[coefficients binomiaux]] dans les formules{{sfn|Sardy|Velenik|2010}}.

== 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<ref>Certains exemples de cette partie proviennent de {{harvsp|Boneh|Hofri|1997}}.</ref>.

* Certaines méthodes pour identifier les [[Contrainte (mathématiques)|contraintes]] intéressantes en [[Optimisation (mathématiques)|optimisation]], consistent à faire un certain nombre de tests et à supposer qu'après cet examen on a trouvé toutes les contraintes intéressantes{{sfn|Boneh|1983}}. 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{{Référence nécessaire|date=19 juin 2023}}.
* Cette technique est aussi utilisée pour détecter des pannes{{Référence nécessaire|date=19 juin 2023}}.
* Dans le domaine de la diffusion de rumeur (''{{lang|en|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{{Référence nécessaire|date=19 juin 2023}}.
* Le problème du collectionneur de vignettes permet d'apporter un argument en faveur, mais non une preuve, de ce que le nombre [[Pi (nombre)|π]] est un [[nombre normal]]. En effet si c'est bien le cas, on peut estimer le nombre de décimales à lire pour trouver les dix chiffres de 0 à 9, les cent séquences de 00 à 99 et ainsi de suite ; les estimations données par le problème du collectionneur de vignettes sont proches des valeurs obtenues en observant le [[développement décimal]] de π{{sfn|Delahaye|2023}}.
* Le problème du collectionneur de vignettes intervient dans l'étude de la [[Complexité en moyenne des algorithmes|complexité en moyenne]] de l'[[algorithme de Gale-Shapley]]<ref name=":0">. {{Ouvrage|langue=fr|auteur1=Donald Knuth|titre=Mariages Stables et leurs relations avec d'autres problèmes combinatoires|lieu=Montréal|éditeur=Les Presses de l'Université de Montréal|année=1976|pages totales=106|isbn=978-2-7606-0529-9|isbn10=2-7606-0529-9|présentation en ligne=http://www-cs-faculty.stanford.edu/~uno/ms.html}}.</ref>. L'objectif de cet algorithme est de calculer un [[Problème des mariages stables|mariage stable]]. L'algorithme procède comme suit. Chaque homme propose un mariage à la femme qu'il préfère le plus parmi celles à qui il n'a pas encore fait de proposition. Lorsqu'une femme célibataire reçoit une proposition, elle l'accepte. Si elle est mariée, elle accepte une proposition uniquement si cette dernière lui convient mieux. L'analyse en moyenne écrite par Donald Knuth<ref name=":0" /> fait une analogie avec le problème du collectionneur de vignettes comme suit. Son analyse repose sur des hommes amnésiques qui font des propositions à des femmes aléatoires. L'algorithme termine alors lorsque les hommes ont fait des propositions à toutes les femmes. L'ensemble des hommes représente les collectionneurs ; les femmes sont les vignettes.

== Notes et références ==
{{Références}}

== Bibliographie ==
=== Étude détaillée du problème ===
* {{Ouvrage|titre = Les maths en tête|tome = ''Algèbre - Probabilités''|auteur = Xavier Gourdon|éditeur =[[Éditions Ellipses|Ellipses]]|lieu=Paris|numéro édition = 3|année première édition = 1994|isbn = 978-2-340-05676-3 |pages totales = 414| année = 2021|titre chapitre = Probabilités|numéro chapitre = 6|passage = problème {{n°}}9 (Problème du collectionneur), {{p.}}356–359 {{lire en ligne|url={{Google Livres|DSNEEAAAQBAJ|page=356}}}}}}.
* {{Ouvrage|auteur1=Gilles Pagès|auteur2=Claude Bouzitat|champ libre=avec le concours de Fabrice Carrance et Frédérique Petit|illustrateur=Yves Guézou|titre=En passant par hasard|sous-titre=Les probabilités de tous les jours|titre chapitre=Pour quelques images de plus|lieu=Paris|éditeur=[[Vuibert]]|date=1999|pages totales=268|isbn=2-7117-5258-5}}.

=== Vulgarisation et aspects généraux ===
* {{ouvrage|auteur1=[[Pierre-Simon de Laplace]]|passage=195 {{lire en ligne|url=https://gallica.bnf.fr/ark:/12148/btv1b8625611h/f205}}|titre=[[Théorie analytique des probabilités]]|année=1812|lieu=Paris|éditeur=Courcier|id=Laplace1812}}.
* {{lien web
 | auteur1 = Sylvain Sardy
 | auteur2 = Yvan Velenik 
 | titre = Petite collection d’informations utiles pour collectionneur compulsif
 | site = [[Images des mathématiques|Images des maths]]
 | date = 11 août 2010 
 | lire en ligne = https://images.math.cnrs.fr/Petite-collection-d-informations-utiles-pour-collectionneur-compulsif
}}.
* {{article
 | langue = en
 | auteur1 = Arnon Boneh 
 | auteur2= Micha Hofri 
 | titre = The coupon-collector problem revisited—a survey of engineering problems and computational methods
 | périodique = {{lien|Stochastic Models}}
 | volume = 13
 | numéro = 1
 | passage = 39–66
 | année = 1997
 | éditeur = [[Taylor & Francis]]
 | lire en ligne = http://web.cs.wpi.edu/~hofri/CCP.pdf
 | doi=10.1080/15326349708807412
}}.
* {{Ouvrage
 | langue=en
 | auteur1=[[William Feller]]
 | titre=An Introduction to Probability Theory and Its Applications
 | volume=1
 | lieu=New York
 | éditeur=[[John Wiley & Sons|Wiley]]
 | année=1968
 | numéro d'édition=3
 | passage=225
}}.
* {{Randomized Algorithms (Motwani et Raghavan)
 |titre chapitre = The Coupon  Collector's Problem |numéro chapitre= 3.6
 |passage= 57–63}}.
* {{Article|auteur1=Robert Ferréol|titre=Le problème du collectionneur|périodique=[[Tangente (magazine)|Tangente Sup]]|date=février 2014|lire en ligne=http://mapage.noos.fr/r.ferreol/atelecharger/textes/Probl%C3%A8me%20du%20collectionneur.pdf|pages=52–56}}.
* {{Article|langue=français|périodique=[[Pour la science]]|titre=Les dures lois des collections|auteur=[[Jean-Paul Delahaye]]|numéro=547|date=mai 2023|lire en ligne=https://www.pourlascience.fr/sr/logique-calcul/les-dures-lois-des-collections-25019.php|pages=80–85}}.

=== Articles et ouvrages de recherche ===

* {{chapitre
 | langue = en
 | auteur1 = Arnon Boneh 
 | titre chapitre = Preduce—A probabilistic algorithm identifying redundancy by a random feasible point generator (RFPG)
 | titre ouvrage = Redundancy in Mathematical Programming
 | passage = 108–134
 | année= 1983
 | éditeur = Springer
}}.
* {{Ouvrage
 | langue=en
 | auteur1=Aimo Torn
 | auteur2=Antanas Zilinskas
 | titre=Global optimization
 | éditeur=[[Springer Science+Business Media|Springer-Verlag]]
 | année=1989
 | isbn=
}}.
* {{article
 | auteur1=[[Dominique Foata]]
 | auteur2 = Guo-Niu Han 
 | auteur3 = Bodo Lass 
 | titre= Les nombres hyperharmoniques et la fratrie du collectionneur de vignettes
 | périodique = Séminaire Lotharingien de Combinatoire
 | volume= 47
 | année = 2001
 | lire en ligne = http://www.emis.de/journals/SLC/wpapers/s47hanfolass.pdf
}}.

== Voir aussi ==
=== Source de la traduction ===
 {{Traduction/Référence|en|Coupon collector's problem|594791832}}

{{Portail|probabilités et statistiques}}

[[Catégorie:Expérience aléatoire]]