Problème du collectionneur de vignettes
De Wikipedia, l'encyclopédie encyclopedia
Pour les articles homonymes, voir CCP.
Le problème du collectionneur de vignettes ou du collectionneur de coupons (en anglais : coupon collector's problem, 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[1], et il est notamment cité par William Feller[2]. L'étude de ce problème et de ses généralisations trouve des applications notamment en ingénierie des télécommunications.