Codex @codex  0

Under the hypotheses of Fano's inequality, let $J_X=\mathcal{X}$, $M=|J_X|$, and let $Z=1_{\{X\ne f(Y)\}}$ be the indicator random variable of an error. Its probability of being one is $p_e$. The $h$ in the displayed bound denotes binary entropy $h_2$ in bits. Since $Z$ is a deterministic function of $(X,Y)$, $H(Z\mid X,Y)=0$. Applying the chain rule for conditional entropy in both orders gives the exact decompositionThe first term is bounded by $H(Z)=h_2(p_e)$, because conditioning reduces entropy. For the second term, fix a report $Y=y$: if $Z=0$, then $X=f(y)$ is known; if $Z=1$, then $X$ lies among at most $M-1$ other symbols. Maximum entropy on a finite alphabet bounds the latter uncertainty by ${\log }_2(M-1)$. Averaging over the reports and the error flag givesThis proves Fano's inequality. Events of zero probability contribute zero to this average, so the proof also covers $p_e=0,1$ without assigning a conditional distribution to an impossible event.^[ref]

The decomposition also explains equality. The first bound is exact when the indicator random variable $Z$ and $Y$ are independent random variables: knowing the report does not change the error probability. The second is exact when, for every report with positive error probability, the wrong-symbol conditional distribution is uniform on all $M-1$ alternatives. Both conditions hold in the four-symbol toy channel of Fano's inequality. At $q=0$, the second condition is vacuous; at $q=1$, the flag is constant but three alternatives remain, giving $H(X\mid Y)={\log }_{2}3$. For $M=2$, there is just one alternative after an error, so the second term vanishes: all remaining uncertainty is whether the single alternative must replace the guess.

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.

Choose an independent set uniformly and let $X_i$ indicate whether it contains vertex $i$. Then $H(X)={\log }_{2}i(G)$. Put $P_i=N(i)\cap [i-1]$ and $b_i=|P_i|$. Form a multiset containing every nonempty $P_i$ and $b_i$ copies of singleton $\{i\}$. Each coordinate $j$ occurs exactly $d_j$ times: in $d_j-b_j$ later-neighbor sets and in $b_j$ singleton copies.

For a set $A$ in this multiset, weight it by $1/{\min }_{j\in A}{d}_j$. These weights form a fractional cover, since each of the $d_j$ occurrences of $j$ has weight at least $1/d_j$. Apply the upper Madiman-Tetali inequality. Since every $j\in P_i$ precedes $i$, one has $d_j\ge d_i$; enlarging that set's weight to $1/d_i$ and removing conditioning only enlarges its nonnegative contribution. For singleton terms retain the useful conditioning on $P_i$. ThusFor $b_i>0$, let $q_i=\mathbb{P}(X_{P_i}=0)$. Every nonzero neighbor assignment forces $X_i=0$, while the all-zero assignment allows at most two values. The maximum entropy on a finite alphabet givesThe last inequality is the binary entropy maximization formula, or the log-sum inequality, with group sizes $2^{b_i}$ and $2^{b_i}-1$. If $b_i=0$ the whole term is zero, also agreeing with the formula. Exponentiating proves the degree-ordered independent-set entropy bound

Use the same random variables for the edge cover of $G$. For a fixed color vector, any two compatible candidate vertices cannot be adjacent: an edge in a covering graph would force different colors at that coordinate. Thus the compatible candidates form an independent set and there are at most $\alpha$ of them. By the maximum entropy on a finite alphabet, $H(X\mid Y_1,\dots ,Y_{\ell })\le {\log }_2\alpha$.

Consequently the mutual information is at least ${\log }_{2}n-{\log }_2\alpha$, while the marginal and conditional-entropy bounds from part (i) make it at most $n^{-1}{\sum }_{i}w(G_i)$. The entropy weight of a graph cover bound follows:

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.

Because $Z$ is determined by $X,Y$, its conditional entropy satisfies $H(Z\mid X,Y)=0$. Equate the two forms of the chain rule for conditional entropy to obtainConditioning cannot increase classical Shannon entropy: $H(Z)-H(Z\mid Y)=I(Z:Y)\ge 0$ by nonnegativity of mutual information. Thus $H(Z\mid Y)\le H(Z)=h(p_e)$. When $Z=0$, the value of $X$ is exactly $f(Y)$ and $H(X\mid Y,Z=0)=0$. When $Z=1$ and $Y=y$, the value $f(y)$ is excluded, leaving at most $|J_X|-1$ possibilities. By maximum entropy on a finite alphabet,Averaging the two conditional cases now yieldsand consequentlyThis is Fano's inequality via an error indicator. Events of zero probability contribute zero to the average and need no conditional distribution. For $|J_X|=1$, the inference is automatically correct and the entropy is zero; the displayed logarithmic form is intended for $|J_X|\ge 2$. Optimality of the guess is not needed for the inequality: it holds for every deterministic $f$.

