Petit problème de combinatoire simple

[championnet]

Disons que j'ai un ensemble/univers de taille N. Je réalise k tirages aléatoires uniformes indépendants. Quelle est l'espérance du nombre d'elements distincts que j'aurai à la fin ?


-----

[fderwelt]

Bonjour,

Disons que ça dépend beaucoup de ce que sont tes N objets au départ... S'ils sont tous identiques, tu en auras k identiques à la sortie quel que soit k

Ou alors ils sont tous distincts, mais tu effectues k tirages avec remise?

-- françois

[championnet]

Les objects parmis lesquels je tire sont tous différents. Et oui, on fait des tirages avec remise.

[Taar]

Salut.

Après moult calculs de sommes dans tous les sens, je trouve



comme espérance. C'est trop beau pour être vrai, ça doit pas être ça...

Quoique, c'est toujours inférieur ou égal à k (raisonnable) et à N (tout aussi raisonnable).

Taar.

[A voir en vidéo sur Futura]

[championnet]

Tu peux me donner quelques détails sur la façon dont tu fais le calcul ?

[invité576543]

Par exemple...

Notons f(k, i) la probabilité de i éléments différents après k tirages.

1/ Pour k>0, f(k, i) s'exprime en fonction de certains des f(k-1, i) en remarquant que, si on a déjà i valeurs différentes, il y a une probabilité i/N de tirer une valeur déjà connue, et (1-i/N) d'en tirer une nouvelle.

2/ Si on ne cherche que l'espérance mathématique, on cherche , et on va pouvoir exprimer, grâce à la récurrence trouvé en 1/, cette somme comme une fonction assez simple de M(k-1) et de N.

3/ On trouve alors que la suite M(k) est affine, ce qui permet d'obtenir facilement

Je ne donne pas tous les calculs, un peu de travail est utile...

Cordialement,

Note: Le résultat est bien le même que celui donné par Taar...

[championnet]

Par exemple...

Notons f(k, i) la probabilité de i éléments différents après k tirages.

1/ Pour k>0, f(k, i) s'exprime en fonction de certains des f(k-1, i) en remarquant que, si on a déjà i valeurs différentes, il y a une probabilité i/N de tirer une valeur déjà connue, et (1-i/N) d'en tirer une nouvelle.

Euh, moi j'ai ça comme formule de récurrence :


Donc la sommation ne s'écrit pas si simplement chez moi (à moins que je sois un boulet quelque part...), à cause du "i-1".