The Setting
A Boolean function of a uniform cube point and a noisy copy of that point have a joint distribution whose mutual information can be expressed through bias entropy. For a nonnegative integer , the uniform cube assigns mass to each point.✦ The uniform average of a real function is the scalar in (1). (1)✦
Write , with natural logarithms throughout the entropy definitions, and use the convention .✦ The entropy gap of a bias is the scalar defined by (2). (2)✦ For a bias , the bias entropy is given by (3). (3)✦ Averaging the bias entropy over the cube gives the mean bias entropy of a field , as in (4). (4)✦ The information deficit of a field is the entropy difference in (5). (5)✦ The logarithmic product is the real function that multiplies a real argument by its natural logarithm.✦
The transition kernel of a binary symmetric channel on with crossover probability is the function of two cube points given by (6). (6)✦ The noise kernel with correlation is the function of two cube points in (7). (7)✦ The noise operator sends a real function on to the function defined by (8). (8)✦ The sign representation of a Boolean function is the real function on given by (9). (9)✦
Let be uniform on , and let be the channel output with conditional law . The joint probability of and , for , is defined by (10). (10)✦ Summing over the observation gives the function marginal in (11). (11)✦ The observation marginal is given by (12). (12)✦ The mutual information , measured in bits, is the functional of the joint law of and given by (13). (13)✦ The binary entropy of a bit with success probability is the function in (14), also measured in bits. (14)✦
The Claim
Theorem 1. Let be a Boolean function, and let . For the uniform input and binary symmetric channel output , the mutual information and information deficit satisfy (15). (15)✦
What Is Checked
The identity (15) is stated over Boolean functions on any uniform cube and binary symmetric channels whose crossover probability lies in .