Le collectionneur de vignettes

import numpy.random as rd

def collection(n):
    vues = [False] * n
    restant, achats = n, 0
    while restant > 0:
        v = rd.randint(0, n)          # entier de 0 a n-1
        achats = achats + 1
        if not vues[v]:
            vues[v] = True
            restant = restant - 1
    return achats

n = 50
X = [collection(n) for _ in range(10000)]
print(sum(X) / len(X))                       # ~225
print(n * sum(1 / k for k in range(1, n + 1)))   # 224.96

Le calcul exact. Découpons l'attente. Quand on possède déjà $j$ vignettes distinctes, chaque paquet apporte une nouveauté avec la probabilité $\frac{n-j}{n}$, et les paquets sont indépendants : le nombre $T_j$ de paquets à acheter pour passer de $j$ à $j+1$ vignettes suit donc une loi géométrique de paramètre $\frac{n-j}{n}$, d'espérance $\frac{n}{n-j}$.

Comme $X=T_0+T_1+\cdots +T_{n-1}$, la linéarité de l'espérance — qui ne réclame aucune hypothèse d'indépendance — donne

$$E(X)=\sum _{j=0}^{n-1}\frac{n}{n-j}=n\sum _{k=1}^n\frac{1}{k}.$$

Pour $n=50$ : ${\sum }_{k=1}^{50}\frac{1}{k}\approx 4,4992$, donc $E(X)\approx 224,96$. La moyenne simulée s'en approche à moins de $1\%$.

Le point à retenir. Cette somme est la somme partielle de la série harmonique, qui diverge : le coût par vignette augmente sans cesse. Pour $n=100$ on trouve $E(X)\approx 518,7$, soit $2,3$ fois plus pour deux fois plus de vignettes. Doubler la collection coûte plus du double — et c'est le chapitre sur les séries qui le dit.