In a Monte Carlo simulation, my goal is to compute an estimate of the mean of a distribution via sampling. Traditional, straightforward statistics generates samples (via simulation) and computes the mean and variance of the samples, and uses the variance estimate divided by $n$ as an error estimate on the mean. This all works and produces the desired estimate with error bounds on that estimate.

But I know a little more about my problem. Abstracting the details, my simulation is actually picking samples from multiple independent distributions, each with a different probability of being picked. Think of my sample as having two (or more) urns, each filled with its own distribution of values. Their means and distributions may be the same or completely different... I don't know, and that's why I'm sampling. But I also don't care about the mean of each urn; at the end I only care about some weighted combination of their means.

I can achieve the sampling easily by picking my samples randomly from one urn or the other with the appropriate weight, then computing the mean and variance of the final samples. This all certainly works.

But this is also throwing away a lot of information which may improve my estimates... I have this known stratification in my problem, and the random sampling is throwing that potential information away. What if the urns have differing variances, and after pulling 100 samples from each, I can see one urn's variance is much higher than the others? Then I should start taking more samples from the high variance urn (and compensating by reducing the weight of each one of those samples.) But that decision on the variance is in itself sampled, so I shouldn't trust it! In the worst case, I could take two samples and they happen to be identical, my variance estimate for that urn is 0.. but that doesn't mean I should trust that estimate and ignore the urn from now on!

So my question is given multiple distributions $D_i$ with unknown mean and variance each, and a known set of weights $\alpha_i$, I want to sample values from these $D$ to efficiently form an unbiased estimate of $\sum \alpha_i \bar{D}_i$.

In my problem, I'll typically sample 10,000 to 50,000 times, and I may have between 2 and 10,000 sub-distributions. This may affect strategy, since I sometimes have so many distributions I can't even afford one sample for every one of them.. some have to be skipped!

My current plan will work but it feels ad-hoc. I'll first take say 1000 samples from the distributions, where the number of samples for distribution $D_i$ is proportional to $\alpha_i$. I'll then compute the estimated variance for each $D_i$ and continue sampling, this time with samples apprortioned proportionally to the measured variance of each $D$. I think this will work pretty well, but it's not necessarily the most efficient. And what happens if I have an $\alpha_i$ that's so small that I don't give many (or any) initial samples to the distribution? Should I start combining disparate low-$\alpha$ distributions into one so that they have a better chance of being sampled?

My entire goal is to minimize the number of samples needed, but the strategy to apportion them is far from obvious. Any thoughts or suggestions are welcome!

  • $\begingroup$ Reminds me of this paper (though I haven't read it in a while): www-graphics.stanford.edu/papers/combine $\endgroup$ – dls Mar 15 '12 at 3:39
  • $\begingroup$ I think you'll have to take care not to introduce bias by having the sampling strategy depend on the initial samples. There might be ways to avoid that, but to be on the safe side you could first do some sampling to decide the strategy and then not use those initial samples for the estimate. $\endgroup$ – joriki Mar 15 '12 at 11:01

Your question does not seem very clear to me. If you do not know the mean and variance of the different mixture components ahead of time, then either you must estimate those as you draw random sample, or you are assuming something about them. In either case, you should first check on whether you can use something like the EM Algorithm, which is a standard thing to use when estimating mixture distribution (and then you can just compute the mean at the end of the estimation process).

You should also look at stratified sampling to see if it can help you, and possibly also hybrid Monte-Carlo where some care is taken to adaptively change the sampling procedure.

Overall, your problem does not sound like it requires any special treatment. You would like to spend more time sampling from mixture components with higher variance, but how do you know they have higher variance? Unless you solve intermediate EM estimation problems, I'm not sure that just basing it on currently simulated results will give you anything sensible.


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.