2
$\begingroup$

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.

histogram of # of points per bin

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:

N=1000 sampled histogram

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.

N=10000 sampled histogram

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).

$\endgroup$
12
  • 5
    $\begingroup$ I'm not sure about "goal is to draw a random sample from this distribution which has a roughly uniform distribution". It's clearly not uniform - so why? What am I missing? $\endgroup$ – rbm Apr 18 '17 at 12:17
  • $\begingroup$ The original distribution is not uniform. I wish to draw a random subsample which is roughly uniform. The question of why I want to do this seems like an irrelevant detail, unless I am misunderstanding your question. $\endgroup$ – abeboparebop Apr 18 '17 at 13:00
  • 1
    $\begingroup$ Sorry, still makes no sense, as you can't draw a uniform subsample from non-uniform distribution. It's like trying to get a U(0,1) subsample from a N(0,1) distribution. Perhaps someone else understands what you're trying to do. $\endgroup$ – rbm Apr 18 '17 at 13:09
  • 4
    $\begingroup$ Sorry but it is still unclear... Why can't you just sample from uniform distribution within the given interval? You'll end up with a perfectly uniform sample... $\endgroup$ – Tim Apr 18 '17 at 14:24
  • 1
    $\begingroup$ I think it is perfectly clear what OP is asking, and also it makes no sense. Suggest trying a beta distribution, not a uniform one. If OP wants to map a beta distribution into a uniform one, then the x-axis becomes non-linear. One can do this by having unequal histogram category widths, but whatever for? Why bother? Provide some motivation, please. $\endgroup$ – Carl Apr 19 '17 at 2:34
4
$\begingroup$

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.

drawing of two bins one with 98 red balls and one with two green balls and a list of draws from the two bins generated by coin toss H=red, T=green which goes H H H T H T H H ... noting that at the fifth draw the second bin is empty and we can only get red from here on

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.]

$\endgroup$
4
  • $\begingroup$ I think this is exactly the correct explanation of the phenomenon -- indeed, sampling with replacement gives the expected uniform distribution. Unfortunately, sampling with replacement doesn't work for my use case. My hope is that there is a principled way to overweight the sparser bins based on the number of draws I will be making, given that I still expect to be drawing substantially fewer than the total number from each bin. $\endgroup$ – abeboparebop Apr 19 '17 at 8:02
  • $\begingroup$ If the bins are equal width (you say "linearly spaced" but that's not quite unambiguous; I presume that's equal width) then my answer already responds to that. Simply continue to sample each bin with equal probability no matter how many (or how few) points it contains. If the bins are not equal width you'd need to sample points from the bins in proportion to their width. $\endgroup$ – Glen_b Apr 19 '17 at 11:40
  • $\begingroup$ Yes, equal width bins. So to make it explicit, your proposed sampling procedure would to first choose a bin (by e.g. uniform sampling) and then randomly choose an item within that bin? I did end up implementing essentially this solution and it has exactly the features that I wanted. $\endgroup$ – abeboparebop Apr 19 '17 at 11:48
  • $\begingroup$ Yes, that's it. You can do it without choosing a bin -- by choosing points directly -- though then there's additional overhead since each time you choose a point you have to distributed the weight to that point across the rest of the points in its bin to keep the bin probability constant $\endgroup$ – Glen_b Apr 19 '17 at 12:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.