4
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ See our posts on the curse of dimensionality. This is the simplest possible example: the relative (hyper)volumes described by these matrices scale as $(\sigma_1/\sigma_2)^d.$ $\endgroup$
    – whuber
    Apr 29, 2021 at 17:20
  • $\begingroup$ @whuber I couldn't find a computation to this effect in the search page you suggested. To clarify, you mean the hypervolume of a Gaussian with $\sigma_1$ vs. the [scaled up version] dominating one with $\sigma_2$? $\endgroup$
    – Student
    Apr 30, 2021 at 13:07

1 Answer 1

3
$\begingroup$

...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$.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.