Étendre une gamme aléatoire de 1-5 à 1-7

Question

Étant donné une fonction qui produit un nombre entier aléatoire compris entre 1 et 5, écrivez une fonction qui produit un nombre entier aléatoire compris entre 1 et 7.

1. Quelle est une solution simple ?
2. Quelle est une solution efficace pour réduire l'utilisation de la mémoire ou fonctionner sur un processeur plus lent ?

Answer 1

Cette solution est équivalente à celle d'Adam Rosenfield, mais elle peut être un peu plus claire pour certains lecteurs. Elle suppose que rand5() est une fonction qui renvoie un nombre entier statistiquement aléatoire compris entre 1 et 5 inclus.

int rand7()
{
    int vals[5][5] = {
        { 1, 2, 3, 4, 5 },
        { 6, 7, 1, 2, 3 },
        { 4, 5, 6, 7, 1 },
        { 2, 3, 4, 5, 6 },
        { 7, 0, 0, 0, 0 }
    };

    int result = 0;
    while (result == 0)
    {
        int i = rand5();
        int j = rand5();
        result = vals[i-1][j-1];
    }
    return result;
}

Comment cela fonctionne-t-il ? Imaginez que vous imprimez ce tableau à double dimension sur du papier, que vous le fixez à un jeu de fléchettes et que vous lancez des fléchettes au hasard. Si vous atteignez une valeur non nulle, il s'agit d'une valeur statistiquement aléatoire comprise entre 1 et 7, puisqu'il existe un nombre égal de valeurs non nulles parmi lesquelles choisir. Si vous obtenez un zéro, continuez à lancer la fléchette jusqu'à ce que vous obteniez une valeur différente de zéro. C'est ce que fait ce code : les indices i et j sélectionnent aléatoirement un emplacement sur le jeu de fléchettes, et si nous n'obtenons pas un bon résultat, nous continuons à lancer des fléchettes.

Comme Adam l'a dit, cela peut fonctionner éternellement dans le pire des cas, mais statistiquement le pire des cas n'arrive jamais :)

Answer 2

Il n'existe pas de solution (exactement correcte) qui s'exécute en un temps constant, puisque 1/7 est une décimale infinie en base 5. Une solution simple serait d'utiliser l'échantillonnage par rejet, par exemple :

int i;
do
{
  i = 5 * (rand5() - 1) + rand5();  // i is now uniformly random between 1 and 25
} while(i > 21);
// i is now uniformly random between 1 and 21
return i % 7 + 1;  // result is now uniformly random between 1 and 7

Le temps d'exécution prévu est de 25/21 = 1,19 itérations de la boucle, mais il existe une probabilité infinitésimale de boucler indéfiniment.

Answer 3

Je voudrais ajouter une autre réponse, en plus de ma première réponse . Cette réponse tente de réduire au minimum le nombre d'appels à rand5() par appel à rand7() pour maximiser l'utilisation de l'aléatoire. En d'autres termes, si vous considérez le caractère aléatoire comme une ressource précieuse, nous voulons en utiliser autant que possible, sans jeter aucun bit aléatoire. Cette réponse présente également des similitudes avec la logique présentée dans le document suivant La réponse d'Ivan .

Le site entropie d'une variable aléatoire est une quantité bien définie. Pour une variable aléatoire qui prend N états avec des probabilités égales (une distribution uniforme), l'entropie est égale à log ₂ N. Ainsi, rand5() a approximativement 2,32193 bits d'entropie, et rand7() a environ 2,80735 bits d'entropie. Si nous espérons maximiser notre utilisation de l'aléatoire, nous devons utiliser les 2,32193 bits d'entropie de chaque appel à rand5() et les appliquer à la génération de 2,80735 bits d'entropie nécessaires pour chaque appel à rand7() . La limite fondamentale est donc que nous ne pouvons pas faire mieux que log(7)/log(5) = 1,20906 appels pour rand5() par appel à rand7() .

Remarques : tous les logarithmes dans cette réponse seront en base 2, sauf indication contraire. rand5() sera supposé retourner des nombres dans la plage [0, 4], et rand7() sera supposé renvoyer des nombres dans la plage [0, 6]. Ajuster les plages à [1, 5] et [1, 7] respectivement est trivial.

