Rejection sampling ineffectiveness in high dimensions

Question

I guess I really have two questions.

First, iv'e seen quoted in a couple of places that the probability of accepting a given sample in a rejection sampling algorithm (sampling from a density $f$ with an envelope $g$) is $1/k$, where $k$ is the constant by which $g$ is multiplied to dominate $f$ (so $k=\sup_x \frac{f\left(x\right)}{g\left(x\right)}$)

What if $f$ is an unnormalized measure? Does this affect the probability of acceptance? It seems so.. but feels like it shouldn't

Second, in these lecture notes, it's stated as an example for the ineffectiveness of rejection sampling in high dimensions that taking two Gaussians of dimension $d$ $$f\left(x\right)=\mathcal{N}\left(0,\sigma_{1}I_d\right)$$ $$g\left(x\right)=\mathcal{N}\left(0,\sigma_{2}I_d\right)$$

with $\sigma_{1}\neq\sigma_{2}$ will cause the acceptance rate to plummet with increasing $d$. Specifically, it says that for $d=1,000$ the acceptance rate will be $\sim \frac{1}{20,000}$. Can someone point out the dependence on $d$ here?

Answer 1

...the probability of accepting a given sample in a rejection sampling algorithm (sampling from a density $f$ with an envelope $g$) is $1/k$, where $k$ is such that $$k\ge\sup_xf(x)/g(x)$$ Whenf $f$ is an unnormalized measure, does this affect the probability of acceptance?

The acceptance-rejection method does not depend on the normalising constants of $f$ and $g$ and can thus be operated with unnormalised versions $\tilde f$ and $\tilde g$, using the associated constant$$\tilde k\ge\sup_x\tilde f(x)/\tilde g(x)$$This does not impact the efficiency of the algorithm in that the probability of acceptance remains equal to $1/k$ and not $1/\tilde k$. The reason for this invariance is that \begin{align} \mathbb P_{U\sim \mathcal U(0,1),X\sim g}\left(U\le \frac{\tilde f(X)}{\tilde k\tilde g(X)}\right) &= \mathbb P_{U\sim \mathcal U(0,1),X\sim g}\left(U\le \frac{f(x)}{k g(X)}\right) \\ &= \frac{1}{k} \end{align} The fundamental reason for this invariance is that one does not generate from $\tilde g$ but always from $g$: simulation [when possible] over-rides the missing constant.

Can someone point out the dependence on $d$?

Take a simple case when $$f(\mathbf x)=\prod_{i=1}^d f_0(x_i)$$ and $$g(\mathbf x)=\prod_{i=1}^d g_0(x_i)$$with $$\sup_x \dfrac{f_0(x)}{g_0(x)}=k_0$$Then $$\sup_\mathbf x \dfrac{f(\mathbf x)}{g(\mathbf x)}=k_0^d=k$$ explains why the acceptance probability decreases as a power of $d$.