13. 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.