What is the name of this simple discrete sampling algorithm?

Question

I have a vector of probabilities $p \in \mathbb{R}^n$ which I have never seen before. I would like a single sample from the indices $(1, 2, \ldots n)$ according to the distribution defined by $p$. This could be performed in python with the following code.

import numpy as np

# Vector of probabilities
p = [0.1, 0.2, 0.3, 0.4]

# Uniform [0,1]
u = np.random.rand()

# Here's the algorithm
i = 0
while u > 0:
    u -= p[i]
    i += 1

# The variable `i` now has the desired distribution
print(i)

Questions:

1. What is the name of this algorithm?

2. What is an appropriate reference to cite when referring to this algorithm?

---

I am aware of the alias method which provides a superior way to sample from a distribution in $O(1)$, assuming you can afford a modest precomputation cost. However, since I only want to draw a single sample, this is less efficient than the algorithm described above.

Answer 1

The random variable you are generating is $X \sim \text{Categorical}(\mathbf{p})$, which is a discrete random variable with a distribution function that is a step function. Your algorithm is performing inverse transformation sampling, and the inversion is done by a sequential search (as pointed out in the excellent answer by Moormanly). This is a common way to perform inversion in inverse transformation sampling when you are generating a discrete random variable.

Answer 2

The algorithm is described on page 86 of Non-Uniform Random Variate Generation (1986).

1. The book refers to this algorithm as "Inversion by sequential search".

2. The book attributes the algorithm to "Kemp 1981", although the algorithm is much older. It would be reasonable to cite the book itself:

@Book{devroye1986non-uniform,
    author = {Devroye, Luc},
    title = {Non-uniform random variate generation},
    publisher = {Springer-Verlag},
    year = {1986},
    address = {New York},
    isbn = {978-1-4613-8643-8}
 }