skip to content

What does a conditional entropy H(data centre | region) of 0.54 bits tell you about a two-column routing log?

level: middleimportance: must knowfreq 55%

answer

  1. uncertainty left over, not total
  2. average across the conditioning column
  3. per-slice entropy, weighted by slice share
  4. zero means one column determines the other
  5. residual sits in the exception rows

basics

~20 s

Conditional entropy H(data centre | region) is the data-centre uncertainty left, on average, once the region is known. At 0.54 bits against 2 bits unconditioned, the region nearly fixes the data centre, but not completely.

solid answer

~40 s

`H(Y | X)` is the average number of bits of `Y` still unknown after `X` is revealed. You compute it in two steps: take the entropy of the data-centre values *inside* each region, then average those per-region entropies weighted by how often each region occurs. In a log whose four regions are equally common and whose data centre is the region's home one 7 rows in 8, every region contributes H(7/8, 1/8) = 0.544 bits, so H(data centre | region) = 0.54 bits against H(data centre) = 2 bits with the region hidden. Those remaining 0.54 bits are not spread evenly over the log: they are mostly the rows that left the home mapping. Zero would have meant the region determined the data centre outright.

code

pseudocode · 16 lines
pseudocode
// counts[x][y] = rows seen with region x and data centre y
total = sum of all counts
H_cond = 0

for each region x:
    n_x = sum over y of counts[x][y]
    if n_x == 0:
        continue                      // region never observed
    h_x = 0
    for each data centre y:
        if counts[x][y] > 0:          // skip empty cells before the log
            p = counts[x][y] / n_x    // renormalised inside the slice
            h_x = h_x - p * log2(p)
    H_cond = H_cond + (n_x / total) * h_x

return H_cond   // bits of data centre still unknown after the region

go deeper

for a junior

Recall the shape of the idea: entropy counts bits of uncertainty, and a conditional entropy counts the bits still left after you are told another field's value. Zero means fully determined.

for a middle

Be able to compute it from a small joint table out loud: entropy within each slice, then a frequency-weighted average of those. State what zero and what the unconditioned value each mean.

for a senior

Show that you read it as an average over a measured window. Say where the residual bits actually sit, and what a slice with very few rows does to the estimate before you act on the number.

for a principal

Frame it as a decision input: it prices a field pair and bounds what a derivation rule can promise, but it never licenses dropping data on its own. Say what else you would need measured.

## The quantity in one line **Conditional entropy** `H(Y | X)` is the average number of bits of uncertainty that remain about column `Y` once the value of column `X` is known. Three things it is not, and each is a routine interview slip: - it is not the entropy of one particular region's rows (that is `H(Y | X = x)`, one slice); - it is not the amount by which knowing the region *helps* (that reduction is a separate, separately named quantity with its own topic); - it is not a per-row guarantee, because it is an average. The setting throughout: each row of a log records the **region** a request arrived in and the **data centre** it was routed to. Both columns take four values. ## How it is computed from a joint table Two steps, in this order. 1. For each region `x`, look only at the rows carrying that region and take the entropy of the data-centre values inside that slice: `H(Y | X = x) = -sum over y of p(y given x) * log2 p(y given x)`. 2. Average those slice entropies, weighting each by how often the region occurs: `H(Y | X) = sum over x of p(x) * H(Y | X = x)`. The weighting in step 2 is the part candidates drop. A region holding 1% of the rows contributes 1% of its own entropy, no matter how chaotic that slice is. Note also that the conditional probabilities in step 1 are renormalised **within** the slice: they sum to one per region, not across the table. ## The worked log Four regions, each a quarter of the rows. Each region sends 7 rows in 8 to its home data centre and 1 row in 8 to one failover data centre, cyclically, so each data centre also ends up holding a quarter of the rows. | quantity | value | what it says | |---|---|---| | entropy of the region column | 2 bits | four equally likely regions | | entropy of the data-centre column | 2 bits | pooled, it is also uniform over four | | data centre given region | 0.544 bits | H(7/8, 1/8), the same inside every region | | region given data centre | 0.544 bits | equal here only because both margins are uniform | | joint entropy of the pair | 2.544 bits | the region's 2 bits plus the residual | H(7/8, 1/8) works out as 0.875 * log2(8/7) + 0.125 * log2(8) = 0.169 + 0.375 = 0.544 bits. ## Reading the number The scale runs between two anchors, and the useful reading is where you sit between them: - **0 bits** — the region determines the data centre in every row. The second column is a function of the first and carries nothing new. - **2 bits** — knowing the region changes nothing: inside every region the four data centres appear in the same proportions as in the log overall. That is the independence case. - **0.54 bits** — the region predicts the data centre well but not perfectly. Concretely, 1 row in 8 departs from its region's home data centre, and the residual is the cost of saying **which** rows those are and where they went. The residual is also lumpy rather than smooth. A conforming row costs log2(8/7) = 0.19 bits of surprisal; a departing row costs log2(8) = 3 bits. Weighted, the departing eighth supplies 0.375 of the 0.544 bits, about 69% of the total, from 12.5% of the rows. ## Why the direction matters `H(Y | X)` and `H(X | Y)` are different quantities and generally different numbers. They came out equal in this log only because both columns happen to be uniform over four values. The identity that pins their relationship is the chain rule read both ways, which forces `H(X | Y) - H(Y | X) = H(X) - H(Y)`. So whenever the two columns have different entropies, so do the two conditionals, and "the conditional entropy of these columns" without a direction is an ambiguous phrase. ## Where this lands at work A near-deterministic column pair is common in real records: a region beside the data centre it routes to, a status code beside a category, a customer identifier beside a country. Conditional entropy is how you say *how* near, in units you can then put into a storage or modelling argument, instead of eyeballing the table and calling the second column redundant. Two practical cautions: the number is estimated from a finite window of rows, so a slice with only a handful of rows will look more deterministic than it is; and it is an average over the window you measured, which is not a promise about the next window.

  • What would H(data centre | region) = 2 bits mean in this log?
    It equals the unconditioned entropy of the data-centre column, so the region removes nothing on average: inside every region the four data centres appear in the same proportions as in the log overall. That is the independence case, and the chain rule then prices the pair at the full 4 bits a row.
  • Is H(region | data centre) necessarily the same number?
    No. It equals 0.54 bits here only because both columns happen to be uniform over four values. Reading the chain rule both ways gives H(X | Y) - H(Y | X) = H(X) - H(Y), so the two conditionals agree exactly when the two marginal entropies do. Always state which column is being conditioned on.
  • Why does a rarely seen region barely move the number?
    Each slice enters the sum multiplied by its share of rows. A region holding 1% of the log contributes at most 1% of its own entropy, so even a slice that is maximally uncertain shifts the average by a fraction of a bit. That weighting is also why the average can stay low while one slice is terrible.

saying these in an interview costs you the question

  • Treats H(Y|X) as one particular region's entropy rather than the average
  • Says a low conditional entropy means the columns are independent
  • Reads 0.54 bits as a per-row guarantee instead of an average
  • Assumes H(Y|X) and H(X|Y) are always the same number
  • Averages the per-region entropies without weighting by region frequency