Random numbers

That still seems to pessimize a bit too much to me. If you have all of them right around 12.5%, why use a selection algorithm that makes half (on average) effectively 0%? Instead of introducing a divide for your average, just track the sum, make a random number within [0, sum) (any other scheme is likely to have something here anyways to get a number within your domain), then subtract off each bucket's size until you get a value < 0 and you've found your selection. Tracking is then just counting into each bucket and the sum and you reweight to avoid overflows every so often. Reweighting after each measurement seems excessively expensive.