# Finding the target distribution for the Metropolis algorithm

Let's consider the Markov chain $$X_n$$ defined on $$\mathbf{X} = \{0,1,2...,n \}$$, generated according to Metropolis algorithm. Let $$X_0 := 0$$ be a starting state. The accepting rule is as follows:

if $$X_n = x$$, then:
$$\text{ }$$ let $$y := \min(x+1, n)$$ with probability $$1/2$$ or $$y := \max(x-1, 0)$$ with probability $$1/2$$
$$\text{ }$$ if $$y \le x$$ then: $$X_{n+1} := y$$
$$\text{ }$$ if $$y > x$$ then: $$X_{n+1} := y$$ with probability $$q$$ and $$X_{n+1} := x$$ with probability $$1-q$$
where $$0.

We want to find the limiting probability distribution $$\pi(x) = \lim_{n \to \infty} P(X_n = x).$$

Therefore, as far as I understand we have to find the target distribution of this algorithm. Let's denote it $$\pi(x)$$.

Here are my attemps.

Given proposal value $$y$$ and the previous value $$x$$, we accept $$y$$ with probability $$P(y \le x) + P(y> x) \frac{1}{2} = \frac{1}{2} + \frac{1}{2}q$$ and reject with probability $$\frac{1}{2}(1-q)$$.

In general acceptance ratio is equal to: $$\min(1, \frac{\pi(y)}{\pi(x)}).$$ Therefore we know that $$\frac{\pi(y)}{\pi(x)} = \frac{1}{2} + \frac{1}{2}q.$$

I got stuck and I do not know how to proceed. Any help much appreciated.

I implemented the algorithm in R for n=10. But I have no idea what probability distribution it is.

N<-2000
res <- numeric(N)
res[1] <- 0
n <- 10
q <- 0.8
for(i in 2:N){

x <- res[i-1]
y <- sample( c(min(x+1, n),  max(x-1,0)), prob=c(0.5,0.5), size=1 )

if (y <= x) res[i] <- y else{
u <- runif(1)
res[i] <- ifelse(u<q, y, x)
}
}

hist(res[100:2000])


• is this home work? then self-study tag to be applied – Aksakal Jun 8 '20 at 14:36
• I did not know. Sorry – Elizabeth_Banks Jun 8 '20 at 14:45

I think your probability of accpetation should depend on both $$x$$ and $$y$$. Let's denote it $$\pi(x, y)$$ (probability of accepting proposal state $$y$$ if current state is $$x$$).

$$\pi(x, y) = \left\{ \begin{array}[ccc] \text{}1 & \text{if} & y \leq x \\ q & \text{if} & y = x + 1 \\ \end{array} \right.$$

As the proposal distribution is symmetric (probability of proposing $$y$$ from $$x$$ is the same as the probability of proposing $$x$$ from $$y$$), this acceptance probability satisfies $$\pi(x, y) = \min(1, \frac{f(y)}{f(x)})$$ where $$f$$ is the target distribution.

In particular, applying this to $$y = x + 1$$ for $$x\leq n-1$$ we get that $$\frac{f(x+1)}{f(x)} = q$$. Thus $$f(1) = q\times f(0), f(2) = q^2\times f(0), \cdots, f(n) = q^n\times f(0)$$. Now, in order to have $$\sum_{i= 0 }^{n}f(i) = 1$$ we need that $$f(0) = \frac{1 - q}{1 - q^{n + 1}}$$.

So, for any $$i \in \{1, ..., n\}$$,

$$f(i) = \frac{1 - q}{1 - q^{n+1}} q^i$$

And this tends to a particular well known discrete distribution when $$n$$ goes to $$\infty$$...

• Oh, I see :) Thanks so much! I would never came up with that – Elizabeth_Banks Jun 8 '20 at 15:20