Generate random number from an arbitrary weighted list

Question

Here's what I need to do, I'll be doing this both in PHP and JavaScript.

I have a list of numbers that will range from 1 to 300-500 (I haven't set the limit yet). I will be running a drawing where 10 numbers will be picked at random from the given range.

Here's the tricky part: I want some numbers to be less likely to be drawn up. A small set of those 300-500 will be flagged as "lucky numbers".

For example, out of 100 drawings, most numbers have equal chances of being drawn, except for a few, that will only be picked once every 30-50 drawings.

Basically I need to artificially set the probability of certain numbers to be picked while maintaining an even distribution with the rest of the numbers.

The only similar thing I've found so far is this question: Generate A Weighted Random Number, the problem being that my spec has considerably more numbers (up to 500) so the weights would get very small and supposedly this could be a problem with that solution (Rejection Sampling). I'm still trying it, though, but I wonder if there other solutions.

Math is not my thing so I appreciate any input. Thanks.

Answer 1

I wrote a quick little JSFiddle to handle this:

http://jsfiddle.net/cHVsC/

Basically, I generate an array called the pool which contains the full list of numbers, including duplicates for the more heavily weighted numbers. Selection then happens exactly as it would with a non-weighted Array.

Sample JS:

function generatePool (count, luckyNumbers) {
    var arr = [], i, j;
    for (i = 1; i <= count; i++) {
        if (luckyNumbers[i]) {
            for (j = 0; j < luckyNumbers[i]; j++) {
                arr.push(i);
            }
        } else {
            arr.push(i);
        }
    }
    return arr;
}

function randomNumber (pool) {
    return pool[ Math.floor(Math.random() * pool.length) ];
}

And a usage example

var luckyNumbers = {};
luckyNumbers[13] = 10;
luckyNumbers[25] = 100;

var pool = generatePool(300, luckyNumbers);

alert(randomNumber(pool));

UPDATE: I misinterpreted the original goal. Here is an updated version:

function generatePool (count, luckyNumbers) {
    var arr = [], i, j;
    for (i = 1; i <= count; i++) {
        for (j = 0; j < (luckyNumbers[i] || 10); j++) {
            arr.push(i);
        }
    }
    return arr;
}

function randomNumber (pool) {
    return pool[ Math.floor(Math.random() * pool.length) ];
}

A usage example:

var luckyNumbers = {};
luckyNumbers[13] = 1; //-- ~1:10 odds
luckyNumbers[25] = 2; //-- ~2:10 odds

var pool = generatePool(300, luckyNumbers);

console.log(randomNumber(pool));

Answer 2

function pick_number() {

    $lucky_numbers = range(1,10);
    $regular_numbers = range(11,100);

    //pick lucky numbers with 30% probability
    //even though they only represent 10% of all numbers
    if(rand(1,100) <= 30) {
        $index = rand(0,count($lucky_numbers)-1);
        $number = $lucky_numbers[$index];
    }
    else {
        $index = rand(0,count($regular_numbers)-1);
        $number = $regular_numbers[$index];
    }

    return $number;
}

$frequency = [];

foreach(range(1,1000) as $i) {
    $frequency[pick_number()]++;
}

ksort($frequency);

print_r($frequency);

OUTPUT

Array
(
    [1] => 27
    [2] => 31
    [3] => 31
    [4] => 37
    [5] => 25
    [6] => 37
    [7] => 33
    [8] => 20
    [9] => 34
    [10] => 33
    [11] => 7
    [12] => 11
    [13] => 11
    [14] => 9
    [15] => 13
    [16] => 9
    [17] => 13
    [18] => 5
    [19] => 4
    [20] => 6
    [21] => 9
    [22] => 3
    [23] => 4
    [24] => 9
    [25] => 6
    [26] => 10
    [27] => 2
    [28] => 10
    [29] => 14
    [30] => 7
    [31] => 7
    [32] => 3
    [33] => 13
    [34] => 8
    [35] => 14
    [36] => 8
    [37] => 8
    [38] => 3
    [39] => 13
    [40] => 12
    [41] => 7
    [42] => 7
    [43] => 8
    [44] => 4
    [45] => 8
    [46] => 10
    [47] => 7
    [48] => 5
    [49] => 5
    [50] => 6
    [51] => 9
    [52] => 7
    [53] => 14
    [54] => 12
    [55] => 4
    [56] => 9
    [57] => 4
    [58] => 8
    [59] => 1
    [60] => 9
    [61] => 14
    [62] => 8
    [63] => 13
    [64] => 4
    [65] => 4
    [66] => 10
    [67] => 11
    [68] => 7
    [69] => 7
    [70] => 8
    [71] => 4
    [72] => 4
    [73] => 6
    [74] => 6
    [75] => 10
    [76] => 6
    [77] => 10
    [78] => 4
    [79] => 10
    [80] => 9
    [81] => 5
    [82] => 8
    [83] => 7
    [84] => 8
    [85] => 8
    [86] => 6
    [87] => 10
    [88] => 8
    [89] => 5
    [90] => 6
    [91] => 8
    [92] => 2
    [93] => 8
    [94] => 4
    [95] => 8
    [96] => 5
    [97] => 6
    [98] => 12
    [99] => 11
    [100] => 7
)