Conditional entropy: $H(X | Y)$ large implies $H(X | Y, X \neq Y)$ large?

Suppose that $X$ and $Y$ are two random variables that are defined on the same support. Furthermore, suppose that $H(X | Y) = \log n$ for some $n$. I am now interested in how much the term $H(X | Y, X \neq Y)$ may differ from $H(X | Y)$.

Suppose that $X|Y=y$ is uniformly distributed (for every y). Intuitively, as $H(X | Y) = \log n$, for a typical element $y$ in the support of $X$ and $Y$, we also have $H(X | Y=y) = \log n$. Thinking about a uniform distribution, X takes on at least n different values, and, therefore, we should expect $H(X | Y, X \neq Y) \ge \log(n-1)$ as the conditioning on $X \neq Y$ eliminates only a single potential element.

Can such a result be obtained in full generality?

Thanks very much for your answers. I am new to stackexchange so I don't know yet where and how to respond to suggested answers.

The fact that you can bound $H(X|Y) - H(X|Y, X \neq Y) \le \log(\frac{n}{n-1})$ is very interesting, as you can compute: $\log(\frac{n}{n-1}) = \log( \frac{1}{1-\frac{1}{n}} ) = - \log(1-\frac{1}{n}) = -\Theta(\log(e^{-\frac{1}{n}})) = \Theta(\frac{1}{n})$. This result matches the intuition very well as if the entropy $H(X|Y) = \log(n)$ then knowing that $H(X|Y, X \neq Y)$ essentially eliminates only one possible choice for $X$. This is somehow quantified by the $\Theta(\frac{1}{n})$.

• I do not know the answer, but if you do not put any restriction on Y, the general case can be reduced to the case where Y is a constant, which is probably easier to consider. Dec 7 '14 at 22:37
• Can you say formally what the notation $H(X|Y,X\neq Y)$ means?
– usul
Dec 8 '14 at 1:41
• I am interpreting it as in Thomas' answer: $\sum_{x,y} P(x,y~|~X\neq Y) \log(1/P(x~|~y, X\neq y))$.
– usul
Dec 8 '14 at 17:41
• Hi usul, that's exactly what I meant by it. Dec 10 '14 at 21:16

Let $X$ and $Y$ be random variables with the same range. Let $Z$ be the indicator of the event $X \ne Y$. By the chain rule, $$H(X|Y,Z) = H(X,Z|Y)-H(Z|Y).$$ Since $Z$ is determined by $X$ and $Y$, we have $H(X,Z|Y)=H(X|Y)$. Now, by the definition of conditional entropy, $$H(X|Y,Z) = \underset{z \leftarrow Z}{\mathbb{E}}[H(X|Y,Z=z)] = \mathbb{P}[X \ne Y] \cdot H(X|Y, X \ne Y) + \mathbb{P}[X = Y] \cdot H(X|Y, X = Y).$$ Clearly $H(X|Y, X = Y)=0$. Combining the above gives $$\mathbb{P}[X \ne Y] \cdot H(X|Y, X \ne Y) = H(X|Y) - H(Z|Y).$$ Now we have an equation linking the quantities we want. We have $$0 \leq H(Z|Y) \leq H(Z) = H_2(p) \leq 1,$$ where $p = \mathbb{P}[X \ne Y]$. In particular, $$p \cdot H(X|Y,X \ne Y) \leq H(X|Y) \leq p \cdot H(X|Y,X \ne Y) + H_2(p).$$

For convenience let $H(X|Y) = \log(n)$, then

$$-\infty ~~\leq~~ H(X|Y) - H(X|Y,X\neq Y) ~~\leq~~ \log\left(\frac{n}{n-1}\right)$$

and both sides have tight examples (i.e. as $p\to 0$ it can be arbitrarily negative, and your example matches the upper bound). More specifically, if $p = \Pr[X \neq Y]$, then:

$$H(X|Y) - H(X|Y,X\neq Y) ~~ \geq ~~ -\frac{(1-p)H(X|Y)}{p}$$ and $$H(X|Y) - H(X|Y,X\neq Y) ~~\leq~~ \log\frac{1}{p} + \frac{1-p}{p}\left[\log\frac{1}{1-p} ~-~ H(X|Y)\right]$$

and we have tight examples for the second, and arbitrarily close to tight examples for the first, for every $p,H(X|Y)$.

There will be two steps to the proof: (1) prove an upper bound and matching examples for $H(X|Y,Z)$ where $Z$ is an indicator; (2) convert these to your quantity of interest $H(X|Y,X\neq Y)$.

Upper Bound

Step 1.

Claim 1. Let $Z$ be the indicator for $X\neq Y$ and let $p = \Pr[X\neq Y]$. Then $$H(X|Y) - H(X|Y,Z) \leq H(p)$$ and for any fixed values of $H(X|Y)$ and $p$, we can construct tight examples.

Proof. The natural quantity to consider is $$H(X|Y) - H(X|Y,Z)$$ where $Z$ is the indicator, $Z=1$ if $X \neq Y$ and $Z=0$ otherwise. Let $p = \Pr[X\neq Y] = \Pr[Z=1]$.

Then as Thomas points out, by the chain rule and the fact that $H(X,Y,Z) = H(X,Y)$, $$H(X|Y) - H(X|Y,Z) = H(Z|Y) \leq H(p) . ~~~~~~~~ (*)$$

