2
$\begingroup$

I wasn't able to find anything on google, but is there a variant of the Metroplis-Hastings algorithm where the acceptance probability (not the proposal kernel) in the $i$th iteration might depend on the stats $X_0,\ldots,X_{i-1}$ generated so far?

I guess the problem is that the resulting process is not a time-homogeneous Markov chain anymore. However, it might still obey a law of large numbers ...

In order to motivate what I would like to do: I would like to generate a fixed amount of candidate proposals in each iteration (like in Multiple-Try Metropolis-Hastings) and choose among the candidates the proposal which has the largest distance to all of the already generated states. Would this still tend (in a suitable sense) to the target distribution?

EDIT: Let me try to formalize this: Let

  • $(E,\mathcal E,\lambda)$ be a measure space;
  • $p:E\to[0,\infty)$ be $\mathcal E$ measurable with $$c:=\lambda p\in(0,\infty)$$ and $$\mu:=\frac{p\lambda}c;$$
  • $k\in\mathbb N$;
  • $q:E^k\times E\to[0,\infty)$ be $\mathcal E^{\otimes k}\otimes\mathcal E$-measurable with $$c_x:=\lambda q(x,\;\cdot\;)\in(0,\infty)\;\;\;\text{for all }x\in E^k$$ and $$Q(x,\;\cdot\;):=\frac{q(x,\;\cdot\;)\lambda}{c_x}\;\;\;\text{for }x\in E^k.$$

The idea would be that we are actually want to obtain a Markov chain $(X_n)_{n\in\mathbb N_0}$ with stationary distribution $\mu$ by running the Metropolis-Hastings algorithm with proposal kernel $Q$. By definition, $Q$ depends on the last $k$ states.

In order to actually apply this, we need to run the Metropolis-Hastings algorithm on $(E^k,\mathcal E^{\otimes k})$. I guess the target distribution should be $$\tilde \mu:=\tilde p\lambda^{\otimes k},$$ where $$\tilde p(x):=\prod_{i=1}^kp(x_i)\;\;\;\text{for }x\in E^k.$$ However, I Have no idea how I need to define the proposal kernel $\tilde Q$ on $(E^k,\mathcal E^{\otimes k})$, since it should intuitively be given by $$\tilde Q(x,B_1\times\cdots\times B_k)=\prod_{i=1}^{k-1}\delta_{x_i}(B_i)Q(x_1,\ldots,x_k,B_k);$$ which doesn't work since this proposal kernel doesn't admit a density with respect to $\lambda^{\otimes k}$.

(maybe we should replace the domain of $q$ by $\bigcup_{i=1}^kE_i\times E$)

$\endgroup$
11
  • $\begingroup$ @Xi'an Thank you, I will check that out. I don't necessarily need a Markov chain Monte Carlo algorithm. If a suitable estimator can be formed out of the $X_1,\ldots,X_i$, that is all I need. $\endgroup$
    – 0xbadf00d
    Commented Dec 2, 2022 at 14:31
  • $\begingroup$ @Xi'an Is there a variant of the Metropolis-Hastings algorithm where the proposal kernel can depend not only on the current state, but the past $k$ states (where $k$ is fixed apriori or maybe can even be adapted)? Something like what's being described here: academia.edu/16453972/… $\endgroup$
    – 0xbadf00d
    Commented Dec 17, 2022 at 21:29
  • $\begingroup$ @Xi'an Thank you for your comment. How do the proposal kernel, acceptance function, etc. changed if we use an order $k$ Markov chain? Is there any reference considering that? $\endgroup$
    – 0xbadf00d
    Commented Dec 18, 2022 at 11:20
  • $\begingroup$ @Xi'an Please let me try to understand this: My definition is that $(X_n)_{n\in\mathbb N_0}$ is a Markov chain of order $p\in\mathbb N$ iff $$X^{(p)}_n:=\left(X_n,\ldots,X_{n+p-1}\right)\;\;\;\text{for }n\in\mathbb N_0$$ is a Markov chain. Now, you are considering $$Y_n:=\left(X_{pn},\ldots,X_{p(n+1)-1}\right)=X^{(p)}_{pn}\;\;\;\text{for }n\in\mathbb N_0.$$ I guess we easily see that if $\kappa_p$ is the transition kernel of $\left(X^{(p)}_n\right)_{n\in\mathbb N_0}$, then $\kappa_p^p$ is the transition kernel of $(Y_n)_{n\in\mathbb N_0}$, right? $\endgroup$
    – 0xbadf00d
    Commented Dec 18, 2022 at 14:15
  • $\begingroup$ @Xi'an Assuming everything above is correct: (a) Why do you consider $(Y_n)_{n\in\mathbb N_0}$ instead of $\left(X^{(p)}_n\right)_{n\in\mathbb N_0}$? (b) I still don't see how you obtain a variant of the Metropolis-Hastings algorithm, where the generated chain has order $p$, from these considerations ... Is the generated chain $(E^p,\mathcal E^{\otimes p})$-valued? Do you simply choose a proposal kernel on $(E^p,\mathcal E^{\otimes p})$? $\endgroup$
    – 0xbadf00d
    Commented Dec 18, 2022 at 14:17

