Finding the target distribution for the Metropolis algorithm

Question

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<q<1$.

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

Answer 1

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