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.

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)


enter image description here

  • 2
    $\begingroup$ is this home work? then self-study tag to be applied $\endgroup$
    – Aksakal
    Jun 8, 2020 at 14:36
  • $\begingroup$ I did not know. Sorry $\endgroup$ Jun 8, 2020 at 14:45

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

  • $\begingroup$ Oh, I see :) Thanks so much! I would never came up with that $\endgroup$ Jun 8, 2020 at 15:20

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.