What does Shannon entropy measure for a discrete distribution, in bits?

## 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.