Probabilité de doublon

[TheReveller]

Bonjour,

J'ai toujours adoré les probabilités, mais là je cherche une réponse rapide qui m'échappe.

Disons que j'ai un ensemble de nombres entiers de 1 à N. Je veux piger avec remise M nombres de telle sorte que la probabilité que mes M nombres soient tous uniques (sans doublon) soit d'au moins 95%. Quelle est la formule générique derrière cela ? Si M = 1024 nombres, alors quel devra être N pour répondre à cette probabilité de 95% ?

À l'inverse, disons que j'ai un ensemble de nombres entiers de 1 à N. Je pige avec remise M nombres. Quelle est ma probabilité d'avoir un doublon ? Deux doublons ? Trois doublons ? Un triplet ? Deux triplets ? [etc.] ? Quelle est la formule générique ?

Merci !

[Skullkid]

Bonjour, sauf erreur de calcul, la probabilité d'avoir exactement n k-uplets, et aucun autre p-uplet si p est différent de k, en tirant M fois dans |[1,N]| est . Évidemment la formule n'est valable que si nk est inférieur ou égal à M, sinon la proba vaut 0.

Si tu as besoin de trucs plus complexes du genre la proba d'avoir 2 doublons et 7 triplets, va falloir réfléchir à comment combiner les formules...

[TheReveller]

Merci.

Considérant que la formule nécessite des factorielles, je m'aperçois que je deviens limité pour mon calcul avec 1024 dans la plupart des logiciels.

Je crois cependant qu'il y a probablement une erreur dans la formule, puisque j'obtiens une probabilité impossible pour k = 1, m = 10, n = 10.

http://www.wolframalpha.com/input/?i=%28m%21*n%21%29%2F%28n%5Em*%28k%21%29%5En*%28m-n*k%29%21*%28n-m%2Bn*%28k-1%29%29%21%29+where+m+%3D+10%2C+n+%3D+10%2C+k+%3D+1

En fait, je me suis peut-être mal exprimé. Le cas simple d'obtenir une valeur unique à chaque fois est, par exemple avec 5 piges (avec remises) parmi 5 nombres :

5/5 * 4/5 * 3/5 * 2/5 * 1/5 = 5!/5^5

Donc bref, si ça avait été 3 piges parmi 5 nombres :

5/5 * 4/5 * 3/5

C'était pour ce cas spécifique simple, reste la généralisation.

Merci de votre aide.

[Skullkid]

Je crois cependant qu'il y a probablement une erreur dans la formule, puisque j'obtiens une probabilité impossible pour k = 1, m = 10, n = 10.

http://www.wolframalpha.com/input/?i=%28m%21*n%21%29%2F%28n%5Em*%28k%21%29%5En*%28m-n*k%29%21*%28n-m%2Bn*%28k-1%29%29%21%29+where+m+%3D+10%2C+n+%3D+10%2C+k+%3D+1

C'est parce que tu as mal recopié la formule, qui dépend de 4 variables et non 3. La proba d'obtenir M valeurs différentes (M "1-uplets") en tirant M fois dans |[1,N]| s'obtient en posant k = 1 et n = M. On obtient N!*M!/(N^M*(N-M)!). On obtient d'ailleurs le même résultat en considérant la proba d'avoir 0 k-uplets (n = 0) quel que soit k (ce qui est un peu bizarre, mais c'est lié au fait que dans mon calcul j'ai supposé k > 1).

Pour éviter d'avoir à calculer des factorielles gigantesques tu peux découper la formule intelligemment.

[Ben314]

Si je me suis pas gourré ( :hein: ), la proba que, parmi les N numéro de l'urne, il y en ait qui n'ait jamais été tirés, qui ait été tirés une et une seule fois, qui ait été tirés exactement 2 fois,... etc... est :

avec évidement et .

Le cas donné par Skullkid correspondant à , ,

[TheReveller]

Effectivement, le vendredi a été difficile et j'ai complètement mélangé n et N.

Par contre, le résultat est le même :

http://www.wolframalpha.com/input/?i=%28M%21*N%21%29%2F%28N%5EM*%28k%21%29%5En*%28M-n*k%29%21*%28N-M%2Bn*%28k-1%29%29%21%29+where+M+%3D+10%2C+N+%3D+10%2C+n+%3D+10%2C+k+%3D+1

http://www.wolframalpha.com/input/?i=%28M%21*N%21%29%2F%28N%5EM*%28N-M%29%21%29+where+M+%3D+10%2C+N+%3D+10

n k-tuplets, soit 10 1-tuplets, donc 10 nombres uniques, donc n = 10, k = 1
en tirant M fois dans |[1,N]|, soit je tire 10 fois dans [1,10], donc M = 10, N = 10

Bref, dans cet exemple, je tire 10 fois avec remise parmi 10 nombres et je veux obtenir 10 nombres différents, la probabilité étant : 10/10 * 9/10 * 8/10 * ... * 2/10 * 1/10 = 9!/10^9 = 0.000 362 880

[Skullkid]

En effet, avec la formule plus générale de Ben314 (que je te conseille d'utiliser comme référence puisqu'elle ne fait appel à aucune hypothèse ad hoc comme mon k > 1) on voit que j'ai oublié un n! au dénominateur, qui corrige à la fois "l'explosion" que tu as constatée et l'inconsistence entre les cas (n = 0 et k > 1) et (n = M et k = 1).

[Ben314]

Concernant la formule :
Il y a un truc qui me perturbe quand même, c'est que je vois pas trop à quel "polynôme générateur" ça correspond.
Je vois même pas comment montrer que la somme des vaut 1 (évidement en sommant sur tout les tels que et avec et fixés)

Si quelqu'un a une idée (ou une référence vu que ça m'étonnerais fort qu'on soit en train "d'inventer la lune" là)...

[Ben314]

En fait, en réfléchissant un peu, je pense la réponse vient du fait que :

où les désignent les coefficients multinomiaux
et où, dans le 2em coeff. multinomial, il y a en bas fois le nombre 0, fois le nombre 1, etc..

Si on se donne un (M+1)-uplet tels que et et qu'on cherche le nombre de N-uplet tels que :
Pour tout on ait (*)
Alors ce nombre est justement le coefficient multinomial et, par "symétrie" des coeff. multinomiaux, on a systématiquement (avec zéros, un, deux, etc)

Donc où la somme se fait sur les vérifiant (*)

La somme des avec et
est donc égale à la somme des avec .

Et tout cela n'a rien d’étonnant vu que , c'est la proba d'avoir tiré fois la boule n°1, fois la boule n°2, etc...