Probabilità di pescare N oggetti in M pescate

[zagamid]

Propongo un problema/giochetto che mi sono posto, che non sono riuscito a risolvere, e che ritengo non banale.

Data una collezione di \(\displaystyle N \) oggetti:
1) si pesca un oggetto a caso;
2) si annota l'oggetto pescato;
3) si ripone l'oggetto pescato insieme agli altri;
4) si riparte dal punto 1 finché ogni oggetto non è stato annotato almeno una volta.

Mi chiedo:
a) ripetendo l'esperimento infinite volte, qual è il numero medio di pescate eseguite per annotare tutti gli oggetti?
b) qual è la probabilità di riuscire ad annotare tutti gli oggetti in esattamente \(\displaystyle M \) pescate?
c) e in non più di \(\displaystyle M \) pescate?
d) e in non meno di \(\displaystyle M \) pescate?
\(\displaystyle M \) è un numero di pescate arbitrario.

Il mio tentativo:

Indico gli \(\displaystyle N \) oggetti con \(\displaystyle a_1, a_2, ..., a_N \).
Pescando \(\displaystyle M \) volte, si può considerare la lista di oggetti pescati come una stringa \(\displaystyle a_{i_1}, a_{i_2}, ..., a_{i_M} \), di \(\displaystyle M \) elementi.
Ogni possibile stringa è una disposizione con ripetizioni di \(\displaystyle N \) elementi presi a gruppi di \(\displaystyle M \), cioè le possibili stringhe sono \(\displaystyle N^M \).
Pescare \(\displaystyle M \) volte e riuscire ad annotare tutti gli \(\displaystyle N \) oggetti significa che la stringa associata alla serie di \(\displaystyle M \) pescate contiene ogni oggetto almeno una volta; si tratta allora di capire quali delle \(\displaystyle N^M \) disposizioni con ripetizione contengono delle sotto-stringhe che sono permutazioni degli \(\displaystyle N \) oggetti. Capiamo quindi che si deve avere \(\displaystyle M \geq N \), altrimenti la probabilità di annotare tutti gli \(\displaystyle N \) oggetti è \(\displaystyle 0 \).

Quindi riguardo la domanda b, la probabilità è \(\displaystyle \frac{X}{N^M} \), dove \(\displaystyle X \) è il numero delle sotto-stringhe che contengono le permutazioni. Trovare \(\displaystyle X \), a meno che \(\displaystyle M=N \), caso nel quale \(\displaystyle X=N! \), non mi sembra un problema di calcolo combinatorio banale. Non ho idea di come trovare \(\displaystyle X \) dati \(\displaystyle N \) e \(\displaystyle M \) arbitrari.

Le altre domande mi sembrano intrinsecamente legate alla b, quindi non so come procedere.

Indizi?

[nino_12]

Il numero medio di pescate è:

$ N/N + N/(N-1) + N/(N-2) + .... + N/2 + N/1 $

Cerca con google "Problema del collezionista" e "costante di Eulero-Mascheroni"

Per quanto riguarda il calcolo del numero che tu definisci X, guarda questa discussione:
http://www.trekportal.it/coelestis/show ... 0&page=110
partendo dal testo #1067.