Espérance et collectionneur de vignettes

Bonjour,

Je viens d'essayer de résoudre le "Problème du collectionneur de vignettes". On a un collectionneur de vignettes qui veut obtenir toutes les vignettes et il commence alors à en acheter jusqu'à avoir toutes les vignettes qui existent. On veut savoir combien en moyenne faudrait-il qu'il achète de vignettes pour obtenir toutes les différentes vignettes. Et le résultat d'un achat est indépendant de celui qui le précède.
J'ai naïvement posé $Y$ la variable aléatoire qui donne le nombre de vignettes achetées par le collectionneur avant de trouver toutes les vignettes. Alors si on a $N$ vignettes, la probabilité que $Y$ prenne des valeurs inférieures strictement à $N$ est nulle. La probabilité que $Y=N$ est de $\frac{N!}{N^{N}}$ parce qu'on a chaque vignette achetée il a $N$ choix ce qui donne le $N^{N}$ possibilités de construire une série de $N$ vignettes à partir de $N$ vignettes différentes, et le nombre de choix possibles pour avoir toutes les vignettes différentes dans la même série de $N$ vignettes est $N!$. Pour $Y=N+1$ alors cette probabilité est $\frac{N.N!}{(N+1)^{(N+1)}}$...
L'espérance est alors $E(Y)=\sum_{k=0}^{+\infty}{\frac{N!N^{k}}{(N+k)^{N+k}}}(N+k)$
J'aimerais vous demander si ce calcul est juste. J'ai vu une solution où ils ont posé $Y_{i}$ le nombre de vignettes achetées pour trouver la i-ème différente vignette puis $X_{i}=Y_{i+1}-Y_{i}$... ce qui m'a l'air un peu moins intuitif, c'est pour cela que je vous demande confirmation.

J'espère que vous pourrez m'aider.

Merci d'avance.

Réponses

  • Pour $Y=N+1$ alors cette probabilité est $\frac{N.N!}{(N+1)^{(N+1)}}$...
    Cette formule n'a ni queue ni tête.

    Si on prend $N=1$, elle donne $\frac{1}{4}$, alors qu'on attend 0
    Si on prend $N=2$, elle donne $\frac{4}{27}$, alors qu'on attend $\frac{1}{4}$.
  • On note $X_1$ le temps nécessaire pour obtenir la 1re vignette, $X_2$ le temps nécessaire pour obtenir la 2e (une fois qu'on a la 1re), etc. On note $N$ le nombre total de vignettes.

    Si on a déjà $k$ vignettes, la probabilité d'obtenir une nouvelle vignette lors d'un choix aléatoire est $\frac{N-k}{N}.$ Donc le temps d'attente avant d'avoir la $(k+1)$e vignette suit une loi géométrique de paramètre $\frac{N-k}{N},$ et son espérance est $\frac{N}{N-k}.$

    Ainsi $E(X_1)=\frac{N}{N-0}=1$ (c'est évident, la 1re vignette est nécessairement nouvelle), $E(X_2)=\frac{N}{N-1},$ $E(X_3)=\frac{N}{N-2},$ etc.

    Le temps total pour avoir toutes les vignettes est $X=X_1+X_2+\cdots+X_N,$ donc son espérance est
    $$E(X)=\frac{N}{N-0}+\frac{N}{N-1}+\frac{N}{N-2}+\cdots+\frac{N}{N-(N-1)}=N\left(\frac{1}{N}+\frac{1}{N-1}+\frac{1}{N-2}+\cdots +\frac{1}{1}\right).$$

    Si on veut une valeur approchée, on peut dire que $\frac{1}{N}+\frac{1}{N-1}+\frac{1}{N-2}+\cdots +\frac{1}{1}=\ln N+\gamma+o(1/N)$ ($\gamma$ est la constante d'Euler), donc
    $$E(X)\approx N\left(\ln N +\gamma\right).$$
Connectez-vous ou Inscrivez-vous pour répondre.