patternMinor
Under what conditions does the function C = f(A,B) satisfy H(C|A) = H(B)?
Viewed 0 times
thewhatfunctionsatisfyunderdoesconditions
Problem
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.
$$
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.
Solution
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.
\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.
Context
StackExchange Computer Science Q#106156, answer score: 8
Revisions (0)
No revisions yet.