Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Problème du collectionneur de vignettes
Résumé
vignette|Graphique qui donne, pour chaque nombre n de vignettes différentes (axe vertical), le nombre moyen 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 (, CCP) est un problème de probabilités et de combinatoire qui consiste à estimer le nombre de paquets de céréales à acheter pour collectionner une série complète de vignettes, à raison d'une vignette 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 n vignettes différentes, il faut acheter n (1 + 1/2 + 1/3 + ... + 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 Erdős et Rényi, la convergence vers la loi de Gumbel. Il est aussi mentionné par George Pólya, et il est notamment cité par William Feller. L'étude de ce problème et de ses généralisations trouve des applications notamment en ingénierie des télécommunications.
L'objectif du collectionneur est de posséder une vignette pour chacun des 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 équiprobables : on a une probabilité de 1/n d'obtenir tout type de vignettes lors de l'achat d'une boîte.
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.
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.