MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Hi, I hope this isn't too basic. We were working on a simulation using a Monte Carlo Within Metropolis algorithm and noticed that the whole thing could be expressed in the form below and simplified dramatically.

I've given a detailed description, but for a quick informal idea: simulate a random variable $X$ by choosing a suitable event $E$ in some larger probability space and draw from $X$ conditioned on $E$, then hold the chain in state $x$ for a geometric number of steps with mean $\left(\mathbb P\left(E | X=x \right)\right)^{-1}$.

I've tried to find this approach in the literature, with no luck, but I'm not an expert in this area. It would be really helpful to know if anyone has heard of anything like it.

Let $\left(\Omega,\mathscr F, \mathbb P\right)$ be a probability space. We are interested in the distribution of some $\mathscr F$-measurable $X:\Omega\to \mathcal X$ which generates a $\sigma$-algebra $\mathscr G \subset \mathscr F$.

The space is too complicated to calculate any probabillties directly, but we can simulate a draws from $\mathbb P$ under two different forms of conditioning.

1$\qquad$ Given a value of $X$ we may draw from the distribution of $\mathbb P$ conditioned on $\mathscr G$.

2$\qquad$There is an event $E\in\mathscr F$ for which we can simulate the conditional distribution of $\mathbb P$ conditioned on $E$.

Under these conditions we can construct a Markov chain $X_i\in\mathcal X$ with stationary distribution $\mathbb P$ by simulating a draw $Y$ from $\mathbb P$ conditioned on $\mathscr G$ with $\left[X = X_i\right]$ and choosing $X_{i+1}$ as follows.

$\circ\qquad$If $Y\notin E$ set $X_{i+1} = X_i$.

$\circ\qquad$If $Y\in E$ draw $X_{i+1}$ independently from $\mathbb P$ conditioned on the event $E$.

It is easy to check that for $x_1\neq x_2$ the probability that $x_1\mapsto x_2$ is $\mathbb P\left(E|X=x_1\right) \mathbb P\left(X\in\mathbf d x_2 | E\right)$ and so detailed balance is satisfied.

We can also show that if $X_0$ is drawn from $\mathbb P$ conditioned on $E$ and $p$ and $q$ are such that $\mathbb P\left(\mathbb P \left(E|\mathscr G\right)\leq p\right)\leq q$ then the total variation distance between the distributions of $X$ and $X_n$ is at most $q+(1-p)^n$.

My question is, does a technique like this appear in the literature and if so is there a know rate of convergence similar or tighter to the one above?

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.