Proof of `High edge cost forces a strict entropy decrease`
groundedproofs/Lax263307Proofs/EntropyDecrease.lean · lax-263307
What this proof establishes
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
Exceeding the edge-cost threshold forces a positive-cost vertex whose conditioning decreases entropy by more than the prescribed amount.
Proof strategy
Normalize the costs by the target size and apply the average entropy-gap inequality to the joint distribution. A strictly small weighted average has a strictly small term with positive weight. The checked conditional probability identities identify that term with the next conditioning step.
Attribution
Bonnet–Chang, proof of Lemma 12, equation (18).