How to Generate Weighted Random Numbers in Programming: Rejection Sampling vs. Iterative Search?

Generating Weighted Random Numbers in Programming

Weighted random numbers find application in various scenarios where specific values within a range have different probabilities of being selected. In this article, we explore two effective approaches to achieve this:

The first approach, proposed by the original questioner, involves Rejection Sampling. This method creates a lookup table populated with the elements in the range, where each element appears a number of times proportional to its weight. Subsequently, a random index is chosen from the lookup table to retrieve the random number. The trade-off here lies in the linear time complexity for building the lookup table and the potential memory consumption for large weight specifications.

Alternatively, the Iterative Search method iteratively calculates the sum of weights while traversing the weight specification. It compares this sum with a randomly generated number between 0 and 1. If the sum exceeds the random number, the corresponding value is returned as the random number. Unlike rejection sampling, this approach incurs no upfront cost but exhibits an average time complexity linear to the number of entries in the weight specification.

To demonstrate both approaches in JavaScript:

// Rejection Sampling
function weightedRand(spec) {
  var i, j, table = [];
  for (i in spec) for (j = 0; j < spec[i] * 10; j++) table.push(i);
  return function() { return table[Math.floor(Math.random() * table.length)]; };
}
var rand012 = weightedRand({0:0.8, 1:0.1, 2:0.1});

// Iterative Search
function weightedRand2(spec) {
  var i, sum = 0, r = Math.random();
  for (i in spec) { sum += spec[i]; if (r <= sum) return i; }
}

The choice of approach depends on the specific application requirements, balancing time complexity, memory usage, and deterministic behavior. Rejection sampling offers constant-time lookups at the cost of upfront table construction, while iterative search provides a simpler implementation with linear-time performance. By leveraging these techniques, programmers can effectively generate weighted random numbers for their various programming needs.

The above is the detailed content of How to Generate Weighted Random Numbers in Programming: Rejection Sampling vs. Iterative Search?. For more information, please follow other related articles on the PHP Chinese website!