come utilizzare i bit casuali per simulare un dado a 26 facce giusto?

Question

Come utilizzare un generatore di numeri casuali che fornisce bit (0 o 1) per simulare un dado a 26 facce giusto? Voglio usare un flusso di bit per selezionare le lettere dell'alfabeto inglese in modo tale che le probabilità di ogni lettera in arrivo siano le stesse di qualsiasi altra lettera (so che le parole reali non sono così e hanno distribuzioni di frequenza specifiche per ogni lettera ma non importa qui). Qual è il modo migliore per utilizzare le decisioni binarie 0/1 per selezionare le lettere in modo corretto dal set A-Z? Posso pensare ad alcuni modi per mappare i bit sulle lettere, ma non è ovvio che non saranno distorti. C'è un buon modo noto?

Answer 1

L'approccio più semplice nel tuo caso è quello di lanciare 5 bit, ciò che dà 32 (0-31) risultati equiprobabili. Se si ottiene un valore al di fuori vostra gamma (maggiore di 25) si tenta di nuovo (e ancora ...)

Il numero medio di "monete" (bit) per gettare in questo caso per ogni lettera sarebbe

5 x 32/26 = 6.15 

(per riferimento, vedere geometric distribution)

Answer 2

Se limitarvi a un numero finito di bit e il vostro stampo dispone di 26 lati il ​​metodo sarà sempre essere prevenuto. Devi permettere la possibilità che tu debba guardare a un numero potenzialmente illimitato di bit per essere sicuro che sia imparziale.

Un semplice algoritmo consiste nel scegliere un numero casuale compreso tra 0 e il successivo numero più grande del modulo 2^n - 1 (31 in questo caso). Se il numero scelto a caso è troppo grande, scartalo e ripeti finché non ottieni un numero nell'intervallo.

Chiaramente questo non è un algoritmo ottimale in quanto "rifiuti" alcune informazioni, ma dovrebbe essere sufficiente per la maggior parte degli scopi. È molto dispendioso se il numero di lati del dado è appena sopra lo 2^m per alcuni m, ad esempio: 33 lati. In questo caso dovrai scartare il valore quasi il 50% delle volte.

Answer 3

Un'implementazione ingenua sarebbe quella di combinare i bit casuali per ottenere un valore decimale o intero, utilizzando un numero fisso di bit (ad esempio, 4 byte per ottenere un numero intero). Dividere il risultato per il massimo valore possibile per il numero di bit forniti, che a mio avviso dovrebbe fornire un decimale distribuito uniformemente nell'intervallo 0-1. (Esenzialmente una funzione rand()). Quindi fare 26 * rand()

Answer 4

26 è 11010 in binario.
Genera cinque bit, se superano 26, sia:

1. restituire il valore mod 26 (favorirà i valori più bassi)
2. scartare il risultato e andare di nuovo (ha la possibilità di non finire mai)

O generalizzando:
Genera (registra n in base 2) + 1 bit. Se superano n, restituire il valore mod n oppure scartare & andare di nuovo.

Answer 5

La risposta di base qui sembra corretta - se il numero casuale 0..32 è maggiore di 25, reroll. Tuttavia, è possibile impilare le probabilità contro un risultato arbitrariamente lungo cercando un multiplo di 26 che offre una minore possibilità di andare long.

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

... e così via.Ho gettato insieme uno script Python per capire il miglior numero disponibile di bit fino a 32, per risatine, e ottenuto questo risultato:

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

Quindi in entrambi i casi, si ha un 1 a 2^12 possibilità di rilaminazione se usi 13 o 14 bit. Il vostro algoritmo in questo caso sarebbe:

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: Per curiosità, ho confrontato quelle quote con alcuni valori importanti, per vedere se il 13 è stato davvero il numero ottimale (supponendo che si può generare alcun numero di bit, Da 1 a 32, nella stessa quantità di tempo - se non puoi, 13 bit sembra il migliore). Basandomi sulla mia matematica (certamente assonnata), se riesci a ottenere 32 bit a un prezzo basso di 16, scegli quello. In caso contrario, favore 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