2
$\begingroup$

Can we generate samples by the Metropolis-Hastings algorithm with target density $p(x)$ and proposal kernel density $q(x,y)$ such that the samples satisfy a certain constraint?

Take the simple example where the sample space is $[0,1)^2$. Can we generate samples such that the sample points have a given minimal distance?

I think the only way to do this is ensuring that the proposals satisfy this constraint, but please let me know if I'm wrong. Since this means we need ensure that samples distributed according to $q(x,\;\cdot\;)$ satisfy this constraint, I think the question boils down to asking whether we can sample from any distribution and ensure that the generated samples satisfy the constraint (e.g. have a certain minimal distance).

If that's correct at all, how should we do that? I think the most simple approach would be to generate each sample in a loop and only accepting it, if the constraint is satisfied. But maybe there is a better option.

$\endgroup$

1 Answer 1

1
$\begingroup$

This constraint is contradictory with the aim of generating marginal realisations from the target density. Under stationarity, Metropolis-Hastings produces (Markov) dependent simulations such that each term in the sequence is distributed from $p(\cdot)$. It does not aim at a specified joint distribution of the chain (even though its joint distribution obviously exists by the very construction of the algorithm).

To achieve a minimal distance between realisations is not achievable this way since the minimal distance constraint is expressed in terms of the joint distribution of the chain. This seems to require low discrepancy sequences used in quasi-Monte Carlo Metropolis algorithms such as Owen's (2005).

$\endgroup$
6
  • $\begingroup$ Thank you for your answer. Could you explain why the constraint is contradictionary? I mean, if we ensure that the proposal satisfies the constraint, shouldn't we still be able to run the MH algorithm and obtain samples which are distributed according to the target density? The MH algorithm is independent of the chosen proposal kernel isn't it? $\endgroup$
    – 0xbadf00d
    Nov 11, 2022 at 18:54
  • $\begingroup$ Maybe we can do something weaker: (1) Fix $k,h\in\mathbb N$, generate $k$ proposal candidates and choose the one which has the maximimum minimum distance to the last $h$ generated samples. (2) Another idea would be to only "locally" trying to ensure a certain distance between samples. $\endgroup$
    – 0xbadf00d
    Dec 17, 2022 at 23:03
  • $\begingroup$ To give some motivation: I would like that I end up with samples which have a bluse noise characteristic as described, for example, here: abdallagafar.com/publications/dyadic-nets $\endgroup$
    – 0xbadf00d
    Dec 17, 2022 at 23:03
  • $\begingroup$ Solution (1) could be theoretically validated to ensure stationarity of the intended target but the implementation would likely be hellish since the reverse / backward move (from iteration $t$ to iteration $t-1$) would likewise imply generating $k-1$ proposed values with a smaller minimum distance than the one resulting from the forward move. $\endgroup$
    – Xi'an
    Dec 18, 2022 at 10:10
  • $\begingroup$ You mean that each proposal was a vector $(x_1,\ldots,x_k)$ such that the distance of the $x_i$ to each other is as large as possible? Or did you denote samples of the chain at iteration $k$ by $(x_1,\ldots,x_k)$? Efficiency is not my main goal at this point, but the blue noise characteristic mentioend above. $\endgroup$
    – 0xbadf00d
    Dec 18, 2022 at 11:38

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.