Show that the following procedure generates a random variable $X \sim p_{X|Y}(x|y)$

Question

Suppose that $X$ and $Y$ are discrete random variables with a joint probability mass function $p_{XY}(x, y)$.

1. Generate $X \sim p_X(x)$

2. Accept $X$ with probability $p(y|X)$

3. If $X$ is accepted, terminate and return $X$. Otherwise go to step $1$.

I tried:

$p_{X|Y}(x|y) = P(X=x|Y=y) = \frac{P(X=x,Y=y)}{P(Y=y)} = \frac{p(x,y)}{\sum_x p(x,y)}$,

$p_X(x) = \sum_y p(x,y)$

and (I am not sure)

$p(y|X) = \frac{p(x,y)}{\sum_y p(x,y)}$.

But I don't know what to do with this. Any ideas?

Answer 1

Call the first attempt $X_1$, which can take any values $x_j$ and may be accepted or not. If not then we call the second attempt $X_2$ etc.

Then for a particular $X_j$ and $y$, $$\Pr(X_1=x_j \text{ and }X_1 \text{ is accepted}) = \Pr(X_1=x_j) \Pr(Y=y|X_1=x_j)$$ $$= \Pr(X_1=x_j \text{ and } Y=y) = \Pr(Y=y) \Pr(X_1=x_j|Y=y). $$

Summing over $j$ gives $\Pr(X_1 \text{ is accepted}) = \Pr(Y=y)$ and $\Pr(X_1 \text{ is not accepted}) = 1-\Pr(Y=y)$. So $\Pr(X_2 \text{ is accepted}) = \Pr(Y=y)(1-\Pr(Y=y))$, $\Pr(X_3 \text{ is accepted}) = \Pr(Y=y)(1-\Pr(Y=y))^2$ etc., making $\Pr(X_n \text{ is accepted}) = \Pr(Y=y)(1-\Pr(Y=y))^{n-1}$ and $\Pr(X_n=x_j \text{ and }X_n \text{ is accepted}) = \Pr(Y=y)(1-\Pr(Y=y))^{n-1} \Pr(X_n=x_j|Y=y).$

Now summing over $n$, we have the desired result: $$\Pr(x_j \text{ is accepted}) = \Pr(X=x_j|Y=y).$$