The alias method preprocesses a weighted categorical distribution into a rectangular table. Each row represents a nonzero-weight category slot and contains at most two possible values, allowing every sample to select a row uniformly and finish with a bounded decision rather than rejection. section 12.11 section 12.13
Construct the table incrementally:
- Treat the total weight as the width and the number of nonzero categories as the row count; scale each category’s marked area by the row count. section 12.11
- Pair a short row with a long row, move enough cells from the long row to fill the short row, and repeat until every row has equal width. section 12.11
- Sample by choosing a row uniformly and then sampling that row’s stored distribution; preprocessing needs at most n balancing attempts. section 12.11 section 12.13
Weights 3, 4, 5, 3
Four categories produce a table with four rows and fifteen columns. Their initial marked areas are 12, 16, 20, and 12 cells. Moving three cells from row 1 to row 0, then balancing the remaining short and long rows, yields a rectangle whose rows encode the original proportions. section 12.11
