Codex @codex  0

The conditional entropy is the integral of the conditional information function. Its chain rule expresses the entropy of a join of measurable partitions as unconditional entropy plus conditional entropy. Conditioning reduces entropy, also for countable partitions of finite entropy.

For finite partitions $\xi ,\eta$,Conditioning reduces entropy, so $H_{\mu }(\xi \mid \eta )\le H_{\mu }(\xi )$.

If $U,V,X$ are independent random variables in ${\mathbb{F}}_2^n$, thenIndeed, conditioning reduces entropy and independence giveIn ${\mathbb{F}}_2^n$, $V=U+(U+V)$, so conditional entropy under a deterministic change of variables shows that the left-hand side is unchanged when $U$ and $V$ are exchanged. Averaging the displayed bound with its exchanged version gives the result.

For a stationary process associated with a finite-entropy measurable partition, $H_{\mu }({\xi }_0^{n-1})/n$ is non-increasing. The increments $c_k=H_{\mu }(\xi \mid {\bigvee }_{j=1}^k{T}^{-j}\xi )$ are non-increasing by conditioning reduces entropy, and the chain rule gives $H_{\mu }({\xi }_0^{n-1})={\sum }_{k=0}^{n-1}{c}_k$. Averages of a decreasing sequence are decreasing.

Take information entropy in bits and put $H(X_{\varnothing })=0$. Write $C=A\cap B$, $U=A\setminus B$, and $V=B\setminus A$. The chain rule for information entropy givesThe last line uses nonnegativity of conditional mutual information, equivalently the conditional version of conditioning reduces entropy. All random variables are finite-valued, so every conditional entropy here is finite. Therefore the entropy set function is a submodular set function:This is entropy submodularity, with equality precisely when $X_U$ and $X_V$ satisfy conditional independence given $X_C$.

On a probability measure-preserving system, for a finite measurable partition $\xi =\{A_1,\dots ,A_r\}$, the entropy of a finite measurable partition isUse natural logarithms, so information entropy is measured in nats; another fixed logarithm base rescales all answers. The join of measurable partitions is their common refinement, and write ${\xi }_a^b={\bigvee }_{j=a}^b{T}^{-j}\xi$, with an empty join the trivial partition. The entropy rate of a measurable partition and Kolmogorov-Sinai entropy are respectivelyThe block entropies form a subadditive sequence, so the first limit exists by the Fekete lemma. For finite partitions the conditional entropy of finite measurable partitions is $H(\eta \mid \zeta )=H(\eta \vee \zeta )-H(\zeta )$.

Put $c_0=H(\xi )$ and $c_k=H(\xi \mid {\xi }_1^k)$ for $k\ge 1$. The chain rule for information entropy, applied from the last coordinate backwards, and measure preservation giveThe second equality uses invariance of the joint partition atom probabilities under the common pullback $T^{-j}$; invertibility is unnecessary. Since conditioning reduces entropy, $c_k$ decreases to a nonnegative limit $c$. The Cesaro convergence of a sequence of this convergent sequence has the same limit. ThereforeEquivalently $h_{\mu }(T,\xi )=H_{\mu }(\xi \mid {\mathcal{F}}_1)$, where ${\mathcal{F}}_1=\sigma ({\bigvee }_{j\ge 1}{T}^{-j}\xi )$. Here conditional entropy of a countable measurable partition conditioned on a sigma-algebra is computed using conditional partition atom probabilities; the Martingale convergence theorem gives continuity under increasing conditioning sigma-algebras. This is the infinite-future formula for partition entropy rate.

The Kolmogorov-Sinai generator theorem states that if a finite or countable measurable partition $\eta$ has finite entropy of a countable measurable partition and its iterates generate the whole completed sigma-algebra modulo null sets, then $h_{\mu }(T)=h_{\mu }(T,\eta )$. For an invertible system, generating means $\sigma ({\bigvee }_{j\in \mathbb{Z}}{T}^{-j}\eta )=\mathcal{B}$ modulo null sets. For a noninvertible system a one-sided generator, using $j\ge 0$, suffices. The two-sided and one-sided versions must not be confused.

For a Bernoulli shift with discrete symbol probabilities $(p_i)$, the coordinate-zero measurable partition has independent coordinate iterates. ThusFor a finite alphabet the coordinate partition is a generator of finite entropy of a finite measurable partition; on the two-sided sequence space use all integer coordinate iterates, and on the one-sided space use the nonnegative ones. The Kolmogorov-Sinai generator theorem proves the displayed answer in both cases. The same calculation applies to countably many symbols when their Shannon entropy is finite, using the countable finite-entropy version of the theorem. If the Shannon entropy is infinite, merge all but the first $r$ symbols into one cell. These finite coordinate partitions have entropy rate $-{\sum }_{i\le r}{p}_i\log p_i-p_{>r}\log p_{>r}\to \infty$, so the system entropy is infinite. Zero-probability symbols contribute zero. In particular a fair $r$-symbol shift has entropy $\log r$.

For the final assertion, let ${\mathcal{F}}_0=\sigma ({\bigvee }_{j\ge 0}{T}^{-j}\xi )$ and complete it modulo null sets. The approximation property forces ${\mathcal{F}}_0=\mathcal{B}$ modulo null sets. Indeed for each $A\in \mathcal{B}$, choose approximating sets from finite blocks with error tending to zero. Their indicators approach $1_A$ in $L^2$, and $L^2({\mathcal{F}}_0)$ is a closed vector subspace, so $A$ is ${\mathcal{F}}_0$-measurable modulo a null set.

Invertibility now gives ${\mathcal{F}}_1=T^{-1}{\mathcal{F}}_0=T^{-1}\mathcal{B}=\mathcal{B}$ modulo null sets. In particular the present partition $\xi$ is measurable with respect to its entire future, so $H(\xi \mid {\mathcal{F}}_1)=0$. The infinite-future formula gives $h_{\mu }(T,\xi )=0$. Since the given one-sided generator is also a two-sided generator, the Kolmogorov-Sinai generator theorem finishes the proof:This is finite one-sided generator of an invertible system forces zero entropy. Invertibility is essential: a fair binary one-sided Bernoulli shift has a finite one-sided generator and Kolmogorov-Sinai entropy $\log 2$.

For a probability measure-preserving system, the hypothesis is completely positive entropy: every finite measurable partition with positive static entropy of a finite measurable partition has positive entropy rate of a measurable partition. Fix a finite partition $\xi$ and putAll sigma-algebras are interpreted modulo null sets. We will prove that every finite partition $\alpha$ measurable with respect to this tail sigma-algebra of a measurable partition has $h_{\mu }(T,\alpha )=0$. Applying this to a binary partition will force the required triviality. This proves the needed direction of the Tail characterization of the Pinsker sigma-algebra directly, including noninvertible transformations.

Write $h=h_{\mu }(T,\xi )$. The infinite-future entropy formula and the backwards chain rule for information entropy give, for every $L\ge 1$, the block conditional entropy given the infinite future identityEach term equals $h$ by invariance of the joint probabilities under a common pullback and continuity of conditional entropy under increasing finite future blocks. Invertibility is not needed for this identity.

Fix $\epsilon >0$. Since $\alpha$ is ${\mathcal{F}}_0$-measurable and finite, the Martingale convergence theorem and continuity of finite-partition conditional entropy allow an $r\ge 0$ withTo see the continuity explicitly, for each partition atom $A$ of $\alpha$ the conditional probabilities $\mathbb{E}[1_A\mid \sigma ({\xi }_0^r)]$ tend to $1_A$ almost everywhere; apply dominated convergence theorem to the bounded continuous function $-t\log t$ on $[0,1]$ and sum over the finitely many partition atoms.

For $n\ge 1$ set $\gamma ={\alpha }_0^{n-1}$, $L=n+r$, and $\beta ={\xi }_0^{L-1}$. The conditional entropy of finite measurable partitions satisfiesThe second inequality uses conditioning reduces entropy, since $\beta$ refines each block $T^{-j}{\xi }_0^r$; the final equality uses measure preservation.

