Evaluating quality of a sampler on a small subset of the entire sample space Assume a multi-dimensional discrete sample space $X$, which is "large", e.g. millions of possible objects. Function $f: X \rightarrow (0;1]$ that assigns a "reward" to each object $x \in X$ (the higher $f(x)$, the "better" $x$ is). $f(x)$ is easy to compute for any given $x$; $Z = \sum_X{f(x)} \neq 1$.
I've a got a sampling algorithm (think MCMC) that should sample objects from $X$ proportional to values of $f$, i.e. $P(x) \propto f(x)$. Is there a way to evaluate quality of this sampler using a relatively small number of samples, e.g. a million or so?
In principle, it is possible - for the sake of evaluation - to materialise the entire $X$, compute the normalisation constant $Z$, and then compare the observed distribution $P^\prime(x) = \frac{N(x)}{N}$ to the exact target distribution, e.g. by calculating KL-divergence. The problem is that depending on $f_{max} - f_{min}$, it might take a lot of samples before each $x \in X$ is observed at least once, which usually doesn't play well with distribution distance measures.
Assumptions that may or may not help:


*

*I am actually interested in the samples themselves, as opposed to estimating something about $f$, so some form of (weighted) integration wouldn't suffice on its own.

*I am more interested in high values of $f$, so evaluating sampling quality can be biased towards that region, e.g. using a weighted distribution distance measure (?).

*A heuristic, not strictly rigorous approach that helps to assess sampler's quality "visually" would still serve the purpose (at least one of convincing myself that it's worth further exploration).


My current idea is compare conditional CDFs of values of $f$, e.g. somehow aggregate values of $distance(P(x \mid f(x) > a), P^\prime( \mid f(x) > a)), a \in {0, 0.25, 0.5, 0.75}$ to demonstrate sampling quality in various regions of interest without suffering the problem of unsampled $x$s, and accompany it with comparison of marginal probabilities of individual dimensions to show that it samples diverse objects within each "bin".
 A: Interesting question.
Let's try: $P(x)$ only depends on $f(x)$, $P(x) = g(f(x))$ (in your case $g(f)=f/a)$). Thus, your samples will not be close to the maximum of $f(x)$: the probability to observe a sample with value $f$ is
$$P(f) = \int dx \int df\delta(f-f(x)) g(f(x))dx = \rho(f)g(f)$$
where $\rho(f)=\int \delta(f-f(x)) dx$ is the density of $f$. Your samples will most likely be at the maximum of $\rho(f)g(f)$.
I agree with you that, ideally, looking at $P(x)$ is the correct way of doing it. However, I also agree with you that it may be difficult to observe at least one x, given that x is high dimensional.
In general, the quality of the sampler is quantified by the autocorrelation time of the average you want to compute, because the variance of the average depends on that time. Without a specific average, I don't know any general methodology.
I would try to look at $P(f)$. I would measure $P(f)$ as a function of the number of samples N and see how the KL between $N$ and $2N$ goes to zero with N. The quality of the sampler can then be formulated how many samples are required to achieve a given KL on $\rho(f)$.
