Usando um conjunto de probabilidades para gerar outro [duplicado]

Question

Esta questão já tem uma resposta aqui:

• Expandir uma variedade aleatória de 1-5 para 1-7 77 respostas

Como posso gerar um conjunto probabilidade maior de um conjunto menor probabilidade?
Isto é de Algoritmo Projeto manual -Steven Skiena
Q:

Use um gerador de números aleatórios (rng04) que gera números de {0,1,2,3,4} com igual probabilidade para escrever um gerador de números aleatórios que gera números de 0 a 7 (rng07) com igual probabilidade

Eu tentei por cerca de 3 horas agora, principalmente com base na soma de duas saídas rng04. O problema é que, nesse caso, a probabilidade de cada valor é diferente - 4 pode vir com 5/24 probabilidade enquanto 0 acontecer é 1/24. Eu tentei algumas maneiras de mascará-lo, mas não pode.

Alguém pode resolver isso?

Answer 1

Você tem que encontrar uma maneira de combinar os dois conjuntos de números aleatórios (o primeiro eo segundo {0,1,2,3,4} aleatório) e fazer n*n possibilidades distintas. Basicamente, o problema é que com a adição você obter algo como isto

        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

Que tem duplicatas, o que não é o que você quer. Uma maneira possível combinar os dois conjuntos seria o Z = X + Y*5 onde X e Y são os dois números aleatórios. Isso iria dar-lhe um conjunto de resultados como este

        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

Portanto, agora que você tem um maior conjunto de números aleatórios, você precisa fazer o inverso e torná-lo menor. Este conjunto tem valores distintos 25 (porque você começou com 5, e utilizados dois números aleatórios, de modo 5*5=25). O conjunto que pretende tem 8 valores distintos. Uma maneira ingênua de fazer isso seria

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

Esta seria, de fato têm uma gama de {0,7}. Mas o {1,7} valores apareceria 3/25 vezes, e o valor 0 parece 4/25 vezes. Isso ocorre porque 0 mod 8 = 0, 8 mod 8 = 0, 16 mod 8 = 0 e 24 mod 8 = 0 .

Para corrigir isso, você pode modificar o código acima para isso.

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

Isso levará a um valor (24) que está jogando fora suas probabilidades e descartá-lo. Gerando um novo número aleatório se obter um valor de 'mau' como este irá fazer o seu algoritmo de corrida muito ligeiramente mais longo (neste caso 1/25 do tempo que levará 2x mais tempo para executar, 1/625 levará 3x longa, etc). Mas ele vai te dar as probabilidades certas.

Answer 2

O verdadeiro problema, é claro, é o fato de que os números no meio da soma (4 neste caso) ocorrem em muitas combinações (0 + 4, 1 + 3, etc.) enquanto que 0 e 8 têm exatamente uma maneira de ser produzido.

Eu não sei como resolver este problema, mas eu vou tentar reduzi-lo um pouco para você. Alguns pontos a considerar:

• A gama 0-7 tem 8 valores possíveis, de modo que, finalmente, o número total de possíveis situações que você deve apontar para tem de ser um múltiplo de 8. Dessa forma, você pode ter um integrante do número de distribuições por valor em que codomain.
• Quando você toma a soma de duas funções de densidade, o número de possíveis situações (não necessariamente distintas quando você avaliar a soma, apenas em termos de diferentes permutações de insumos) é igual ao produto do tamanho de cada uma das entradas conjuntos.
• Assim, dadas duas {0,1,2,3,4} conjuntos somados, você tem 5 * 5 = 25 possibilidades.
• Não será possível obter um múltiplo de oito (ver primeiro ponto) de poderes de 5 (ver segundo ponto, mas extrapolar-lo para qualquer número de sets> 1), então você precisa ter um excedente de possível situações em sua função e ignorar alguns deles se eles ocorrerem.
• A maneira mais simples de fazer isso, tanto quanto eu posso ver, neste ponto, é usar a soma de dois {0,1,2,3,4} conjuntos (25 possibilidades) e ignorar 1 (para deixar 24 , um múltiplo de 8).
• Assim, o desafio agora foi reduzido a isto: Encontre uma maneira de distribuir os restantes 24 possibilidades entre os valores de saída 8. Para isso, você provavelmente não quer usar a soma, mas sim apenas os valores de entrada.

Uma maneira de fazer isto é, imaginar um número na base 5 construídos a partir de sua entrada. Ignorar 44 (que é o seu 25º, valor supérfluo; se você obtê-lo, sintetizar um novo conjunto de entradas) e tomar as outras, modulo 8, e você vai chegar em suas 0-7 através de 24 diferentes combinações de entrada (3 cada), que é uma distribuição igual.

Answer 3

Minha lógica seria a seguinte:

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

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

rn07 += num % 2