Le collectionneur de vignettes

import numpy as np
import numpy.random as rd

def collecte(n):
    vues = np.zeros(n)          # vues[i] = 1 des que la vignette i est obtenue
    nb, paquets = 0, 0
    while nb < n:
        v = rd.randint(0, n)
        paquets = paquets + 1
        if vues[v] == 0:
            vues[v] = 1
            nb = nb + 1
    return paquets

n, N = 10, 20000
s = 0
for r in range(N):
    s = s + collecte(n)
print(s / N, n * sum(1 / k for k in range(1, n + 1)))

Le calcul exact. Décomposons $T=T_1+\cdots +T_n$, où $T_i$ est le nombre de paquets ouverts pour passer de $i-1$ à $i$ vignettes distinctes. Quand on en possède déjà $i-1$, chaque paquet apporte une nouveauté avec la probabilité $\frac{n-i+1}{n}$, indépendamment des précédents : $T_i$ est le rang du premier succès, donc $T_i\hookrightarrow \mathcal{G}\left(\frac{n-i+1}{n}\right)$ et $E(T_i)=\frac{n}{n-i+1}$.

La linéarité de l'espérance — qui n'exige aucune indépendance — recolle le tout :

$$E(T)=\sum _{i=1}^n\frac{n}{n-i+1}=n\sum _{k=1}^n\frac{1}{k}.$$

Pour $n=10$ : $E(T)=10\times 2,9290=29,29$.

L'accord. La simulation rend environ $29,3$ sur $20000$ répétitions.

Le point à retenir. Décomposer une attente en une somme d'attentes géométriques est la méthode : chaque étape est sans mémoire, donc géométrique, et la linéarité fait le reste. On y lit aussi la croissance en $n\ln n$ : collectionner $100$ vignettes coûte en moyenne $519$ paquets, pas $100$.