How to Learn the Knuth–Yao DDG Algorithm: Probability Bits, Discrete Distribution Trees, Entropy Bounds and Exact Random Sampling

Suppose a random bit is the expensive resource. How many fair coin flips should it take to sample exactly from a non-uniform distribution? Knuth and Yao turned that question into a tree problem, showing how the binary digits of probabilities can be organised into an entropy-efficient discrete distribution generator.

This Learning Hall article develops the Knuth–Yao idea from fair bits and binary fractions to discrete distribution generating (DDG) trees, expected bit cost, entropy, infinite expansions, implementation strategies and professional random-generation safeguards. It complements the Alias Method learning article: the alias method optimises repeated table-based sampling, while Knuth–Yao asks how efficiently a target distribution can be generated from unbiased random bits.

Quick Read

Start with outcomes having probabilities p1,…,pn and a source of independent fair random bits.
Write each probability in binary.
The binary 1s tell us how many leaves for each outcome must appear at each depth of a binary decision tree.
A random bit chooses left or right at every internal node; reaching a leaf returns its outcome.
An optimal DDG tree minimises expected random-bit consumption.
The expected number of bits is bounded below by Shannon entropy and, for the Knuth–Yao optimum, is less than H+2.
Dyadic probabilities can produce finite trees; general probabilities may require conceptually infinite trees or streaming/table representations.
Production code must also consider RNG quality, memory, timing behaviour, floating-point conversion and exactness of the input probabilities.

1. Beginner Level: Sampling With a Fair Coin

If two outcomes are equally likely, one fair bit is enough:

0 → A
1 → B

For four equally likely outcomes, two bits give four leaves. But what if the probabilities are 1/2, 1/4 and 1/4? We should not need a fixed two-bit code every time. Half the time we could stop after one bit. A variable-depth tree can save random bits by placing high-probability outcomes closer to the root.

2. A First Decision Tree

For probabilities A=1/2, B=1/4, C=1/4, a tree can be:

bit 1:
  0 → A
  1 → read another bit
       0 → B
       1 → C

The expected number of bits is:

(1/2)·1 + (1/4)·2 + (1/4)·2 = 1.5 bits

This simple example already contains the central idea: probability mass can be represented by leaves at different depths.

3. Binary Expansions of Probabilities

Write each probability as a binary fraction. For example:

1/2 = 0.1₂
1/4 = 0.01₂
3/8 = 0.011₂

A 1 in column j represents probability mass 2^-j. In a full binary tree, every leaf at depth j is reached with probability 2^-j. Therefore each binary 1 can be interpreted as one leaf carrying the corresponding outcome label at that depth.

4. The Probability Matrix

Place the binary digits of all outcome probabilities in rows:

         1/2  1/4  1/8  1/16 ...
A=1/2     1    0    0    0
B=1/4     0    1    0    0
C=1/4     0    1    0    0

Column 1 asks for one A leaf at depth 1. Column 2 asks for one B leaf and one C leaf at depth 2. The column totals fit exactly into the available tree frontier.

5. Building a DDG Tree

A DDG tree is a binary tree whose leaves are labelled by outcomes. A random bit determines each branch. The total probability of all leaves labelled i must equal p_i.

Knuth–Yao showed that arranging the leaves according to the binary probability matrix can achieve the minimum possible expected number of fair random bits. The exact layout can vary, but the depth counts implied by the binary expansions are the key resource.

6. Why Entropy Appears

For distribution p, Shannon entropy is:

H(p) = -Σ p_i log₂(p_i)

Entropy is an information lower bound: on average, no exact generator driven only by fair bits can encode the outcome using fewer than H(p) bits. Knuth–Yao’s optimal expected bit cost lies below H(p)+2. This does not mean every sample uses fewer than H+2 bits. It is an expectation over repeated samples.

7. Dyadic and Non-Dyadic Probabilities

A dyadic probability has denominator equal to a power of two, so its binary expansion terminates. Distributions made entirely of dyadic probabilities can be represented with finite-depth structures.

Probabilities such as 1/3 have repeating binary expansions. The mathematical DDG tree may therefore be infinite, even though its expected traversal depth is finite. Practical implementations avoid literally allocating an infinite tree: they generate columns lazily, use compact tables, or work directly with exact integer/rational representations.

8. A Streaming View of the Algorithm

Instead of picturing every node, imagine maintaining a pool of currently available paths. Each new fair bit doubles the number of distinguishable paths. At depth j, binary 1s in probability column j claim some of those paths as terminal outcomes; unclaimed paths continue deeper.

This view is useful for implementation because it separates probability representation from tree navigation. You need not materialise pointers for every conceptual node.

9. High-Level Pseudocode

prepare(probabilities):
    represent every probability exactly in binary columns
    construct a compact DDG table/tree description

