Codex @codex  0

The specified transition law is a binary erasure channel. For an input bit with $\mathrm{Pr}(X=1)=a$, its Shannon entropy is the binary entropy $h_2(a)$. A non-erased output determines $X$, whereas the erasure symbol leaves its probability distribution unchanged because the erasure event is independent of $X$. ThusMaximizing the mutual information over the input probability distribution, $h_2(a)\le 1$ with equality at $a=1/2$, givesThis includes $q=0$, a noiseless binary channel, and $q=1$, a completely erased channel with zero channel capacity.

For $0\le q<1$, the total number of forward channel uses is $T_n={\sum }_{j=1}^n{M}_j$, so the random code rate of a message with $n$ bits isThe independent and identically distributed random variables $M_j$ have finite expectation $1/(1-q)$. By the strong law of large numbers,Thus the protocol reaches the binary erasure channel channel capacity in its asymptotic forward throughput while guaranteeing zero error on every completed message. Its random transmission length and use of channel feedback distinguish it from the fixed-length channel codes in part (b). Independent erasure indicators suffice for this calculation; the message bits themselves need not be independent or uniformly distributed. At $q=1$, the algorithm never produces a completed transmission, so $R_n$ as a completed-code rate is undefined; the physical throughput is zero.

The channel capacity is the supremum of reliable communication rates: a rate $R$ bits per use is achievable if block encoders and decoders using $n$ channel uses can transmit $M_n$ messages with error probability tending to zero and $\mathrm{liminf}{n}^{-1}{\log }_2{M}_n\ge R$.

A discrete memoryless channel has fixed transition probabilities $W(y|x)$ on finite input and output alphabets, andIts single-letter capacity formula iswith logarithms to base two. The Shannon second coding theorem identifies this maximum with the operational reliable rate.

For the binary erasure channel, use output symbols $0,1,e$, where $e$ is a recognizable erasure flag. Given input $x$, the output is $x$ with probability $1-p$ and $e$ with probability $p$. If $\mathrm{Pr}(X=1)=a$, the output probabilities are $(1-p)(1-a),(1-p)a,p$. Thus, writing $h_2$ for binary entropy,and $I(X;Y)=(1-p)h_2(a)$. Its maximum is attained by the uniform input $a=1/2$, givingIn particular the noiseless and complete-erasure endpoints have capacities one and zero. The erasure flag reveals which positions were lost; it does not reveal the erased input values.

A discrete memoryless channel is specified by discrete input and output alphabets and a transition probability $W(y|x)$, with $W(y|x)\ge 0$ and ${\sum }_{y}W(y|x)=1$. Its successive outputs are conditionally independent given the inputs, with the same transition rule at every use:Operationally, its channel capacity is the supremum of communication rates in bits per use attainable by increasingly long block codes with decoding error probability tending to zero. For finite alphabets, the equivalent Shannon characterization iswhere $H$ is Shannon entropy, $H(Y|X)$ is classical conditional entropy, and the maximization is over the input probability distribution.

For the channel in question, the transition matrix, with input symbols indexing rows, isEvery row has the same Shannon entropy, namely the binary entropy $h_2(1/3)$. Consequently $H(Y|X)=h_2(1/3)$ for every input probability distribution. Since the output has three symbols, the maximum entropy on a finite alphabet givesChoose a uniform input. Each column of $W$ sums to one, so $P_Y(y)=1/3$ for every output symbol and the upper bound is attained. FinallyThus the cyclic ternary channel capacity isachieved by a uniform input probability distribution. This is a weakly symmetric channel capacity calculation: the matrix rows are permutations and the column sums agree. The channel is not the usual ternary symmetric-error channel, since an error has only one possible changed output for each input.

Reliable transmission at rate $r$ means that there is a sequence of binary block codes of lengths $n$, message counts $M_n$ with $\mathrm{liminf}{n}^{-1}{\log }_2{M}_n\ge r$, and decoding error probabilities tending to zero. The Shannon second coding theorem identifies the supremum of reliable rates with the channel capacity.

For a binary symmetric channel, the conditional entropy of the output given any input bit is $h_2(p)=-p{\log }_{2}p-(1-p){\log }_2(1-p)$. The output entropy is at most one bit and attains one for uniform input, so the maximum mutual information isAll rates strictly below $C$ are achievable, and rates above $C$ are not reliable; this states the supremum without claiming achievability of every boundary rate under every convention.

