Say I want to create a histogram of $N$ samples from some simple compactly supported distribution on $\mathbb{R}$, where $N$ is very large, say $N = 10^{30}$. The histogram has $K$ disjoint bins, where $K$ is a more reasonable number like $10$ or $1000$. Obviously it's not feasible for me to directly draw $N$ Monte Carlo samples from my distribution and bin them up to form the histogram. However, it seems to me that there might be some correct method which works by sampling the number of counts in each bin, one at a time, for a total of only $K$ samples. I'm looking for some help finding such a method.

The number of counts in each bin is a binomial random variable with parameters that can easily be calculated by integrating the distribution over the bin interval. So if I have a good way to simulate binomial random variables with large means, I can simulate the number of counts in each bin using only $K$ Monte Carlo draws of a binomial random variable.

The problem is that the total counts in the bins are correlated by the constraint that they must add up to $N$. My method will produce a random number of total counts which will almost certainly not be $N$.

I can think of a couple more sophisticated methods that would avoid this problem, but they create thornier ones - and the bottom line is, I don't know how to prove that any of these heuristic methods are correct.

Can anybody think of an $O(K)$ algorithm that generates a provably correct (or provably nearly correct) histogram sample for this kind of problem? More formally, a correct method for sampling the random vector $H \in \mathbb{Z}^K$ whose entries are the histogram counts? If not, what's the best that I can hope for?

  • $\begingroup$ It seems to me that you would have a better chance of getting a good answer at stats.stackexchange.com . $\endgroup$ – Angelo May 29 '12 at 2:25

Can we assume the number of counts in each bin are large enough that the binomial distribution of counts in the bin will be close to a normal distribution? And in that case, is it enough to just sample the normal distribution for each bin, add up the samples, and get a total $N'=a\cdot N$ where $a=1\pm O\big({1\over \sqrt K}\big)$ or something like that. Then just scale all the counts by a factor of $1/a$ to get them to add up to the right thing (scaling the normal distributions keeps them normal). Am I missing something significant?

  • 2
    $\begingroup$ If you're going to use the CLT, then you can do better by explicitly building in the constraint and using correlated normal random variables. $\endgroup$ – Anthony Quas May 29 '12 at 4:48
  • $\begingroup$ Both those ideas occurred to me, and I might end up going with them if I can't think of anything more accurate. $\endgroup$ – Paul May 30 '12 at 19:42

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.