Weighted multinomial sampling

Background

Weighted (multinomial) sampling draws categories in proportion to given weights — the basis of importance sampling, weighted bootstrap, and roulette-wheel selection in genetic algorithms. You normalize the weights into a probability distribution, then use inverse-transform sampling: build the cumulative distribution and map uniform random numbers through it.

Problem statement

Implement weighted_sample(weights, n, seed=0) returning n category indices drawn with probability proportional to weights:

$$p_k = \frac{w_k}{\sum_j w_j}, \qquad F_k = \sum_{j\le k} p_j, \qquad x_i = \text{searchsorted}(F, u_i),\ \ u_i \sim \mathcal U(0,1)$$

Use np.random.default_rng(seed) and side='right'.

Input

• weights — np.ndarray (K,), non-negative weights (need not sum to 1).
• n — int, number of samples.
• seed — int.

Output

An np.ndarray of n integer indices in [0, K).

Examples

Example 1

Input:  weights = [1, 3], n = large
Output: index 0 about 25% of the time, index 1 about 75%

Explanation: normalizing gives $p=[0.25, 0.75]$, so category 1 (weight 3) is drawn three times as often as category 0.

Constraints

• Normalize the weights to a probability distribution first.
• Sample via the cumulative distribution (searchsorted), not a per-sample loop.
• Indices are integers in [0, len(weights)).

Notes

• This is inverse-transform sampling applied to a categorical distribution defined by arbitrary weights.
• A weight of 0 means that category is never drawn; its cumulative step has zero width.