What must be true of two record columns for their joint entropy to equal the sum of their separate entropies?

middleshould knowfreq 40%

answer

additive only in the independence case
every cell equals the product of margins
margins alone constrain nothing inside
uncorrelated is weaker than independent
any dependence makes the joint strictly smaller

basics

~10 s

Exactly independence: H(X,Y) = H(X) + H(Y) holds if and only if every joint probability factorises as p(x,y) = p(x) p(y). Any dependence at all makes the joint strictly smaller than the sum.

solid answer

~40 s

The chain rule gives H(X, Y) = H(X) + H(Y | X), so the sum form holds exactly when H(Y | X) = H(Y), and that is the equality case of the conditioning inequality: independence. Operationally, every cell of the joint table must equal the product of its two margin probabilities. That is a stronger demand than it sounds. Matching margins are not enough, and zero correlation is not enough either, since correlation only detects a monotone-linear relationship between numeric codes while independence forbids any relationship at all. The payoff of additivity is concrete: only then can the two columns be modelled and stored separately with nothing lost, because neither predicts the other. Under any dependence, the pair is strictly cheaper described together.

The chain rule gives `H(X, Y) = H(X) + H(Y | X)`, so the sum form holds exactly when `H(Y | X) = H(Y)`, and that is the equality case of the conditioning inequality: **independence**. Operationally, every cell of the joint table must equal the product of its two margin probabilities. That is a stronger demand than it sounds. Matching margins are not enough, and zero correlation is not enough either, since correlation only detects a monotone-linear relationship between numeric codes while independence forbids any relationship at all. The payoff of additivity is concrete: only then can the two columns be modelled and stored separately with nothing lost, because neither predicts the other. Under any dependence, the pair is strictly cheaper described together.

code

pseudocode · 14 lines

pseudocode

// counts[x][y] over N rows of a two-column log
N = total rows

for each x:
    p_x = row_total(x) / N
    for each y:
        p_y  = column_total(y) / N
        p_xy = counts[x][y] / N
        if abs(p_xy - p_x * p_y) > tolerance:
            report "cell (x, y) contradicts independence"
            stop

report "no cell contradicts independence at this tolerance"
// note: failing to contradict is not a proof of independence

go deeper

for a junior

Remember the direction of the bound: describing two fields together never costs more than describing them apart, and the two costs match only when the fields are genuinely unrelated.

for a middle

State the condition as an if-and-only-if and show the check: every joint cell equal to the product of its margins, not merely margins that look plausible.

for a senior

Bring the sampling problem with you: sparse tables cannot settle independence, and acting on an unchecked additivity assumption overprices or over-simplifies a real record layout.

for a principal

Treat additivity as the assumption that lets teams own fields separately. Say what it is worth when it holds and what breaks in modelling and storage when it quietly stops holding.

The equality case

Two standard facts meet here. The chain rule, H(X, Y) = H(X) + H(Y | X), is an identity that always holds. The conditioning inequality, H(Y | X) <= H(Y), holds with equality exactly when the columns are independent. Put them together and you get the bound everyone quotes:

H(X, Y) <= H(X) + H(Y), with equality if and only if p(x, y) = p(x) * p(y) for every cell.

So "when is the joint additive?" has one answer, and it is an if-and-only-if in both directions. Independence gives additivity; additivity gives independence back.

Checking it against a joint table

The check is mechanical, cell by cell:

Compute each row's total and each column's total, divided by the number of rows, to get the two margins.
For each cell, compare its observed probability against the product of its margins.
One cell that disagrees beyond sampling noise is enough to kill independence; every cell must agree for it to survive.

Two things this check cannot do. It cannot prove independence from a finite sample, only fail to contradict it at whatever tolerance you chose. And it degrades badly when the table is sparse, because a cell seen twice tells you almost nothing, and a table with many distinct values in either column is mostly such cells.

Why "uncorrelated" is not enough

A frequent and expensive substitution. Correlation is defined on numbers and measures a linear relationship; independence is defined on distributions and forbids any relationship. Two columns can be perfectly uncorrelated and completely dependent: let one column take values -1, 0 and 1 with equal probability and the other be its square. The correlation is zero, yet knowing the first column determines the second, so the conditional entropy is 0 rather than the marginal, and the joint is strictly below the sum. A categorical column such as a region code has no natural numeric order at all, so a correlation coefficient computed over its encoded values is not even measuring the right thing.

claim about two columns	does it give additive joint entropy?
every joint cell equals the product of its margins	yes, this is exactly the condition
both columns are uniform over their own values	no, margins constrain nothing about the interior
the columns are uncorrelated	no, correlation is weaker than independence
neither column determines the other perfectly	no, partial dependence still shrinks the joint
the columns come from different systems	no, common causes make unrelated-looking fields dependent

What additivity actually buys

Additivity is the licence to treat the columns separately with no loss:

each can be modelled and described on its own, and the total is the same as describing them jointly;
no conditional model has to be built, kept correct, or carried alongside the data;
a per-column summary loses nothing that a joint summary would have kept.

That is why the question is worth asking about a real record: independence is the case where the simplest thing you could do is also optimal. Dependence is where joint description pays, and the chain rule prices exactly how much.

Partial dependence is the normal case

Real columns are rarely at either extreme. A region beside the data centre it routed to is strongly but not perfectly dependent: if each region sends 7 rows in 8 to its home data centre, the conditional entropy is 0.544 bits against a marginal of 2 bits, and the joint is 2.544 rather than the additive 4. Nothing about that is unusual, and the useful statement is not "they are dependent" but the number: the pair costs 2.544 bits a row, so a design that assumes additivity is overpaying by about 36%.

