Let $Z_1, Z_2, Z_3, ... \sim \text{Ber}\left(\frac{1}{2} \right) $ and iid.

Let \begin{align*} X_1 &= Z_1\\ X_2 &= Z_1 + Z_2\\ X_3 &= Z_1 + Z_2 + Z_3\\ \vdots\\ X_n &= Z_1 + Z_2 + \cdots Z_n \end{align*}

I want to calculate mutual information $I(X_1; X_2, ..., X_n)$

By chain rule, \begin{align*} I(X_1; X_2, ..., X_n) &= I(X_1; X_2) + \sum_{i = 3}^n \underbrace{I(X_1; X_i| X_{2}, ..., X_{i - 1})}_{ = 0} \end{align*} because conditioned on $X_{i-1}$, I think $X_1$ and $X_i$ are conditionally independent (right)?

So I have:

\begin{align*} I(X_1; X_2, ..., X_n) &= I(X_1; X_2)\\ &= H(Z_1 + Z_2) - H(Z_1 + Z_2 | Z_1)\\ &= H(Z_1 + Z_2) - H(Z_2) \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \text{ define } Y = Z_1 + Z_2\\ &= H(Y) - 1 \end{align*}

From here, I can easily calculate $H(Y)$ from its distribution $$p_Y(y) = \begin{cases} \frac{1}{2} & y = 1\\ \frac{1}{4} & y = 0 \text{ or } y = 2 \end{cases}$$

Is this correct?

Interpretation of the result:

Having $I(X_1; X_2, ..., X_n) = I(X_1; X_2)$ implies that the amount of information $X_1$ gives about $X_2, X_3, ..., X_n$ is equal to the amount of information $X_1$ gives about $X_2$ alone. But this does not mean $X_1$ gives no information about $X_3, X_4, ..., X_n$ but rather qualitatively, $X_1$ gives the same information about $X_2$ that it gives about each of $X_3, ..., X_n$.

So it is inherent in the mutual information that it does not count redundant information.

Anyone want to comment on this interpretation?


1 Answer 1


Your solution is correct. The conditional independence assumption follows from the independence of $\{Z_i\}_i$.

Your interpretation is also correct. Using the symmetry of mutual information, I want to flip your interpretation and look at it from the other perspective. Suppose we want to see what we can say about $X_1$, from observing the rest of the sequence. The subsequence $\{X_i\}_{i>2}$ only contain the noisier and noisier version of the same information that $X_2$ carries about $X_1$. This is because $\{Z_i\}_{i > 2}$ are noise from the point of view of inferring about $X_1$ due to the independence of that set from $Z_1$. With this intuition, it makes sense that just observing $X_2$ is as informative as seeing all future entries of the sequence when we want to reason about $X_1$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .