# [racket] on reversing a list by way of sort

 From: Daniel Prager (daniel.a.prager at gmail.com) Date: Wed Sep 17 08:29:46 EDT 2014 Previous message: [racket] on reversing a list by way of sort Next message: [racket] on reversing a list by way of sort Messages sorted by: [date] [thread] [subject] [author]

```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)

(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