Can a two-symbol distribution be dyadic?

Yes; equal probabilities of 1/2 and 1/2 are a simple example.

Is a probability of 3/8 allowed under this definition?

No. It is not an integer power of one half, even though it has a power-of-two denominator.

Does a dyadic distribution require equal probabilities?

No. The example with halves, quarters and eighths has unequal probabilities.

AI Glossary / MLOps and deployment / Intermediate

Dyadic distribution

Definition

In source coding, a dyadic distribution is a discrete probability distribution whose positive probabilities are integer powers of one half, such as 1/2, 1/4 and 1/8. It is useful because the ideal information length −log2(p) is then an integer for every possible symbol, matching whole-bit codeword lengths naturally.

What it means

For many distributions, a symbol's ideal information content is fractional, such as 1.3 bits, while an individual binary prefix codeword must contain a whole number of bits. A dyadic distribution avoids this particular mismatch. Its probabilities still must sum to one. Here “dyadic” has the standard source-coding meaning of powers of one half, rather than the broader mathematical idea of any fraction with a power-of-two denominator. For example, 3/8 is a dyadic rational but is not itself an inverse power of two.

How it works

Assign a symbol with probability 2 to the power −k a codeword of length k. The resulting lengths satisfy the binary Kraft equality because their corresponding probabilities sum to one. A suitable prefix-free code can therefore be constructed. Its expected length equals the distribution's entropy, calculated as the probability-weighted average of −log2(p). This is an ideal coding statement for the specified source model. It does not remove file headers, model storage, finite-message effects or dependencies between successive symbols.

Three practical examples

A student uses a dyadic example to understand why more probable symbols should receive shorter prefix codewords.
A compression engineer tests a Huffman implementation against a distribution with known entropy and expected code length.
A researcher studying probability models compares the cost of a simple integer-length code with arithmetic coding, which can approach fractional average lengths over sequences for non-dyadic probabilities.

Think of it this way

Think of dividing a cake repeatedly into equal halves: one piece may be a half, another a quarter and two others eighths. The pieces correspond neatly to paths of different lengths in a binary tree. The analogy explains the powers-of-two structure, but probability is not a physical substance and observed symbol counts need not match the model exactly in a short sample.

Worked example

Let P(A) = 1/2, P(B) = 1/4 and P(C) = P(D) = 1/8. One prefix-free code is A = 0, B = 10, C = 110 and D = 111. No codeword begins with another complete codeword. The expected length is (1/2)×1 + (1/4)×2 + (1/8)×3 + (1/8)×3 = 1.75 bits per symbol. Entropy gives the same result because −log2(1/2) = 1, −log2(1/4) = 2 and −log2(1/8) = 3. A fixed two-bit code would use 2 bits per symbol. The 0.25-bit expected saving excludes any cost of communicating the codebook.

Illustrative case study

Fictional case: Pine Data teaches new analysts how compression relates to probability. Its training exercise first uses the four-symbol dyadic model above, then changes the probabilities while keeping the same code. The analysts calculate the new expected length and see that a code suited to one model need not remain optimal for another. They also encode a short sample whose symbol counts differ from the expected proportions. The case illustrates a learning exercise, not an operational compression claim.

Common misconceptions and mistakes

Do not assume that any probability expressible as a finite binary fraction satisfies this source-coding definition. Do not confuse equality of expected length and entropy with identical length for every message. A finite sample dominated by a long-codeword symbol can cost more than the average. Also, entropy depends on the model and the unit of coding: exploiting relationships between symbols can change the relevant entropy rate. The dyadic property does not make a source predictable or its data automatically small.

Business use

For most business users, this is a foundational concept rather than a procurement criterion. It helps explain why a simple coding method may leave a gap above an information-theoretic benchmark and why modeling accuracy matters. When evaluating compression claims, ask whether quoted bits per symbol include metadata and whether the probability model matches actual data. A clean textbook example should not be mistaken for an end-to-end estimate of archive or network costs.

Check your understanding

For probabilities [1/2, 1/4, 1/4], what codeword lengths achieve entropy?

Answer: Lengths [1, 2, 2], for example codewords 0, 10 and 11. The expected length and entropy both equal 1.5 bits per symbol, before any framing or codebook overhead.

Related terms

Entropy
Arithmetic coding
prefix-free code
Huffman coding
Kraft inequality
expected code length

Learn next

Calculate entropy and expected code length for [1/2, 1/4, 1/8, 1/8], then repeat with [0.4, 0.3, 0.2, 0.1]. Keep the distinction between fractional ideal lengths and actual integer codeword lengths visible. Finally, encode a short sample to see how empirical counts differ from expectations.

Entropy

Sources

Primary teaching references: Stanford EE376A lecture on prefix codes for dyadic distributions, https://web.stanford.edu/class/ee376a/files/lecture_5.pdf ; Stanford data-compression course notes, https://stanforddatacompressionclass.github.io/notes/lossless_iid/prefix_free_codes.html . Institutional course search excerpts consulted; full mathematical and editorial review remain pending.

Previous: Dutch eligibility trace Next: Dykstra's projection algorithm