1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ This might not have a name because (a) it's rare to need just a single random sample from a distribution and (b) when you take more than a very small number of samples, this is a computationally terrible algorithm (it costs $O(n)$ time for each realization). Thus, it's likely many authors would describe it as something like "brute force." $\endgroup$ – whuber Aug 16 at 11:22
  • 2
    $\begingroup$ As a fun mental exercise, you can make this approximately twice as fast on average by starting from the end and walking backwards if u > 0.5. But that's like finding an acceleration of the horse and buggy today... $\endgroup$ – Cliff AB Aug 16 at 21:20
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

enter image description here

  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}
 }
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.