0
$\begingroup$

Mutual information (see Wikipedia) is defined as

$I(X_1;X_2) = \mathbb{E}\left[\log \frac{p(X,Y)}{p(X)p(Y)}\right]$, which can be in the case of descrete random variables $X$ and $Y$ "simplified" to

$$\sum_{x,y}p(x,y)\log \frac{p(x,y)}{p(x)p(y)}\quad\quad (a)$$

Wikipedia also says that the multivariate mutual information (MMI) is defined as

$$I(X_1;\ldots;X_{n}) = I(X_1;\ldots;X_{n -1}) - I(X_1;\ldots;X_{n - 1}|X_{n})$$

where $I(X_1;\ldots;X_{n-1}|X_{n}) = \mathbb E_{X_{n}}\big(I(X_1;\ldots;X_{n - 1})|X_{n}\big)\text{.}$

For $n = 3$, the situation is clear to me, since my intuition of what $\mathbb E_{X_{n}}\big(I(X_1;\ldots;X_{n - 1})|X_{n}\big)$ should be (simply condition all probabilities in $(a)$), agrees with the formula:

$$I(X_1;X_2|X_3) = \mathbb E_{X_3} \big(I(X_1;X_2)|X_3\big) = \sum_{x_3} p(x_3) \sum_{x_2} \sum_{x_1} p(x_1,x_2|x_3) \log \frac{p(x_1,x_2|x_3)}{p(x_1|x_3)p(x_2|x_3)}\text{.}$$

Moreover, in the case of $n = 3$, the MMI can be expressed by the "inclusion-exclusion principle" sum $$I(X_1;X_2;X_3) = \sum_{I \subseteq \{1,2,\dots ,n\}} (-1)^{|I| + 1}H(X_I)\text{,}$$ where $H(X_I)$ is the entropy of the vector of the variables $X_i$, for which $i\in I$.


For $n= 4$, I would say that

$I(X_1;X_2;X_3|X_4) = \sum_{x_4}p(x_4)\sum_{x_3} p(x_3|x_4)\sum_{x_2}\sum_{x_1} p(x_1,x_2|x_3,x_4)\log\frac{p(x_1,x_2|x_3,x_4)}{p(x_1|x_3,x_4)p(x_2|x_3,x_4)}$, but in this case, the upper "inclusion-exclusion principle sum" does not hold, since some terms are missing. This answer to a similar question offers a nice suggestion for the definition of MMI, but there are two problems:

  • The answer lacks a motivation for the definition.
  • Only for odd $n$s, the definition is in concordance with the fact that MMI should equal $$\sum_{I \subseteq \{1,2,\dots ,n\}} (-1)^{|I| + n}H(X_I){.}$$

Can you give me an explicit formula for conditional MMI for $n\in \mathbb{N}$ or at least for $I(X_1;X_2;X_3|X_4)$ (and motivation for it)?

From here, I will be probably able to find the defintion of MMI itself.

$\endgroup$
  • $\begingroup$ I am not really sure, why labelling the equation $(a)$ by \tag{a}\label{MI} works only in the case, when I am editing the question. Otherwise, only plain text \sum_{x, y} p(x, y) ... is visible. $\endgroup$ – Antoine Nov 23 '16 at 16:28
  • $\begingroup$ You've made an error - The expression you write for $I(X_1;X_2;X_3\mid X_4)$ is actually equal to $ I(X_1;X_2 \mid X_3 ,X_4) $. This is because you've simply taken an extra expectation over the expression for $I(X_1;X_2\mid X_3)$ instead of first working out what $I(X_1;X_2;X_3)$ is. A simple way to see that the expression is incorrect is to note that it's not symmetric in $(X_1, X_2, X_3)$, which the 'MMI' is designed to be. $\endgroup$ – stochasticboy321 Nov 25 '16 at 6:01
  • $\begingroup$ NB - if you want motivations, the above arise naturally in Marton's inner bound for the rate region of the $n$ to $1$ (discrete memoryless) broadcast channel. $\endgroup$ – stochasticboy321 Nov 25 '16 at 6:03
  • $\begingroup$ @stochasticboy321 Can you give some appropriate links or maybe a complete answer, please? $\endgroup$ – Antoine Dec 14 '16 at 12:19
  • $\begingroup$ Added an answer, do ask me if something is unclear. $\endgroup$ – stochasticboy321 Dec 14 '16 at 16:07
1
$\begingroup$

I'll use the shorthand $p_i$ for $p(x_i)$ as you've used in the question. Sums below are over the set $\mathcal{X}_1\times \mathcal{X}_2 \times \mathcal{X}_3 \times \mathcal{X}_4$, and it's tacitly assumed that all of these are finite sets.

\begin{align*}I(X_1;X_2;X_3|X_4) &= I(X_1;X_2|X_4) - I(X_1;X_2|X_3X_4) \\ &= \sum p_{1234} \log \frac{p_{12|4}}{p_{1|4} p_{2|4}} - \sum p_{1234} \log \frac{p_{12|34}}{p_{1|34} p_{2|34}} \\&= \sum p_{1234} \log \frac{p_{12|4} p_{1|34} p_{2|34}}{p_{1|4}p_{2|4}p_{12|34}},\end{align*}

where the first equality is by definition, and the rest are manipulation. But $p_{1|34}p_{3|4} = p_{13|4}$ by Bayes' rule. We thus have $$I(X_1;X_2;X_3|X_4) = \sum p_{1234} \log \frac{p_{12|4}p_{13|4}p_{23|4}}{p_{1|4}p_{2|4}p_{3|4}^2 p_{12|34}} = \sum p_{1234} \log \frac{p_{12|4}p_{23|4}p_{13|4}}{p_{1|4}p_{2|4}p_{3|4} p_{123|4}}$$

which is a nice expression since it shows the symmetry of the functional explicitly. Now note that the expression you've written is actually $I(X_1;X_2|X_3X_4)$, and not $I(X_1;X_2;X_3|X_4)$.

Working further from this, you should be able to show that $$I(X_1;X_2;X_3;X_4) = \sum p_{1234} \log \frac{p_{12}p_{13}p_{14}p_{23}p_{24}p_{34} \cdot p_{1234}}{p_1 p_2 p_3 p_4 \cdot p_{123} p_{124} p_{134} p_{234}}$$

(the dots are the usual products and are only put in for clarity). From here the inclusion-exclusion expression in terms of entropies of subsets is obvious. Indeed, it's possible to show the same inductively for every $n$-fold expression.(try it!).


One operational meaning for the expression $I(X_1;X_2:\dots; X_k)$ is in the achievability region for the $k$-user broadcast channel determined by the coding scheme due to Marton. Check out ch. 8(?) in the book by El-Gamal & Kim. (NB - there may well be other motivations for the same, this is just the one I happen to know)

$\endgroup$
  • $\begingroup$ Thanks, your derivation is clear. Will try to find the book. $\endgroup$ – Antoine Dec 14 '16 at 16:21
  • $\begingroup$ Oh, and if in general you want to learn/work in network information theory, it's a great book to have a physical copy of, and usually runs ~$50 second hand. $\endgroup$ – stochasticboy321 Dec 14 '16 at 16:36
  • $\begingroup$ I have read the instructions and you can delete them:) $\endgroup$ – Antoine Dec 14 '16 at 18:07

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.