2
$\begingroup$

If we run the Metropolis-Hastings algorithm for a target distribution $\mu$ with proposals from a quasi-Monte Carlo sequence $(y_n)_{n\in\mathbb N}$ (such as a Sobol sequence) and the generated chain is denoted by $(X_n)_{n\in\mathbb N_0}$, will $$\frac1n\sum_{i=0}^{n-1}f(X_i)\xrightarrow{n\to\infty}\int f\:{\rm d}\mu\tag1$$ still hold?

The obvious question is: How do we need to compute the acceptance probability $\alpha$? Since the proposals are non-random, they don't have a density with respect to the reference measure with respect to which $\mu$ has a density $p$. So, do we simply use $$\alpha(x,y)=\min\left(1,\frac{p(y)}{p(x)}\right)\tag2$$ as in the "random walk Metropolis-Hastings algorithm" (where the proposal density is assumed to be symmetric)?

I was able to find two works on this subject:

  1. In his thesis MARKOV CHAIN MONTE CARLO ALGORITHMS USING COMPLETELY UNIFORMLY DISTRIBUTED DRIVING SEQUENCES Tribble proves consistency of the Metropolis-Hastings estimator when the input sequence of uniformly distributed random numbers is replaced by a "completely uniformly distributed" sequence. However, his result needs is established only under the assumption of a finite state space.
  2. Tribble also published a paper A quasi-Monte Carlo Metropolis algorithm together with Owen. I think they described what they intend to do in equations $(4)$ and $(5)$, but I honestly don't get what they do and I don't find an answer to the question I've raised above about the definition of $\alpha$. What would their $\Psi_i$ look like, when the quasi-Monte Carlo sequence is, say, a Sobol sequence?
$\endgroup$
1
  • $\begingroup$ from what I remember of QMC, QMC properties degenerate very fast with the number of dimensions.(So typically one would use some sort of PCA to decide which dimensions to prioritise) see eg people.maths.ox.ac.uk/gilesm/mc/mc/lec5.pdf $\endgroup$
    – seanv507
    Commented Nov 21, 2022 at 10:18

1 Answer 1

2
$\begingroup$

The obvious question is: How do we need to compute the acceptance probability 𝛼?

Or the different question is

"Why do we need to compute the acceptance probability 𝛼?"

If your point is to compute an integral, then you don't need acceptance-rejection sampling.*

If your point is to generate some random sample (e.g for testing some statistical method), then I don't think that quasi-Monte Carlo methods give a random sample with properties as you expect. For example, when generating samples from a uniform distribution with this method, then there won't be any acceptance-rejection going on and your final sample is the same as the sequence that you used as input.


A use for quasi methods, might be to make the chain easier to walk around the space without revisiting too much the same place.

That is I think also the point of Metropolis Hastings, to automatically generate more proposals in areas with higher density.

If you replace the proposal from the MH algorithm with proposals from some pseudo-random number generator, then there is little point to applying the acceptance-rejection rules from the MH algorithm.


A related technique might be described here Generate a point cloud distributed according to a Boltzmann-Gibbs distribution with prescribed marginals , which is about generating quasi-random distributions according to some gradient.

For integrating some function of a variable $X$, it might be better to have a higher density of sampled points in the region where the function is larger. Here is an example of generating such a sample of points

example toy model

However, if the way to get these points is being done by rejecting points, then one doesn't really gain a lot.

*On the other hand, possibly when computing the function $f$ is costly, then it might be beneficial to put a extra work in generating an efficient sample $X$ to compute $E[f(X)]$.

$\endgroup$
11
  • $\begingroup$ Thank you for your answer. "then there is little point to applying the acceptance-rejection rules from the MH algorithm". The point is that if we don't use acceptance-rejection, then we use every sample from the proposal sequence, but those samples are not distributed according to the target density $p$. $\endgroup$
    – 0xbadf00d
    Commented Jun 18, 2023 at 11:03
  • $\begingroup$ How is my other question you've quoted (stats.stackexchange.com/questions/600929/…) related to the problem here? When, say, we want to estimate an integral $\int pf$ with target density $p$? $\endgroup$
    – 0xbadf00d
    Commented Jun 18, 2023 at 11:06
  • $\begingroup$ And what do you think about the thesis and paper I've linked above? $\endgroup$
    – 0xbadf00d
    Commented Jun 18, 2023 at 11:09
  • $\begingroup$ @0xbadf00d ah, that's interesting, I didn't notice that the question that I quoted was yours. $\endgroup$ Commented Jun 18, 2023 at 12:40
  • 1
    $\begingroup$ @0xbadf00d I took a look but not enough to comment on it yet. $\endgroup$ Commented Jun 18, 2023 at 15:02

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.