skip to content

Your Shannon entropy estimate for a high-cardinality field comes from 500 sampled events — why does it read low?

level: seniorimportance: nice to knowfreq 26%

answer

  1. the sample is not the source
  2. what you never saw counts zero
  3. capped by log2 of the sample size
  4. bias grows with values per sample
  5. biased low on average, not always

basics

~20 s

Counting from a sample gives the plug-in estimate, which is biased low on average: values never sampled contribute nothing, and the figure cannot exceed log2 N — under 9 bits from 500 events, whatever the truth is.

solid answer

~40 s

The estimator substitutes observed frequencies for probabilities: `H_est = -sum (c/N) log2 (c/N)` over the values that actually appeared. Two things pull it down. Values that exist but did not appear in 500 draws contribute exactly zero, and a sampled distribution is lumpier than the one it came from, while entropy rewards evenness — so on average the estimate lands below the truth. There is a hard ceiling as well: with `N` observations the estimate is at most `log2 N`, which is 8.97 bits at `N = 500`, even if the field truly carries 14. A first-order correction is about `(k-1) / (2 N ln 2)` bits for `k` occupied values; when that correction is a large fraction of the estimate you have a lower bound, not a measurement.

code

pseudocode · 15 lines
pseudocode
function estimate_entropy(observations):
    counts = empty map
    for each v in observations:
        counts[v] = counts[v] + 1      // values never seen never enter the map

    N = length(observations)
    H = 0
    for each (v, c) in counts:
        p = c / N
        H = H - p * log2(p)

    return H

// H <= log2(N) always, with equality only when every observation differs;
// at N = 500 that ceiling is 8.97 bits, whatever the field's true entropy is

go deeper

for a junior

Take away one habit: an entropy figure computed from counts describes the sample you counted. Ask how many events it came from before believing it.

for a middle

Explain the two mechanisms — values never observed contribute nothing, and the estimate cannot exceed log2 of the sample size — and be able to compute that ceiling for a given sample.

for a senior

Show the operating discipline: report the ceiling with the estimate, recompute on halves and on more data, count distinct values against the sample size, and treat a figure from one quiet hour as unrepresentative until proven otherwise.

for a principal

Decide how much measurement a sizing decision deserves. A cheap lower bound is often enough to reject a plan; it is not enough to commit to a representation whose payoff depends on the distribution staying where you found it.

## What the count-based estimate actually computes You rarely know a field's true probabilities. You count: `c(v)` occurrences of each value across `N` observed events, then feed the observed frequencies into the formula as if they were the probabilities. This **plug-in estimate** `H_est = - sum over observed v of (c(v)/N) * log2 (c(v)/N)` is the entropy of the *sample*, not of the *source*. On a low-cardinality field with plenty of data the two are close. On a high-cardinality field with 500 events they can be worlds apart, always in the same direction. ## Why it comes out low 1. **Missing mass.** The sum runs only over values that appeared. A route field with thousands of live values, sampled 500 times, simply has no term for the ones that did not turn up — and collectively they may carry most of the uncertainty. 2. **Sampling makes the distribution lumpier.** Entropy is maximal for even distributions and a finite sample is never as even as the source it came from: some values land above their true rate, others below, and the resulting figure sits below the entropy of the true distribution on average. 3. **A hard ceiling at `log2 N`.** The estimate is an entropy over at most `N` non-zero cells, so it cannot exceed `log2 N` — reached exactly when all 500 observations are distinct. At `N = 500` that is **8.97 bits**. A field whose true entropy is 14 bits is *arithmetically incapable* of being measured at 14 bits from 500 samples. Point 2 is a statement about the **average over samples**, not a guarantee about yours. A particular small sample can land above the truth — take a field that is 0.9/0.1 and draw two events, one of each: the estimate is 1 bit against a true 0.469. The value of the bias result is that the opposite happens more often, and systematically so when there are many values. ## How many samples is enough A first-order correction for the bias is about `(k - 1) / (2 N ln 2)` bits, where `k` is the number of values with non-zero probability. At `N = 500`: | Occupied values `k` | Correction | Read against the ceiling of 8.97 bits | |---|---|---| | 3 | about 0.003 bits | Negligible — a 0.56-bit estimate is trustworthy | | 50 | about 0.07 bits | Small, worth noting in the figure you quote | | 5,000 | about 7.2 bits | Larger than most estimates you could produce — out of regime | The last row is the important one, and it needs an honest caveat: that correction formula itself assumes `N` is much larger than `k`. When it computes to something comparable to your estimate, the right reading is not "subtract 7.2" but **"this sample cannot measure this field"**. The rule of thumb that follows is the one to state in an interview: you want the number of *distinct values seen* to be small next to `N`, not close to it. ## An hour is not a day The statistical bias is only half the problem. The plug-in estimator assumes the sample is drawn from one fixed distribution, and real feeds are not stationary: - Overnight traffic can be dominated by scheduled work with a completely different value mix from daytime interactive traffic. - A per-tenant or per-client-version split can hide inside a pooled figure, so the pooled entropy describes a blend nobody actually sees. - Incidents create value distributions that exist for an hour and never recur. So a figure measured over one quiet hour can be both statistically clean and operationally wrong. Sample across a whole period, and across the partitions you care about. ## What to do about it - **Report the ceiling alongside the estimate.** "6.1 bits, from 500 samples, ceiling 8.97" is a measurement; "6.1 bits" is a claim. - **Recompute on halves and on a doubled sample.** If the figure is still climbing with more data, you are measuring the sample. - **Count distinct values seen.** When that count is a large fraction of `N`, stop and collect more rather than quoting a number. - **Treat the estimate as a lower bound** for any decision that gets worse when the true content is higher — sizing headroom, for instance, where under-reading the content is the dangerous direction. - **Re-measure after any change to the producer.** A new value, a new client, a new retry policy all move the distribution, and an old estimate quietly stops describing it.

  • How many observations do you want before quoting a Shannon entropy for a field?
    Enough that the number of distinct values you see is small next to the sample size, since the bias term scales roughly like `k/N`. A practical check needs no theory: recompute on halves of the sample and on a doubled sample. If the figure is still climbing, you are measuring the sample rather than the field.
  • The estimate stops rising as you add data — does that prove it has converged on the true value?
    It is necessary, not sufficient. A figure that is stable within one window can still miss a distribution that shifts by hour, by tenant or by client version, so re-measure over a full period and across the partitions you care about. Stability inside a slice only tells you that slice is well sampled.
  • Can a count-based estimate ever come out above the field's true entropy?
    Yes, for an individual sample — the bias result is about the average over samples, not a per-sample guarantee. A small sample that happens to look more even than the source overshoots. The point is that the opposite happens more often, and systematically so when the field has many values.

saying these in an interview costs you the question

  • Treats the count-based estimate as the field's true entropy
  • Says more samples cannot change an entropy already computed
  • Ignores that unseen values contribute zero to the estimate
  • Assumes one quiet hour represents the whole day's distribution
  • Believes the estimate can exceed log2 of the sample size