Generating Biased Random Numbers (Perl Cookbook, 2nd Edition)

## 2.9. Generating Biased Random Numbers

### 2.9.1. Problem

You want to pick a random value where the probabilities of the values are not equal (the distribution is not even). You might be trying to randomly select a banner to display on a web page, given a set of relative weights saying how often each banner is to be displayed. Alternatively, you might want to simulate behavior according to a normal distribution (the bell curve).

### 2.9.2. Solution

If you want a random value distributed according to a specific function—e.g., the Gaussian (Normal) distribution—consult a statistics textbook to find the appropriate function or algorithm. This subroutine generates random numbers that are normally distributed, with a standard deviation of 1 and a mean of 0:

>     sub gaussian_rand {
>         my ($u1, $u2);  # uniformly distributed random numbers
>         my $w;          # variance, then a weight
>         my ($g1, $g2);  # gaussian-distributed numbers

>         do {
>             $u1 = 2 * rand( ) - 1;
>             $u2 = 2 * rand( ) - 1;
>             $w = $u1*$u1 + $u2*$u2;
>         } while ($w >= 1 || $w =  = 0);

>         $w = sqrt( (-2 * log($w))  / $w );
>         $g2 = $u1 * $w;
>         $g1 = $u2 * $w;
>         # return both if wanted, else just one
>         return wantarray ? ($g1, $g2) : $g1;
>     }

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`, and then use the distribution to randomly pick a value with `weighted_rand`:

>     # weight_to_dist: takes a hash mapping key to weight and returns
>     # a hash mapping key to probability
>     sub weight_to_dist {
>         my %weights = @_;
>         my %dist    = ( );
>         my $total   = 0;
>         my ($key, $weight);
>         local $_;

>         foreach (values %weights) {
>             $total += $_;
>         }

>         while ( ($key, $weight) = each %weights ) {
>             $dist{$key} = $weight/$total;
>         }

>         return %dist;
>     }

>     # weighted_rand: takes a hash mapping key to probability, and
>     # returns the corresponding element
>     sub weighted_rand {
>         my %dist = @_;
>         my ($key, $weight);

>         while (1) {                     # to avoid floating point inaccuracies
>             my $rand = rand;
>             while ( ($key, $weight) = each %dist ) {
>                 return $key if ($rand -= $weight) < 0;
>             }
>         }
>     }

### 2.9.3. Discussion

The `gaussian_rand` function implements the polar Box Muller method for turning two independent, uniformly distributed random numbers between 0 and 1 (such as `rand` returns) into two numbers with a mean of 0 and a standard deviation of 1 (i.e., a Gaussian distribution). To generate numbers with a different mean and standard deviation, multiply the output of `gaussian_rand` by the new standard deviation, and then add the new mean:

>     # gaussian_rand as shown earlier
>     $mean = 25;
>     $sdev = 2;
>     $salary = gaussian_rand( ) * $sdev + $mean;
>     printf("You have been hired at \$%.2f\n", $salary);

The Math::Random module implements this and other distributions for you:

>     use Math::Random qw(random_normal);
>     $salary = random_normal(1, $mean, $sdev);

The `weighted_rand` function picks a random number between 0 and 1. It then uses the probabilities generated by `weight_to_dist` to see which element the random number corresponds to. Because of the vagaries of floating-point representation, accumulated errors in representation might mean we don't find an element to return. This is why we wrap the code in a `while` to pick a new random number and try again.

Also, the CPAN module Math::Random has functions to return random numbers from a variety of distributions.

### 2.9.4. See Also

The `rand` function in perlfunc(1) and Chapter 29 of Programming Perl; Recipe 2.6; the documentation for the CPAN module Math::Random

Copyright © 2003 O'Reilly & Associates. All rights reserved.