The usual errors

Claiming the joint can exceed the sum. It cannot; the sum is an upper bound.
Treating uncorrelated columns as independent, or checking only that the margins look right.
Assuming independence implies the two columns have similar entropies. It says nothing about their sizes, only about their arrangement.
Deciding independence from a sparse table, where most cells are too thin to contradict anything.

## The equality case Two standard facts meet here. The chain rule, `H(X, Y) = H(X) + H(Y | X)`, is an identity that always holds. The conditioning inequality, `H(Y | X) <= H(Y)`, holds with equality exactly when the columns are **independent**. Put them together and you get the bound everyone quotes: `H(X, Y) <= H(X) + H(Y)`, with equality if and only if `p(x, y) = p(x) * p(y)` for every cell. So "when is the joint additive?" has one answer, and it is an if-and-only-if in both directions. Independence gives additivity; additivity gives independence back. ## Checking it against a joint table The check is mechanical, cell by cell: 1. Compute each row's total and each column's total, divided by the number of rows, to get the two margins. 2. For each cell, compare its observed probability against the product of its margins. 3. One cell that disagrees beyond sampling noise is enough to kill independence; every cell must agree for it to survive. Two things this check cannot do. It cannot *prove* independence from a finite sample, only fail to contradict it at whatever tolerance you chose. And it degrades badly when the table is sparse, because a cell seen twice tells you almost nothing, and a table with many distinct values in either column is mostly such cells. ## Why "uncorrelated" is not enough A frequent and expensive substitution. Correlation is defined on numbers and measures a **linear** relationship; independence is defined on distributions and forbids **any** relationship. Two columns can be perfectly uncorrelated and completely dependent: let one column take values -1, 0 and 1 with equal probability and the other be its square. The correlation is zero, yet knowing the first column determines the second, so the conditional entropy is 0 rather than the marginal, and the joint is strictly below the sum. A categorical column such as a region code has no natural numeric order at all, so a correlation coefficient computed over its encoded values is not even measuring the right thing. | claim about two columns | does it give additive joint entropy? | |---|---| | every joint cell equals the product of its margins | yes, this is exactly the condition | | both columns are uniform over their own values | no, margins constrain nothing about the interior | | the columns are uncorrelated | no, correlation is weaker than independence | | neither column determines the other perfectly | no, partial dependence still shrinks the joint | | the columns come from different systems | no, common causes make unrelated-looking fields dependent | ## What additivity actually buys Additivity is the licence to treat the columns separately with no loss: - each can be modelled and described on its own, and the total is the same as describing them jointly; - no conditional model has to be built, kept correct, or carried alongside the data; - a per-column summary loses nothing that a joint summary would have kept. That is why the question is worth asking about a real record: independence is the case where the simplest thing you could do is also optimal. Dependence is where joint description pays, and the chain rule prices exactly how much. ## Partial dependence is the normal case Real columns are rarely at either extreme. A region beside the data centre it routed to is strongly but not perfectly dependent: if each region sends 7 rows in 8 to its home data centre, the conditional entropy is 0.544 bits against a marginal of 2 bits, and the joint is 2.544 rather than the additive 4. Nothing about that is unusual, and the useful statement is not "they are dependent" but the number: the pair costs 2.544 bits a row, so a design that assumes additivity is overpaying by about 36%. ## The usual errors - Claiming the joint can **exceed** the sum. It cannot; the sum is an upper bound. - Treating uncorrelated columns as independent, or checking only that the margins look right. - Assuming independence implies the two columns have similar entropies. It says nothing about their sizes, only about their arrangement. - Deciding independence from a sparse table, where most cells are too thin to contradict anything.

If two columns are independent, what does the chain rule reduce to?
The conditional term collapses to a marginal: H(Y|X) = H(Y), so H(X,Y) = H(X) + H(Y). Every slice's distribution matches the pooled one, conditioning buys nothing, and describing the two columns separately costs exactly what describing them together does.
Does zero correlation between two columns guarantee an additive joint entropy?
No. Correlation measures a linear relationship between numeric codes; independence forbids any relationship. A column taking -1, 0, 1 equally and a second column holding its square are uncorrelated yet one determines the other, so the joint entropy is strictly below the sum. For categorical columns a correlation coefficient is not even well defined.
Can a finite sample of rows prove that two columns are independent?
No. Cell-by-cell agreement with the margins can only fail to contradict independence at the tolerance you picked. Sparse tables make this weak in both directions: thin cells rarely contradict anything, and a handful of rows in a slice makes the slice look more deterministic than it is.

saying these in an interview costs you the question

Treats uncorrelated columns as independent for entropy purposes
Claims the joint entropy can exceed the sum of the marginals
Says matching margins are enough to establish independence
Thinks a single dependent cell still leaves the sum form valid
Assumes independent columns must have similar entropies

What must be true of two record columns for their joint entropy to equal the sum of their separate entropies?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

The equality case

Checking it against a joint table

Why "uncorrelated" is not enough

What additivity actually buys

Partial dependence is the normal case

The usual errors

▾common follow-ups3 questions

▾red flags5 flags

The equality case

Checking it against a joint table

Why "uncorrelated" is not enough

What additivity actually buys

Partial dependence is the normal case

The usual errors

answer

go deeper