# Chain rule for mutual information

$X$ and $Y$ are two Bernoulli random variables. ${P(X = 1) = \frac{1}{M}}$, and ${P(Y = 1) = \frac{1}{2}}$. Relation between them in terms of mutual information is given by: \begin{align*} I(X;Y) = h_2(\frac{1}{M}) - \frac{1}{2}h_2(\frac{2}{M}). \end{align*}

If we have $n$ realizations of these variables denoted by $X_1, X_2, \cdots , X_n$, and $Y_1, Y_2, \cdots , Y_n$ such that $Y_i$ is independent of $Y_j$ when $j \neq i$, and $X_i$ are dependent on each other.

How is it possible to calculate the mutual information between $n$ realizations of $X$ and $Y$? Here is what I attempted but I am not sure if it is correct. My doubt is in this particular step:

\begin{align*} I(X^n;Y^n) &= H(Y^n) - H(Y^n|X^n), \end{align*} where \begin{align*} H(Y^n) &= \sum_{i = 1}^{n} H(Y_i) \qquad \because \text{ $Y_i$'s are independent of each other}\\ &= nH(Y), \end{align*} and \begin{align*} H(Y^n|X^n) & = \sum_{i = 1}^{n} H(Y_i|X^n) \qquad \because \text{ $Y_i$'s are still independent of each other when $X^n$'s are given}\\ & = \sum_{i = 1}^{n} H(Y_i|X_i) \qquad \because \text{ when $X_i$ is given, $Y_i$ is independent of $X_j$ when $j \neq i$ }\\ & = nH(Y|X). \end{align*} Thus, \begin{align*} I(X^n;Y^n) = n I(X;Y). \end{align*}

Please tell me if the obtained result is correct? I have attempted another strategy using the chain rule for mutual information but could not process it. I will include that attempt as well if someone is interested?

• Both assumptions you write on the right side seem wrong. "$Y_i$'s are still independent of each other when $X^n$'s are given" (not true in general, I can give you counterexamples if you don't believe this). "when $X_i$ is given, $Y_i$ is independent of $X_j$ " (why?). – leonbloy Sep 11 '16 at 13:36