<div dir="ltr">Modulo bias is easy enough to correct by checking and occasional re-sampling. It's explained nicely in the following article: <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><div><br></div><div>Let's *deliberately* generate some modulo bias in Racket by simulating a low largest random number:</div><div><br></div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div><div><font face="courier new, monospace">(define (biased-random RAND-MAX n)</font></div></div><div><div><font face="courier new, monospace"> (modulo (random (add1 RAND-MAX)) 3))</font></div></div></blockquote><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div><div><span style="font-family:'courier new',monospace"> </span><br></div></div><div><div><font face="courier new, monospace">(define (check-bias method [n 10000])</font></div></div><div><div><font face="courier new, monospace"> (define sample (for/list ([i n]) (method 4 3)))</font></div></div><div><div><font face="courier new, monospace"><br></font></div></div><div><div><font face="courier new, monospace"> (for ([i (in-range 3)])</font></div></div><div><div><font face="courier new, monospace"> (displayln</font></div></div><div><div><font face="courier new, monospace"> (~a i " " (~a (real->decimal-string</font></div></div><div><div><font face="courier new, monospace"> (* 100.0 (/ (count (λ (j) (= i j)) sample) n))</font></div></div><div><div><font face="courier new, monospace"> 1) "%")))))</font></div></div><div><font face="courier new, monospace"><br></font></div></blockquote><font face="arial, helvetica, sans-serif">> (check-bias biased-random)</font><div style="font-family:'courier new',monospace"><font face="arial, helvetica, sans-serif">0 38.3%</font></div><div style="font-family:'courier new',monospace"><font face="arial, helvetica, sans-serif">1 41.0%</font></div><div><font face="arial, helvetica, sans-serif">2 20.7%</font></div><div style="font-family:'courier new',monospace"><br></div><div style="font-family:'courier new',monospace"><span style="font-family:arial">Remove the generated bias by rejecting some "high" values:</span><br></div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div><font face="courier new, monospace"><br></font></div><div><div><div><font face="courier new, monospace">(define (unbiased-random RAND-MAX n)</font></div><div><font face="courier new, monospace"> (define excess (add1 (modulo RAND-MAX n)))</font></div><div><font face="courier new, monospace"> (define limit (- RAND-MAX excess))</font></div><div><font face="courier new, monospace"> (define (in-limit m)</font></div><div><font face="courier new, monospace"> (if (<= m limit) m (in-limit (random (add1 RAND-MAX)))))</font></div><div><font face="courier new, monospace"> (modulo (in-limit (random (add1 RAND-MAX))) n))</font></div></div><div></div></div></blockquote><div><div><br></div><div><div>> (check-bias unbiased-random)</div><div>0 33.9%</div><div>1 33.8%</div><div>2 32.4%</div></div></div><div><br></div><div>Conclusion: We should be ok regarding modulo bias provided (random n) uses a rejection strategy along these lines. If not, it's quite fixable.</div><div><br></div><div>Dan</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Sep 17, 2014 at 1:44 AM, Eli Barzilay <span dir="ltr"><<a href="mailto:eli@barzilay.org" target="_blank">eli@barzilay.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">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>
</span>:) (Indeed, my main point is that all that random-number stuff is<br>
foreign to me...)<br>
<span class=""><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>
</span>(It's just time -- the space is the roughly same for both, since sorting<br>
will create an intermediate vector too.)<br>
<span class=""><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>
</span>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>
<div class="HOEnZb"><div class="h5"><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>
</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>