# Approximate Metropolis algorithm - does it make sense?

Some time ago Xi'an asked What is the equivalent for cdfs of MCMC for pdfs? The naive answer would be to use "approximate" Metropolis algorithm in form

Given $X^{(t)} = x^{(t)}$
1. generate $Y \sim q(y|x^{(t)})$
2. take $$X^{(t+1)} = \begin{cases} Y & \text{ with probability } & \min\left( \frac{F(Y+\varepsilon) - F(Y-\varepsilon)}{F(x^{(t)}+\varepsilon) - F(x^{(t)}-\varepsilon)} , 1 \right)\\ x^{(t)} & \text{ otherwise.} \end{cases}$$

where $F$ is a target CDF and $\varepsilon$ is some small constant. This enables us to use Metropolis algorithm with CDF's.

The question is: is there any reason why this may actually be a bad idea?

• Have you seen my answer to Xi'an question? I think we are proposing a similar thing (you don't even need to use Metropolis, in fact, since you have the CDF). The problems are listed at the end of my answer (the cost of evaluating the approximation is exponential in the number of dimensions). – lacerbi Jul 24 '16 at 19:49
• @lacerbi thanks. I know that since I have CDF I do not need it, it's just curiosity. Anything besides the cost? – Tim Jul 24 '16 at 19:55
• @Tim: thank you for the proposal. A potential solution when $X$ is multidimensional is to proceed by Gibbs sampling and take $\epsilon$-derivatives one direction at a time. – Xi'an Jul 27 '16 at 6:21
• @Xi'an yes this could be easily extended to Gibbs, M-H etc. – Tim Jul 27 '16 at 7:00

No, I don't see why this is a bad idea. It seems to me that it is a natural (and interesting) extension to draw samples from a CDF.

However, I believe that the acceptance should be

$$\min\left( \frac{F(Y+\varepsilon) - F(Y)}{F(x^{(t)}+\varepsilon) - F(x^{(t)})} , 1 \right)$$

because by definition

$$\lim_{\varepsilon\rightarrow 0}\frac{F(x + \varepsilon) - F(x)}{\varepsilon} = PDF(x)$$

Nevertheless, it is the first time I see this. With a strong case for sampling from a non-trivial CDF, this could become an interesting publication.

• The acceptance criterion proposed by OP is motivated by the central difference expression of the derivative as $\lim_{\epsilon\rightarrow 0} (F(x+\epsilon) - F(x-\epsilon)) / (2\,\epsilon)$, see for example math.stackexchange.com/a/888280/104295. (I have no idea whether there are some reason to believe either of these approximations to work better in this case). – Juho Kokkala Aug 12 '16 at 11:39
• @JuhoKokkala +/- approach also treats boundary cases evenly. – Tim Aug 12 '16 at 13:10