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 at 14:36
  • $\begingroup$ I did not know. Sorry $\endgroup$ – Elizabeth_Banks Jun 8 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$...

| cite | improve this answer | |
  • $\begingroup$ Oh, I see :) Thanks so much! I would never came up with that $\endgroup$ – Elizabeth_Banks Jun 8 at 15:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.