= Random number generation
<Random number generation> produces values intended to follow a prescribed <probability distribution>. A physical source uses a measured uncertain process; a <pseudorandom number generator> deterministically expands a seed into a reproducible sequence. For a uniform <integer> on $\{0,\ldots,m-1\}$, reducing a uniform $b$-bit <integer> modulo $m$ is biased unless $m$ divides $2^b$. <Rejection sampling> fixes this by accepting only values below $m\lfloor2^b/m\rfloor$ before taking the remainder. For $b=3,m=3$, accept $0,\ldots,5$: each residue then has exactly two preimages.
Back to article page
