Il s'agit encore du problème du collectionneur, déjà proposé il y a quelques mois : 
"Dans chaque tablette de chocolat, on trouve, de façon équiprobable, l'une des n images de la collection. Combien faut-il, en moyenne, acheter de tablettes pour obtenir la collection complète ?
La réponse est : n * somme (1/i, i = 1..n)."

Réponse 1 :

Une approche combinatoire bestiale débouche sur des calculs atroces. Heureusement Super Markov est là.
Posons : T(i,n) = temps restant pour tirer les i boules non encore tirées
Ainsi T(0,n) = 0 (toutes tirées) et T(n,n) est le temps que l'on cherche.
Regardons les transitions à partir de l'état (i,n) :
T(i,n) = 1 + (i / n) * T(i-1,n) + (n-1 / n) * T (i, n).
En effet :
1 : temps d'une transition
(i / n) * T(i-1,n) : temps restant si on a tiré une des boules non encore tirées
(n-1 / n) * T (i, n) : si pas de bol dans le tirage.

En simplifiant :
T(i,n) = n/i + T(i-1,n)
D'où T(n,n) = n * (somme {i entre 1 et n} 1/i) = n * (C + ln (n) + 1/2*n + ....)
Avec C = constante d'Euler (0.577218...)
Une simulation informatique style Monte-Carlo avec n = 100 donne pour 1000 exécutions :

T(100,100) = 521.848
et
n * (C + ln (n) + 1/2*n) = 518.74
Y'a donc des bonnes chances que la formule soit bonne.

Réponse 2 :

Le nombre moyen de tirages est n*(1 + 1/2 + .. + 1/n) (donc n*(1 + 1/2 + .. + 1/n)-1 minutes)
Je définit les variables aléatoires suivantes :
X(m) = nombre de tirages pour obtenir m boules différentes , m=1,2,..,n
Y(m) = X(m+1) - X(m) - 1 , m=1,2,..,n-1
Il est évident que X(1)=1 et X(m) >= m

On cherche d'abord la distribution de probabilité pour Y(m).
On tient compte du fait que les tirages constituent des évènements indépendants et équiprobables.
L'évènement {Y(m)= t} signifie {t tirages consécutifs parmi les m boules différentes déjà tirées, suivis d'un tirage parmi les autres n-m boules}
Pr{tirage parmi les m boules différentes déjà tirées} = m/n
Pr(tirage parmi les autres n-m boules} = (n-m)/n
Donc : Pr{Y(m]=t} = ((m/n)^t)*(n-m)/n
La moyenne de Y(m) sera :
E(Y(m)) = ((n-m)/n)*(m/n)*(1 + 2*(m/n) + 3*((m/n)^2) + ... + t*((m/n)^(t-1))+ ...) =
= ((n-m)/n)*(m/n)*(1/((1 - m/n)^2)) = m/(n-m)
De la définition Y(m)+1 = X(m+1)-X(m) on obtient n/(n-m) = E(X(m+1)) - E(X(m)) .
En additionnant ces relations , de m=1 à m=k-1, on obtient :
E(X(k)) = n*(1/(n-k+1) + 1/(n-k+2) + .. + 1/n), pour tout 2 =< k =< n
Pour k=n on obtient la moyenne recherchée :
E(X(n)) = n*(1 + 1/2 + .. + 1/n)