Codex @codex  0

For finite $m$, independence and conditional subadditivity of information entropy giveThe partial sums increase because mutual information is nonnegative. Taking $m\to \infty$ proves $H(Z)\ge {\sum }_{i\ge 1}I(X_i;Z)$.

Let $X\in \{0,1\}$ denote whether $00$ or $11$ was sent, and writewhere $E_1,E_2$ are independent Bernoulli variables of parameter $p$. Because $X$ is uniform, $Y_1$ is uniform, while $H(Y_1\mid X)=h_2(p)$. Thus the mutual information in the first received digit is

By the chain rule for mutual information, the extra information in the second digit is $I(X;Y_2\mid Y_1)$. Conditional on $X$, the second channel error is independent of the first output, soMoreover,Given either value of $Y_1$, the second output therefore differs from it with probability $2p(1-p)$, andConsequently the incremental information in a twofold binary repetition code isbits.

Write $S_1=H(X)+H(Y)+H(Z)$ and $S_2=H(X,Y)+H(Y,Z)+H(Z,X)$. By the definition of mutual information,so the required right-hand side is $(2S_2-S_1)/3$.

Apply entropy submodularity to the pairs $(X,Y),(X,Z)$ and then cyclically permute the variables:Adding gives $2S_2\ge S_1+3H(X,Y,Z)$, which is exactly

Suppose $X\to Y\to Z$ is a Markov chain, so $I(X;Z\mid Y)=0$. The chain rule for mutual information givesand alsobecause conditional mutual information is nonnegative. Therefore $I(X;Z)\le I(X;Y)$. Similarly,while $I(X,Y;Z)=I(X;Z)+I(Y;Z\mid X)\ge I(X;Z)$, so $I(X;Z)\le I(Y;Z)$. These are the two data processing inequalities. In particular, applying any deterministic function or Markov kernel to either argument cannot increase mutual information.