1 Answer 1

1
$\begingroup$

If the dependence-on-the-past horizon, $k$, is fixed, a proposal based on the $k$ previous values of the sequence $(X_t)_t$ defines an order $k$ Markov chain, i.e. $$\forall t\in\mathbb Z,\quad\mathbb P(X_t\in A|X_{t-1},\ldots,X_1)=\mathbb P(X_t\in A|X_{t-1},\ldots,X_{t-k})$$ An order $1$ Markov chain $(Y_t)_t$ is then made of the vector $$\forall t\in\mathbb Z,\quad Y_t=(X_{kt+1},\ldots,X_{kt+k})$$ which is made of $k$ consecutive steps of the original Markov chain, since the components of $Y_t$ only depend on the components of $Y_{t-1}$ and of the components of $Y_t$ with lesser indices. This reformulation means that a regular (order $1$) Markov $(Y_t)_t$ can be constructed via a standard MCMC algorithm, provided a joint target distribution $\tilde\pi(y)$, $y\in\mathfrak X^k$,with all marginals equal to the original target $\pi(x)$, $x\in\mathfrak X$, is defined. (For instance, it could be a copula.)

Practical implementation may however prove delicate / hard to calibrate though and I am not aware of a generic version (but H. Tjemeland may have proposed something similar in his multiproposal scheme).

As an illustration, consider a proposal at iteration $t$ with density $$q(z|x_{t-1},\ldots,x_{t-k})$$ and a proposed move from $Y_t$ to $Y_{t+1}$ using the proposals $$\begin{align} q(z|&x_{kt+k},\ldots,x_{kt+1})\\ &\vdots\\ q(z|&x_{k(t+1)+k-1},\ldots,x_{k(t+1)}) \end{align}$$ or $$\tilde q(y_{t+1}|y_t)=\prod_{i=1}^n q(x_{k(t+1)+i-1}|x_{k(t+1)+i-2},\ldots,x_{kt+i})$$ Let $\tilde\pi(y)$, $y\in\mathfrak X^k$,with all marginals equal to the original target $\pi(x)$, $x\in\mathfrak X$, i.e. $$\pi(x_i)=\int_{\mathfrak X^{k-1}} \tilde\pi(y)\,\text dy_{-i}$$ A valid Metropolis-Hastings scheme can then be based on the ratio $$1\wedge\dfrac{\tilde q(y_{t}|y_{t+1})}{\tilde q(y_{t+1}|y_t)} \times\dfrac{\tilde\pi(y_t)}{\tilde\pi(y_{t-1})}$$

$\endgroup$
2
  • $\begingroup$ Thank you for the edit. When you say "proposal with density $q(z|x_{t-1},\ldots,x_{t-k})$, your proposal is a single value (not a $k$-dimensional vector), right? And in your move from $Y_t$ to $Y_{t+1}$, $Y_t$ is the current state, right? I guess I simply don't understand your notation, but when you write "using the proposals \begin{align} q(z|&x_{kt+k},\ldots,x_{kt+1})\\ &\vdots\\ q(z|&x_{k(t+1)+k-1},\ldots,x_{k(t+1)}) \end{align} I have no idea what you mean. $\endgroup$
    – 0xbadf00d
    Commented Dec 18, 2022 at 18:37
  • $\begingroup$ Please write this differently: If $x_1,\ldots,x_i$ are the generated samples so far, then the proposal $Y$ should be an $E$-valued random variable taken from $Q((x_{i-k+1},\ldots,x_i),\;\cdot\;)$. $\endgroup$
    – 0xbadf00d
    Commented Dec 18, 2022 at 18:39

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.