On me donne un générateur de nombres aléatoires entiers uniformes ~ U 3 (1,3) (inclus). Je voudrais générer des entiers ~ U 5 (1,5) (inclus) en utilisant U 3 . Quelle est la meilleure façon de procéder?
Cette approche la plus simple à laquelle je puisse penser consiste à échantillonner deux fois à partir de U 3 , puis à utiliser un échantillonnage par rejet. C'est à dire, échantillonner deux fois à partir de U 3 nous donne 9 combinaisons possibles. Nous pouvons attribuer les 5 premières combinaisons à 1,2,3,4,5, et rejeter les 4 dernières combinaisons.
Cette approche s'attend à échantillonner à partir de U 3 9/5 * 2 = 18/5 = 3,6 fois.
Une autre approche pourrait consister à échantillonner trois fois à partir de U 3 . Cela nous donne un espace échantillon de 27 combinaisons possibles. Nous pouvons utiliser 25 de ces combinaisons et rejeter la dernière 2. Cette approche prévoit d'utiliser U 3 27/25 * 3,24 fois. Mais cette approche serait un peu plus fastidieuse à rédiger car nous avons beaucoup plus de combinaisons que la première, mais le nombre d'échantillons attendu à partir de U 3 est meilleur que le premier.
Y a-t-il d'autres approches, peut-être meilleures, pour y parvenir?
Je l'ai marqué comme indépendant du langage, mais je cherche principalement à le faire en Python ou C ++.
3 Réponses :
Pour la plage [1, 3] à [1, 5], cela équivaut à lancer un dé à 5 faces avec un à 3 faces.
Cependant, cela ne peut pas être fait sans «gaspiller» le hasard (ou courir indéfiniment dans le pire des cas), puisque tous les facteurs premiers de 5 (à savoir 5) ne se divisent pas 3. Ainsi, le mieux que l'on puisse faire est de utiliser l'échantillonnage de rejet pour se rapprocher arbitrairement de l'absence de "gaspillage" du caractère aléatoire (par exemple en regroupant plusieurs rouleaux du dé à 3 faces jusqu'à ce que 3 ^ n soit "assez proche" d'une puissance de 5). En d'autres termes, les approches que vous donnez dans votre question sont aussi bonnes que possible.
Plus généralement, un algorithme pour lancer un dé à k faces avec un dé à p faces "gaspillera" inévitablement le hasard (et fonctionnera indéfiniment dans le pire des cas) à moins que "chaque nombre premier divisant k divise également p ", selon le lemme 3 dans " Simuler un dé avec un dé " par B. Kloeckner. Par exemple:
Voir aussi cette question: Conversion frugale de nombres aléatoires uniformément distribués d'une plage à une autre .
Vous n'avez pas besoin de combinaisons. Un léger ajustement en utilisant l'arithmétique de base 3 supprime le besoin d'une table. Plutôt que d'utiliser directement le résultat 1..3, soustrayez 1 pour le placer dans la plage 0..2 et traitez-le comme un chiffre de base 3. Pour trois échantillons, vous pouvez faire quelque chose comme:
function sample3() result <- 0 result <- result + 9 * (randU3() - 1) // High digit: 9 result <- result + 3 * (randU3() - 1) // Middle digit: 3 result <- result + 1 * (randU3() - 1) // Units digit: 1 return result end function
Cela vous donnera un nombre compris entre 0..26 ou 1..27 si vous en ajoutez un. Vous pouvez utiliser ce numéro directement dans le reste de votre programme.
Ah, cela semble être ce à quoi j'ai fait allusion avec ma deuxième approche, mais plus joliment écrite. Donc, essentiellement ici, les premier, deuxième, troisième échantillons représentent les bits les plus significatifs aux bits les moins significatifs d'un entier de base 3?
Peter O. a raison, vous ne pouvez pas vous échapper pour perdre un peu de hasard. Le seul choix est donc entre le coût des appels à U (1,3), la clarté du code, la simplicité, etc.
Voici ma variante, créer des bits à partir de U (1,3) et les combiner avec le rejet
C / C ++ (non testé!)
int U13(); // your U(1,3)
int getBit() { // single random bit
return (U13()-1)&1;
}
int U15() {
int r;
for(;;) {
int q = getBit() + 2*getBit() + 4*getBit(); // uniform in [0...8)
if (q < 5) { // need range [0...5)
r = q + 1; // q accepted, make it in [1...5]
break;
}
}
return r;
}
Je suggérerais que votre deuxième approche soit optimale. Le taux de rejet (2/27 = 7,4%) est le meilleur qui puisse être atteint avec l'arithmétique 32 bits. (Rien ne vaut cela jusqu'à ce que vous atteigniez 5 ^ 15 et 3 ^ 22, ce qui réduit le taux de rejet à 2,75%)
@ r3mainer Pourquoi rien ne le bat jusqu'à ce que vous atteigniez 5 $ ^ 15 $ et 3 $ ^ 22 $. Je ne sais pas ce que signifient ces chiffres dans le contexte de ce problème.
Si vous générez U (1,27) à partir de trois lancers de U (1,3), vous devez défausser, en moyenne, 2 numéros sur 27. Il s'agit d'un taux de rejet très faible. En général, vous recherchez des valeurs de p et q telles que 1 - 5 ^ p / 3 ^ q ne soit pas négative mais aussi petite que possible. Pour p = 2 et q = 3, la valeur est 0,074 (ce qui signifie que vous devez rejeter 7,4% de vos valeurs U (1,27)). Il n'y a pas de combinaison de p et q qui améliore cela jusqu'à ce que vous arriviez à p = 15 et q = 22, où il diminue à 0,0275 (soit un taux de rejet de 2,75%), mais au prix d'une complexité supplémentaire considérable.