Petit problème de combinatoire simple
Répondre à la discussion
Affichage des résultats 1 à 7 sur 7

Petit problème de combinatoire simple



  1. #1
    invite0cea7419

    Petit problème de combinatoire simple


    ------

    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 ?


    -----

  2. #2
    invite6de5f0ac

    Re : Petit problème de combinatoire simple

    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

  3. #3
    invite0cea7419

    Re : Petit problème de combinatoire simple

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

  4. #4
    invite9cf21bce

    Re : Petit problème de combinatoire simple

    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.

  5. A voir en vidéo sur Futura
  6. #5
    invite0cea7419

    Re : Petit problème de combinatoire simple

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

  7. #6
    invité576543
    Invité

    Re : Petit problème de combinatoire simple

    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...

  8. #7
    invite0cea7419

    Re : Petit problème de combinatoire simple

    Citation Envoyé par mmy Voir le message
    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".

Discussions similaires

  1. problème de combinatoire
    Par christophe_de_Berlin dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 15/03/2007, 08h26
  2. Petit soucis de proba combinatoire
    Par invite88fa9f2c dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 04/10/2006, 23h36
  3. Petit pb. de combinatoire.
    Par Bleyblue dans le forum Mathématiques du supérieur
    Réponses: 9
    Dernier message: 23/07/2006, 12h29
  4. probleme de combinatoire
    Par invitedf6d88d6 dans le forum Logiciel - Software - Open Source
    Réponses: 0
    Dernier message: 26/02/2006, 10h01
  5. Problème combinatoire.
    Par Antikhippe dans le forum Mathématiques du supérieur
    Réponses: 5
    Dernier message: 23/05/2004, 10h08