2
$\begingroup$

Let $X$ be a discrete random variable, and let $E$ be an event on the same probability space as $X$. Let $X_E$ be $X$ conditioned on the event $E$. Is there a general relationship between the Shannon entropy of $X$ and $X_E$?

I originally thought that one could say that $H(X_E) \geq H(X) - \log 1/\Pr(E)$, but this is not true: consider a $p$-biased coin $X$, and let $E$ denote the event that $X$ lands ``heads'' (which happens with probability $p$). Then, $H(X_E) = 0$, but $H(X) - \log 1/\Pr(E) = p\log(1/p) + (1 - p)\log(1/(1-p)) - \log(1/p) = (1 - p)\log p/(1 -p) > 0$, when $p > 1/2$.

Is there nothing we can say about the two quantities?

$\endgroup$
  • $\begingroup$ In general, conditioning could reduce Entropy. $$H(X)\geq H(X|A)$$ where $A$ is an event. To see this, the Mutual Information definition is as follows. $$I(X;A)=H(X)-H(X|A)$$. Mutual Information is non-negative and hence the result follows. $\endgroup$ – Sudarsan Nov 17 '13 at 18:58
  • $\begingroup$ Hi Sudarsan: that is correct, but here I'm talking about the entropy of $X|A = 1$, rather than the conditional entropy of $X|A$, which is the convex combination of the entropies of $X|A = a$. $\endgroup$ – Henry Yuen Nov 17 '13 at 19:11
  • $\begingroup$ I don't understand what the difference is though. Conditioning on an event in the same probability space only induces a random variable with a reduced sample space whose Entropy is less than or equal to the Entropy of the original random variable. $X_E$ is also a random variable and in your example, once you condition that the coin takes a value 'heads', the random variable becomes degenerate. $\endgroup$ – Sudarsan Nov 18 '13 at 0:53
  • $\begingroup$ Sudarsan, here's an example where $H(X_E)$ can be much greater than $H(X)$. Consider the following experiment: flip a coin $E$ that is heads with probability $0.01$. If $E$ is tails, then $X = 0$. If $E$ is heads, then $X$ is a fair coin. Thus, $H(X)$ is close to $0$, yet $H(X_{E = 1}) = 1$. $\endgroup$ – Henry Yuen Nov 18 '13 at 3:46
  • 3
    $\begingroup$ To broadly answer your question now that I understand the notion, your last example takes X to a completely different sample space defined by a Bernoulli with probability one half. Hence this particular comparison looks like you want to compare the entropies of two different sample spaces with two different probability measures. Hence there is no relation between them I.e. it is like asking if you can arbitrarily compare the entropies of two different probability spaces. $\endgroup$ – Sudarsan Nov 18 '13 at 5:08

Your Answer

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

Browse other questions tagged or ask your own question.