How to Generate Weighted Random Numbers: Rejection Sampling vs. Iterative Weight Summing?

Generate a Weighted Random Number

Introduction

In various applications, it's often necessary to select a random number from a set of options, where each option is assigned a specific probability of being chosen. This concept is known as generating a weighted random number.

Rejection Sampling Approach

One method of generating weighted random numbers is through rejection sampling. This approach involves creating a lookup table where each option appears as many times as its assigned weight. For example, if option A has an 80% probability, it would appear in the lookup table 80 times. To generate a random number, a random location in the table is selected, and the corresponding option is returned.

Advantages and Disadvantages of Rejection Sampling

Rejection sampling provides constant-time performance for choosing a random number after the lookup table is constructed. However, it requires linear algorithmic performance for building the table, which can be problematic for large sets of options or those with highly precise weights.

Iterative Weight Summing Approach

An alternative approach is iterative weight summing. Here, a random number is generated in the range [0,1) and is compared to the cumulative sum of weights. The option associated with the weight that exceeds the random number is selected as the weighted random number.

Advantages and Disadvantages of Iterative Weight Summing

Compared to rejection sampling, iterative weight summing has no upfront costs but has linear average algorithmic performance in relation to the number of options in the set. It also assumes that the weights sum to one.

Implementation Considerations

When implementing these approaches, it's recommended to create a higher-order function that takes a specification of weights and returns a function that generates weighted random numbers. This allows for reusability and avoids the overhead of building the lookup table or accumulating the weights multiple times.

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