Arc4random modulo polarizzato

Question

Secondo this documentation,

arc4random_uniform() è consigliato su costruzioni come arc4random() % upper_bound quanto evita "polarizzazione modulo" quando il limite superiore non è una potenza di due.

Quanto pessimo è il pregiudizio? Ad esempio, se generi numeri casuali con un limite superiore di 6, qual è la differenza tra l'utilizzo di arc4random con % e arc4random_uniform()?

Answer 1

arc4random() restituisce un 32 bit senza segno intero, significa i valori sono compresi tra 0 e 2^32-1 = 4 294 967 295.

Ora, i risultati di polarizzazione dal fatto che la pluralità di sottointervalli creato con il modulo non si adattano esattamente all'intervallo di uscita casuale. Consente di immaginare per chiarezza un generatore casuale che crea numeri compresi tra 0 e 198 inclusi. Volete i numeri da 0 a 99, quindi si calcola casuale()% 100, cedendo 0-99:

0% 100 = 0
99% 100 = 99
100% 100 = 0
198% 100 = 98

Si vede che 99 è l'unico numero che può avvenire solo una volta mentre tutti gli altri si possono verificare due volte in una corsa. Ciò significa che la probabilità per 99 è dimezzata esattamente che è anche il caso peggiore in una polarizzazione in cui sono coinvolti almeno i sottointervalli 2.
Poiché tutte le potenze di due inferiori all'intervallo di intervallo si adattano perfettamente all'intervallo 2^32 , in questo caso il bias scompare.

Le implicazioni sono che quanto più piccolo è il set di risultati con modulo e quanto più alto è l'intervallo di uscita casuale, minore è il bias. Nell'esempio, 6 è il limite superiore (presumo 0 è il limite inferiore), quindi si utilizza% 7, risultante che 0-3 si verifica 613 566 757 volte mentre 4-6 si verifica 613 566 756 volte.
Quindi 0-3 è 613 566 757/613 566 756 = 1,0000000016298 volte più probabile di 4-6.

Mentre sembra facile respingere, alcuni esperimenti (specialmente Monte-Carlo esperimenti) sono state viziate proprio perché queste apparentemente incredibili piccoli differenze erano abbastanza importante.

Ancora peggio è il bias se l'intervallo di uscita desiderato è più grande rispetto a l'intervallo di destinazione casuale. Si prega di leggere il Fisher-Yates shuffle ingresso perché molti siti di poker hanno imparato nel modo più duro che le normali lineari generatori casuali congruenziali e algoritmi di mischiare le cattive provocato mazzi impossibili o molto probabili o peggio, prevedibili ponti.