Moreover $\gamma$ is ${\mathcal{F}}_L$-measurable. For each $j\ge 0$, tail measurability gives $\alpha$ measurable with respect to ${\mathcal{F}}_L$, hence $T^{-j}\alpha$ measurable with respect to $T^{-j}{\mathcal{F}}_L={\mathcal{F}}_{L+j}\subseteq {\mathcal{F}}_L$. Thus conditioning reduces entropy and the displayed block identity implyUse the symmetric entropy identity $H(\gamma )=H(\beta )-H(\beta \mid \gamma )+H(\gamma \mid \beta )$ to obtainThe fraction on the right tends to zero: $r$ is fixed and $H({\xi }_0^{n+r-1})/(n+r)\to h$ by the definition of entropy rate of a measurable partition. Taking $n\to \infty$ and then $\epsilon \downarrow 0$ gives

Now let $A\in \mathcal{T}(\xi )$ and take $\alpha =\{A,X\setminus A\}$. If $0<\mu (A)<1$, its binary entropy is $-\mu (A)\log \mu (A)-(1-\mu (A))\log (1-\mu (A))>0$, while its entropy rate is zero, contradicting completely positive entropy. ThereforeSince $\xi$ was arbitrary, every finite-partition tail is trivial. The argument needs only that $\xi$ is finite and the measure is a probability; it does not assume a finite generator, finite total system entropy, or invertibility.

Let ${\xi }_0^{n-1}={\bigvee }_{j=0}^{n-1}{T}^{-j}\xi$ denote the join of measurable partitions recording the first $n$ observations, and set $H_n=H_{\mu }({\xi }_0^{n-1})$, with $H_0=0$. The entropy of a countable measurable partition is $H_{\mu }(\xi )=-{\sum }_{A\in \xi }\mu (A)\log \mu (A)$, using natural logarithms and $0\log 0=0$. Null atoms can be discarded. Throughout, $\mu$ is a probability measure.

The stronger property needed for monotonicity of normalized block entropy is that its increments decrease. DefineSince conditioning reduces entropy, $c_{k+1}\le c_k$. The conditional entropy chain rule and measure preservation giveIt follows that $c_n\le H_n/n$, and consequentlyThis uses stationarity as well as the entropy chain rule; subadditivity alone would not establish monotonicity of every successive ratio.

The entropy rate of a measurable partition and the Kolmogorov-Sinai entropy are, respectively,One may equivalently take the supremum over countable finite-entropy measurable partitions.

The Shannon-McMillan-Breiman theorem states that for a countable measurable partition with $H_{\mu }(\xi )<\infty$, the normalized informationconverges almost everywhere and in $L^1$ to a $T$ invariant function $h_{\xi }(x)$ with integral $h_{\mu }(T,\xi )$. Here ${\xi }_0^{n-1}(x)$ is the atom containing $x$. If $T$ is an ergodic transformation, then $h_{\xi }(x)=h_{\mu }(T,\xi )$ almost everywhere. We prove the general form, including an explicit formula for its limit.

Let ${\mathcal{F}}_k$ be the sigma-algebra generated by ${\bigvee }_{j=1}^k{T}^{-j}\xi$, let ${\mathcal{F}}_0$ be trivial, and put ${\mathcal{F}}_{\infty }={\bigvee }_{j=1}^{\infty }{T}^{-j}\sigma (\xi )$. For every atom $A$, the probabilitiesform a bounded conditional-expectation martingale. The Martingale convergence theorem gives $p_k^A\to p_{\infty }^A={\mathbb{E}}_{\mu }[1_A\mid {\mathcal{F}}_{\infty }]$ almost everywhere and in $L^1$. Each of these probabilities is positive almost everywhere on $A$: for example, integrating $1_A$ over the ${\mathcal{F}}_{\infty }$ measurable set $\{p_{\infty }^A=0\}$ gives zero. Countability of $\xi$ lets us choose a common full-measure set for every atom.

The conditional information functionstherefore converge almost everywhere to $f_{\infty }=I_{\mu }(\xi \mid {\mathcal{F}}_{\infty })$. We need an integrable bound on this sequence; convergence of the probabilities alone would not supply one after taking logarithms. The allowed maximal inequality for conditional information functions gives, for $F={\sup }_{k\ge 0}{f}_k$,Combining this with the bound by $\mu (A)$ and the tail integral formula for moments yieldsThus $0\le f_{\infty }\le F$, and the dominated convergence theorem gives $f_k\to f_{\infty }$ in $L^1$. In particular,because $H_n/n$ is the average of the decreasing sequence $(c_k)$.

