7
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ 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). $\endgroup$
    – lacerbi
    Commented Jul 24, 2016 at 19:49
  • $\begingroup$ @lacerbi thanks. I know that since I have CDF I do not need it, it's just curiosity. Anything besides the cost? $\endgroup$
    – Tim
    Commented Jul 24, 2016 at 19:55
  • $\begingroup$ @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. $\endgroup$
    – Xi'an
    Commented Jul 27, 2016 at 6:21
  • $\begingroup$ @Xi'an yes this could be easily extended to Gibbs, M-H etc. $\endgroup$
    – Tim
    Commented Jul 27, 2016 at 7:00

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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). $\endgroup$
    – Juho Kokkala
    Commented Aug 12, 2016 at 11:39
  • $\begingroup$ @JuhoKokkala +/- approach also treats boundary cases evenly. $\endgroup$
    – Tim
    Commented Aug 12, 2016 at 13:10

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.