PHP Numbers Generating Biased Random Numbers

PHP Numbers

Generating Biased Random Numbers

Problem

You want to generate random numbers, but you want these numbers to be somewhat biased, so that numbers in certain ranges appear more frequently than others. For example, you want to spread out a series of banner ad impressions in proportion to the number of impressions remaining for each ad campaign.

Solution

Example   rand_weighted()

            // returns the weighted randomly selected key
            function rand_weighted($numbers) {
                    $total = 0;
                    foreach ($numbers as $number => $weight) {
                             $total += $weight;
                             $distribution[$number] = $total;
                    }
                    $rand = mt_rand(0, $total - 1);
                    foreach ($distribution as $number => $weights) {
                             if ($rand < $weights) { return $number; }
                    }
            }

Discussion

Imagine if instead of an array in which the values are the number of remaining impressions, you have an array of ads in which each ad occurs exactly as many times as its remaining number of impressions. You can simply pick an unweighted random place within the array, and that’d be the ad that shows.

This technique can consume a lot of memory if you have millions of impressions remaining. Instead, you can calculate how large that array would be (by totaling the remaining impressions), pick a random number within the size of the make-believe array, and then go through the array figuring out which ad corresponds to the number you picked. For instance:

            $ads = array('ford' => 12234, // advertiser, remaining impressions
                                   'att' => 33424,
                                 'ibm' => 16823);

            $ad = rand_weighted($ads);


You could select the weighted random number without having to build the distribution array first:

            function incremental_total($numbers) {
                    $total = 0;
                    foreach ($numbers as $number => $weight) {
                            $total += $weight;
                            yield $number => $total;
                    }
            }

            // returns the weighted randomly selected key
            function rand_weighted_generator($numbers) {
                    $total = array_sum($numbers);
                    $rand = mt_rand(0, $total - 1);
                    foreach (incremental_total($numbers) as $number => $weight) {
                            if ($rand < $weight) { return $number; }
                    }
            }