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

<p>Givens:</p>

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

<p>The algorithm is as follows (pseudocode):</p>

<pre><code>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)
</code></pre>

<p>The distribution that this algorithm selects is</p>

<p>$$\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)$$</p>

<p>Solving for $\mathbf q$: </p>

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

<p>$$\mathbf p = \mathbf q$$</p>

<p>And the time complexity is</p>

<p>$$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)$$</p>

<p>$$Nt = \frac{1}{M} + N(1+t) - \frac{t+1}{M}$$</p>

<p>$$0 = N - \frac{t}{M}$$
$$t = MN$$</p>

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

<p>My question is: is there a name for this algorithm?</p>

<randomized-algorithms><terminology>
Quick Sampling from Probability Distribution: Is there a name for this algorithm?
k_g
# Quick Sampling from Probability Distribution: Is there a name for this algorithm?

(Asked by: username_0 on 2016-07-23)

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?

**Tags:** randomized-algorithms, terminology

---

## 0 answers

