Weighted Reservoir Sampling
Weighted Reservoir Sampling Weighted Reservoir Sampling selects a random sample from a stream where each item has a weight. Higher weight items should be more likely to appear in the sample. A common method assigns each item a random priority derived from its weight, then keeps the $k$ items with the largest priorities. Problem Given a stream of weighted items: $$ (x_1, w_1), (x_2, w_2), \dots, (x_n, w_n) $$ where...