What does Shannon entropy measure for a discrete distribution, in bits?
answer
- average surprise, not a single draw
- expected yes/no questions per draw
- log base 2 gives bits, ln gives nats
- flat distribution is the maximum
- -sum p log2 p
basics
~20 sShannon entropy is a distribution's average uncertainty: H = -sum p log2 p, the expected number of yes/no questions needed to pin down one draw. It is largest for equally likely outcomes and zero when one outcome is certain.
solid answer
~50 sShannon entropy of a discrete distribution is `H(X) = -sum_i p_i * log2(p_i)`, measured in bits when the log is base 2. It is the expected surprise per draw, where the surprise of an outcome with probability `p` is `-log2(p)` bits — rare outcomes are more surprising. Operationally it is the expected number of well-chosen yes/no questions, or the shortest achievable average code length, needed to communicate one draw. For a 4-symbol alphabet with probabilities 1/2, 1/4, 1/8, 1/8 the entropy is 1.75 bits, below the 2 bits a uniform alphabet of the same size would need, and the codewords 0, 10, 110, 111 hit that 1.75 average exactly. Entropy depends only on the probabilities, never on the labels or numeric values of the outcomes, and it is maximal for the uniform distribution and zero when some outcome has probability 1.
go deeper
Be ready to write -sum p log2 p, say the unit is bits, and state the two extremes: uniform is maximal, a certain outcome is zero.
Explain the surprise-and-expectation derivation and the coding reading, including why a skewed 4-symbol alphabet can average 1.75 bits per symbol instead of 2.
Show judgment about estimation: entropy computed from counts is biased low on small samples because unseen outcomes contribute nothing, so plug-in entropy on a long tail understates uncertainty.
Own the framing choice: argue when an information-theoretic summary is the right currency for a decision versus a task-specific metric, and insist units and normalisation are fixed before numbers get compared across teams.
## The quantity For a discrete random variable `X` taking values `x_1, ..., x_k` with probabilities `p_1, ..., p_k`, the Shannon entropy is ``` H(X) = -sum_i p_i * log(p_i) ``` with the convention that a term with `p_i = 0` contributes 0 (because `p log p -> 0` as `p -> 0`). Entropy is a functional of the *distribution*, not of the outcomes themselves: relabelling the outcomes, or rescaling numeric values, leaves it unchanged. That is the first thing that separates it from variance, which very much depends on the numeric values. ## Units: bits versus nats The base of the logarithm sets the unit. Base 2 gives **bits**, the natural log gives **nats**. They differ only by a constant factor: 1 nat = 1 / ln(2) ≈ 1.4427 bits, and 1 bit = ln(2) ≈ 0.693 nats. Any statement about which of two distributions has more entropy is unit-independent; only the numbers change. Interview answers should name the unit, because "the entropy is 0.69" is ambiguous — that is one bit expressed in nats. ## Surprise and expectation Define the surprise (self-information) of an outcome with probability `p` as `-log2(p)` bits. A certain outcome (`p = 1`) carries 0 bits of surprise; an outcome with `p = 1/8` carries 3 bits; a vanishingly rare outcome carries arbitrarily many. Entropy is then simply the *expected* surprise, `E[-log2 p(X)]`. This is why entropy is an average property of the distribution and not a property of any single observed draw: a single draw has a surprise value, the distribution has an entropy. ## The coding / twenty-questions reading The reason entropy is measured in bits is Shannon's source coding result: the expected number of bits per symbol of any uniquely decodable binary code for i.i.d. draws from the distribution is at least `H(X)`, and codes exist that approach it. Equivalently, playing twenty questions optimally against the distribution, the expected number of yes/no questions is about `H(X)`. Take a four-symbol alphabet A, B, C, D with probabilities 1/2, 1/4, 1/8, 1/8. Then ``` H = 0.5*1 + 0.25*2 + 0.125*3 + 0.125*3 = 1.75 bits ``` A prefix code assigning A -> 0, B -> 10, C -> 110, D -> 111 has expected length 0.5*1 + 0.25*2 + 0.125*3 + 0.125*3 = 1.75 bits per symbol — it meets the bound exactly, because every probability here is a power of 1/2. A fixed-length code would spend 2 bits per symbol. The 0.25-bit gap is exactly the compressibility that the skew in the distribution buys you. ## Bounds and the two extremes For a distribution over `k` outcomes, `0 <= H(X) <= log2(k)` bits. - The **maximum** `log2(k)` is attained only by the uniform distribution: maximal uncertainty, nothing to exploit, every symbol needs its full `log2(k)` bits. - The **minimum** 0 is attained only when some outcome has probability 1: no uncertainty, nothing to transmit. For a Bernoulli variable with success probability `p`, `H(p) = -p log2(p) - (1-p) log2(1-p)`. This curve is concave, symmetric about `p = 0.5`, peaks at exactly 1 bit when `p = 0.5`, and falls to 0 at both `p = 0` and `p = 1`. It is also flat near the top and steep near the ends: `H(0.4) ≈ 0.971` bits, barely below the maximum, while `H(0.9) ≈ 0.469` bits and `H(0.99) ≈ 0.081` bits. A heavily imbalanced binary outcome carries very little information per observation — a fact worth remembering whenever you are told a label is "rare". ## Common confusions worth heading off - **Entropy is not variance.** A variable taking values 0 and 1000 with probability 1/2 each and a variable taking values 0 and 1 with probability 1/2 each have the same entropy (1 bit) and wildly different variances. - **Entropy is not a probability**, so it is not bounded by 1; only the *binary* case caps at 1 bit. - **It is a property of the model, not of the sample.** Estimating entropy from counts on a small sample is biased downward, because unobserved outcomes get probability 0 and contribute nothing. - **Continuous variables need care.** The analogous differential entropy `-integral f(x) log f(x) dx` can be negative and is not invariant under a change of units, so it is not a drop-in replacement for the discrete quantity. In an interview, the strongest short answer states the formula, names the unit, gives the coding or twenty-questions interpretation, and cites the uniform-maximum / certain-minimum extremes.
- What is the entropy of a Bernoulli variable with p = 0.5, and how does it change as p moves toward 0 or 1?At `p = 0.5` it is exactly 1 bit, the maximum for a binary outcome. `H(p) = -p log2 p - (1-p) log2(1-p)` is concave and symmetric about 0.5, falling to 0 at both `p = 0` and `p = 1`. The fall is slow near the middle and fast near the ends: `H(0.4) ≈ 0.97` bits but `H(0.9) ≈ 0.47` bits. Heavily imbalanced binary outcomes carry little information per observation.
- Can entropy ever exceed log2 of the number of possible outcomes?No. For `k` outcomes, `H <= log2(k)`, with equality only for the uniform distribution. Any skew away from uniform strictly reduces entropy, because concentrating probability makes some outcomes more predictable. This upper bound is what lets you normalise entropy to a 0-to-1 scale by dividing by `log2(k)` when comparing alphabets of different sizes.
- Two variables have the same entropy but very different variances. How is that possible?Entropy depends only on the probability vector, not on the outcome values. A coin paying 0 or 1 and a coin paying 0 or 1000, both fair, each have entropy 1 bit but variances of 0.25 and 250000. Entropy measures how hard the outcome is to guess; variance measures how far the numeric values spread. Neither implies the other.
It is the average length of the shortest message you could design to report one draw: predictable sources compress, unpredictable ones do not.
saying these in an interview costs you the question
- Says entropy is a property of a single observed outcome
- Confuses entropy with variance or with spread of values
- Claims entropy is capped at 1 for any distribution
- Reports a number without saying bits or nats
- Thinks entropy depends on the numeric labels of outcomes