Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
259 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

problème de répartition uniforme

Envoyé par lebelge5 
problème de répartition uniforme
il y a huit années
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.
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 147 733, Messages: 1 484 846, Utilisateurs: 28 072.
Notre dernier utilisateur inscrit Tournencarré.


Ce forum
Discussions: 9 033, Messages: 68 448.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page