s c h e m a t i c s : c o o k b o o k

This Web

Other Webs

Schematics

RSS

Scheme Links

Generating Biased Random Numbers

Problem

Instead of a truly random number, you wish to randomly select a value from a set in which some values are more likely than others. For example, you may wish to simulate a normal distribution (i.e., a "bell curve") for a set of data.

Solution

We will give a recipe for generating numbers with a normal distribution (aka Gaussian distribution, the bell shaped one). A library is under way see: Schemathics CVS, but we will discuss a do-it-yourself method for explanatory purposes.

You will have to determine what kind of distribution you want, and locate the appropriate algorithm from a statistics reference.

For this recipe, we will consider the normal (Gaussian) distribution. If you need other distributions see either the CVS or consult a numerical analyst.

The function make-normal-distributed-variable returns a stochastic variable (a thunk) with mean mu and standard deviance sigma.:

; derived from example in the documentation of SRFI27

(require (lib "27.ss" "srfi"))

(define (make-normal-distributed-variable mu sigma)
  (let ((mu    (* 1.0 mu))
        (sigma (* 1.0 sigma))
        (next  #f))
    (lambda ()
      (cond
        (next  (let ((result next))
                 (set! next #f)
                 (+ mu (* sigma result))))
        (else  (let loop ()
                 (let* ((v1 (- (* 2.0 (random-real)) 1.0))
                        (v2 (- (* 2.0 (random-real)) 1.0))
                        (s  (+ (* v1 v1) (* v2 v2))))
                   (cond
                     ((>= s 1.0) (loop))
                     (else       (let ((scale (sqrt (/ (* -2.0 (log s)) s))))
                                   (set! next (* scale v2))
                                   (+ mu (* sigma scale v1))))))))))))

An example of usage:

> (define X (make-normal-distributed-variable 0 1))
> (X)
0.7386912134436788
> (X)
-0.4388994504610697
> (X)
0.5826066449247809

> (random-source-randomize! default-random-source)

Discussion

The algorithm used is the polar Box Muller method. The algorithm takes two independent uniformly distributed random numbers between 0 and 1 (present in the code as (random-real)) and generates two numbers with a mean of my and standard deviation sigma. Note that the method produces two numbers at a time. Since we only need one, the second is saved for later in the variable next.

Comments about this recipe

Note that the Perl Cookbook includes an interesting discussion of converting a set of values (and weights) into a distribution. This should also be converted to Scheme and shown here.

Mathematically-inclined Schemers should also take a good look at Schemathics, which contains these and many other statistical methods.

It's also worth noting that if a bell-curve type thing is all you're looking for, generating two or more random numbers and taking the average will tend to favor the middle values. For example, consider a pair of dice: there is exactly one combination out of 36 that yields 2 and one that yields 12 (the outlying values), while there are six combinations that yield 7 (the center value). You could also use a weighed average to reduce the effect if averaging two random numbers produces a bell curve which is too steep for your application.

Contributors

-- BrentAFulgham - 14 May 2004

-- JensAxelSoegaard - 01 Jun 2004

[TODO: Move the following remarks to another recipe]

If you wish to randomly select from a set of weights and values, convert the weights into a probability distribution, then use the resulting distribution to pick a value.

If you have a list of weights and values you want to randomly pick from, follow this two-step process: First, turn the weights into a probability distribution with weight_to_dist below, and then use the distribution to randomly pick a value with weighted_rand: