What is the distribution of $Y$ from using the Rejection Sampling algorithm?

  • Repeat Sample $X$ with distribution function $F_X = (1-(1+x^\alpha)^{-1})1_{x\ge 0}(x)$
  • Until $X>x_0$, where $x_0$ is a positive constant.
  • Set $Y=X$

The solution begins as follows, however i do not understand this part: "The probability of accepting a value is 1 if $X>x_0$, so the ratio of $f_Y$ to $f_X$ is proportional to $1_{x_0\le x < \infty}$. Therefore

$$ f_{accept}(x)=\frac{f(x;\alpha)1_{x_0 \le x < \infty}(u)}{\int_{x_0}^\infty f(u;\alpha)du}$$

So here are my questions:

  1. If $P(Accept|X>x_0)=1$, then why is the ratio of the target density to the proposal density is proportional to $1_{x_0 \le x < \infty}$? Is this just a property of the algorithm?
  2. How do you go from the statement above to the equation of the acceptance density?

1 Answer 1


Consider an iid sequence $X_1,X_2,\ldots$ from $f(\cdot;\alpha)$. Then $Y=X_N$ when $$N=\min\{n; X_i>x_0\}$$ Hence \begin{align}\mathbb P(Y<y)&=\mathbb P(X_N<y)\\&=\sum_{i=1}^\infty\mathbb P(N=i,X_i<y)\\&=\sum_{i=1}^\infty\mathbb P(X_i<y,X_i>x_0,X_{i-1}<x_0,\ldots,X_1<x_0)\\&=\sum_{i=1}^\infty\mathbb P(x_0<X_i<y)\mathbb P(X_1<x_0)^{i-1}\\&=\mathbb P(x_0<X_1<y)\sum_{i=1}^\infty\mathbb P(X_1<x_0)^{i-1}\\&=\mathbb P(x_0<X_1<y)\big/\mathbb P(x_0<X_1) \end{align} which is indeed the truncated version of the distribution $f(\cdot;\alpha)$.

If one was to rephrase the algorithm as an accept-reject algorithm, one would take $$f_Y(y)/f_X(y)\propto\mathbb I_{y>x_0}\le 1$$ Hence following an accept-reject approach by (i) generating $U\sim\mathcal U(0,1)$ and (ii) accepting $X\sim f_X(x)$ as $Y=X$ only when$$U\le \mathbb I_{X>x_0}$$means accepting $X$ when $X>x_0$ and rejecting $X$ otherwise. The uniform generation is superfluous in this particular case since the decision does not depend on $U$. If there is no typo in the equation $$f_{accept}(x)=\frac{f(x;\alpha)\mathbb I_{x_0 \le x < \infty}(u)}{\int_{x_0}^\infty f(u;\alpha)\,\text du}$$ produced in the question, the indicator $\mathbb I_{x_0 \le x < \infty}(u)$ is constant in $u$, the constant being either zero or one. (Note that the use of $u$ as the dummy variable for the integration is particularly confusing!)


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.