Problème du collectionneur de vignettes

Carte Commune · n° 295316

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, 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.

Lire sur Wikipédia · Image Cmglee, CC BY-SA 3.0