Walker's Alias Method — weighted random sampling in constant time.

A WAM table is built once from a set of values and their weights, and every draw afterwards costs one integer index, one comparison and at most two tuple reads. Neither the number of values nor the spread of the weights changes that cost, which is what the structure exists for: sampling from tens of thousands of weighted values as cheaply as from three.

Installation

Add wam to the dependencies in mix.exs:

def deps do
  [
    {:wam, "~> 0.3.0"}
  ]
end

Building a table

new/1 takes the values and their weights together, in whichever shape the caller already holds them — a map, or a list of {value, weight} pairs:

wam = WAM.new(%{a: 10, b: 4, c: 5})
wam = WAM.new([{:a, 10}, {:b, 4}, {:c, 5}])

new/2 takes them as two lists of equal length, paired by position:

wam = WAM.new([:a, :b, :c], [10, 4, 5])

Weights are relative and the caller does not normalise them: %{a: 10, b: 4, c: 5} and %{a: 10 / 19, b: 4 / 19, c: 5 / 19} describe the same distribution and build interchangeable tables. Integers and floats mix freely.

Building is O(n) and allocates four tuples. It is meant to happen once, at load time, and the resulting struct to be held and read many times.

Drawing

A draw needs two numbers from the caller: a bucket index in [0, size) and a random float in [0, 1).

index = :rand.uniform(wam.size) - 1
rng = :rand.uniform()

{:ok, value} = WAM.fetch(wam, index, rng)

Both come from outside on purpose. The library holds no generator state and never calls one, so the caller chooses the source — :rand, a fixed sequence in a test, or any other random number generator — and the table stays a plain immutable term that can live in ETS, be shared between processes and be drawn from concurrently without a lock.

fetch/3 answers {:ok, value}, get/4 answers the value or a default, and index/3 answers the drawn index instead of the value — useful when the values are large, or are held elsewhere and only their position is needed.

How it works

The alias method reshapes an arbitrary distribution over n values into n equal-sized buckets, each holding at most two of them. Every weight is compared against the mean weight; a value lighter than the mean cannot fill its own bucket on its own, so the rest of that bucket is given to a value heavier than the mean, which is recorded as the bucket's alias. The pairing repeats — the heavy value's leftover weight goes back to whichever side it now belongs to — until every bucket is full.

That leaves two tuples of n entries. aliases[i] is the index the bucket falls back to, and probs[i] is the share of bucket i that belongs to value i. A draw picks a bucket uniformly, then decides between the bucket's own value and its alias with a single comparison. The uniform bucket choice and the split inside the bucket together reconstruct the original weights, which is why both numbers have to be drawn and neither may be derived from the other.

The probability table

probs[i] is the probability of keeping bucket i, so a draw reads

if rng < probs[i], do: i, else: aliases[i]

This orientation is what makes a weight of 0 unreachable by construction rather than merely improbable. A zero-weight value is always paired away, so its probs entry is exactly 0.0, and rng < 0.0 is false for any rng >= 0 — the guarantee holds whatever the generator's upper bound turns out to be and whatever a caller passes. Code that mutes content by giving it a weight of 0 can rely on it:

wam = WAM.new([{:a, 10}, {:muted, 0}, {:c, 5}])
# no index and no rng produce :muted

probs and aliases are public so a table can be inspected, but nothing outside this module should draw by reading them. Reading a slot without drawing is at/3 and fetch_at/2, never get/4 with an rng picked to defeat the comparison — that trick depends on how probs is oriented and breaks silently when it changes.

Weights that sum to zero

The muting above works because the muted slot is paired away with a slot heavier than the mean. When the weights sum to 0 there is no heavy slot to pair with: every slot lands below the mean, the pairing loop rewrites no alias, and each slot keeps the identity alias it started with. A slot whose alias is itself is returned by the draw for any value of probs — rng < probs[i] picks i, and rng >= probs[i] picks aliases[i], which is also i.

Unreachability is therefore not a state this structure can express, and new/1 raises ArgumentError rather than handing back a table that cannot honour what its weights say:

WAM.new(%{a: 0, b: 0})
** (ArgumentError) cannot build a WAM whose weights sum to 0: ...

Before 0.3.0 that case answered a table of probs filled with 1.0, which drew uniformly over values every one of which had been muted. That was a defect, not a policy. The clause also stood on a literal 0, which does not match 0.0, so float zeros fell through and died with an ArithmeticError instead — one meaning, two incompatible behaviours. The guard is now sum == 0, and both reach the same refusal.