L'utilisation d'une probabilité de générer un autre mis en [double]

StackOverflow https://stackoverflow.com/questions/1268025

  •  13-09-2019
  •  | 
  •  

Question

    

Cette question a déjà une réponse ici:

    
            
  •              Développer une gamme aléatoire 1-5 à 1-7                                      77 réponses                          
    •     
    

Comment puis-je générer une plus grande probabilité d'établir un ensemble plus restreint de probabilité?
Ceci est de l'algorithme Manuel de conception -Steven Skiena
Q:

  

utiliser un générateur de nombres aléatoires (rng04) qui génère des nombres de {0,1,2,3,4} avec une probabilité égale à écrire un générateur de nombres aléatoires qui génère des nombres de 0 à 7 (rng07) avec une probabilité égale

J'ai essayé pendant environ 3 heures maintenant, la plupart du temps basé sur la somme de deux sorties rng04. Le problème est que dans ce cas, la probabilité de chaque valeur est différente - 4 peut venir avec 5/24 probabilité alors que 0 se produise est 1/24. J'ai essayé quelques façons de le masquer, mais ne peut pas.

Quelqu'un peut-il résoudre ce problème?

Était-ce utile?

La solution

Vous devez trouver un moyen de combiner les deux ensembles de nombres aléatoires (la première et la deuxième {0,1,2,3,4} au hasard) et faire n*n possibilités distinctes. Fondamentalement, le problème est que plus vous obtenez quelque chose comme ceci 

        X
      0 1 2 3 4

  0   0 1 2 3 4
Y 1   1 2 3 4 5
  2   2 3 4 5 6
  3   3 4 5 6 7
  4   4 5 6 7 8

Ce qui a des doublons, ce qui est pas ce que vous voulez. Une façon de combiner les deux ensembles seraient les Z = X + Y*5 où X et Y sont les deux nombres aléatoires. Cela vous donne un ensemble de résultats comme celui-ci 

        X
       0  1  2  3  4

  0    0  1  2  3  4
Y 1    5  6  7  8  9
  2   10 11 12 13 14
  3   15 16 17 18 19
  4   20 21 22 23 24

Alors, maintenant que vous avez un plus grand ensemble de nombres aléatoires, vous devez faire l'inverse et de le rendre plus petit. Cet ensemble a 25 valeurs distinctes (parce que vous avez commencé avec 5 et utilisé deux nombres aléatoires, donc 5*5=25). L'ensemble que vous voulez a 8 valeurs distinctes. Une façon naïve de le faire serait 

x = rnd(5)  // {0,1,2,3,4}
y = rnd(5)  // {0,1,2,3,4}
z = x+y*5   // {0-24}
random07 = x mod 8

Ce serait en effet une gamme de {0,7}. Mais les valeurs {1,7} semble 3/25 fois, et la valeur 0 semble 4/25 fois. En effet, 0 mod 8 = 0, 8 mod 8 = 0, 16 mod 8 = 0 et 24 mod 8 = 0 .

Pour résoudre ce problème, vous pouvez modifier le code ci-dessus à ce sujet. 

do {
  x = rnd(5)  // {0,1,2,3,4}
  y = rnd(5)  // {0,1,2,3,4}
  z = x+y*5   // {0-24}
while (z != 24)

random07 = z mod 8

Cela prendra une valeur (24) qui jette vos probabilités et le jeter. Création d'un nouveau nombre aléatoire si vous obtenez une valeur « mauvais » comme celui-ci fera fonctionner votre algorithme très légèrement plus long (dans ce cas 1/25 du temps il faudra 2x aussi longtemps à courir, il faudra 1/625 3x comme long, etc.). Mais il vous donnera les probabilités droite.

Autres conseils

Le vrai problème, bien sûr, est le fait que les chiffres au milieu de la somme (4 dans ce cas) se produisent dans de nombreuses combinaisons (0 + 4, 1 + 3, etc.), tandis que 0 et 8 ont exactement d'une façon à produire.

Je ne sais pas comment résoudre ce problème, mais je vais essayer de le réduire un peu pour vous. Quelques points à considérer:

  • La gamme 0-7 a 8 valeurs possibles, donc en fin de compte le nombre total de situations possibles que vous devriez viser doit être un multiple de 8. De cette façon, vous pouvez avoir un nombre entier de distributions par valeur dans ce codomain.
  • Lorsque vous prenez la somme de deux fonctions de densité, le nombre de situations possibles (pas nécessairement distincte lorsque vous évaluez la somme, juste en termes de permutations différentes d'entrées) est égal au produit de la taille de chacune des entrées ensembles.
  • Ainsi, étant donné deux {0,1,2,3,4} ensembles additionnés, vous avez 5 * 5 = 25 possibilités.
  • Il ne sera pas possible d'obtenir un multiple de huit (voir le premier point) des puissances de 5 (voir deuxième point, mais extrapoler à un certain nombre d'ensembles> 1), de sorte que vous aurez besoin d'avoir un excédent de possible situations dans votre fonction et ignorer certains d'entre eux si elles se produisent.
  • La façon la plus simple de le faire, pour autant que je peux voir à ce stade, est d'utiliser la somme de deux {0,1,2,3,4} ensembles (25 possibilités) et ignorer 1 (quitter 24 , un multiple de 8).
  • Ainsi, le défi a été réduit à ceci: Trouver un moyen de répartir les 24 possibilités restantes parmi les 8 valeurs de sortie. Pour cela, vous aurez probablement pas à utiliser la somme, mais plutôt seulement les valeurs d'entrée.

Une façon de le faire est, imaginez un nombre en base 5 construit à partir de votre entrée. Ignorer 44 (c'est votre 25, la valeur superflue, si vous l'obtenez, synthétiser une nouvelle série d'entrées) et de prendre les autres, modulo 8, et vous obtiendrez vos 0-7 à travers 24 différentes combinaisons d'entrée (3 chacun), qui est une répartition égale.

Ma logique serait: 

rn07 = 0;
do {
  num = rng04;
}
while(num == 4);

rn07 = num * 2;
do {
  num = rng04;
}
while(num == 4);

rn07 += num % 2
Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top