Examples showing tightness: Let $Y$ be distributed arbitrarily; then conditioned on $Y=y$, we let $X=y$ with probability $1-p$ and with probability $p$ we let $X$ be distributed arbitrarily on any set not containing $y$. To be very concrete, you could let $Y=0$ always and let $X=0$ with probability $1-p$ and otherwise $X$ is uniform on $\{1,\dots,m\}$. Choose $m$ to get the desired value of $H(X|Y)$.

In these examples, $H(Z|Y) = H(Z) = H(p)$. So we can make the inequality $(*)$ tight for any $p$ and any $H(X|Y)$. $\square$

Step 2.

"Theorem" 1. $$H(X|Y) - H(X|Y, X\neq Y) \leq \log\frac{1}{p} + \frac{1-p}{p}\left[\log\frac{1}{1-p} ~ - ~ H(X|Y) \right]$$ and for any fixed $H(X|Y)$ and $p$ there are tight examples.

Proof. Now, again as Thomas points out, we have $$H(X|Y,Z) = p\cdot H(X|Y, X \neq Y) .$$ Now, by plugging in to $(*)$, we have the inequality $$H(X|Y) - p\cdot H(X|Y, X\neq Y) \leq H(p) . ~~~~~~~~ (**)$$ and we can make this tight for any $p$. Let $H(X|Y) = p\cdot H(X|Y) + (1-p)H(X|Y)$ and rearrange: \begin{align} H(X|Y) - H(X|Y, X\neq Y) &\leq \frac{H(p) - (1-p)H(X|Y)}{p} \\ &= \log\frac{1}{p} + \frac{1-p}{p}\left[\log\frac{1}{1-p} ~ - ~ H(X|Y) \right] . \end{align} and, again, we can make this tight using the examples from before (since we have only renamed things and rearranged the inequality). $\square$

Claim 2. For any fixed $H(X|Y) > 0$, as $p \to 0$, we always have $$H(X|Y,Z) - H(X|Y,X \neq Y) \to -\infty .$$

Proof. In the bound of the "theorem", for small enough $p$, the upper bound is $\log\frac{1}{p} - \frac{1}{p}\Theta(H(X|Y))$, which approaches $-\infty$ as $p \to 0$ for all fixed $H(X|Y)$. $\square$

Claim 3. For any fixed $H(X|Y)$, we have $$H(X|Y,Z) - H(X|Y,X\neq Y) \leq \log\frac{2^{H(X|Y)}}{2^{H(X|Y)}-1} ,$$ and there are tight examples. In such examples, $p = 1 - 2^{-H(X|Y)}$.

Proof. Taking the bound in the "theorem" and taking the derivative with respect to $p$, we find that the upper bound is maximized uniquely at $p = 1 - 2^{-H(X|Y)}$. In that case, the quantity inside the brackets is zero, and we obtain

\begin{align} H(X|Y) - H(X|Y, X\neq Y) &\leq \log\frac{1}{p} \\ &=\log\frac{2^{H(X|Y)}}{2^{H(X|Y)}-1} . \end{align}

Again, for any $H(X|Y)$, the prior examples with this choice of $p$ make this inequality tight. $\square$

Lower Bound

Step 1.

Claim 4. For any $p$, $$H(X|Y) - H(X|Y,Z) \geq 0$$ and we can construct examples that are arbitrarily close to $0$.

Proof. As stated above, $H(X|Y) - H(X|Y,Z) = H(Z|Y) \geq 0$. To construct examples arbitrarily close to $0$, fix $p$. The intuition is $H(p)$ is concave, so we will have sometimes $\Pr[Z|Y] = \epsilon$ and sometimes $\Pr[Z|Y] = 1-\epsilon$, so that $H(Z|Y) = H(\epsilon) \to 0$, yet still $H(Z) = H(p)$.

Let $Y = -1$ with probability $1-p$ and $Y = 0$ with probability $p$. If $Y=-1$, then with probability $\epsilon$ we have $X=Y$ and otherwise $X$ is uniform on $\{1,\dots,m\}$. If $Y=0$, then with probability $1-\epsilon$ we have $X=Y$ and otherwise $X$ is uniform on $\{1,\dots,m\}$. Now we can check that $H(Z|Y) = H(\epsilon)$ and $p = \Pr[Z] = (1-p)\cdot \epsilon + p\cdot(1-\epsilon) = p$. Taking $\epsilon \to 0$ gives the example. $\square$

Step 2.

"Theorem" 2. For any $p$ and $H(X|Y)$, $$H(X|Y) - H(X|Y,X\neq Y) \geq -\frac{(1-p)H(X|Y)}{p}$$ and there are examples arbitrarily close.

Proof. Again we have $p\cdot H(X|Y,X\neq Y) = H(X|Y,Z)$, so by the previous claim, $$H(X|Y) - p\cdot H(X|Y,X\neq Y) \geq 0 .$$ Again let $H(X|Y) = p\cdot H(X|Y) + (1-p)H(X|Y)$ and rearrange. By the previous claim, we have arbitrarily close examples (since we have only rearranged the inequality). $\square$

• The lower bound can be simplified: Let $Y=0$ be constant. Let $X=Y=0$ with probability $1-p$ and $X\ne Y=0$ with probability $p$. Let $k=H(X|X\ne Y)=H(X|Y,X \ne Y)$. Then $H(X|Y)=H(X)=H_2(p)+p\cdot k \leq 1 + p k$. Clearly, as $k \to \infty$, $H(X|Y,X \ne Y) - H(X|Y) \to \infty$, so long as $p < 1-\omega(1/k)$. Dec 9 '14 at 4:09