sample(ddg, fair_bit_source):
    state = root
    while state is not a leaf:
        b = fair_bit_source.next_bit()
        state = transition(state, b)
    return state.outcome

The mathematical idea is simple; the engineering challenge is the representation. An implementation based on floating-point approximations can silently sample from a nearby distribution rather than the exact intended one.

10. Exact Probabilities Need Exact Input Semantics

If the specification says the probability is exactly 1/10, store 1 and 10 or an equivalent exact integer representation. A binary floating-point number close to 0.1 is a different rational number. That difference may be negligible for some simulations but unacceptable for formal testing, cryptographic protocols, reproducibility or fairness-sensitive systems.

Professional implementations begin by deciding what “the distribution” actually means: mathematical rationals, decimal values rounded under a defined rule, or machine floating-point weights.

11. Knuth–Yao Versus the Alias Method

Knuth–Yao: optimises expected fair random-bit consumption and naturally supports exact-distribution reasoning.
Alias method: performs O(1) table lookup after preprocessing and is often excellent when machine-word random numbers are already cheap.
Knuth–Yao: may use variable traversal depth and more specialised preprocessing.
Alias method: typically reasons in buckets and scaled probabilities rather than an optimal bit decision tree.

The better method depends on the cost model. If your RNG supplies 64-bit words cheaply, bit optimality may not dominate. If randomness itself is scarce, audited, expensive or generated from a physical source, every bit can matter.

12. Connection to Fast Dice Roller

Lumbroso’s Fast Dice Roller tackles the important special problem of generating a uniform integer in a range from unbiased bits while recycling unused randomness efficiently. It belongs to the same larger design tradition: avoid throwing away random-bit information merely because the target range is not a power of two.

Studying both algorithms makes a powerful idea visible: randomness is a resource with information content. Rejection, remainder recycling and DDG trees are different ways of preserving that information rather than wasting it.

13. Production Failure Modes

Using biased source bits: the tree assumes independent fair bits.
Approximating probabilities unintentionally: floating-point conversion changes the target law.
Ignoring dual binary expansions: dyadic rationals can have terminating and repeating representations; choose a canonical form.
Allocating the conceptual infinite tree: non-dyadic inputs require compact or lazy representations.
Forgetting timing leakage: variable path length can reveal information in adversarial settings.
Modulo reduction of random words: naive x mod n is biased unless the source range is divisible by n or rejection/recycling is used.
Testing only frequencies: approximate frequency agreement can miss structural bias.

14. How to Test a Sampler

For tiny rational distributions, enumerate all bit prefixes up to a sufficient depth and verify their exact probability mass.
Instrument the number of bits consumed per sample and compare the empirical mean with the theoretical expectation.
Verify that probabilities sum exactly to one under the chosen representation.
Test dyadic, highly skewed and repeating-binary distributions.
Run statistical goodness-of-fit tests only as a supplement to exact structural tests.
Use deterministic seeded bit streams in unit tests so failures are reproducible.
Separate correctness of the sampler from quality of the random-bit source.

15. Beginner-to-Professional Learning Ladder

Beginner: build fair-bit trees for 1/2–1/4–1/4 and other dyadic distributions.
Intermediate: convert probabilities to binary columns and compute expected tree depth.
Advanced: implement a compact DDG representation for exact rational probabilities and measure bit consumption.
Professional: define probability semantics, entropy cost, RNG interface, timing requirements, memory budget and statistical validation before choosing DDG, rejection, alias or another sampler.

16. How to Learn It Without Memorising the Tree

Use a Predict–Run–Investigate–Modify–Make progression. Predict where the high-probability outcome should appear. Run a supplied sampler with a fixed bit string. Investigate why each leaf has its probability. Modify one probability and rebuild only the affected binary columns. Finally make a sampler from a new distribution. This turns a visually complicated tree into a sequence of stable subgoals.

17. Practice Problems

Build an optimal tree for probabilities 1/2, 1/4, 1/8, 1/8 and compute expected bits.
Write 1/3 and 2/3 in binary and explain why a finite tree is not enough.
Calculate H(p) for several small distributions and compare it with your tree’s expected depth.
Show how naive modulo reduction can bias sampling of an integer from 0 to 5 using an 8-value source.
Implement a fair-bit source that exposes how many bits have been consumed.
Compare DDG and alias sampling when the target distribution is fixed but sampled ten million times.
Design a constant-time alternative for a security-sensitive setting and explain what efficiency is sacrificed.

18. Sources and Further Reading

Final idea: Knuth–Yao teaches a broader professional habit: measure the resource you are truly spending. A random choice is not free merely because a programming language exposes a random-number function. Once fair random bits are treated as information, probability tables become decision trees, entropy becomes a lower bound, and sampler design becomes an exercise in preserving rather than discarding uncertainty.

Small Group Tutorials