Tiny VoltA linear-algebraic treatment of the alias table for O(1) discrete sampling
The alias method is the fastest way to sample from a fixed discrete distribution. It pays an O(n) cost once to build an alias table, and from then on every draw takes O(1) time, independent of how many outcomes there are. The usual account of the method is combinatorial: you chop the probability mass into bins, then pour the surplus of the heavy bins into the deficit of the light ones. This article takes a different route. It reads the alias table as a row-stochastic matrix , and lets linear algebra explain why the table works, what its spectrum means, and where the constant-time guarantee comes from.
The alias table is a directed graph
The finished table stores two numbers per bin : a threshold (the probability of keeping bin ) and an alias (the bin you jump to otherwise). That is exactly a weighted directed graph. Each bin is a node with a self-loop of weight and one outgoing alias edge of weight .
Take a three-bin table with , where bins and both alias to bin . Drawn out, that is the : green self-loops carry the keep-mass, amber arrows carry the jump-mass, and bin has no amber arrow at all.
Structure. Because the two weights on every node sum to , the graph is row-stochastic: the out-weights of each bin form a probability distribution. And because sampling never revisits a bin (a keep stops, a jump lands and stops), the reachability relation is acyclic. The alias table is a row-stochastic directed acyclic graph, and that is the object the rest of this article studies.
A row-stochastic matrix with two nonzeros per row
Collect those out-weights into a matrix. Row gets on the diagonal and in the alias column , and zeros everywhere else.
Here is , Example 1 laid out cell by cell. The two nonzeros per row are unmissable: a green keep-cell on the diagonal, an amber jump-cell in the alias column. The same matrix, written as a live formula, lets us paint the two roles directly:
Spectral insight. For this table the diagonal are not just entries, they are the eigenvalues. Whenever the alias graph can be topologically ordered, is (a permutation of) a triangular matrix, and a triangular matrix's eigenvalues are precisely its diagonal. So the spectrum of the alias table is the multiset of keep-thresholds . The green diagonal you just painted is the spectrum.
Multiplying by P recovers the target: vP
The point of the construction is that transports the uniform choice of a bin into the target distribution. Let be the uniform row vector. Then is the target.
Watch how the left-hand uniform bars, pushed through , on the right. Each amber edge of the DAG is one term of the matrix product: a slice of a light bin's mass slides along its alias arrow and piles onto the heavy bin it points at. The construction of the table is exactly the condition .
A bigger example, and the dominant eigenvalue
Nothing about this is special to three bins. Consider a five-bin table with , where bin aliases to and bins alias to .
The draws the sources on the left and the two bins as absorbing sinks on the right. Its matrix
has spectrum again read straight off the diagonal.
The dominant eigenvalue and absorbing states. Every row of sums to , so the all-ones column vector satisfies : is always an eigenvalue, and by row-stochasticity it is the one of largest modulus. Its multiplicity counts the absorbing bins, the ones with and hence a on the diagonal and no alias edge. Here bins and are absorbing, and has multiplicity two. In the DAG they are exactly the sinks that the green self-loops never leave.
Left eigenvectors and centrality. The right eigenvector for is uninformative (it is ), but the left eigenvectors are where the target lives: a left eigenvector with is a stationary distribution, and its weight concentrates on the absorbing sinks. Reading as graph centrality, the sinks that collect the most alias edges are the most central nodes, and those are precisely the outcomes the target distribution favors.
The trace sets the branch probability
Finally, the constant-time draw. To sample, pick a bin uniformly, draw , and keep if , otherwise jump to its alias. Two array lookups and one comparison, no loop: that is the O(1) guarantee.
The 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. The trace, the sum of the very eigenvalues we read off the diagonal, is the global branch probability of the sampler. Every piece of the algorithm, its structure, its spectrum, its dominant eigenvalue, and its running behavior, is a statement about the matrix .