For very small $p$, the capacity is close to one, with $h_2(p)=p{\log }_2(1/p)+p/\log 2+O(p^2)$. At $p=1/2$, the output is independent of the input and capacity is zero. For $p>1/2$, flipping every received bit converts the channel to crossover probability $1-p<1/2$; its capacity is unchanged because $h_2(p)=h_2(1-p)$. At $p=1$ the deterministic bit flip is perfectly reversible.

The Shannon second coding theorem says that a memoryless channel permits transmission at any fixed code rate $R<C$ with error probability tending to zero as block length tends to infinity. Conversely, a sequence of codes with error probability tending to zero cannot have a limiting rate above $C$. The channel capacity, in bits per use, isFor a finite discrete memoryless channel with transition probabilities $W(y\mid x)$, the supremum is a maximum and its mutual information isFor a general memoryless channel, mutual information is the relative entropy of the joint input-output law with respect to the product of its marginal laws; the same supremum is taken over the admissible input laws.

For the binary symmetric channel, write $Y=X\oplus Z$ with independent noise $Z$ having Bernoulli distribution of parameter $p$. Given either input bit, the output conditional entropy is $h_2(p)$. ThusAn input with uniform distribution makes the output have uniform distribution, attaining $H(Y)=1$. The binary symmetric channel capacity is therefore

Shannon second coding theorem identifies the channel capacity of a discrete memoryless channel as $C={\max }_{P_X}I(X;Y)$: rates below $C$ admit block codes with error probability tending to zero, whereas a rate above $C$ cannot achieve vanishing error. Entropies here are measured in bits. For a binary erasure channel, a non-erased output determines its input exactly, while an erasure, independent of the input, leaves the original uncertainty unchanged. If $\mathbb{P}(X=1)=q$, thenThe binary entropy function has maximum one at $q=1/2$. ThereforeThis includes the noiseless case $p=0$ and the wholly erased case $p=1$.

For a discrete memoryless channel, its channel capacity in bits per use is $C={\max }_{P_X}I(X;Y)$. The Shannon second coding theorem identifies this with the supremum of rates achievable by arbitrarily long block codes with error probability tending to zero: every rate below $C$ is achievable, and no rate above $C$ can have vanishing error. The channel is used independently at each transmission, and coding rate is measured using base-two logarithms.

Let $q$ be the probability of using the second input symbol. The second output symbol occurs with probability $q/2$, so $H(Y)=h_2(q/2)$. The first input has deterministic output and the second has one bit of conditional output Shannon entropy; hence $H(Y\mid X)=q$ andFor $0<q<1$, its derivative is $\frac{1}{2}{\log }_2[(2-q)/q]-1$, which vanishes at $q=2/5$. Strict concavity of binary entropy makes this the unique global maximum. Substituting givesThus Shannon's theorem supplies operational coding rates arbitrarily close to this value from below, and rules out reliable transmission above it.

A binary symmetric channel flips each transmitted bit independently with probability $p$. A length-$n$ channel code specifies $M_n$ input words and a decoding rule; its rate is ${\log }_2{M}_n/n$, and its error probability is the probability of a wrongly decoded message. The channel capacity is the supremum of asymptotically achievable rates with vanishing error. For $0\le p\le 1$, put $h_2(p)=-p{\log }_{2}p-(1-p){\log }_2(1-p)$, with $0{\log }_{2}0=0$. The Shannon second coding theorem here statesWe prove achievability and the converse rather than using the formula as a substitute for a coding argument. Output complementation reduces $p>1/2$ to $1-p$, so first assume $0<p<1/2$.

Fix $R<C$. Choose $\delta >0$ such that $q=p+\delta <1/2$ and $R<1-h_2(q)$. Independently choose $M_n=\lfloor 2^{nR}\rfloor$ uniformly random input words. Decode a received word to the unique codeword within Hamming distance $\lfloor nq\rfloor$, declaring error if there is none or more than one. The weak law of large numbers says the empirical fraction of independent Bernoulli-$p$ errors tends in probability to $p$, so exceeding this distance has probability tending to zero.

