Modulo bias is easy enough to correct by checking and occasional
re-sampling. It's explained nicely in the following article:
http://zuttobenkyou.wordpress.com/2012/10/18/generating-random-numbers-without-modulo-bias/
Let's *deliberately* generate some modulo bias in Racket by simulating a
low largest random number:
(define (biased-random RAND-MAX n)
(modulo (random (add1 RAND-MAX)) 3))
(define (check-bias method [n 10000])
(define sample (for/list ([i n]) (method 4 3)))
(for ([i (in-range 3)])
(displayln
(~a i " " (~a (real->decimal-string
(* 100.0 (/ (count (λ (j) (= i j)) sample) n))
1) "%")))))
> (check-bias biased-random)
0 38.3%
1 41.0%
2 20.7%
Remove the generated bias by rejecting some "high" values:
(define (unbiased-random RAND-MAX n)
(define excess (add1 (modulo RAND-MAX n)))
(define limit (- RAND-MAX excess))
(define (in-limit m)
(if (<= m limit) m (in-limit (random (add1 RAND-MAX)))))
(modulo (in-limit (random (add1 RAND-MAX))) n))
> (check-bias unbiased-random)
0 33.9%
1 33.8%
2 32.4%
Conclusion: We should be ok regarding modulo bias provided (random n) uses
a rejection strategy along these lines. If not, it's quite fixable.
Dan
On Wed, Sep 17, 2014 at 1:44 AM, Eli Barzilay <e...@barzilay.org> wrote:
> On Wed, Sep 17, 2014 at 1:53 AM, Daniel Prager
> <daniel.a.pra...@gmail.com> wrote:
> >
> > [Sorry for drawing you further in.]
>
> :) (Indeed, my main point is that all that random-number stuff is
> foreign to me...)
>
>
> > My take on your 3 points:
> >
> > Fisher-Yates is only a few lines, so although not a one-liner, it
> > seems reasonable to use it for the better space and time performance.
>
> (It's just time -- the space is the roughly same for both, since sorting
> will create an intermediate vector too.)
>
> > I agree that an inside-out version is more apt.
> > On my reading the final point is an issue if (random n) has problems
> > like modulo bias, but if that's the case surely it is (random n) that
> > needs fixing.
>
> It goes into all kinds of arguments that are exactly in that area that
> I'm trying to avoid -- but IIUC, it's hard to avoid module-biases, and
> the FY use of `random' is particularly nasty since it uses all modulos
> in the range of the number of items. See also the point that the WP
> page makes about the size of the random number generator state, and how
> it limits the number of different permutations that can be generated.
> It looks to me like Racket's state is made of 6 fixnums => 2^192 states,
> which still doesn't cover all of the permutations of 52 cards. I have
> no idea if this is correct, if some bias reduces the number of
> permutations, or whether all of this is something to worry about...
>
> --
> ((lambda (x) (x x)) (lambda (x) (x x))) Eli Barzilay:
> http://barzilay.org/ Maze is Life!
>
--
*Daniel Prager*
Agile/Lean Coaching, Software Development and Leadership
Startup: www.youpatch.com
Twitter: @agilejitsu <https://twitter.com/agilejitsu>
Blog: agile-jitsu.blogspot.com
____________________
Racket Users list:
http://lists.racket-lang.org/users
