Eliminazione del bias del modulo: come si ottiene nella funzione arc4random_uniform()?

Question

Il bias del modulo è un problema che si verifica quando ingenuamente si utilizza l'operazione modulo per ottenere numeri pseudocasuali più piccoli di un determinato "limite superiore".

Pertanto, come programmatore C sto utilizzando una versione modificata della funzione arc4random_uniform() per generare numeri pseudocasuali distribuiti uniformemente.

Il problema è che non capisco come funzioni la funzione, matematicamente.

Questo il commento esplicativo della funzione, seguito da un link al codice sorgente completo:

/* 
* Calculate a uniformly distributed random number less than upper_bound 
* avoiding "modulo bias". 
* 
* Uniformity is achieved by generating new random numbers until the one 
* returned is outside the range [0, 2**32 % upper_bound). This 
* guarantees the selected random number will be inside 
* [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound) 
* after reduction modulo upper_bound. 
*/ 

http://cvsweb.openbsd.org/cgi-bin/cvsweb/src/lib/libc/crypt/arc4random_uniform.c?rev=1.1&content-type=text/x-cvsweb-markup

Dal commento di cui sopra possiamo definire:

• [2^32 % upper_bound, 2^32) - Intervallo A
• [0, upper_bound) - intervallo B

Per funzionare, la funzione si basa sul fatto che le mappe di intervallo A a B. intervallo

La mia domanda è: matematicamente, come mai i numeri nell'intervallo Una mappa uniformemente a quelli dell'intervallo B? E c'è una prova per questo?

Answer 1

A volte è utile iniziare con un esempio facilmente comprensibile e quindi generalizzare da lì. Per semplificare le cose, immaginiamo che arc4random restituisca un uint8_t anziché un uint32_t, quindi l'output da arc4random è un numero nell'intervallo [0,256). E cerchiamo di scegliere un upper_bound di 7.

Nota che il 7 non si divide in modo uniforme in 256

256 = 7 * 36 + 4 

Ciò significa che ingenuamente utilizzando l'operazione di modulo per ottenere numeri pseudocasuali inferiori a 7 comporterebbe la seguente distribuzione di probabilità

37/256 for outcomes 0,1,2,3 
36/256 for outcomes 4,5,6 

Questo è ciò che è noto come bias modulo, i risultati 0,1,2,3 è più probabile che i risultati 4,5,6.

Per evitare il bias del modulo, è possibile rifiutare semplicemente i valori 252,253,254,255 e generare un nuovo numero finché il risultato non si trova nell'intervallo [0,252). Tutti i numeri nell'intervallo [0,252) hanno uguale probabilità (il rifiuto di numeri più alti non influisce sulla distribuzione dei numeri più bassi). E poiché 7 divisibile per 252, la distribuzione di probabilità risultante è uniforme

36/252 for outcomes 0,1,2,3,4,5,6,7 

Questo è in sostanza quello arc4random_uniform fa, eccetto che arc4random_uniform numeri scarti a parte inferiore della gamma.Specificamente, intervallo A sarebbe

[2^8 % 7, 2^8) which is [4, 256) 

Dopo aver generato un numero (chiamata esso N) nell'intervallo [4.256) il calcolo finale

outcome = N % 7 

Ci sono 252 numeri nell'intervallo [4.256), e poiché 252 è un multiplo di 7, ogni risultato dell'intervallo [0,7) ha uguale probabilità.

---

Ecco come funziona arc4random_uniform, respinge/tentativi su un piccolo intervallo di numeri, e il conteggio dei numeri nel campo rimanente è un multiplo del superiore limite. (Dato che l'upper_bound è in genere un numero piccolo rispetto a 2^32, le probabilità di avere più tentativi per un singolo risultato sono piuttosto piccole.)

Ma ti interessa davvero il bias del modulo? Nella maggior parte dei casi, la risposta è "No". Si consideri l'esempio con un limite superiore di 7. La distribuzione di probabilità per l'attuazione modulo naive è

613566757/4294967296 for outcomes 0,1,2,3 
613566756/4294967296 for outcomes 4,5,6 

che è un bias modulo inferiore ,0000,002 mila%.

Quindi, c'è una tua scelta: o spendere un tempo minimo su tentativi per ottenere una distribuzione perfetta, o accettare un errore minuscolo nella distribuzione di probabilità per evitare i tentativi.