Weighted Random Sampler · Analysis

01 · Frame the problem

Understand the central challenge

Choose one item with probability proportional to its nonnegative integer weight. This educational sampler is not intended for security-sensitive lotteries; the caller supplies a uniform bounded-integer random source.

Weighted sampling requires exact interval sizes over a uniform bounded draw. Analyse zero weights, integer overflow and the randomness adapter's contract before selecting a search structure.

02 · Find the design pressure

Start simple, then identify the gap

Begin with cumulative integer weights and binary search. Floating thresholds can blur boundaries, and modulo reduction can bias draws. Require an unbiased integer in the exact total range and select the first prefix strictly above it.

Snapshot validated items and checked integer prefix sums once. Each sample obtains a uniform integer below total weight and binary-searches the first prefix strictly greater than that draw. Validate unique item IDs and nonnegative safe-integer weights. Accumulate with checked addition and reject an empty or zero-total distribution. Store immutable item and cumulative-weight arrays. Zero-weight entries retain repeated prefixes and therefore empty draw intervals. Call the injected bounded generator with total weight and validate its returned integer range. Use upper-bound search to find the selected index in logarithmic time. Document O(n) construction and O(log n) sampling with O(n) storage. Updating weights creates a new sampler; security-sensitive randomness and mutable weighted trees are outside this exercise.

03 · Define success

Requirements to preserve

Reject negative weights, duplicate IDs and zero total weight.
Use checked exact prefix-sum arithmetic.
Skip zero-weight items naturally.
Define half-open draw intervals and reproducible boundary tests.

04 · Identify the correctness boundary

Invariants, representation and mutation boundaries

Use checked integer prefix sums and draw uniformly from [0,totalWeight). Binary-search the first prefix strictly greater than the draw so zero-weight entries never win. The randomness adapter must guarantee unbiased bounded integers; applying modulo to an arbitrary random range can introduce bias.

05 · Make it concrete

Reason through a worked example

Weights A=2, B=0 and C=3 produce prefixes 2,2,5. Draws 0 and 1 select A; draws 2 through 4 select C. B is never selected. An all-zero total is rejected rather than returning an arbitrary item or attempting an empty random range.