problème de répartition uniforme
Bonjour,
J'ai le problème suivant :
je dois répartir nxm boules dans m urnes de taille n. Les boules sont de trois types (a, b ou c). J'ai donc n_a boules de type a, n_b boules de type b, n_c boules de type c, avec n_a + n_b + n_c = mxn. Je veux les répartir dans les urnes de toutes les façons possibles, sans considérer l'ordre des urnes.
Par exemple, si j'ai 3 urnes de taille 2 (m = 3, n = 2) et n_a = 2, n_b = 3 et n_c = 1, alors j'ai 3 répartitions différentes possibles :
aa bb bc (1)
ab ab bc (2)
ac ab bb (3)
parce que la répartition bc aa bb par exemple n'est en fait qu'une permutation de la répartition aa bb bc.
Quand m et n sont grands, le nombre de cas devient gigantesque, je ne peux pas tous les étudier. Je cherche donc une méthode pour générer un échantillon aléatoire de tous ces cas, tel que chaque répartition possible ait la même probabilité d'être sélectionnée.
Une manière de faire qui ne marche pas consiste à générer toutes les répartitions possibles sans tenir compte des permutations et à en tirer certaines au sort de manière uniforme. Mais ça ne marche pas parce que chaque répartition différente n'a pas le même nombre de permutations possibles.
Dans l'exemple ci-dessus, la répartition (1) a 6 permutations possibles, la (2) en a 6 également mais la (3) n'en a que 3. Donc il y a 15 possibilités, mais si je tire aléatoirement et uniformément des nombres entre 1 et 15, j'aurai en moyenne 2 fois plus de profils de type (1) ou (2) que de type (3), ce qui n'est pas uniforme...
Voilà, merci de partager vos idées.
J'ai le problème suivant :
je dois répartir nxm boules dans m urnes de taille n. Les boules sont de trois types (a, b ou c). J'ai donc n_a boules de type a, n_b boules de type b, n_c boules de type c, avec n_a + n_b + n_c = mxn. Je veux les répartir dans les urnes de toutes les façons possibles, sans considérer l'ordre des urnes.
Par exemple, si j'ai 3 urnes de taille 2 (m = 3, n = 2) et n_a = 2, n_b = 3 et n_c = 1, alors j'ai 3 répartitions différentes possibles :
aa bb bc (1)
ab ab bc (2)
ac ab bb (3)
parce que la répartition bc aa bb par exemple n'est en fait qu'une permutation de la répartition aa bb bc.
Quand m et n sont grands, le nombre de cas devient gigantesque, je ne peux pas tous les étudier. Je cherche donc une méthode pour générer un échantillon aléatoire de tous ces cas, tel que chaque répartition possible ait la même probabilité d'être sélectionnée.
Une manière de faire qui ne marche pas consiste à générer toutes les répartitions possibles sans tenir compte des permutations et à en tirer certaines au sort de manière uniforme. Mais ça ne marche pas parce que chaque répartition différente n'a pas le même nombre de permutations possibles.
Dans l'exemple ci-dessus, la répartition (1) a 6 permutations possibles, la (2) en a 6 également mais la (3) n'en a que 3. Donc il y a 15 possibilités, mais si je tire aléatoirement et uniformément des nombres entre 1 et 15, j'aurai en moyenne 2 fois plus de profils de type (1) ou (2) que de type (3), ce qui n'est pas uniforme...
Voilà, merci de partager vos idées.
Connectez-vous ou Inscrivez-vous pour répondre.