0
$\begingroup$

Let $P_{XYZ}$ be the joint distribution of discrete RVs $X,Y,Z$ where $Z$ is binary-valued. Let $Q_{XY}=P_{XY|Z=0}$, i.e. the distribution of $XY$ conditioned on $Z=0$. Are there lower/upper bounds on $H(X|Y)_P$ in terms of $H(X|Y)_Q$ and the probability $P[Z=0]$? (Mainly I would need an upper bound, but I would also be interested to know if some lower bound can be found.)

A somewhat similar question was asked at Confusion about conditional entropy when conditioning on another event, but was more restricted (the conditioning event was determined by $Y$ alone) and was mostly focused on the "lower bound" side of the question.

$\endgroup$

1 Answer 1

1
$\begingroup$

Going to change your notation to use more standard $H(X|Y)$ to represent $H(X|Y)_P$ and $H(X | Y, Z=0)$ to represent $H(X | Y)_Q$

\begin{align} H(X|Y) &\geq H(X | Y, Z) \quad \textrm{(conditioning reduces entropy)} \\ &= H(X|Y, Z=0) Pr(Z=0) + H(X | Y, Z=1) Pr(Z=1) \end{align}

Note that the second term on the RHS is non-negative so depending on your use case, a loose bound would be $H(X|Y) \geq H(X | Y, Z=0)Pr(Z=0)$

$\endgroup$
3
  • $\begingroup$ Unfortunately, the conditioning-reduces-entropy inequality is in the wrong direction here; what you have is a lower bound on $H(X|Y)$ (similar to that in the linked answer), not an upper bound... $\endgroup$
    – helloworld
    Commented Aug 1, 2023 at 15:56
  • $\begingroup$ My mistake. I've edited the answer. In general, $H(X|Y, Z=0)$ can vary arbitrarily. For example, we can have $Y = \mathrm{Bernoulli}(1)$ if $Z = 0$ (i.e., $Y$ is deterministic) and $Y=\mathrm{Bern}(0.5)$ if $Z = 1$. Alternatively, we can switch the indices of $Z$ so $Y$ is deterministic if $Z=1$. $H(X|Y, Z=0)$ can be larger or smaller than $H(X|Y)$ but the average value $H(X|Y, Z) \leq H(X|Y)$ $\endgroup$
    – ltcoding
    Commented Aug 2, 2023 at 18:23
  • $\begingroup$ I think that construction does not preclude the possibility of an upper bound on $H(X|Y)$ that depends on both $H(X|Y;Z=0)$ and $P[Z=0]$ though, as stated in the question. For instance, in the case of min-entropy it is known that $H_\mathrm{min}(X|Y) \leq H_\mathrm{min}(X|Y;Z=0) + \log(1/P[Z=0])$, so while it is true that $H_\mathrm{min}(X|Y)$ and $H_\mathrm{min}(X|Y;Z=0)$ can be sort of "arbitrarily different", it turns out that the amount of arbitrariness is at most $\log(1/P[Z=0])$, so to speak. I was basically wondering if something in this vein could hold for Shannon entropy as well. $\endgroup$
    – helloworld
    Commented Aug 11, 2023 at 21:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.