Et donc je commence au sujet des questions posées par Chronica universalis.
Le problème soulevé dans le cadre de la discussion sur Chronica Universalis est connu en maths comme celui du collectionneur de vignettes (coupon collector en anglais).
C’est un problème bien connu et bien étudié dans ses versions simples. On trouve sur le site du CNRS un article relativement facile d’accès sur le sujet pour les personnes avec une certaine aisance en mathématique.
Je vous fais un résumé du cas le plus simple car le raisonnement l’est aussi. On suppose que la collection comprend au total n cartes différentes. On suppose que les cartes sont achetées une par une et qu’elles sont équiprobables, ce qui veut dire que chaque carte à 1/n chance d’être celle qu’on achète : on prend une carte parmi n, d’où le 1 divisé par n.
Pour la première carte achetée, on est bien sûr certain d’avoir une nouvelle carte. Quand on possède p cartes, la probabilité d’obtenir une nouvelle carte tombe à (n-p)/n, grâce à l’hypothèse d’uniformité. En effet, sur les n cartes, j’en possède déjà p, donc il ne reste que n-p cartes intéressantes. Parmi les n tirages possibles, seuls n-p m’intéressent, d’où la probabilité (n-p)/n (qui vient toujours de l’hypothèse d’équiprobabilité).
Pour étudier le problème, on introduit des variables aléatoires (ce n’est pas sale). Ce sont des quantités aléatoires auxquelles on donne un nom, pour simplifier. X1 est le nombre de cartes que j’achète pour passer de 0 carte à 1 carte (on sait que X1=1, ce n’est pas une variable aléatoire dans les faits). X2 est le nombre de cartes que j’achète pour passer de 1 carte à 2 cartes distinctes, etc. Par exemple Xk est le nombre de cartes que j’achète pour passer de k-1 cartes distinctes à k cartes distinctes.
X2 est bien une quantité aléatoire car j’ai une probabilité de (n-1)/n de passer de 1 à 2 en un achat, mais il me reste une probabilité de 1/n de rester avec une seule carte après mon achat. X2 (et ses copines) sont des variables géométriques et on connaît bien leur comportement : la probabilité que Xk soit égale à p, P(Xk=p), vaut (k-1)^(p-1)(n-k+1)/(n^p) (je note a^b pour a à la puissance b). La formule s’explique bien : il vaut que je me rate (p-1) fois puis que je réussisse. Comme les achats sont indépendants, je multiplie les probabilités. Chaque ratage a une probabilité de (k-1)/n (je retombe sur une de mes k-1 cartes) alors que la réussite a une probabilité de (n-k+1)/n.
Un truc bien pratique est que la valeur moyenne de Xk est tout simplement n/(n-k-1). Un autre truc bien pratique est que pour obtenir une collection complète, je dois acheter X1+X2+…+Xk+…+Xn cartes (d’après la définition). Un dernier truc pratique est que la valeur moyenne d’une somme de variables aléatoires est la somme de leur valeurs moyennes. En moyenne, je dois donc acheter 1+n/(n-1)+n/(n-2)+…+n/(n-k+1)+…+n cartes. Cela peut s’écrire n(1+1/2+1/3+…+1/n). La somme 1+1/2+1/3+…+1/n est Hn le n-ème nombre harmonique, un truc qui plaît bien aux matheux. On sait en particulier approcher l’objet et dire que Hn vaut environ ln n + 0.5772156649.
Donc en moyenne, il faut acheter n(ln n + 0.5772156649) paquets pour obtenir une collection complète. Donc pour 150 cartes, on est sur environ 838 cartes (et pas 752 comme j’avais écrit ailleurs en oubliant le 0.58).
Voilà pour la version facile. On peut dire de nombreuses autres choses en s’appuyant sur le fait que les variables sont indépendantes. De ce fait la variance du nombre de cartes est la somme des variantes des différentes variables aléatoires. La variance de Xk vaut (1-lk)/(lk^2) avec lk=(n-k+1)/n. Avec quelques manipulations, on peut montrer que la variance est plus petite que pi^2n^2/6 (oui, oui, le pi des cercles). Pour 150 cartes, ça nous fait une variance de 37011 (!!!) et donc un écart type de 192. Attention, ce n’est pas une distribution gaussienne, donc on ne peut pas en déduire que dans 95% des cas on aura entre 838-2192=454 et 838+2192=1222 cartes à acheter, mais ça donne une idée de la variabilité assez importante à laquelle on est confronté.
En s’appuyant sur la variance ou sur d’autres approches plus précises, on peut estimer la concentration du nombre de paquet autour de la valeur moyenne d’une façon plus raisonnable que mon calcul gaussien au dessus. Par exemple pour être sûr à 95% d’avoir une collection complète, il faut acheter environ 1201 cartes (comme quoi l’approximation gaussienne n’est pas si mauvaise). La formule n’est pas super compliquée : si on être sûr avec une probabilité de 1-delta, il faut (1-log delta/log n) n log n achats.
Malheureusement, les choses se compliquent considérablement quand on achète des paquets de cartes. La suite au prochain numéro…