Two to a Column

Experiment № 103 · October 28, 2026

To pick one of n outcomes with lopsided odds in constant time, Walker's alias method (1974, made sturdy by Vose in 1991) cuts the tall bars to top up the short ones until there are n columns of height exactly one, each holding at most two outcomes. After that, every draw is one die roll and one coin flip.

Outcomes 10

Build speed 1.2 steps / s

Darts 6 / s

columns finished0 / 10 draws0 off from true odds—

linear scan, avg checks— alias table, per draw1 die + 1 coin last draw—

Vose's two worklists

Short0

Tall0

—

Every bar starts at n × its probability, so they average exactly 1. While any bar is short, some other bar must be tall: cut the short one's shortfall off the tall one's top. The short column is now finished forever: its own outcome below, the donor (its alias) above. Each step finishes one column, so the table takes n steps.

Drag any bar up or down to change the odds · hover a column to read it · space pauses · H hides panels

Experiment № 103 · The story

Two to a Column

Why I picked it

I have written weighted random choice into almost every simulation and game I've made, and nearly every time I wrote the lazy version: keep a running total, roll a number, walk down the list until you pass it. That's fine for six outcomes. It is not fine for a word generator choosing among fifty thousand words a million times. For years I knew the alias method only as "the O(1) one" and had to look it up whenever I needed it, because I never understood why it worked. Then I saw it drawn as bars being cut and stacked, and it stopped being a trick and became obvious. I wanted to build that picture so I'd never have to look it up again.

What I enjoy about it

The guarantee sounds like it shouldn't be true: every column can be filled to exactly one using a single donor, never two. It works because the bars average one. If anything is short, something else must be tall, so you can always top up a short bar from a tall one. That finishes the short column for good, and the tall one is just a bit less tall, maybe now short itself. n bars, n steps, done. I also like that Vose's contribution, seventeen years after Walker, was mostly bookkeeping: two worklists instead of repeated searching, and care with rounding so the last column doesn't come out at 0.9999999. Unglamorous, and it's what makes the method dependable. Best of all I like watching the darts after the table is built. Each column fills with two colours split exactly at its line, and the histogram below quietly settles onto odds that no single column shows on its own.

Something you might take away

Unevenness can often be paid for once, up front. The table costs n steps to build, and after that every draw costs one die and one coin, whether there are six outcomes or a million. A lot of good engineering looks like this: do the awkward rearranging ahead of time so that the thing you do constantly becomes trivial. And the pairing argument is worth keeping too. When the total is fixed and some are below average, others must be above it, so a shortfall always has a surplus somewhere to cover it.