Taking many uniform random samples from very skewed distribution

Question

I have a dataset which has a very skewed distribution across a parameter S, which is in the range [0,1). There are many, many values close to 0, and very few above 0.05. My goal is to draw a random sample from this distribution which has a roughly uniform distribution across S.

I start by binning the points into 1000 linearly-spaced bins, and then calculate a weight parameter w_i = 1/N_i, where N_i is the number of points in bin i. The figure below shows the number of points per bin. Some bins have more than 100M points, others have as few as 500.

Then I perform a weighted random sample on this parameter. To perform the weighted random sampling, I sort by a parameter weight_order = -log(rand())/w_i and take the first N rows. (I originally saw this suggested on this Stack Overflow answer, and I have not thought through the math carefully.) Note that this is sampling without replacement.

This approach results in a uniform distribution as long as N is sufficiently small. See for example the histogram for N=1000:

The histogram is somewhat sparse because I have included all 1000 bins so the average number per bin N_i=1, but aggregating into fewer larger bins visually confirms that the sample is reasonably uniform.

However, for larger N, the resulting sample starts to become skewed. See the same but for N = 10000.

I want 10 samples per bin, but already the resulting sample is quite skewed towards the thicker parts of the source distribution.

Thus, my question: is there a better way to sample my original dataset such that I get an approximately uniform distribution even as N becomes larger? Ultimately I would like to sample 100000 points, which would ideally result in about 100 samples per bin, which is still quite a bit less than the smallest number of points in a bin in the original dataset (~500).

Answer 1

I believe the difficulty you observe may simply be due to attempting to sample without replacement -- as you deplete the sparser bins, you can't avoid starting to sample the high-density bins more heavily.

If you weight the observations according to the inverse of the density but keep the weights to each observation unchanged you have a problem almost as soon as you start - consider the interval (0,1) split into two bins (split at $\frac12$), the first one with 98 observations and the second one with 2. We can calculate the weights to the observations in the second bin will be 49 times as large as the first bin. So far everything is fine, but within the first few draws you expect to take an observation from the second bin. Now unless you adjust the weights at this point, you're now on average twice as likely to get an observation from the first bin as the second, so the first bin starts to be more heavily sampled.

However, the problem you observe will happen even if you keep readjusting the sampling probabilities to observations (equivalently, if you weight the bins rather than the observations) as you sample because once you empty the smallest bins you can no longer sample anywhere else but the ones with lots of observations.

Again consider just two bins as above, one with 98 observations in it, and one with 2. We sample from each bin with a 50-50 chance (so that after we sample one observation from the second bin the weight to the remaining point roughly doubles). On average, after we have sampled only a few observations, the second bin will be empty.

Up to this point we will have sampled uniformly, but we can't sample the empty bin ever again and from now on things will start to look more and more like the original distribution until eventually we've sampled the entire original data set and the distribution shape is identical.

[If you try sampling with replacement you should see that you don't get this problem; that should serve to confirm my explanation is what you're seeing in what you're doing.]