The Setting
Let be a random variable taking values in a finite set of elements, and a second random variable, the data from which is to be recovered. Suppose a list of candidates is attached to each value of , and that on an event of probability the list has at most entries and contains . The lemma bounds the conditional entropy , the uncertainty left in once is known, in terms of , and alone, and bounds from below the deficit .
Laws and Entropy
A finite probability law on a finite set is a function that is nonnegative at every point and whose values sum to one: (1) The points of are the outcomes, a random variable is a map from to a finite set, and an event has probability .
The pushforward of along a map from to a finite set is the finite probability law on that gives each point the total mass of its preimage: (2)✦ The law of a random variable is its pushforward .
The entropy of a finite probability law on a finite set is its Shannon sum, in natural logarithms and with : (3)✦ A random variable on has entropy , the entropy of its law.✦ For random variables and on , the pair is the random variable , and the conditional entropy of given is (4) The binary entropy of is .
The Claim
Theorem 1. Let be a finite probability law on a finite set , and let and be random variables on with values in finite sets and , where has elements. Let assign to each a subset of , let be a real number, and let be an event of probability such that at every outcome with the list has at most elements and contains . Then (5)✦ and the deficit of from is bounded below: (6)✦
In the paper, the result reads: if has at most values, is finite data and is a list of possible values of with for some , then .
What Is Checked
The claim is stated over finite probability laws (1), their pushforwards (2), the entropy of a law as its Shannon sum (3), the entropy of a random variable as the entropy of its law, and the conditional entropy (4), with the binary entropy .