Numero medio di tentantivi per estrarre 10 numeri a caso diversi

[superfox1]

Ciao,
scusate, mi sono nuovamente incasinato con la probabilita`. Allora ho un generatore pseudo-casuale che tira fuori un intero nell`intervallo [1, M] con distribuzione uniforme.Voglio estrarre N numeri diversi per inserirli in un insieme S, inizialmente vuoto, con un algoritmo del tipo:
1. Estrai a caso \( n \in [1,M] \)
2. Aggiungi n in S se non e` gia presente
3. Ripeti 1. se \( |S| < N \)
Il mio quesito e` quante iterazioni sono in media necessarie?

L'approccio che ho seguito e` stato quello di contare il numero di tentativi per estrarre il k-esimo numero valido:
- con k=1, e` necessario un solo tentativo perche` S e`vuoto.
- con k>1, sono gia`stati estratti k-1 numeri, ed il numero di tentativi necessari e`descritto da una geometrica con \( p = \frac{M - (k-1)} { M} \) e media \( \frac { M }{ M - k + 1} \).
Dunque la media di iterazione e` data da \( M \cdot \sum_{k=0}^{N-1} \frac{1} {M-k} \) ??

C`e`un approccio meno "artigianale"?

Ciaps,
s.fox

[superfox1]

Ciao Sergio,
E` un algoritmo semplice e molto elegante, sicuramente da tenere in considerazione. Pero` attenzione, tecnicamente le iterazioni sono N, mentre la complessita` e lo spazio dell`algoritmo e` O(M) perche` bisogna impostare E = [ 1 .. M ].

Ciao & grazie,
s.fox