Exact Discrete pseudo-Random Sampling

[Albert Chan]

(04-08-2020 05:42 AM)Paul Dale Wrote:  Don't reinvent the wheel. Look up Lemire's delightful: Fast Random Integer Generation in an Interval.

Amazingly, Lemire's sample rejection trick work in any base.

Example, say random r = [0, 10), but we wanted random range [0, 7), without bias.

Code:

r      0  1  2  3  4  5  6  7  8  9   m=10, s=7
sr     0  7 14 21 28 35 42 49 56 63
sr//m  0  0  1  2  2  3  4  4  5  6
sr %m  0  7  4  1  8  5  2  9  6  3
reject x        x        x            // reject cases = m%s = 10%7 = 3
sr//m     0  1     2  3     4  5  6   // remain cases to return

Note: we could also reject high cases (sr%m = 7,8,9), and still remove the bias.

Now, try the same, but with random r = [0, 12)

Code:

r      0  1  2  3  4  5  6  7  8  9 10 11   m=12, s=7
sr     0  7 14 21 28 35 42 49 56 63 70 77
sr//m  0  0  1  1  2  2  3  4  4  5  5  6
sr %m  0  7  2  9  4 11  6  1  8  3 10  5
reject x     x     x        x     x         // reject cases = m%s = 12%7 = 5
sr//m     0     1     2  3     4     5  6   // remain cases to return

Again, reject high cases (sr%m = 7,8,9,10,11) also remove the bias.