Independent scholarship · Open accessThe monthly digest

Indexed text attachment

entropy-sources-and-channels-in-higher-categories.tex

Source for Entropy, Sources, and Channels in Higher Categories

View paper · Download original file

Lines 2541–2640 of 4249. Source text is displayed literally.

2541 2542\section{Memoryless channels}2543 2544For a stochastic matrix $W\colon A\to B$ and a distribution $p$ on $A$, write $I(p,W)$ for the mutual2545information of the joint distribution $p\rtimes W$.2546 2547\begin{theorem}\label{thm:dmc}2548\Scl[\cite{Sha48}] The capacity of the memoryless channel with matrix $W$ is2549\[ C(W)=\max_pI(p,W), \]2550attained by the source of independent letters with a maximizing distribution.2551\end{theorem}2552 2553\begin{proof}2554Given the input block, the output letters are independent, so2555$I(x_1^n;y_1^n)=H(y_1^n)-\sum_kH(y_k\st x_k)\le\sum_kI(x_k;y_k)\le n\max_pI(p,W)$. Independent inputs give2556equality.2557\end{proof}2558 2559\begin{example}\label{ex:channels}2560The binary symmetric channel with flip probability $\delta$ has $C=1-\hb(\delta)$; for $\delta=0.1$ this is2561$0.531$. The binary erasure channel, which replaces its input by an erasure symbol with probability $e$,2562has $C=1-e$. The Z-channel, which sends $0$ to $0$ and flips $1$ to $0$ with probability $\delta$, has2563$C=\log\bigl(1+(1-\delta)\,\delta^{\delta/(1-\delta)}\bigr)$, which is $0.763$ for $\delta=0.1$.2564\end{example}2565 2566\section{Capacity as a function on morphisms}2567 2568Restricted to memoryless channels, capacity is a function on the morphisms of $\FinStoch$.2569 2570\begin{proposition}\label{prop:capacity}2571\Scl2572\begin{enumerate}[label=(\roman*)]2573\item $C(\id_X)=\log|X|$, and $C(W)=0$ iff $W$ factors through the one-point set.2574\item $C(V\circ W)\le\min\{C(V),C(W)\}$.2575\item $C(W\otimes W')=C(W)+C(W')$.2576\item If $W$ factors through a set with $r$ elements, then $C(W)\le\log r$.2577\end{enumerate}2578\end{proposition}2579 2580\begin{proof}2581(ii) For $X\to Y\to Z$ the data-processing inequality gives $I(X;Z)\le\min\{I(X;Y),I(Y;Z)\}$. (iii) Product2582inputs give $\ge$; conversely for the product channel2583$I(XX';YY')=H(YY')-H(Y\st X)-H(Y'\st X')\le I(X;Y)+I(X';Y')$. (iv) follows from (i) and (ii).2584\end{proof}2585 2586These are the properties of the logarithm of the rank of a matrix: it is $\log n$ on the identity of an2587$n$-dimensional space, it does not increase under composition, it is additive under tensor product, and2588it is bounded by the logarithm of the dimension of anything the matrix factors through. Capacity is a2589rank for stochastic matrices that is stable under small perturbations. The next chapter makes this exact:2590capacity is the growth rate of the largest identity onto which the tensor powers of $W$ retract, up to2591$\varepsilon$.2592 2593\begin{example}[A channel with memory]\label{ex:isi}2594Let $A=B=\{0,1\}$ and $y_n=x_n\oplus x_{n-1}\oplus z_n$, where the $z_n$ are independent bits equal to $1$ with2595probability $\delta$. This channel is stationary and without anticipation, has memory $1$, and has output2596memory $0$, since the outputs are independent given the input. It is the composite of the sliding block2597code $\phi(x)_n=x_n\oplus x_{n-1}$ with the memoryless binary symmetric channel, so its capacity is at most2598$1-\hb(\delta)$ by the inequality above. Equality holds: $\phi$ maps independent fair bits to independent2599fair bits, so the source of independent fair bits has rate of transmission $1-\hb(\delta)$. The memory costs2600nothing here because $\phi$ is invertible up to one bit.2601\end{example}2602 2603For channels with memory (ii) persists in the form $R(\mu,\nu'\circ\nu)\le\min\{R(\mu,\nu),R(\nu\circ\mu,\nu')\}$, by the same2604inequality applied to blocks.2605 2606\section{Joinings and the backward channel}2607 2608The compound source $\omega$ is a stationary measure on $\AZ\times\BZ$ with marginals $\mu$ and $\eta$, a2609\term{joining} of the two sources in the sense of ergodic theory \cite{Gla03}. Conversely, by2610disintegration, every joining arises from a stationary channel, unique up to $\mu$-null sets. So the2611morphisms from $(\AZ,\mu)$ to $(\BZ,\eta)$ in the equivariant version of the category $\Krn$ of2612\cref{ch:martingales} are the joinings, composition is the relatively independent joining over the middle2613factor, and the dagger reverses a joining. The reverse of $\nu$ with respect to $\mu$ is the \term{backward2614channel} $\nu^\dagger\colon\BZ\to\AZ$, which gives the conditional law of the input given the output.2615 2616The rate is symmetric, $R(\mu,\nu)=R(\eta,\nu^\dagger)$. The two conditional entropy rates are the noise2617$H(\omega)-H(\mu)$ of the channel and the \term{equivocation} $H(\omega)-H(\eta)=H(\mu)-R(\mu,\nu)$, which is the noise of2618the backward channel. Shannon's second theorem, in Khinchin's formulation, is a statement about the2619equivocation.2620 2621\section*{Notes}2622 2623Khinchin's definitions and the two theorems on the compound source are \cite[Ch.~III]{Khi56}. The2624insufficiency of his finite-memory condition and its repair are discussed in \cite{Tak58,Fei59,Bre60};2625ergodic properties of channels with infinite memory are treated by Adler \cite{Adl61}, and the modern theory2626is in Gray's book \cite{Gra11}, where the compound source is called the hookup. The equality of ergodic and2627stationary capacity is due to Parthasarathy \cite{Par61} and Breiman \cite{Bre60}; see also2628\cite{Ned57,Jac59}. For joinings see \cite{Gla03}.2629 2630\section*{Exercises}2631 2632\begin{exercise}2633Derive the capacities of the erasure channel and the Z-channel in \cref{ex:channels}.2634\end{exercise}2635 2636\begin{exercise}2637Show that the composite of binary symmetric channels with flip probabilities $\delta_1,\delta_2$ is binary symmetric2638with flip probability $\delta_1(1-\delta_2)+\delta_2(1-\delta_1)$. Compute the capacity for $\delta_1=\delta_2=0.1$ and compare with2639\cref{prop:capacity}(ii).2640\end{exercise}