Alors comment faisons-nous ? Nous générons un infiniment précis un nombre réel aléatoire compris entre 0 et 1 (supposons pour l'instant que nous puissions réellement calculer et stocker un tel nombre infiniment précis - nous y reviendrons plus tard). Nous pouvons générer un tel nombre en générant ses chiffres en base 5 : nous choisissons le nombre aléatoire 0. a ₁ a ₂ a ₃ ..., où chaque chiffre a _{<code>i</code>} est choisi par un appel à rand5() . Par exemple, si notre RNG a choisi un _{<code>i</code>} = 1 pour tous les i puis, en ignorant le fait que ce n'est pas très aléatoire, cela correspondrait au nombre réel 1/5 + 1/5. 2 + 1/5 3 + ... = 1/4 (somme d'une série géométrique).

Nous avons donc choisi un nombre réel aléatoire entre 0 et 1. Je prétends maintenant qu'un tel nombre aléatoire est uniformément distribué. Intuitivement, c'est facile à comprendre, puisque chaque chiffre a été choisi uniformément et que le nombre est infiniment précis. Cependant, une preuve formelle de cette affirmation est un peu plus complexe, car nous avons maintenant affaire à une distribution continue au lieu d'une distribution discrète, et nous devons donc prouver que la probabilité que notre nombre se trouve dans un intervalle [ a , b ] est égal à la longueur de cet intervalle, b - a . La preuve est laissée comme un exercice pour le lecteur =).

Maintenant que nous avons un nombre réel aléatoire choisi uniformément dans la plage [0, 1], nous devons le convertir en une série de nombres uniformément aléatoires dans la plage [0, 6] pour générer la sortie de rand7() . Comment faisons-nous cela ? C'est juste l'inverse de ce que nous venons de faire - nous le convertissons en une décimale infiniment précise en base 7, et alors chaque chiffre en base 7 correspondra à une sortie de rand7() .

En reprenant l'exemple précédent, si notre rand5() produit un flux infini de 1, alors notre nombre réel aléatoire sera 1/4. En convertissant 1/4 en base 7, nous obtenons la décimale infinie 0,15151515..., nous produirons donc en sortie 1, 5, 1, 5, 1, 5, etc.

Ok, nous avons donc l'idée principale, mais il nous reste deux problèmes : nous ne pouvons pas calculer ou stocker un nombre réel infiniment précis, alors comment faire avec seulement une partie finie de celui-ci ? Deuxièmement, comment le convertir en base 7 ?

Une façon de convertir un nombre entre 0 et 1 en base 7 est la suivante :

1. Multiplier par 7
2. La partie intégrale du résultat est le chiffre suivant en base 7
3. Soustrayez la partie intégrale, ne laissant que la partie fractionnaire.
4. Sauter l'étape 1

Pour résoudre le problème de la précision infinie, nous calculons un résultat partiel et nous stockons également une limite supérieure sur ce que le résultat pourrait être. En d'autres termes, supposons que nous ayons appelé rand5() deux fois et il a retourné 1 les deux fois. Le nombre que nous avons généré jusqu'à présent est 0,11 (base 5). Quel que soit le reste de la série infinie d'appels à rand5() produire, le nombre réel aléatoire que nous générons ne sera jamais supérieur à 0,12 : il est toujours vrai que 0,11 ≤ 0,11xyz.... < 0.12.

Donc, en gardant à l'esprit le nombre actuel jusqu'à présent, et la valeur maximale qu'il pourrait jamais prendre, nous convertissons les deux les nombres en base 7. S'ils sont d'accord sur le premier k chiffres, alors nous pouvons sans risque sortir le prochain k chiffres -- quel que soit le flux infini de chiffres en base 5, ils n'affecteront jamais le prochain k chiffres de la représentation en base 7 !

Et c'est l'algorithme -- pour générer la prochaine sortie de rand7() nous ne générons qu'autant de chiffres de rand5() car nous devons nous assurer que nous connaissons avec certitude la valeur du chiffre suivant dans la conversion du nombre réel aléatoire en base 7. Voici une implémentation Python, avec un harnais de tests :

import random

rand5_calls = 0
def rand5():
    global rand5_calls
    rand5_calls += 1
    return random.randint(0, 4)

def rand7_gen():
    state = 0
    pow5 = 1
    pow7 = 7
    while True:
        if state / pow5 == (state + pow7) / pow5:
            result = state / pow5
            state = (state - result * pow5) * 7
            pow7 *= 7
            yield result
        else:
            state = 5 * state + pow7 * rand5()
            pow5 *= 5

if __name__ == '__main__':
    r7 = rand7_gen()
    N = 10000
    x = list(next(r7) for i in range(N))
    distr = [x.count(i) for i in range(7)]
    expmean = N / 7.0
    expstddev = math.sqrt(N * (1.0/7.0) * (6.0/7.0))

    print '%d TRIALS' % N
    print 'Expected mean: %.1f' % expmean
    print 'Expected standard deviation: %.1f' % expstddev
    print
    print 'DISTRIBUTION:'
    for i in range(7):
        print '%d: %d   (%+.3f stddevs)' % (i, distr[i], (distr[i] - expmean) / expstddev)
    print
    print 'Calls to rand5: %d (average of %f per call to rand7)' % (rand5_calls, float(rand5_calls) / N)

Notez que rand7_gen() renvoie un générateur, puisqu'il possède un état interne impliquant la conversion du nombre en base 7. Le harnais de test appelle next(r7) 10000 fois pour produire 10000 nombres aléatoires, puis il mesure leur distribution. Seuls des calculs en nombres entiers sont utilisés, de sorte que les résultats sont exactement corrects.

Notez aussi que les chiffres ici sont très grand, très rapide. Les puissances de 5 et 7 croissent rapidement. Par conséquent, les performances commenceront à se dégrader sensiblement après la génération de nombreux nombres aléatoires, en raison de l'arithmétique du bignum. Mais n'oubliez pas que mon objectif était de maximiser l'utilisation des bits aléatoires, et non de maximiser les performances (bien que ce soit un objectif secondaire).

En une seule fois, j'ai fait 12091 appels à rand5() pour 10000 appels à rand7() Le résultat est uniforme et le minimum de log(7)/log(5) est atteint en moyenne à 4 chiffres significatifs.

Afin de porter ce code dans un langage qui n'intègre pas d'entiers de taille arbitraire, vous devrez plafonner les valeurs des éléments suivants pow5 et pow7 à la valeur maximale de votre type d'intégrale native -- s'ils deviennent trop grands, alors remettez tout à zéro et recommencez. Cela augmentera le nombre moyen d'appels à rand5() par appel à rand7() très légèrement, mais avec un peu de chance, elle ne devrait pas trop augmenter, même pour les entiers 32 ou 64 bits.

Answer 4

(J'ai volé La réponse d'Adam Rosenfeld et l'a fait fonctionner environ 7% plus vite).

Supposons que rand5() renvoie l'un de {0,1,2,3,4} avec une distribution égale et que le but est de renvoyer {0,1,2,3,4,5,6} avec une distribution égale.

int rand7() {
  i = 5 * rand5() + rand5();
  max = 25;
  //i is uniform among {0 ... max-1}
  while(i < max%7) {
    //i is uniform among {0 ... (max%7 - 1)}
    i *= 5;
    i += rand5(); //i is uniform {0 ... (((max%7)*5) - 1)}
    max %= 7;
    max *= 5; //once again, i is uniform among {0 ... max-1}
  }
  return(i%7);
}

Nous gardons la trace de la plus grande valeur que la boucle peut faire dans la variable max . Si le résultat obtenu jusqu'à présent est compris entre max%7 et max-1, alors le résultat sera distribué uniformément dans cet intervalle. Sinon, nous utilisons le reste, qui est aléatoire entre 0 et max%7-1, et un autre appel à rand() pour créer un nouveau nombre et un nouveau max. Puis nous recommençons.

Edit : Le nombre attendu de fois pour appeler rand5() est x dans cette équation :

x =  2     * 21/25
   + 3     *  4/25 * 14/20
   + 4     *  4/25 *  6/20 * 28/30
   + 5     *  4/25 *  6/20 *  2/30 * 7/10
   + 6     *  4/25 *  6/20 *  2/30 * 3/10 * 14/15
   + (6+x) *  4/25 *  6/20 *  2/30 * 3/10 *  1/15
x = about 2.21 calls to rand5()

Answer 5

Algorithme :

7 peut être représenté par une séquence de 3 bits

Utilisez rand(5) pour remplir aléatoirement chaque bit avec 0 ou 1.
Par exemple : appeler rand(5) et

si le résultat est 1 ou 2, remplir le bit avec 0
si le résultat est 4 ou 5, remplir le bit avec 1
si le résultat est 3 , alors ignorez et recommencez (rejet)

De cette façon, nous pouvons remplir 3 bits au hasard avec 0/1 et obtenir ainsi un nombre de 1 à 7.

EDIT : Cela semble être la réponse la plus simple et la plus efficace, alors voici un peu de code pour cela :

public static int random_7() {
    int returnValue = 0;
    while (returnValue == 0) {
        for (int i = 1; i <= 3; i++) {
            returnValue = (returnValue << 1) + random_5_output_2();
        }
    }
    return returnValue;
}

private static int random_5_output_2() {
    while (true) {
        int flip = random_5();

        if (flip < 3) {
            return 0;
        }
        else if (flip > 3) {
            return 1;
        }
    }
}