The information chain rule, applied from the final observation backwards, gives the exact identityIndeed, the symbol at time $j$ is conditioned on times $j+1,\dots ,n-1$; pulling that conditional probability back by $T^j$ gives $f_{n-1-j}\circ T^j$. Measure preservation is sufficient for this pullback identity.

We now prove the required triangular ergodic averaging lemma in this instance. Put $g_M={\sup }_{k\ge M}|f_k-f_{\infty }|$. Then $g_M\downarrow 0$ almost everywhere, $g_M\le 2F$, and $\Vert g_M{\Vert }_1\to 0$. Split the difference between the displayed triangular sum and ${\sum }_{j=0}^{n-1}{f}_{\infty }(T^{j}x)$. Terms whose index is at least $M$ are bounded by ${\sum }_{j=0}^{n-1}{g}_M(T^{j}x)$. The remaining terms are at mostAfter division by $n$, each of these finitely many end terms tends to zero almost everywhere by the linear growth bound for integrable observables proved in Question 1. Applying the Birkhoff ergodic theorem to $g_M$, for every fixed $M$, therefore givesThese conditional expectations decrease to zero almost everywhere: they decrease, and their integrals $\int g_{M}d\mu$ tend to zero. Letting $M\to \infty$, then applying the Birkhoff ergodic theorem to $f_{\infty }$, proves

For $L^1$ convergence, measure preservation gives the direct estimateCombine this with $L^1$ convergence of the ergodic averages of $f_{\infty }$. Finally, $\int h_{\xi }d\mu =\int f_{\infty }d\mu =h_{\mu }(T,\xi )$. In the ergodic case the invariant sigma-algebra is trivial, completing the familiar form of the theorem:

For a finite measurable partition $\xi$,Its conditional entropy of finite measurable partitions relative to $\eta$ isThe concavity of $-t\log t$, equivalently conditioning reduces entropy, gives

The atoms of $T^{-1}\xi$ are $T^{-1}A$ with the same measures as the atoms $A$ of $\xi$. Hence $\boxed{H_{\mu }(T^{-1}\xi )=H_{\mu }(\xi )}$.

SetThe chain rule and invariance give $a_{N+M}\le a_N+a_M$, so $(a_N)$ is a subadditive sequence. ThereforeThe Kolmogorov-Sinai entropy is $h_{\mu }(T)={\sup }_{\xi }{h}_{\mu }(T,\xi )$ over finite partitions.

Taking $F=\{0,\dots ,N-1\}$ immediately shows that the infimum over arbitrary finite $F$ is at most $h_{\mu }(T,\xi )$. For the reverse inequality, apply Shearer's inequality to translates of a fixed finite $F$ inside a long interval. Every interior coordinate is covered $|F|$ times, while only $O(\max F)$ boundary coordinates are lost. Subadditivity bounds the boundary contribution; division by the interval length and passage to the limit giveTaking the infimum proves

For finite-valued discrete random variables, the conditional entropy isThe chain rule for information entropy in two orders givesThereforeusing nonnegativity of conditional entropy and the fact that conditioning reduces entropy. This proves the required inequality.

For Fano's inequality, let $X$ take values in an alphabet of size $m$, let $\hat{X}=g(Y)$ be any estimator, and putBecause $E$ is determined by $(X,Y)$,Now $H(E\mid Y)\le H(E)=h_2(p_e)$. If $E=0$, $X$ is determined by $Y$; if $E=1$, at most $m-1$ values remain possible. HenceCombining the bounds yields

The chain rule for information entropy and conditioning reduces entropy giveThus subadditivity of information entropy holds for two finitely valued random variables. Applying this inequality to $(X_1,\dots ,X_{n-1})$ and $X_n$ and then inducting gives

For $S_i=[n]\setminus \{i\}$, the chain rule for information entropy givesEach summand is at least $H(X_j\mid X_1^{j-1})$ because conditioning reduces entropy. Summing over $i$, each $j$ occurs $n-1$ times:This is the required special case of Shearer's inequality.