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

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

• @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. Dec 2, 2022 at 14:31
• @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/… Dec 17, 2022 at 21:29
• @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? Dec 18, 2022 at 11:20
• @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? Dec 18, 2022 at 14:15
• @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})$? Dec 18, 2022 at 14:17

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.)
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})}$$
• 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. Dec 18, 2022 at 18:37
• 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\;)$. Dec 18, 2022 at 18:39