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$.


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.