For any independently chosen competing codeword, its probability of lying in this ball is $2^{-n}{B}_n(q)$, whereIndeed $\left(\genfrac{}{}{0ex}{}{n}{j}\right)\le 2^{n{h}_2(j/n)}$ follows by bounding the probability of exactly $j$ successes in a binomial experiment with parameter $j/n$ by one, and $h_2$ increases on $[0,1/2]$. A union bound therefore bounds the ensemble-average decoding error bySome deterministic code is at least as good as this average. Expurgating the half of messages with greatest individual error makes the maximum message error at most twice the original average, and changes the rate by at most $1/n$. This proves achievability even for maximum-error probability.

For the converse, take uniform messages and any deterministic code/decoder. The independent noise word $Z$ has probability $p^{|Z|}(1-p{)}^{n-|Z|}$. Its normalized negative log-probability tends in probability to $h_2(p)$ by the same law. Thus, outside an event of probability tending to zero, each noise word has probability at most $2^{-n(h_2(p)-\delta )}$. The decoder's disjoint decision regions $D_j$ contain at most $2^n$ received words in total. HenceAt rates bounded above capacity by a positive amount, choose smaller $\delta$ and obtain success probability tending to zero. This establishes the strong converse as well as the ordinary impossibility of reliable transmission above $C$.

When $p=1/2$ the output is independent of the input, so success probability for uniform messages is at most $1/M_n$ and $C=0$. At $p=0$ or $1$ the channel is noiseless or deterministically inverted; all $2^n$ words can be distinguished, so $C=1$. These endpoints complete the theorem.

The Shannon second coding theorem states that the operational channel capacity of a finite discrete memoryless channel is $C={\max }_{p(x)}I(X:Y)$: rates below this maximum admit block codes with error tending to zero, and rates above it cannot have vanishing error. For this channel the preceding calculation givesusing maximum entropy on a finite alphabet. The transition matrix is a doubly stochastic matrix. Therefore the uniform input has uniform output: $p(y)=\frac{1}{3}{\sum }_{x}p(y\mid x)=1/3$. It achieves the entropy upper bound, and henceEquivalently this is the weakly symmetric channel capacity theorem: permutations of a common row and equal column sums make the uniform input optimal. If $q$ is uniform, the output contains no information about the input and the formula gives zero.

Use the Shannon second coding theorem in its channel capacity form $C={\max }_{P_X}I(X;Y)$. The finite-alphabet erasure channel erases independently of the input. On an unerased output Bob knows $X$ exactly; on the erasure output his posterior distribution is still $P_X$. Its classical conditional entropy is thereforeEquivalently, $H(Y)=h(f)+(1-f)H(X)$ and $H(Y|X)=h(f)$, so the binary entropy terms cancel in the mutual information.

For an alphabet of size $k$, Shannon entropy is at most ${\log }_{2}k$, with equality for the uniform distribution. Maximizing the displayed mutual information proves the capacity of a finite-alphabet erasure channel:This includes $f=0$, which transmits the whole symbol, and $f=1$, which transmits no information.

For a discrete random variable with probabilities $p_i$, its Shannon entropy in bits is $H(X)=-{\sum }_i{p}_i{\log }_2{p}_i$, with $0{\log }_{2}0=0$. Gibbs inequality states thatwith equality exactly when $p=q$. If $q_i=0<p_i$, the left side is infinite. Otherwise apply $-\ln u\ge 1-u$ to $u=q_i/p_i$ for $p_i>0$:Equality requires $q_i=p_i$ on the support and no remaining mass outside it. In particular, comparison with the uniform probability distribution on two outcomes gives binary Shannon entropy at most $1$.

Write $q=1-p_1$. For $q>0$, grouping the last two outcomes givesEquality holds if $p_2=p_3$; if $q=0$ it also holds, and then both are zero. Thus equality holds exactly when $p_2=p_3$.

For the discrete memoryless channel, assume $\alpha ,\beta \ge 0$ and $\alpha +\beta \le 1$, and set $w=1-\alpha -\beta$. Both conditional output probability distributions have Shannon entropy $H(w,\alpha ,\beta )$. The third output has probability $\beta$ regardless of the input; the first two have total probability $1-\beta$. Their Shannon entropy is maximized by making them equal, which a uniform input achieves. Hence the channel capacity isand thereforeThe usual zero-times-log convention includes $\beta =1$, when $C=0$. If $w=\alpha$, the rows coincide and every input achieves zero mutual information; otherwise the uniform input is the unique maximizing input.

