0
$\begingroup$

There is a vast wealth of literature on (approximate) sampling from computationally difficult distributions. Generally, the techniques I have seen assume that we only have queries to a proportional version of the distribution. That is, if we wish to sample from $p(x)$, we can query $\pi(x)$, where $p(x) = \frac{\pi(x)}{\int \pi(x) dx}$. In applications, this is often sensible (for instance, we can usually compute the proportional version of a Bayesian posterior, but not its normalizing constant).

However, are there cases where sampling is difficult even when we have exact query access to the distribution itself? (I.e., we know the normalizing constant $\int \pi(x) dx$). Or would there be some general method to allow us to accurately sample in that case.

And broadly, is there literature on this topic? I've seen endless papers about sampling from unnormalized distributions, but rarely seen this case mentioned (making me wonder if there's some easy way to sample from a distribution as long as you know the normalizing constant exactly).

$\endgroup$
3
  • $\begingroup$ So is the basic idea that access to the normalizing constants may not by itself make sampling any easier, but most techniques assume proportional queries because that's what applications tend to require? (e.g. bayesian posteriors, etc). I.e. proportional queries are a constraint prompted by the applications we use, not because they are the root of the underlying sampling challenge? $\endgroup$
    – Ziddletwix
    Commented May 11, 2020 at 14:23
  • $\begingroup$ Great, thanks. I was curious because some techniques, like sequential importance sampling and particle filter variants (or the related population annealing in physics), appeared to spend much of their attention on handling normalizing constants, but I might be misunderstanding their goals. $\endgroup$
    – Ziddletwix
    Commented May 11, 2020 at 14:34
  • $\begingroup$ The g-and-k distribution would be one example where the pdf can be computed with arbitrary numerical precision, including the constant. It however can be easily simulated... This ruins the example I am afraid! $\endgroup$
    – Xi'an
    Commented May 11, 2020 at 14:53

1 Answer 1

1
$\begingroup$

This is a legitimate question but, on a general basis, getting the normalising constant does not help. For instance, since $$\int_0^\infty \dfrac{x^{\mu-1}+x^{\nu-1}}{(1+x)^{\mu+\nu}}\,\text{d}x=2 B(\mu,\nu) = \dfrac{2\Gamma(\mu+\nu)}{\Gamma(\mu)\Gamma(\nu)}\qquad\mu,\nu>0$$the probability density $$p(x)=\dfrac{\Gamma(\mu)\Gamma(\nu)}{2\Gamma(\mu+\nu)}\,\dfrac{x^{\mu-1}+x^{\nu-1}}{(1+x)^{\mu+\nu}}\qquad 0<x<\infty$$enjoys a known normalising constant. But this does not help me in simulating it, the more because

  1. the Gamma function $\Gamma(\cdot)$ is itself only available through numerical approximations
  2. the associated cdf has no closed-form expression, unless one considers the incomplete Gamma function to be "known".

The only case I can think of where the normalising constant helps is when considering the inverse cdf approach: $X=F_X^{-1}(U)$ is a realisation from the distribution with cdf $$F_X:x \mapsto \int_{-\infty}^x p_X(x)\,\text{d}x$$ However if $p_X$ is known up to a normalising constant and $F_X(x)$ is available for all $x$'s, then one can derive this normalising constant from $F_X(\infty)=1$.

Otherwise, most simulation methods manage very well without the constant (and often produce an estimate of the constant as a by-product). For instance,

  1. accept-reject algorithms work well without the constant, which can be estimated from the acceptance rate;
  2. importance sampling methods, incl. sequential Monte Carlo methods, operate by weighting and resampling, which does not require normalising constants (unless unbiasedness is required);
  3. MCMC algorithms such as Metropolis-Hastings, Gibbs sampling, Langevin algorithms, HMC, all work without the normalising constant.
$\endgroup$
1
  • $\begingroup$ Thank you for the detailed response! This is quite helpful. Two quick follow-ups. 1. Is your example a common, named distribution? It looks something like a Beta or "Beta Prime" distribution, but isn't quite? And 2. This one-dimensional example appears unimodal, so I assume that sampling from it using MCMC or an equivalent would straightforward? I know the point of the example was to address the access to the normalizing constant, I just wanted to confirm my intuition that other methods would make this fairly easy. $\endgroup$
    – Ziddletwix
    Commented May 13, 2020 at 12:55

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.