Intuition behind generating discrete random variables from a uniform random number generator

Question

The following is an exercise from Rice's Mathematical Statistics and Data Analysis:

This problem shows one way to generate discrete random variables from a uniform random number generator. Suppose that F is the cdf of an integer-valued random variable; let U be uniform on [0, 1]. Define a random variable Y = k if F(k − 1) < U ≤ F(k). Show that Y has cdf F.

I know how to prove this (by writing F's cdf as a sum of cdf of uniform distribution, which then eventually cancels / simplifies nicely to give F_Y(x) = F(x)) but I'm having trouble developing an intuition as to what this method means and how it works. I am not looking for a solution to the exercise / a proof. I want to understand why this method works at a conceptual level.

I'm not sure what this method is called so I couldn't search for other resources on this.

Answer 1

I'll try to give a working example. Let's say you want to create a RV from the following discrete distribution: $$p_X(x)=\begin{cases} 0.3, &x=1\\0.2, &x=2\\0.1,&x=3\\0.4,&x=4 \end{cases}$$

One simple way to simulate this distribution is the following intuitive if-else block:

u = rand() // uniform 0-1 RV
if u < 0.3
   x = 1   // we'll be here with 0.3 probability
else if u < 0.5
   x = 2   // we'll be here with 0.5 - 0.3 = 0.2 probability
else if u < 0.6
   x = 3   // we'll be here with 0.6 - 0.5 = 0.1 probability 
else
   x = 4   // we'll be here with 1 - 0.6 = 0.4 probability
end

which is the same procedure described analytically.

Answer 2

Whether for generating values from a continuous or discrete random variable, the method is sometimes called the 'inverse CDF method' or the 'quantile method'. I will illustrate the discrete case.

Suppose we want to simulate $X \sim \mathsf{Binom}(n=2,p=1/2).$ Its CDF table can be found in R as follows:

x = 0:2; cdf = pbinom(x, 2, 1/2);  cbind(x, cdf)
     x  cdf
[1,] 0 0.25
[2,] 1 0.75
[3,] 2 1.00

Suppose you want to simulate $X \sim \mathsf{Binom}(2,1/2)$ using a sample from $U \sim \mathsf{Unif}(0,1).$ Then you could get

• $P(X = 0) = 1/4$ by using values of $U$ in the interval $(0,0.25)$ because $P(0 \le U < 0.25) = 1/4;$

• $P(X = 1) = 1/2 $ by using values of $U$ in $(0.25, 0.75)$, and

• $P(X = 2) = 1/4 $ by using values of $U$ in $(0.75, 1.00).$

The graph on the left below shows the CDF of $X \sim \mathsf{Binom}(2,1/2)$ and on the right its inverse CDF (quantile function). For reference, heavy lines on both graphs show $P(X=1) = 1/2.$

In R, if I want generate 7 observations from $\mathsf{Binom}(2, 1/2),$ I can do it by using rbinom or by using runif with qbinom; by using the same seed both times in the example below, I get exactly the same sample each way.

set.seed(123); rbinom(7, 2, 1/2)
[1] 1 2 1 2 2 0 1
set.seed(123); qbinom(runif(7), 2, 1/2)
[1] 1 2 1 2 2 0 1

Thus, it is reasonable to assume that the R function rbinom implements the quantile method as illustrated above. (But for $p > .5,$ R uses a slightly different method.)