cómo usar bits aleatorios para simular un dado justo de 26 caras?

Question

¿Cómo utilizo un generador de números aleatorios que da bits (0 o 1) para simular un dado justo de 26 lados? Quiero utilizar un flujo de bits para seleccionar letras del alfabeto inglés de manera que las probabilidades de que aparezca una letra coincidan con las de cualquier otra letra (sé que las palabras reales no son así y tienen distribuciones de frecuencias específicas para cada una). carta pero no importa aquí). ¿Cuál es la mejor manera de utilizar las decisiones binarias 0/1 para elegir letras de manera justa del conjunto A-Z? Puedo pensar en algunas formas de asignar bits a letras, pero no es obvio para mí que no sean parciales. ¿Hay una buena manera conocida?

Answer 1

El enfoque más simple en su caso es arrojar 5 bits, lo que da 32 (0-31) resultados equiprobables. Si se obtiene un valor fuera de su rango (mayor de 25) lo intenta de nuevo (y otra vez ...)

El número medio de "monedas" (bits) para lanzar en este caso para cada letra sería

5 x 32/26 = 6.15 

(para referencia, véase geometric distribution)

Answer 2

Si se limite a un número finito de bits y su matriz tiene 26 lados siempre estará sesgada del método. Tienes que permitir la posibilidad de que tengas que mirar una cantidad potencialmente ilimitada de bits para asegurarte de que es imparcial.

Un algoritmo simple consiste en elegir un número aleatorio entre 0 y el siguiente número más grande del formulario 2^n - 1 (31 en este caso). Si el número que elige al azar es demasiado grande, deséchelo y repítalo hasta que obtenga un número dentro del rango.

Claramente este no es un algoritmo óptimo ya que "desperdicia" algo de información, pero debería ser lo suficientemente bueno para la mayoría de los propósitos. Es más derrochador si el número de lados de la matriz está justo por encima de 2^m para algunos m, por ejemplo: 33 lados. En este caso, tendrá que descartar el valor casi el 50% del tiempo.

Answer 3

Una implementación ingenua sería combinar los bits aleatorios para obtener un valor decimal o entero, utilizando un número fijo de bits (digamos, 4 bytes para obtener un número entero). Divida el resultado por el valor máximo posible para la cantidad de bits suministrados, lo que creo que debería darle un decimal distribuido uniformemente en el rango 0-1. (Esencialmente una función rand()). Luego haga 26 * rand()

Answer 4

26 es 11010 en binario.
Generar cinco bits, si exceden de 26 años, ya sea:

1. Devuelve el valor de la MOD 26 (favorecerá los valores más bajos)
2. descartar el resultado e ir de nuevo (tiene la posibilidad de no tener fin)

O generalizándolo:
Generar (log n en la base 2) + 1 bits. Si exceden n, devuelva el valor mod n, o descarte & vuelva a comenzar.

Answer 5

La respuesta básica aquí parece correcta: si su número aleatorio 0..32 es mayor que 25, vuelva a enrollar. Sin embargo, puedes acumular las probabilidades contra un resultado arbitrariamente largo buscando un múltiplo de 26 que ofrezca una menor posibilidad de ir demasiado lejos.

32 - 26 = 6 
64 - 52 = 12 
128 - 78 = 50 

... y así sucesivamente.Me tiró juntos un script Python para averiguar el mejor número disponible de bits de hasta 32, por diversión, y obtuvo el siguiente resultado:

2^13 - 26 * 315 = 2 
2^14 - 26 * 630 = 4 

Así que de cualquier manera, usted tiene un 1 en 2^12 posibilidades de relaminación si Usas 13 o 14 bits. Su algoritmo en este caso sería:

def random_character(): 
    r = 8190 
    while r >= 8190: 
     r = rand(13) # assuming rand generates an N bit integer 
    return chr(r % 26 + ord('a')) 

EDIT: Por curiosidad, me comparó esas probabilidades con unos valores importantes, para ver si 13 era realmente el número óptimo (suponiendo que usted puede generar cualquier número de bits, 1 a 32, en la misma cantidad de tiempo; si no puede, 13 bits parece ser el mejor). De acuerdo con mi matemática (ciertamente adormecida), si puedes obtener 32 bits a un precio tan bajo como 16, ve por eso. De lo contrario, favor 13.

2^8 through 2^12: by definition, no better than 1/2^12 odds 
2^16: diff is 16, so 1/2^11 
2^17: diff is 6, so slightly under 1/2^14 
2^18: diff is 12, so slightly under 1/2^12 
2^19: diff is 24, so slightly under 1/2^14 
2^20: diff is 22, so slightly under 1/2^15 
2^21: diff is 18, so slightly under 1/2^16 
2^22: diff is 10, so slightly under 1/2^18 
2^23: diff is 20, so slightly under 1/2^18 
2^24: diff is 14, so slightly under 1/2^20 
2^25: diff is 2, so 1/2^24 
2^26: diff is 4, so 1/2^24 
2^27: diff is 8, so 1/2^24 
2^28: diff is 16, so 1/2^24 
2^29: diff is 6, so slightly under 1/2^26 
2^30: diff is 12, so slightly under 1/2^26 
2^31: diff is 24, so slightly under 1/2^26 
2^32: diff is 22, so slightly under 1/2^27