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 &lt; N\} \to \mathbb{R}[0,1],$ the probability distribution function
$M : \mathbb{R} = \max_{\forall n &lt; N} p(n)$, the maximum probability


The algorithm is as follows (pseudocode):

define select(N, p, M):
    LET i := a random natural number &lt; 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?
Yes; that's called rejection sampling.