Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Alias tables: constant-work draws from fixed dispatch weights

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

An alias table preprocesses a fixed discrete distribution into one threshold and one fallback outcome per column. A uniform draw chooses a column, then uses its fractional part to decide between the column's own outcome and its alias. Construction scales weights so their average is one, pairing underfilled columns with overfilled columns until every column owns exactly one unit of probability mass. The program retains route names in input order and accepts zero weights but rejects negative, nonfinite, empty, or all-zero distributions. Its deterministic pick_from_unit method exposes the draw mapping for inspection; sample consumes an injected random generator. The table is a static snapshot of weights: changing a route weight requires rebuilding it.

Operational case

North, east, and west routes have weights 19, 47, and 29. Fixed unit draws 0.03, 0.31, 0.69, and 0.94 select north, east, west, and west under this table's column arrangement. Those four draws are a trace, not statistical evidence that the weighted distribution has been reproduced. The sum of weights must remain positive and finite; an all-zero list has no meaningful probability measure. A zero-weight route can occupy a column but its threshold is zero, so the alias receives every draw from that column. The method requires a uniform input on [0,1) and rejects 1 itself.

Working Python program

python
from math import isfinite
from random import Random


class DispatchSampler:
    def __init__(self, weighted_routes):
        if not weighted_routes:
            raise ValueError("at least one route required")
        self.routes = list(weighted_routes)
        weights = list(weighted_routes.values())
        if any(not isfinite(weight) or weight < 0 for weight in weights):
            raise ValueError("weights must be finite and nonnegative")
        total = sum(weights)
        if not isfinite(total) or total <= 0:
            raise ValueError("positive finite total required")
        route_count = len(weights)
        scaled = [weight * route_count / total for weight in weights]
        small = [index for index, value in enumerate(scaled) if value < 1]
        large = [index for index, value in enumerate(scaled) if value >= 1]
        self.threshold = [1.0] * route_count
        self.alias = list(range(route_count))
        while small and large:
            low = small.pop()
            high = large.pop()
            self.threshold[low] = scaled[low]
            self.alias[low] = high
            scaled[high] = scaled[high] + scaled[low] - 1
            (small if scaled[high] < 1 else large).append(high)

    def pick_from_unit(self, unit):
        """Map one uniform draw in [0,1) into a weighted route."""
        if not 0 <= unit < 1:
            raise ValueError("unit draw outside [0,1)")
        position = unit * len(self.routes)
        column = int(position)
        fraction = position - column
        selected = column if fraction < self.threshold[column] else self.alias[column]
        return self.routes[selected]

    def sample(self, random_source):
        return self.pick_from_unit(random_source.random())


dispatch_sampler = DispatchSampler({"north": 19, "east": 47, "west": 29})
print("fixed draws:", [dispatch_sampler.pick_from_unit(draw) for draw in (0.03, 0.31, 0.69, 0.94)])
print("seeded draws:", [dispatch_sampler.sample(Random(seed)) for seed in (17, 29, 47)])

Output

Output
fixed draws: ['north', 'east', 'west', 'west']
seeded draws: ['east', 'east', 'east']

Time, space, and tradeoff

For K routes, table construction does O(K) arithmetic and uses O(K) storage. Each draw performs O(1) array accesses and comparisons after the random source supplies one uniform value. Updating one weight by reconstructing the table costs O(K), so a Fenwick frequency index may be preferable when weights change repeatedly. Floating-point rounding can slightly perturb boundaries, and a production sampler should define numeric precision and random-source requirements. Fixed-seed traces are useful for reproducible tests but are not suitable evidence of cryptographic unpredictability or a performance benchmark.

Common Mistakes

  • Do not use an alias table without rebuilding it after weights change.
  • Do not allow a zero or nonfinite total weight.
  • Do not treat four deterministic draws as a distribution test.
  • Do not pass a unit draw equal to one into a zero-based column table.

Connected lessons

Compare this operation boundary with MinHash bands: retrieve incident candidates, then check exact overlap, Run-length bitmaps: union, intersect, and subtract alert spans, then complete the structure audit and decision quiz.

Space-Saving: ranked candidates with count bounds gives a related indexing or summary tradeoff.

data structures
array-data-structure-guide
Storage details