On game space size and Monte Carlo sampling

[John Aspinall <jga@xxxxxxx>]

At 10:48 AM -0700 4/28/99, Mousheng Xu wrote:
>	Just a minor question: when do you know you can stop while doing random
>sampling in Monte Carlo? Suppose I know a little about statistics. :)

There are two questions here:
 (1) How can I get unbiased samples from my Monte Carlo simulation?
 (2) How many unbiased samples do I need?

Question 2 can be answered by elementary statistics; I assume you can
calculate mean and variance of a sample :-)

Question 1 is the hard one.  The danger is that the way you initialize your
Monte Carlo sampler will bias the samples.  The best answer is to use Propp
and Wilson's "coupling from the past" technique to produce unbiased
samples.  You can get copies of their articles from
http://www-math.mit.edu/~propp/articles.html .