I have a sampling algorithm (a variant of Metropolis-Hastings) which I'm using to generate independent samples from a discrete distribution which is expensive to sample directly. The state space is somewhat large (about 10000 states, though I'd like to be able to deal with up to 1000000), and probabilities between states vary widely as well (up to a factor of about 1000x).

What statistical tests can I use to evaluate how well my sampler is following the probability distribution? My initial thought was to do a chi-square test, of course, but the number of observations required to get all of the states observed with a high frequency seems to be quite formidable. Is there another test that would be more appropriate?