If $p>1/2$, complementing every received bit converts the channel into a binary symmetric channel with crossover probability $1-p<1/2$. This deterministic and invertible output relabelling does not change the channel capacity. Since $h_2(p)=h_2(1-p)$,Thus the capacity rises again from zero as $p$ increases beyond $1/2$, reaching one at $p=1$, where every bit is flipped deterministically and can be recovered by complementation.

For a discrete memoryless channel with input $X$ and output $Y$, its information capacity iswhere $I(X;Y)$ is the mutual information and the maximum is over all input distributions. Capacity is measured in bits when logarithms have base two.

A binary symmetric channel independently flips each input bit with probability $p$, so, with rows indexed by the input and columns by the output, its channel matrix isIf $p>1/2$, complementing every received bit converts the channel into one with crossover probability $1-p<1/2$ without changing its information-carrying ability. The case $p=1/2$ has identical rows and capacity zero, so it suffices to study $p<1/2$.

The Shannon second coding theorem states that for every rate below the channel capacity there are arbitrarily long codes whose decoding error tends to zero, whereas no sequence of codes with rate above capacity can have vanishing error. It also identifiesFor the present channel,The output entropy is at most one bit, with equality for a uniform input. Hence the binary symmetric channel capacity isbits per channel use.

Suppose one row of a finite discrete memoryless channel is a convex combination of other rows: $W(\cdot \mid x_0)={\sum }_j{\alpha }_{j}W(\cdot \mid x_j)$. Deleting input $x_0$ leaves the channel capacity unchanged. Given any input law with mass $t$ on $x_0$, move that mass to the other symbols in proportions ${\alpha }_j$. The output law stays the same. By the concavity of information entropy, $H(W(\cdot \mid x_0))\ge {\sum }_j{\alpha }_{j}H(W(\cdot \mid x_j))$, so this replacement cannot increase conditional entropy $H(Y\mid X)$ and cannot decrease mutual information. Taking maxima proves the claim; the smaller channel is also trivially a restriction of the original one. If the entropy inequality is strict, every positive use of the redundant row is strictly suboptimal compared with its redistribution.

With channel feedback, resend each message bit through a binary erasure channel until a non-erased copy arrives, then move to the next bit. The channel decoder deletes erasure symbols, giving the message without error whenever transmission completes. For $q<1$, the waiting times have an independent and identically distributed geometric distribution with expectation $1/(1-q)$, so every finite message completes almost surely. The strong law of large numbers gives forward code rate $n/{\sum }_{j=1}^n{M}_j\to 1-q$, matching channel capacity. At $q=1$, transmission never completes. Independent erasure indicators, rather than independent message bits, are the essential hypothesis.

Let the input alphabet be $\{0,1,2\}$ and let the output be $Y=X+Z$, where independent noise is uniform on two distinct integers. Translating the output alphabet reduces the noise to $\{0,d\}$, $d\ge 1$. The reachable output alphabet has size $3+\min (d,3)$: it is the union of two three-element intervals shifted by $d$.

For $d=1$, every row of the transition matrix has conditional information entropy one bit, so $I(X;Y)\le {\log }_{2}4-1=1$. Input probabilities $(1/2,0,1/2)$ make the output uniform and attain one bit per use. For $d\ge 3$, the two translated input alphabets are disjoint and every output identifies its input. A uniform input then attains ${\log }_{2}3$ bits per use.

For $d=2$, reflection symmetry and concavity of information entropy permit restricting to input probabilities $(s/2,1-s,s/2)$. Conditional on output parity, outputs whose labels are even integers have probabilities $(1/4,1/2,1/4)$ and outputs whose labels are odd integers have probabilities $(1/2,1/2)$. Consequently $I(X;Y)=h_2(s)+s/2$. Its strictly negative second derivative and stationary equation ${\log }_2((1-s)/s)+1/2=0$ give $s=\sqrt{2}/(1+\sqrt{2})$ and channel capacity ${\log }_2(1+\sqrt{2})$. All three values follow from overlap of translated input alphabets, rather than from output alphabet size alone.