I'm trying to prove the discrete acceptance-rejection algorithm for generating random variables works, but I think I'm misunderstanding something basic.
Let $E$ be a countable set, and let $P$ and $Q$ be probability measures on $E$. Assume there is $c > 0$ such that $$ f(e) := \frac{Q(\{e\})}{P(\{e\})} \leq c \quad \textrm{for all } e \in E \textrm{ with } P(\{e\}) \neq 0. $$ Let $X_1, X_2, \ldots$ be $E$-valued independent random variables with distribution $P$. Let $U_1, U_2, \ldots$ be i.i.d. real random variables that are independent of $X_n$'s and are uniformly distributed on $[0,1]$. Finally define the random variables $$ N := \min\left\{n \geq 1 : U_n \leq \frac 1 c F(X_n) \right\} \quad \textrm{and} \quad Y := X_N. $$ CLAIM: $Y$ has distribution $Q$.
My understanding is we're trying to show that $\mathbb P[Y = e] = Q(\{e\})$ for $e \in E$. Am I wrong about this? Because I'm finding instead that $\mathbb P[Y = e] = P(\{e\})$, and my calculation appears to be right. Someone help please?
My calculation: Since the events $\{N = n\}$ for $n \geq 1$ are disjoint and $\mathop \biguplus_{n = 1}^\infty \{N = n\} = \Omega$, we have that \begin{equation}\label{1} \mathbb P[Y = e] = \sum_{n=1}^\infty \mathbb P[Y = e | N = n] \mathbb P[N = n] = \sum_{n=1}^\infty \mathbb P[X_N = e | N = n] \mathbb P[N = n]. \end{equation} So we need to calculate $\mathbb P[Y = e | N = n]$ and $\mathbb P[N = n]$ for $n \geq 1$ and $e \in E$. The former comes out to $P(\{e\})$, or $Q(\{e\})/f(e)$ if $P(\{e\}) \neq 0$. For the latter, we note that $$ \{N = n\} = \left\{ U_n \leq \frac 1 c f(X_n)\right\} \cap \mathop \bigcap_{k=1}^{n-1} \left\{ U_k > \frac 1 c f(X_k)\right\}, $$ so by independence of the $X_k$'s and $U_k$'s, \begin{align*} \mathbb P[N = n] = \mathbb P\left[ U_n \leq \frac 1 c f(X_n)\right] \prod_{k=1}^{n-1} \mathbb P\left[ U_k > \frac 1 c f(X_k)\right] \end{align*} We calculate the probabilities in the terms in the above equation: \begin{align*} \mathbb P\left[ U_n \leq \frac 1 c f(X_n)\right] &= \sum_{e \in E} \mathbb P\left[ U_n \leq \frac 1 c f(X_n) \bigg| X_n = e\right] \mathbb P\left[X_n = e\right] \\ &= \sum_{e \in E} \mathbb P\left[ U_n \leq \frac 1 c f(e)\right] P(\{e\}) = \sum_{e \in E,\, P(\{e\}) \neq 0} \left(\frac 1 c f(e)\right) \left(\frac{Q(\{e\})}{f(e)}\right)\\ &= \frac 1 c \sum_{P(\{e\}) \neq 0} Q(\{e\}) = \frac 1 c Q\left( \left\{ e : P(\{e\}) > 0\right\}\right). \end{align*} Using a similar calculation, it follows that \begin{align*} \mathbb P \left[ U_k > \frac 1 c f(X_k)\right] = 1 - \frac 1 c Q\left( \left\{ e : P(\{e\}) > 0\right\}\right). \end{align*} Therefore $\mathbb P[N = n] = \frac 1 c Q\left( \left\{ e : P(\{e\}) > 0\right\}\right) \left( 1 - \frac 1 c Q\left( \left\{ e : P(\{e\}) > 0\right\}\right)\right)^{n-1}$. So, by our formula for $\mathbb P[Y = e]$, \begin{align*} \mathbb P[Y = e] &= \sum_{n=1}^\infty \mathbb P[Y = e | N = n] \mathbb P[N = n] \\ &= \frac{Q(\{e\})}{cf(e)} Q\left( \left\{ e'\in E : P(\{e'\}) > 0\right\}\right) \sum_{n=1}^\infty \left( 1 - \frac 1 c Q\left( \left\{ e' \in E: P(\{e'\}) > 0\right\}\right)\right)^{n-1} \\ &= \frac{Q(\{e\})}{cf(e)} Q\left( \left\{ e'\in E : P(\{e'\}) > 0\right\}\right) \left( \frac 1 c Q\left( \left\{ e' \in E: P(\{e'\}) > 0\right\}\right)\right)^{-1} \\ &= \frac{Q(\{e\})}{f(e)} = P(\{e\}). \end{align*}
So why does this come out to $P(\{e\})$ instead of $Q(\{e\})$?
The problem comes from last equation: $\mathbb P[Y=e\mid N=n]\neq \mathbb P[X_n=e]=P(e)$. I suggests you to avoid conditional probability and rewrite the required probability directly as: $$ \mathbb P[Y=e]=\sum_{n=1}^\infty \mathbb P[Y=e, \, N=n] $$ $$ =\sum_{n=1}^\infty \mathbb P\left[\{X_n=e\}\cap\left\{ U_n \leq \frac 1 c f(e)\right\} \cap \mathop \bigcap_{k=1}^{n-1} \left\{ U_k > \frac 1 c f(X_k)\right\}\right] $$ $$ =\sum_{n=1}^\infty \mathbb P\left[X_n=e\right]\mathbb P\left[ U_n \leq \frac 1 c f(\color{red}{e})\right] \mathop{\prod}_{k=1}^{n-1} \mathbb P\left[ U_k > \frac 1 c f(X_k)\right] $$ You can compare it with the summands that you have: $$ \sum_{n=1}^\infty \mathbb P\left[X_n=e\right]\mathbb P\left[ U_n \leq \frac 1 c f(\color{red}{X_n})\right] \mathop{\prod}_{k=1}^{n-1} \mathbb P\left[ U_k > \frac 1 c f(X_k)\right] $$