<p>This might be a partial answer to your question:</p>

<p>Let $X$ and $Y$ be random variables with the same range. Let $Z$ be the indicator of the event $X \ne Y$. By the <a href="http://en.wikipedia.org/wiki/Conditional_entropy#Chain_rule" rel="nofollow">chain rule</a>,
$$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).$$</p>

CC BY-SA 3.0
2014-12-08T07:02:57.923Z
2014-12-08T07:02:57.923Z
Thomas Steinke
<p>For convenience let $H(X|Y) = \log(n)$, then</p>

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

<p>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:</p>

<p>$$ 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] $$</p>

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

<p>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)$.</p>

<h2>Upper Bound</h2>

<p><strong>Step 1.</strong></p>

<blockquote>
  <p><em>Claim 1.</em> 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.</p>
</blockquote>

<p><em>Proof.</em> 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]$.</p>

<p>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) . ~~~~~~~~ (*) $$</p>

<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)$.</p>

<p>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$</p>

<p><strong>Step 2.</strong></p>

<blockquote>
  <p><em>"Theorem" 1.</em>
   $$ 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.</p>
</blockquote>

<p><em>Proof.</em> 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) &amp;\leq \frac{H(p) - (1-p)H(X|Y)}{p}  \\
                          &amp;= \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$</p>

<blockquote>
  <p><em>Claim 2.</em> For any fixed $H(X|Y) &gt; 0$, as $p \to 0$, we always have
  $$ H(X|Y,Z) - H(X|Y,X \neq Y) \to -\infty .$$</p>
</blockquote>

<p><em>Proof.</em> 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$</p>

<blockquote>
  <p><em>Claim 3.</em> 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)}$.</p>
</blockquote>

<p><em>Proof.</em> 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</p>

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

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

<h2>Lower Bound</h2>

<p><strong>Step 1.</strong></p>

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

<p><em>Proof</em>. 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)$.</p>

<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$</p>

<p><strong>Step 2.</strong></p>

<blockquote>
  <p><em>"Theorem" 2.</em> 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.</p>
</blockquote>

<p><em>Proof</em>. 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$</p>

CC BY-SA 3.0
2014-12-09T04:09:28.163Z
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)$.
Thomas Steinke
CC BY-SA 3.0
2014-12-08T17:35:50.547Z
2014-12-08T18:14:45.690Z
2014-12-08T18:14:45.690Z
usul
<p>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)$. </p>

<p>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.    </p>

<p>Can such a result be obtained in full generality? </p>

<hr>

<p>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. </p>

<p>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})$.</p>

CC BY-SA 3.0
2014-12-07T22:37:03.257Z
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.
Tsuyoshi Ito
CC BY-SA 3.0
2014-12-08T01:41:21.813Z
Can you say formally what the notation $H(X|Y,X\neq Y)$ means?
usul
CC BY-SA 3.0
2014-12-08T17:41:31.217Z
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
CC BY-SA 3.0
2014-12-10T21:16:52.683Z
Hi usul, that's exactly what I meant by it.
Chris
<it.information-theory><shannon-entropy>
Conditional entropy: $H(X | Y)$ large implies $H(X | Y, X \neq Y)$ large?
Chris
# Conditional entropy: $H(X | Y)$ large implies $H(X | Y, X \neq Y)$ large?

(Asked by: username_0 on 2014-12-07)

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})$.

**Tags:** it.information-theory, shannon-entropy
> **Comments:**
> **username_1**: 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.  
> **username_2**: Can you say formally what the notation $H(X|Y,X\neq Y)$ means?  
> **username_2**: 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))$.  
> **username_0**: Hi usul, that's exactly what I meant by it.  

---

## 2 answers

### Answer by username_3 on 2014-12-08. Score: 2

This might be a partial answer to your question:

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](http://en.wikipedia.org/wiki/Conditional_entropy#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).$$


---

### Answer by username_2 on 2014-12-08. Score: 2

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$

> **Comments:**
> **username_3**: 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)$.  

---

