Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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

I'm currently reading the article "Exact and computationally efficient likelihood-based estimation for discretely observed diffusion processes" by Beskos, Papaspiliopoulos, Roberts and Fearnhead. I'm not sure if the setup described below is necessary to understand and answer the question, so i've stated my question in the bottom two lines. Anyway, the setup is the following:

We are considering solutions (diffusion processes) to one-dimensional time-homogeneous SDE's with unit diffusion coeffcient, i.e. $$ d X_t=\alpha(X_s)d s+ d W_s, $$ where $(W_t)_{t\geq 0}$ is a Wiener process. Then they introduce the space $C=C([0,t],\mathbb{R})$ of continuous functions from $[0,t]$ into $\mathbb{R}$ equipped with the coordinate $\sigma$-field. Let $(X_t)_{t\geq 0}$ be a solution to the SDE above with $X_0=x$, and since we have unit diffusion we might assume that $(X_t)$ is the canonical process on $C([0,\infty),\mathbb{R})$, i.e. $X_t(\omega)=\omega(t)$ for $\omega\in C([0,\infty),\mathbb{R})$. Let $x,y\in\mathbb{R}$ and $t>0$. Then we let $\mathbb{Q}^{(t,x,y)}$ be the distribution on $C$ of $(X_s)_{0\leq s\leq t}$ conditioned on $X_t=y$. Furthermore we let $\mathbb{W}^{(t,x,y)}$ denote the distribution of a Brownian bridge from $x$ to $y$ over $[0,t]$. Then one can show that

$$ \frac{d\, \mathbb{Q}^{(t,x,y)}}{d\,\mathbb{W}^{(t,x,y)}}(\omega)=K\cdot\exp\left(-r(\omega)\int_0^t\varphi(\omega_s)d s\right),\quad \omega\in C, $$ for some functions $r$ and $\varphi$. Now they propose a method to sample from the distribution $\mathbb{Q}^{(t,x,y)}$ which, if I read it correctly, is something like:

  • Simulate a path $\omega$ from $\mathbb{W}^{(t,x,y)}$ (I know this is not possible in practice)
  • Accept $\omega$ with probability $\exp\left(-r(\omega)\int_0^t\varphi(\omega_s)d s\right)$

I know of the concept of Acceptance-Rejection sampling, but I can't see how this should be Acceptance-Rejection.

I guess my question in general is: If a probability measure $Q$ has a density $f$ with respect to another probability measure $P$, i.e. $\frac{d Q}{d P}=f$, then how do we sample from $Q$ given that we know $f$ and can sample from $P$?

share|cite|improve this question
up vote 2 down vote accepted

I think I have found a solution to the general problem. Please correct me if I am doing anything wrong. Suppose $(\Omega,\mathcal{F})$ is measureable space and $P$ and $Q$ are two probability measures on it, such that $$ \frac{d Q}{d P}(\omega)=K\cdot h(\omega),\quad \omega\in\Omega. $$ Let $P(\text{Accept}\mid \omega)=h(\omega)$ be the probability of accepting an outcome $\omega\in\Omega$, and let $X$ be a random variable with distribution $P$. Then $X\mid \text{Accept}$ has distribution $Q$.

Proof: For $B\in\mathcal{F}$ we have $$ P(X\in B\mid \text{Accept})=\frac{P(X\in B,\text{Accept})}{P(\text{Accept})}=\frac{1}{P(\text{Accept})}\int_B P(\text{Accept}\mid X=\omega) \,P_X(d\omega). $$ Now using that $P_X=P$ and that $h(\omega)=\frac{1}{K}\frac{dQ}{dP}(\omega)$ we get that (here $\tilde{K}=\frac{1}{K\cdot P(\text{Accept})}$) $$ P(X\in B\mid \text{Accept})=\int_B \tilde{K}\frac{dQ}{dP}(\omega)\; P(d \omega)=\tilde{K}\cdot Q(B), $$ and by putting $B=\Omega$ we see that $\tilde{K}=1$.

share|cite|improve this answer

Your Answer


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

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