<div dir="ltr">I've done some testing of the built-in (random n) and I haven't been able to detect evidence of modulo bias. Of course absence of evidence isn't evidence of absence!<div><br></div><div>More generally though, this is an interesting case (at least to me) of the trade-offs between efficiency, clarity, concision, cost of learning about a specialised area as well as arguments from theory vs empirical assessment.</div><div><br></div><div>Dan</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Sep 17, 2014 at 9:14 AM, Robby Findler <span dir="ltr"><<a href="mailto:robby@eecs.northwestern.edu" target="_blank">robby@eecs.northwestern.edu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">There was a bunch of work done to improve the random number generation<br>
algorithms used internally a while back, but if you wanted to have a<br>
look at them again, that would be most welcome.<br>
<br>
Here is a at least part of the code:<br>
<br>
<a href="https://github.com/plt/racket/blob/master/racket/src/racket/src/random.inc" target="_blank">https://github.com/plt/racket/blob/master/racket/src/racket/src/random.inc</a><br>
<br>
Robby<br>
<br>
On Wed, Sep 17, 2014 at 7:29 AM, Daniel Prager<br>
<div class="HOEnZb"><div class="h5"><<a href="mailto:daniel.a.prager@gmail.com">daniel.a.prager@gmail.com</a>> wrote:<br>
> Modulo bias is easy enough to correct by checking and occasional<br>
> re-sampling. It's explained nicely in the following article:<br>
> <a href="http://zuttobenkyou.wordpress.com/2012/10/18/generating-random-numbers-without-modulo-bias/" target="_blank">http://zuttobenkyou.wordpress.com/2012/10/18/generating-random-numbers-without-modulo-bias/</a><br>
><br>
> Let's *deliberately* generate some modulo bias in Racket by simulating a low<br>
> largest random number:<br>
><br>
> (define (biased-random RAND-MAX n)<br>
> (modulo (random (add1 RAND-MAX)) 3))<br>
><br>
><br>
> (define (check-bias method [n 10000])<br>
> (define sample (for/list ([i n]) (method 4 3)))<br>
><br>
> (for ([i (in-range 3)])<br>
> (displayln<br>
> (~a i " " (~a (real->decimal-string<br>
> (* 100.0 (/ (count (λ (j) (= i j)) sample) n))<br>
> 1) "%")))))<br>
><br>
>> (check-bias biased-random)<br>
> 0 38.3%<br>
> 1 41.0%<br>
> 2 20.7%<br>
><br>
> Remove the generated bias by rejecting some "high" values:<br>
><br>
><br>
> (define (unbiased-random RAND-MAX n)<br>
> (define excess (add1 (modulo RAND-MAX n)))<br>
> (define limit (- RAND-MAX excess))<br>
> (define (in-limit m)<br>
> (if (<= m limit) m (in-limit (random (add1 RAND-MAX)))))<br>
> (modulo (in-limit (random (add1 RAND-MAX))) n))<br>
><br>
><br>
>> (check-bias unbiased-random)<br>
> 0 33.9%<br>
> 1 33.8%<br>
> 2 32.4%<br>
><br>
> Conclusion: We should be ok regarding modulo bias provided (random n) uses a<br>
> rejection strategy along these lines. If not, it's quite fixable.<br>
><br>
> Dan<br>
><br>
> On Wed, Sep 17, 2014 at 1:44 AM, Eli Barzilay <<a href="mailto:eli@barzilay.org">eli@barzilay.org</a>> wrote:<br>
>><br>
>> On Wed, Sep 17, 2014 at 1:53 AM, Daniel Prager<br>
>> <<a href="mailto:daniel.a.prager@gmail.com">daniel.a.prager@gmail.com</a>> wrote:<br>
>> ><br>
>> > [Sorry for drawing you further in.]<br>
>><br>
>> :) (Indeed, my main point is that all that random-number stuff is<br>
>> foreign to me...)<br>
>><br>
>><br>
>> > My take on your 3 points:<br>
>> ><br>
>> > Fisher-Yates is only a few lines, so although not a one-liner, it<br>
>> > seems reasonable to use it for the better space and time performance.<br>
>><br>
>> (It's just time -- the space is the roughly same for both, since sorting<br>
>> will create an intermediate vector too.)<br>
>><br>
>> > I agree that an inside-out version is more apt.<br>
>> > On my reading the final point is an issue if (random n) has problems<br>
>> > like modulo bias, but if that's the case surely it is (random n) that<br>
>> > needs fixing.<br>
>><br>
>> It goes into all kinds of arguments that are exactly in that area that<br>
>> I'm trying to avoid -- but IIUC, it's hard to avoid module-biases, and<br>
>> the FY use of `random' is particularly nasty since it uses all modulos<br>
>> in the range of the number of items. See also the point that the WP<br>
>> page makes about the size of the random number generator state, and how<br>
>> it limits the number of different permutations that can be generated.<br>
>> It looks to me like Racket's state is made of 6 fixnums => 2^192 states,<br>
>> which still doesn't cover all of the permutations of 52 cards. I have<br>
>> no idea if this is correct, if some bias reduces the number of<br>
>> permutations, or whether all of this is something to worry about...<br>
>><br>
>> --<br>
>> ((lambda (x) (x x)) (lambda (x) (x x))) Eli Barzilay:<br>
>> <a href="http://barzilay.org/" target="_blank">http://barzilay.org/</a> Maze is Life!<br>
><br>
><br>
><br>
><br>
> --<br>
> Daniel Prager<br>
> Agile/Lean Coaching, Software Development and Leadership<br>
> Startup: <a href="http://www.youpatch.com" target="_blank">www.youpatch.com</a><br>
> Twitter: @agilejitsu<br>
> Blog: <a href="http://agile-jitsu.blogspot.com" target="_blank">agile-jitsu.blogspot.com</a><br>
><br>
</div></div><div class="HOEnZb"><div class="h5">> ____________________<br>
> Racket Users list:<br>
> <a href="http://lists.racket-lang.org/users" target="_blank">http://lists.racket-lang.org/users</a><br>
><br>
</div></div></blockquote></div><br><br clear="all"><div><br></div>-- <br><div dir="ltr"><div style="font-family:arial;font-size:small"><b>Daniel Prager</b></div><div style="font-family:arial;font-size:small">Agile/Lean Coaching, Software Development and Leadership<br></div><div style="font-family:arial;font-size:small"><font color="#999999">Startup: </font><font color="#000000"><a href="http://www.youpatch.com" target="_blank">www.youpatch.com</a></font></div><div style="font-family:arial;font-size:small"><font color="#999999">Twitter:</font> <a href="https://twitter.com/agilejitsu" style="color:rgb(17,85,204)" target="_blank">@agilejitsu</a> </div><div style="font-family:arial;font-size:small"><font color="#999999">Blog:</font> <a href="http://agile-jitsu.blogspot.com/" style="color:rgb(17,85,204)" target="_blank">agile-jitsu.blogspot.com</a></div></div>
</div>