Using a discrete Monte-Carlo technique in a multi-variable model

[snowjoke]

If I have a large amount of data I can sample, with a several discrete variables, and I need to get an average of some function of that data, but it's too computationally intensive to do exhaustively...

I want to do some sampling of the possible outcomes. I guess random sampling (Monte-Carlo technique) is the way forward, but my question is, theoretically, when selecting random numbers for the inputs, should I discard combinations that have already been used?

For large samples it probably won't in practice make any difference, but say I had I have 3 variables a, b and c, each of which can be (0,1,2,3,4,5,6,7,8,9), and I want to compute 100 outputs. Say I've already used {a = 1, b = 8, c = 4}, in theory should I check whether I've used this combination already?

Intuitively it seems like I'll get a more accurate result if I discard already-used inputs, but then the inputs won't be random.

 

[mathman]

Discarding already used combinations will lead to a better (smaller) standard deviation for the estimated average.

 

[bpet]

Interestingly, the chance of having no repeats in sampling k from n is approximately exp(-k^2/2n). I wonder if there is a simple expression for the expected number of unique samples.