[racket] on reversing a list by way of sort

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 <eli at barzilay.org> wrote:

> On Wed, Sep 17, 2014 at 1:53 AM, Daniel Prager
> <daniel.a.prager at 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20140917/2eb4d239/attachment-0001.html>