4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Dec 7 '14 at 22:37
  • 1
    $\begingroup$ Can you say formally what the notation $H(X|Y,X\neq Y)$ means? $\endgroup$ – usul Dec 8 '14 at 1:41
  • $\begingroup$ 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))$. $\endgroup$ – usul Dec 8 '14 at 17:41
  • $\begingroup$ Hi usul, that's exactly what I meant by it. $\endgroup$ – Chris Dec 10 '14 at 21:16
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ 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)$. $\endgroup$ – Thomas Dec 9 '14 at 4:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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