The Setting
Let and be random variables on one finite probability space, with values in a finite set of elements, that coincide outside an event of probability . The question is how much the entropy of can exceed that of , in terms of and ; and the same question for the entropy of given a second variable against that of given , when and , with values in a finite set , also coincide outside that event.
Along a walk of Gaussian integers the comparison is made for a shift in time. Quantities and attached to each time are read at a random time moved by an independent offset uniform on , and the conditional entropy of given at time is set against the one at time , for some .
Finite 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.✦ The probability of an event is . A random variable on with values in a finite set is a map .
The law of a random variable , the pushforward of along , is the finite probability law on that gives each point the total mass of its preimage: (1)✦
The entropy of a finite probability law on a finite set is the Shannon sum (2)✦ in natural logarithms and with . The entropy of a random variable is the entropy of its law .✦ The conditional entropy of a random variable given a random variable on , with values in finite sets and , is the difference (3)✦ where is the random variable with values in . The binary entropy of is .
The uniform law on a finite nonempty set is the finite probability law that gives every point of the mass .✦ Given a finite probability law on a finite set and, for each , a finite probability law on a finite set , the joint law of and the family is the finite probability law on with masses (4)✦
The Claim
Theorem 1. Let be a finite probability law on a finite set .
(a) Let and be random variables on with values in a finite set , and let be an event such that for every with . If is the probability of the complement of , then (5)✦
(b) Let and be random variables on with values in a finite set , let and be random variables on with values in a finite set , and let be an event such that and for every with . If is the probability of the complement of , then (6)✦
(c) Let be a random time, and natural numbers with , and and sequences in finite sets and . Give the joint law of and the uniform law on , let , and write for the random variable , and likewise , and . Then, with , (7)✦
In the paper, the result reads: if two laws of a pair of random variables on the same finite product alphabet of at most elements are at total variation distance at most , and and stand for the pair under the first and the second law, then .
What Is Checked
The claim is stated over finite probability laws on finite sets, the law (1) of a random variable, its entropy as the Shannon sum (2), conditional entropy as the difference (3), and, in its third part, the joint law (4) of with the uniform law on .