# Equivalence of two definitions of mutual information

I am learning quantum computing and as a background study, I am currently learning fundamentals of classical information theory. I thought it best to ask my doubts here. In Nielsen and Chuang, it is stated that mutual information I(X:Y) of two random variables X and Y is the information they have in common while in some books, it is written that mutual information I(X:Y) is the information one variable(say X) has about the other(say Y). I can't understand it intuitively how the two definitions are equivalent. Also, the symmetric property of mutual information,i.e., I(X:Y)=I(Y:X) is obvious to me from the first definition but not from the second one.

• I don't see any definitions in your post. The mutual information between two random variables is given by a formula. Your "definitions" are just interpretations of this formula. – Yuval Filmus Apr 1 '20 at 21:17
• What is the motivation behind the formula? Also, how are these two "interpretations" equivalent? – Rohan Joshi Apr 2 '20 at 6:24
• You can read Shannon’s 1948 paper, where he introduces mutual information. It is the right quantity to consider in some contexts. – Yuval Filmus Apr 2 '20 at 6:26
• How do I prove that S(X)-S(X|Y) = S(Y)-S(Y|X)? – Rohan Joshi Apr 2 '20 at 12:16

You can define the mutual information as $$I(X;Y) = H(X) - H(X|Y)$$. This definition is symmetric in $$X,Y$$ since $$H(X)-H(X|Y) = H(X) - \sum_y \Pr[Y=y] H(X|Y=y) = \\ \sum_x \Pr[X=x] \log \frac{1}{\Pr[X=x]} - \sum_y \Pr[Y=y] \sum_x \Pr[X=x|Y=y] \log \frac{1}{\Pr[X=x|Y=y]} = \\ \sum_{x,y} \Pr[X=x,Y=y] \log \frac{1}{\Pr[X=x]} - \sum_{x,y} \Pr[X=x,Y=y] \log \frac{\Pr[Y=y]}{\Pr[X=x,Y=y]} = \\ \sum_{x,y} \Pr[X=x,Y=y] \log \frac{\Pr[X=x,Y=y]}{\Pr[X=x]\Pr[Y=y]},$$ and this expression is symmetric in $$X,Y$$.
This calculation also shows that if $$X,Y$$ are independent then $$I(X;Y) = 0$$, since then $$\Pr[X=x,Y=y] = \Pr[X=x] \Pr[Y=y]$$.
Moreover, if we write $$I(X;Y) = \sum_{x,y} \Pr[X=x] \Pr[Y=y] \frac{\Pr[X=x,Y=y]}{\Pr[X=x] \Pr[Y=y]} \log \frac{\Pr[X=x,Y=y]}{\Pr[X=x] \Pr[Y=y]},$$ then the convexity of $$z\log z$$ implies that $$I(X;Y) \geq z\log z$$, where $$z = \sum_{x,y} \Pr[X=x] \Pr[Y=y] \frac{\Pr[X=x,Y=y]}{\Pr[X=x] \Pr[Y=y]} = \sum_{x,y} \Pr[X=x,Y=y] = 1.$$ Thus $$I(X;Y) \geq 0$$.