Is there a variant of the Metropolis-Hastings algorithm where the acceptance probabiltiy can depend on all states generated so far?

Question

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$)

Answer 1

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})}$$