Let $\{X_n\}$ be a sequence of independent, discrete random variables, and let $Z$ be another discrete random variable. Show that $$H(Z)\geq\sum_{i=1}^\infty I(X_i;Z)$$ where $H$ is the entropy and $I$ is the mutual information.
I really don't know where to start with this. Of course there is the basic fact (practically by definition) that $H(Z)\geq I(X_i;Z)$ for each $i$ but I don't see how to improve this, especially since we're given practically no information about the relationship between $\{X_n\}$ and $Z$.
UPDATE ON ATTEMPT: Fix $n\geq1$. Then by the chain rule for mutual information $$I(X_1^n;Z)=\sum_{k=1}^nI(X_k;Z|X_1^{k-1}).$$ Then we have by definition $$I(X_k;Z|X_1^{k-1})=H(X_k|X_1^{k-1})-H(X_k|Z,X_1^{k-1}).$$ Because of the independence of the $X_i$, $H(X_k|X_1^{k-1})=H(X_k)$. If we have $H(X_k|Z,X_1^{k-1})=H(X_k|Z)$ then we have shown that for any $n\geq1$ we have $$I(X_1^n;Z)=\sum_{k=1}^nI(X_k;Z).$$ Using the fact that $H(Z)\geq I(X_1^n;Z)$ then gives the result (I think) when taking $n\to\infty$ (although this feels a bit iffy to me).
However the equality $H(X_k|Z,X_1^{k-1})=H(X_k|Z)$ is true if and only if $X_k$ and $X_1^{k-1}$ are conditionally independent given $Z$. I don't think that this is necessarily true, so is there a problem with my approach?
Best Answer
It suffices to show that, if $X,Y,Z$ are discrete random variables with $Y, Z$ independent, then $$I(X; Y, Z) \geq I(X; Y) + I(X; Z).$$ This is equivalent to $$H(X) + H(Y, Z) - H(X, Y, Z) \geq 2H(X) + H(Y) + H(Z) - H(X, Y) - H(X, Z).$$ As $H(Y, Z) = H(Y) + H(Z)$, this is equivalent to $$ H(X, Y, Z) + H(X) \leq H(X, Y) + H(X, Z)$$ or $$ H(Y | X, Z) \leq H(Y | X)$$ which holds as conditioning on more variables decreases entropy.
Anyways, iterating our claim give $$\sum_{i = 1}^n I(Z; X_i) \leq I(Z; X_1,\cdots, X_n) \leq H(Z)$$ and taking $n \to \infty$ gives the desired result.