The Discrete Rejection Method: Suppose we want to simulate X having probability mass function P{X = i} = Pi, i = 1, . . . , n and suppose we can easily simulate from the probability mass function Qi , iQi = 1,Qi ≥ 0. Let C be such that Pi ≤ CQi, i = 1, . . . , n. Show that the following algorithm generates the desired random variable:

Step 1: Generate Y having mass function Q and U an independent random number.

Step 2: If U ≤ PY /CQY , set X = Y. Otherwise return to step 1.