Please forgive me if this is not the right Stack Exchange (and for inventing terms).

For discrete random variables X and Y, the mutual information of X and Y can be defined as follows: $I(X;Y) = \sum_{y \in Y} \sum_{x \in X} p(x,y) \log{ \left( \frac{p(x,y)}{p_1(x)\,p_2(y)} \right) }, \,\!$

I will define the mutual information of a "cell" $x_0$ to be: $CI(x_0,Y) = \sum_{y \in Y} p(x_0,y) \log{ \left( \frac{p(x_0,y)}{p_1(x_0)\,p_2(y)} \right) }, \,\!$

I'm not sure if this quantity goes by another name. Essentially I'm restricting focus to a single state of variable X (and then the full MI can be calculated by summing all the cell MIs).

My question: is it guaranteed that $CI(x_0,Y) \ge 0$? We know $I(X;Y)\ge0$ and we know that the pointwise mutual information can be negative. I feel like CI should be nonnegative and that I might be missing some obvious proof.



$I(x,y)= \sum_{x \in X} \sum_{y \in Y} p(x,y) \log_2 (\frac{p(x , y)}{p(x)p(y)})$

$CI(x,y)= \sum_{y \in Y} p(x,y) \log_2 (\frac{p(x , y)}{p(x)p(y)})$ for $x \in X$

we have,

$p(\cdot) \in [0,1]$

$\rightarrow\frac{p(\cdot)}{p(\cdot)p(\cdot)} \in [0...\infty ]$

$\rightarrow log_2\frac{p(\cdot)}{p(\cdot)p(\cdot)} \in (0...\infty ]$

$\rightarrow p(\cdot) log_2\frac{p(\cdot)}{p(\cdot)p(\cdot)} \in [0...\infty ]$

the codomain of $I$ and $CI$ is defined only on positive real values.

  • 3
    $\begingroup$ Your conclusion is right, but I think you've missed a step. Just because $X$ is non-negative doesn't mean $log_2(X)$ is positive. Trivially: $log_2(0.5) = -1$. You need a stronger constraint on what the product/quotient of the probabilities can be.... $\endgroup$ – Matt Krause Apr 24 '13 at 8:32

Answered on Theoretical Computer Science. CI cannot be negative.

The gist is that $CI=p(x_0) KL(p (y|x_0), p(y))$, and the Kullback-Leibler divergence is non-negative.

  • 2
    $\begingroup$ This is not an answer but a link to an answer on another SE website. Per the help center guidelines a good answer will both answer the question and provide context for links including relevant quotes and sources. The aim of CV is not to provide links to answers but solid answers here. $\endgroup$ – Alexis Apr 1 '15 at 5:57
  • $\begingroup$ @becko Would be better if someone rolled into the answer why the KL divergence can't be negative. $\endgroup$ – Alexis Feb 25 '16 at 23:22

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.