Recipe 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 functione.g., the Gaussian (Normal) distributionconsult 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.

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

 Chapter 1. Strings
 Chapter 3. Dates and Times
 Chapter 4. Arrays
 Chapter 5. Hashes
 Chapter 6. Pattern Matching
 Chapter 7. File Access
 Chapter 8. File Contents
 Chapter 9. Directories
 Chapter 10. Subroutines
 Chapter 11. References and Records
 Chapter 12. Packages, Libraries, and Modules
 Chapter 13. Classes, Objects, and Ties
 Chapter 14. Database Access
 Chapter 15. Interactivity
 Chapter 16. Process Management and Communication
 Chapter 17. Sockets
 Chapter 18. Internet Services
 Chapter 19. CGI Programming
 Chapter 20. Web Automation
 Chapter 21. mod_perl
 Chapter 22. XML