 Correlated binary variables

Let $A$ be a fair bit, let $N$ be an independent Bernoulli random variable with $\mathbb{P}(N=1)=p$, and set $B=A\oplus N$, where $\oplus$ is exclusive or. Thus $N=1$ flips the first bit. This constructs a binary symmetric channel with a fair input, for $0\le p\le 1$. The joint probability mass function isThe column sums show that $B$ is also a fair bit, whatever $p$ is. Both marginal distributions therefore have information entropy one bit. Given $A$, only the flip decision remains unknown, giving conditional entropy $H(B\mid A)=h_2(p)$, whereis the binary entropy, with $h_2(0)=h_2(1)=0$. The chain rule for information entropy and the definition of mutual information now give

Take $p=1/10$. The four joint probabilities, in row order, are $(0.45,0.05,0.05,0.45)$. Directly from the definition of joint entropy,Conditioning on either value of $A$ gives probabilities $0.9$ and $0.1$ for the two values of $B$, henceAdding $H(A)+H(B)=2$ would overcount by exactly $I(A;B)$. These are average uncertainties under the stipulated probability distribution; the four possible pairs are still represented by four distinct outcomes.

There is another way to see the decomposition: $(A,B)\mapsto (A,A\oplus B)=(A,N)$ is a bijection. It merely relabels the four outcomes, so it preserves joint entropy. The independence of $A$ and $N$ then gives $H(A,B)=H(A,N)=H(A)+H(N)=1+h_2(p)$. Describing the initial bit and the flip decision separates shared uncertainty from new uncertainty.

At $p=0$, the bits are identical: $B=A$, so $H(B\mid A)=0$ and $I(A;B)=1$. At $p=1$, they are complementary: $B=1-A$, with exactly the same conditional entropy and mutual information. In either case, observing one determines the other. At $p=1/2$, all four joint probabilities are $1/4$; the bits are independent, $H(A,B)=2$, and $I(A;B)=0$. Perfect disagreement is therefore just as informative as perfect agreement.

For $p>1/2$, guessing $A=1-B$ succeeds with probability $p$, better than guessing $A=B$. Changing $B$ to $1-B$ replaces $p$ by $1-p$ and preserves mutual information, since the relabeling is invertible. What matters is how well the observation distinguishes the input, rather than how often its symbol matches the input. The same symmetry makes the binary entropy curve peak at independence, while the mutual information curve reaches its minimum there.