# Quick Sampling from Probability Distribution: Is there a name for this algorithm?

I'm trying to quickly sample from a near-uniform discrete probability distribution exactly once without calculating the entire CDF. Here's the algorithm.

Givens:

• $N,$ the number of elements to sample from
• $p : \{n \in \mathbb{N} | n < N\} \to \mathbb{R}[0,1],$ the probability distribution function
• $M : \mathbb{R} = \max_{\forall n < N} p(n)$, the maximum probability

The algorithm is as follows (pseudocode):

define select(N, p, M):
LET i := a random natural number < N
WITH PROBABILITY p(i) / M:
return i
ELSE:
return select(N, p, M)


The distribution that this algorithm selects is

$$\mathbf{q} = \frac{1}{N}\sum_{i=0}^N\left(\frac{p_i}{M}\mathbf{e_i} + \left(1-\frac{p_i}{M}\right)\mathbf q\right)$$

Solving for $\mathbf q$:

$$N\mathbf{q} = \frac{1}{M}\mathbf p + N\mathbf q - \frac{1}{M}\mathbf q$$

$$\mathbf p = \mathbf q$$

And the time complexity is

$$t = \frac{1}{n}\sum_{i=0}^n \left(\frac{p_i}{M} \cdot 1 + (1 + t)\left(1-\frac{p_i}{M}\right)\right)$$

$$Nt = \frac{1}{M} + N(1+t) - \frac{t+1}{M}$$

$$0 = N - \frac{t}{M}$$ $$t = MN$$

So for a near-uniform distribution, where $M = O(N^{-1})$ then the algorithm is $O(1)$.

My question is: is there a name for this algorithm?