# Under what conditions does the function C = f(A,B) satisfy H(C|A) = H(B)?

Suppose we have a function $$f$$,

$$C = f(A,B),$$

where $$A$$, $$B$$ and $$C$$ are random variables.

I notice that when the random variables are binary ($$\{0, 1\}$$) and $$f$$ is the XOR operation, we have the following identity:

$$H(C|A) = H(B),$$

where $$H(B)$$ is the entropy of $$B$$ and $$H(C|A)$$ is the conditional entropy of $$C$$ given $$A$$.

Obviously this is not true for a general $$f$$. What I am interested to know is, is there a set of conditions on $$f$$ and $$A,B,C$$, under which the identity above holds.

• The function needs to be injective with respect to its second argument. – Yuval Filmus Mar 28 at 8:04
• @YuvalFilmus Ah that makes sense! I didn't know the term "injective". Do you want to elaborate a bit and write an answer so I can upvote it? – hklel Mar 28 at 8:11

The following answer assumes that $$A,B$$ are independent, and that $$A,B$$ have full support on their respective domains (the latter is without loss of generality). For the general case, see the other answer.

Let's write your equation in a slightly different way: $$H(B) = H(f(A,B)|A) = \operatorname*{\mathbb{E}}_{a \sim A} H(f(a,B)).$$ Clearly $$H(f(a,B)) \leq H(B)$$, with equality if and only if $$f(a,b_1) \neq f(a,b_2)$$ whenever $$b_1 \neq b_2$$. We deduce that $$H(B) = H(f(A,B)|A)$$ if and only if $$f$$ is injective in its second argument, i.e., for all $$a$$ and $$b_1 \neq b_2$$, we have $$f(a,b_1) \neq f(a,b_2)$$.

• $H(f(A,B)|A)=\mathbb{E}_aH(f(a,B)|A=a)$, and $H(f(a,B)|A=a)$ is different from $H(f(a,B))$ since $A$ and $B$ may be dependent. – xskxzr Mar 28 at 8:45
• The conclusion that $f$ is injective in the second argument is only correct if $\Pr(A=a)>0$ and $\Pr(B=b)>0$ for all $(a,b)\in\operatorname{dom}(f)$. – Emil Jeřábek supports Monica Mar 28 at 10:03

Note

\begin{align} 0&=H(C|A,B)\\ &=H(A,B,C)-H(A,B)\\ &=H(B|A,C)+H(C|A)+H(A)-H(A,B)\quad\text{(chain rule)}\\ &=H(B|A,C)+H(C|A)-H(B|A), \end{align}

so $$H(C|A)=H(B)$$ is equivalently $$H(B|A,C)+H(B)-H(B|A)=0$$. Also note $$H(B|A,C)\ge 0$$ and $$H(B)\ge H(B|A)$$, your condition is equivalently $$H(B|A,C)=0\wedge H(B)=H(B|A)$$.

For a human-readable explanation, $$H(B|A,C)=0$$ means $$B$$ is determined by $$A$$ and $$C$$, that is, for any fixed $$a$$ in the support of $$A$$, $$f(a,b)$$ as a function of $$b$$ with domain $$\{b\mid \mathrm{Pr}\{A=a, B=b\}>0\}$$ is an injection. $$H(B)=H(B|A)$$ means $$A$$ and $$B$$ are independent of each other.

• The conclusion that $f$ is injective in the second argument is only correct if $\Pr(A=a)>0$ and $\Pr(B=b)>0$ for all $(a,b)\in\operatorname{dom}(f)$. – Emil Jeřábek supports Monica Mar 28 at 10:04
• @EmilJeřábek Thanks, fixed. – xskxzr Mar 28 at 10:34