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

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.

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.

• Just saw this. (+1) Nice to show if...then...else code. – BruceET Apr 16 at 9:22

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 2 1 2 2 0 1
set.seed(123); qbinom(runif(7), 2, 1/2)
 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.)