Non-uniform Discrete Distribution (Continued)

In the previous lesson, we sketched out an $O(log$ $n)$ algorithm for sampling from a weighted distribution of integers by implementing a discrete variation on the “inverse transform” method where the “inverse” step involves a binary search.

---

Modification of Non-Uniform Discrete Distribution

Can we do better than $O(log n)$? Yes — but we’ll need an entirely different method. We will sketch out two methods, and implement one this time, and the other in the next lesson.

Again, let’s suppose we have some weights, say $10$, $11$, $5$. We have three possible results, and the highest weight is $11$. Let’s construct a $3$ by $11$ rectangle that looks like our ideal histogram; we’ll put dashes to indicate the “spaces”:

0|**********-
1|***********
2|*****------

Here’s an algorithm for sampling from this distribution:

1. Uniformly choose a random row and column in the rectangle; it’s easy to choose a number from $0$ to $2$ for the row and a number from $0$ to $10$ for the column.
2. If that point is a *, then the sample is the generated row number.
3. If the point is a –, try again.

Basically, we’re throwing darts at the rectangle, and the likelihood of hitting a valid point on a particular row is proportional to the probability of that row.

In case that’s not clear, let’s work out the probabilities. To throw our dart, first we’ll pick a row, uniformly, and then we’ll pick a point in that row, uniformly. We have a $\frac{1}{3} \times \frac{10}{11} = \frac{10}{33}$ ...