$$

Suppose we have two (unnormalized) density functions $p(x)$ and $q(x)$ that can be easily evaluated on a point, and suppose that we’re able to get sample from $q$:

$$\mathrm{Pr}[\mathit{X}=x]\propto q(x).$$

Then, assuming that $p$ is not too much more concentrated than $q$ at any point, we can get samples from $p$ by sampling from $q$ then “tweaking the probabilities” appropriately.

Algorithm

Repeatedly:

1. sample $x$ from $q$;
2. with probability $c\frac{p(x)}{q(x)}$, return $x$;
3. otherwise, “reject” $x$ and continue.

Analysis

As long as the “probability” in step 2 is never greater than $1$, we’ll get value $x$ with probability

$$\propto q(x)\times \left(c\frac{p(x)}{q(x)}\right)=cp(x),$$

so this has the right distribution. And it’s enough to set $c:=\underset{x}{min}\frac{q(x)}{p(x)}$.

But the issue is that the smaller we set $c$, the longer the algorithm might take until it accepts for the first time. Indeed, assuming that $p$ and $q$ are actually probabilities (they sum to $1$), the probability of accepting at any iteration of the loop is

$$\sum _{x}q(x)\times \left(c\frac{p(x)}{q(x)}\right)=c\sum _{x}p(x)=c,$$

so it would take $1/c=\underset{x}{max}\frac{p(x)}{q(x)}$ iterations on average until the algorithm succeeds. This quantity $\underset{x}{max}\frac{p(x)}{q(x)}$ is the max-divergence between $p$ and $q$ (see Power entropies and divergences).

Example: sampling from DNFs

Say we want to sample from the set of satisfying assignments of a DNF formula

$$f=T_1\vee \cdots \vee T_m.$$

It’s easy to sample uniformly over the assignments $T_i^{-1}(1)$ that satisfy a particular term $T_i$ of the formula, since they form a hypercube. But the overlaps between the hypercubes $T_i^{-1}(1)$ for different $i$ make it nontrivial to sample uniformly over the entirety of $f^{-1}(1)$.

That said, we can still easily sample according to the following distribution, which is somewhat close to the desired distribution:

• pick a term $T_i$ at random according to how large $|T_i^{-1}(1)|$ is,
• then pick a uniformly random $x$ within $T_i^{-1}(1)$.

This would be perfect if the hypercubes $T_i^{-1}(1)$ were disjoint, but in general, assignments $x$ that satisfy many terms have a higher chance of being drawn: we get density

$$q(x):=\mathrm{\#}\left\{i\right|T_i(x)\},$$

whereas the distribution we wish for is just

$$p(x):=\mathbb{1}[T_1(x)\vee \cdots \vee T_n(x)].$$

The ratio $p(x)/q(x)$ is always at most $1$, so we can just set $c:=1$, and each iteration has at least a

$$\frac{p(x)}{q(x)}\ge \frac{1}{m}$$

chance of accepting $x$, so it takes $\le m$ iterations on average.

#to-write swap $p$ and $q$ and capitalize