= Solution
Assume $0<Z=\sum_xr(x)<\infty$, and work on the <support> $S=\{x:r(x)>0\}$. In <rejection sampling>, choose a normalized proposal <probability mass function> $g$ and a known finite constant $M$ satisfying $r(x)\leq Mg(x)$ everywhere. Draw <independent random variables> $Y\sim g$ and $U\sim\operatorname{Unif}(0,1)$, accepting $Y$ when $U\leq r(Y)/(Mg(Y))$. The joint <probability> of proposing and accepting $x$ is $r(x)/M$, so the overall acceptance <probability> is $Z/M$ and the accepted value has <probability mass function> $r(x)/Z$. Fresh trials therefore produce <independent and identically distributed random variables> with the desired <probability distribution>. For a fixed positive number $N$ of accepted values, the sample average $N^{-1}\sum_{i=1}^Nf(Y_i)$ is an <unbiased estimator> of the <expectation> when that <expectation> is finite. Its <variance> is $\operatorname{Var}_p(f)/N$ if the second moment is finite. Finding a valid envelope can be difficult, and a small acceptance <probability> makes the method expensive.
For the <Metropolis–Hastings algorithm>, choose a proposal <transition matrix> $q$ and, at the current state $x$, propose $y\sim q(x,\cdot)$. Accept with the <Metropolis–Hastings acceptance probability>
$$
\alpha(x,y)=\min\left\{1,\frac{r(y)q(y,x)}{r(x)q(x,y)}\right\}.
$$
A proposal outside $S$ is rejected; an impossible proposal need not be assigned a ratio. Otherwise remain at $x$. This constructs a <Markov chain> satisfying <detailed balance> with $p$, without computing $Z$ or a global envelope. Estimate the <expectation> by averaging $f(X_i)$ over iterations, \b[including repeated states after rejections]. Keeping only accepted jumps generally changes the <stationary distribution> of the recorded process.
The <Metropolis–Hastings algorithm> produces dependent samples, so the <variance> of its average includes <autocovariances>; starting outside <stationarity> can also cause finite-run <bias>. With <Markov chain irreducibility>, suitable recurrence and an integrable $f$, the <countable-state Markov chain ergodic theorem> gives consistency. <Aperiodicity> is additionally needed for the usual convergence of one-time <probability distributions>. In contrast, accepted <rejection sampling> values need no initial transient. Neither method is universally faster: envelope rejection competes with the proposal quality and <mixing time> of the <Markov chain>. Nonnegativity of $f$ alone does not guarantee a finite <expectation> or <variance>.
Back to article page