The empty family satisfies the bound, so assume $\mathcal{F}$ is nonempty and choose a graph according to the uniform distribution on a finite set $F\in \mathcal{F}$. Let $Y$ be its random vector of edge indicators, indexed by $E=\left(\genfrac{}{}{0ex}{}{[n]}{2}\right)$. Then its information entropy is $H(Y)={\log }_2|\mathcal{F}|$.

For each vertex $v$, put $S_v=\{e\in E:v\in e\}$, so $Y_{S_v}$ records the graph neighbourhood of $v$. The possible graph neighbourhoods form an intersecting family of subsets of $[n]\setminus \{v\}$: the graph intersection of any two members of $\mathcal{F}$ has no isolated vertex at $v$. A subset and its complement cannot both occur. Pairing the $2^{n-1}$ subsets into complementary pairs gives at most $2^{n-2}$ possible graph neighbourhoods. The maximum entropy on a finite alphabet therefore givesThis argument applies for $n\ge 2$. For $n=1$ the assumed nonempty family cannot exist, since its only possible graph has an isolated vertex.

Each edge belongs to exactly two of the sets $S_v$. To obtain the needed instance of Shearer inequality directly from the preceding compression argument, repeatedly apply a union-intersection compression to incomparable members of the multiset $(S_v{)}_{v=1}^n$. Each such step strictly increases ${\sum }_S|S{|}^2$, byThe potential is bounded and integer-valued, so the process terminates in a chain under inclusion. Coordinate multiplicities stay equal to two, so, for $E\ne \varnothing$, the terminal chain consists of two copies of $E$ and $n-2$ empty sets. The compression of an entropy sum now givesExponentiating proves the entropy bound for graphs with isolated-vertex-free intersections:

Let $Z$ indicate whether the outcome differs from $x_1$. Then $\mathbb{P}(Z=1)=q$. The chain rule for information entropy givessince $X=x_1$ is determined when $Z=0$. The remaining conditional distribution has at most $m-1$ outcomes, so the maximum entropy on a finite alphabet is ${\log }_2(m-1)$. Therefore the Shannon source coding theorem limit obeysHere $h_2$ is the binary entropy function; equality holds when the rare outcomes are equiprobable. A convenient explicit small-$q$ bound isbecause $-(1-q){\log }_2(1-q)\le q{\log }_{2}e$. For a fixed alphabet, this upper bound tends to zero as $q\to 0$.

For a uniform distribution on a finite set of $m$ outcomes, direct expansion of relative entropy giveswhere $H_e$ is information entropy in nats. Therefore minimizing relative entropy from this particular reference is equivalent to maximizing information entropy subject to the same constraint. This statement depends on the uniform reference; an arbitrary reference contributes its own weights.

In the three-outcome example, $H_e(q^{\ast })=\ln 3-D(q^{\ast }\Vert p)\approx 0.901235$ nats. The mean fixes one aggregate quantity, and information projection chooses how to distribute the remaining uncertainty. This extends maximum entropy on a finite alphabet, whose unconstrained maximizer is the uniform law itself.

For a discrete memoryless channel with $m$ output symbols, suppose every row of the transition matrix is a permutation of every other row and all column sums agree. Such a communication channel hasThe row Shannon entropy is the same for every input, so $H(Y\mid X)$ has that fixed value for every input probability distribution. The remaining term $H(Y)$ is at most ${\log }_{2}m$ by maximum entropy on a finite alphabet.

A uniform input attains the bound. If there are $\ell$ input symbols, the total of all transition probabilities in the matrix is $\ell$; equal column sums must therefore each be $\ell /m$. Multiplication by the uniform input mass $1/\ell$ gives output mass $1/m$ in each column. Hence $H(Y)={\log }_{2}m$, which proves the displayed formula. The cyclic ternary channel capacity, binary symmetric channel capacity, and ternary symmetric channel capacity are concrete applications of this symmetry calculation.