Problème de répartition uniforme

[lebelge5]

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.

[Luc]

Bonjour,

une première étape serait de calculer le nombre de répartitions possibles. Il resterait alors à les numéroter, et on se ramènerait ainsi à une loi uniforme sur un certain
Les entiers n_a, n_b et n_c sont-ils fixés ou sont-ils aléatoires?

Luc

[Matt_01]

Ou, faute de pouvoir les compter, pouvoir les générer entièrement de manière certaine.
Pour cela, je verrai bien un ordre sur les tirages :
On suppose que l'on note a1, ... ,ap les différent n-uplets de boules que l'on peut avoir (l'ordre se porte alors sur les indices), et chaque tirage représente une liste de taille m de (ai).
Pour palier au problème des "permutations" on peut supposer que chaque liste est triée.
Il suffit alors d'énumérer (par algorithme) toutes ces listes (et ce de manière triée). Ce qui est en fait assez aisé :
On démarre de la liste (1,1,...,1).
On incrémente la position la plus à droite que l'on peut incrémenter (de manière à respecter la croissance) en remettant à 1 toutes les positions plus à droite et on recommence (avec les éléments bornés par p).
Par exemple pour p = 3 et m = 3 on aurait :
(1,1,1) ; (2,1,1) ; (2,2,1) ; (2,2,2) ; (3,1,1) ; (3,2,1) ; (3,2,2) ; (3,3,1) ; (3,3,2) ; (3,3,3).
Une fois l'ensemble de ces listes généré, il suffit d'enlever celles qui ne respectent pas la contrainte des n_i, et le tour est joué.

Je pense qu'il y a un moyen de générer directement celles respectant la contrainte, mais je n'y ai pas réfléchi (si t'es pas obligé d'optimiser le truc c'est pas un gros problème).


Edit : Sinon, on tire un nombre entre 1 et (p+1)^m-1, on considère son écriture en base p+1, si elle est triée alors on regarde si son tirage associé respecte les contraintes et dans ce cas on le choisit. Sinon on recommence le tirage.

[lebelge5]

Merci à tous les deux pour vos réponses.
En effet, ce n'est pas compliqué de générer toutes les possibilités, de les numéroter puis de tirer au sort des nombres entre 1 et le nombre de possibilités. Et Matt_01 tu as raison, les séquences décroissantes nous débarrassent du problème des permutations. Mais je ne peux pas le faire, parce que ce nombre augmente incroyablement vite ! Par exemple, s'il y a 10 boules dans chacune 3 urnes, il y a 5151 compositions possibles pour les (n_a, n_b, n_c), et pour chacune de ces compositions, il y a environ 1 million de répartitions possibles ! (Luc, ces nombres peuvent être tirés ou hasard ou pas, ça n'a pas d'incidence. Suppose qu'ils sont donnés).
Alors imaginez s'il y a 100 boules dans 10 urnes, c'est juste infaisable...

C'est pour cela que j'ai besoin de tirer un échantillon aléatoire parmi toutes les possibilités, parce que la machine ne peut pas examiner chaque cas. Elle pourrait en examiner un échantillon.
Mais pour que les conclusions que j'en tire soient "cohérentes", il faut que l'échantillon soit tiré uniformément dans l'ensemble des possibilités.

Voilà, je pense que vous avez bien saisi mon problème, merci de votre aide.

[lebelge5]

Et pour revenir sur ton point, Matt, en effet on peut tirer un nombre entre 1 et (p+1)^m-1, c'est vrai. Mais si p = 1000 (ce qui reste vraiment petit) et m = 10, c'est pas faisable pour une machine de générer des nombres entre 1 et 10^27.

C'est pourquoi il faut vraiment trouver un processus aléatoire qui sélectionne en amont la manière de former les répartitions.