The alias sampling method allows sampling from a discrete probability distribution in O(1) time. It requires setting up a table which takes O(n) time. This cost is amortized over O(1) queries.

This table can actually be seen as a sparse representation of a row stochastic matrix. This allows us view this method through the lens of linear algebra.

An example

The alias table for the distribution looks like so:

Bin		Alias
1	0.9	2	0.1
2	1.0	—	0
3	0.3	2	0.7

Here , and bins and both alias to bin . To draw a sample, pick a bin uniformly at random, then keep with probability and return its alias otherwise. Bin has , so it never sends mass elsewhere.

This table can also be seen as a DAG with three nodes if we ignore the self-loops.

---

Table → Row stochastic matrix

Note that this table can be seen as a row stochastic matrix where each row has at most two non-zero entries. Row gets on the diagonal and in the alias column , and zeros everywhere else.

Here is as a heatmap for the above table.

---

Sampling as a Markov step

Let be the uniform row vector. Then is the target.

Watch how the uniform bars, pushed through , recover the target on the right.

Green entries are the a bin keeps for itself, amber entries are the it ships down an alias edge. Reading column of that product shows where bin 's final comes from:

---

Insight 1: are the eigenvalues

Note that the rows and columns of this matrix can be shuffled to make it triangular. Thus its diagonal entries are the eigenvalues.

Also note that since it is a stochastic matrix, its largest eigenvalue is .

---

Insight 2: dominant eigenvalues correspond to sinks

Let's use a larger matrix for this: a probability distribution with states: .

Bin		Alias
1	0.2	4	0.8
2	0.4	5	0.6
3	0.6	5	0.4
4	1.0	—	0
5	1.0	—	0

Here , bin aliases to , and bins alias to . Bins and have , so they are the two sinks.

The DAG corresponding to the alias table looks like this. Note that it has two sinks (absorbing states). The corresponding stochastic matrix is:

with eigenvalues . The eigenvalue has multiplicity two, which corresponds to the two bins (or the two connected components).

---

Insight 3: trace sets the branch probability

How O(1) sampling works: to sample, pick a bin uniformly, draw , and keep if , otherwise jump to its alias.

The keep-jump split stacks each bin's green keep-fraction under its amber jump-fraction . The chance a random draw keeps its first bin is the average of the green heights, and that average is the normalized trace:

For Example 1, , so a draw keeps its first bin with probability and follows an alias edge only about a quarter of the time.

---

Insight 4: trace and maximum coupling

Maximum coupling between and is a joint distribution such that is as large as possible. One way it is defined is:

Here the bin we land on is uniform, , and the sample we return is the target, . Now, divide the nodes into two parts:

• under-filled: . Note that for such a node.
• over-filled: . Note that for such a node.

Next, rewrite the mean trace as:

The last step is just the definition of the split: on an under-filled bin the smaller of the two is , and on an over-filled bin it is .

The insight: the alias matrix is as efficient as it can be - it tries to maximize the chance that a draw keeps the bin it landed on, and the trace tells us it hits the ceiling that no coupling of the uniform distribution with can beat.