Proof of `Edge mass bounds the average entropy decrease`
What this proof establishes
no assumptions
Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.
Description
The expected entropy decrease is at least the product probability of ordered adjacent pairs.
Proof strategy
The entropy chain rule expresses the decrease as a relative-entropy sum. The inequality bounds each positive-support term below by joint mass minus product mass. Edge pairs have zero joint mass, so their product mass contributes to the gap. Zero marginals are treated explicitly. Divide by to obtain the inequality in bits.
Attribution
Bonnet–Chang, proof of Lemma 12, equations (17) and (18).