Multinomial Sampling with Distribution Checks

Implement sampling from a list of category probabilities. For this exercise, assume probabilities are represented by nonnegative integer weights: category i has probability weights[i] / W, where W is the positive sum of all weights.

The reproducible practice task supplies the integer draws in tickets. Each ticket is in [0, W). Return one zero-based category index for each ticket, in the same order. Do not generate new random values or sort the tickets.

For this exercise, assume categories own consecutive half-open ranges in their original order. If S_i is the sum of weights before category i, its range is [S_i, S_i + weights[i]). A zero-weight category owns no tickets. A ticket exactly at a range’s upper boundary belongs to the next nonempty range.

If the supplied draws are independent and uniform on [0, W), each returned category has the requested probability. A histogram of m such draws is a multinomial count vector. Valid practice tickets need not themselves look uniformly distributed; the returned indices must always obey the mapping.

Distribution-check follow-up

Implement the separate helper maxEmpiricalDeviation(weights, samples) for a nonempty array of valid sampled category indices. For this exercise, assume it returns max_i(abs(count_i / samples.length - weights[i] / W)), using double precision. Include every category, even one with zero weight. The sampler entrypoint is the judged task; this helper is a follow-up with reference implementations in the editorial.

For example, weights [1,0,3] and samples [0,2,2,2] give deviation 0. Samples [0,0,2,2] give deviation 0.25. Finite random samples normally differ from the target. This metric measures a discrepancy; it does not prove a generator is correct or provide a statistical confidence level.

Notebook benchmark follow-up

The report asks for experiments while discussing how to run the program faster. It specifically highlights moving random-number generation outside the loop and replacing a list with a NumPy array; changing linear search to binary search was not the focus.

1. Compare generating one ticket per iteration with generating the same number of tickets in one batch.
2. With a common draw array and the same cumulative masses, compare Python list mapping, array mapping in a Python loop, and vectorized array mapping. Check that outputs agree before timing them.
3. Measure preprocessing, random-number generation, mapping and the complete pipeline separately. Repeat runs, report the environment and sample count, and explain allocations and memory use.
4. Compute a histogram and the empirical discrepancy. Explain why no particular finite random sample must match the probabilities exactly.

For this exercise, assume these timing experiments are an open discussion without a fixed speedup threshold or a judged wall-clock target.