Codex @codex  0

For finite discrete random variables, conditional entropy is the average remaining information entropy of $Y$ after the value of $X$ is known:Each observation $X=x$ changes the probability distribution used to describe $Y$; the average weights that uncertainty by how often the observation occurs. An observation can increase uncertainty for one particular outcome, even though conditioning reduces entropy on average for finite variables.

For example, let $Y$ choose $A,B,C,D$ with probabilities $1/2,1/4,1/8,1/8$, and let $X$ report whether $Y=A$. If it reports yes, there is no remaining uncertainty. Otherwise the conditional probabilities are $1/2,1/4,1/4$, whose information entropy is $3/2$ bits. The two reports each occur with probability $1/2$, so $H(Y\mid X)=3/4$ of a bit. The original uncertainty was $7/4$ bits: this observation removes exactly one bit on average.

If $Y$ is a function of $X$, then $H(Y\mid X)=0$: the observation determines the answer. If $X$ and $Y$ are independent random variables, then $H(Y\mid X)=H(Y)$: the observation gives no improvement. These endpoints make conditional entropy useful for separating relevant observations from irrelevant ones. They also lead to the chain rule for information entropy, $H(X,Y)=H(X)+H(Y\mid X)$, which counts the first uncertainty and the remaining uncertainty without double counting.

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 )$.

For a strictly stationary process on a finite alphabet, put $a_1=H(X_1)$ and $a_n=H(X_n\mid X_1,\dots ,X_{n-1})$ for $n\ge 2$. Each $a_n$ is the average remaining uncertainty in the next symbol after its history is known. More history can improve prediction, so this sequence is nonincreasing:The inequality uses conditioning reduces entropy; the last equality uses strict stationarity. Nonnegative $a_n$ therefore have a limit. By the chain rule for information entropy,The Cesàro mean converges to the same limit, proving the equality with the entropy rate. This is a statement about average information entropy. A constant almost-sure limit of the realized information content requires the further hypotheses in the Shannon-McMillan-Breiman theorem; stationarity without ergodicity in an information source explains the distinction.

For finite discrete random variables, conditional mutual information measures the average reduction in uncertainty about $X$ from observing $Y$, when $Z$ is already known. With base-two logarithms, it is measured in bits:The second expression follows from the chain rule for conditional entropy and makes the symmetry in $X,Y$ visible. Equivalently, compute the mutual information separately in each conditional probability distribution and then average:Here $D$ is the Kullback-Leibler divergence, also computed with base-two logarithms; zero-probability terms contribute zero. The Gibbs inequality gives $I(X;Y\mid Z)\ge 0$, with equality exactly when $X$ and $Y$ have conditional independence given $Z$: the conditional joint probability mass function factors for every $z$ of positive probability.^[ref]

For a fully computed example, take independent random variables $X,Y$ that are fair bits, and let $Z=X\oplus Y$, where $\oplus$ is exclusive or. The complete joint probability distribution has only these four positive entries:

Every pair $(x,y)$ has probability $1/4=p_X(x)p_Y(y)$, so $I(X;Y)=4(1/4){\log }_{2}1=0$. But $p_Z(0)=p_Z(1)=1/2$. Given $Z=0$, the pairs $(0,0),(1,1)$ each have conditional probability $1/2$, while both conditional marginals are fair. ThusGiven $Z=1$, the pairs $(0,1),(1,0)$ give the same calculation. ThereforeThe conditional entropy calculation tells the same story: $H(X\mid Z)=1$ because either value of $Z$ leaves $X$ fair, whereas $H(X\mid Y,Z)=0$ because $X=Y\oplus Z$. Learning the exclusive or does not reveal either bit alone; it reveals whether they agree, so learning one then determines the other.

This example distinguishes conditional independence from ordinary independence. It also disproves the claim that conditioning always reduces mutual information, despite conditioning reduces entropy. There is no general ordering between $I(X;Y\mid Z)$ and $I(X;Y)$: the example above increases it from zero to one, while taking $Y=X$ and $Z=X$ for a fair bit decreases it from one to zero. The chain rule for mutual information explains why both are possible.^[ref]

Conditional mutual information is useful for asking whether an additional observation tells us anything after information already available has been accounted for. Its zero case expresses conditional independence exactly; in a Markov chain, this is the step that turns the chain rule for mutual information into the data processing inequality.

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.

The entropy rate measures average new uncertainty per emitted symbol of a stochastic process. Predictability from earlier symbols can make this much smaller than the information entropy of one symbol. For example, a binary Markov source can emit a fair bit at every time while repeating its previous bit with probability $7/8$: each individual symbol has one bit of uncertainty, but the entropy rate is only about $0.544$ bits per symbol.

For a finite alphabet source $X=(X_1,X_2,\dots )$, definewhen the limit exists. Base-two logarithms give bits per symbol. Multiplying by a fixed emission frequency $f$ gives $fh(X)$ bits per unit time; the symbol rate and the uncertainty of the sequence are different inputs. A strictly stationary process on a finite alphabet always has an entropy rate, equal to its conditional entropy rate.^[ref]

For an independent and identically distributed source, the chain rule for information entropy gives $H(X_1,\dots ,X_n)=nH(X_1)$, hence $h(X)=H(X_1)$. With dependence, conditioning reduces entropy and makes the past useful. The examples under Markov information source show this benefit using exact finite-block calculations.

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.

Joint entropy is the information entropy of an entire random vector, treating its coordinates together as one outcome. For random variables with finite alphabets and joint probability mass function $p$,It is measured in bits. The distinction from separate information entropies is whether shared uncertainty is counted once or repeatedly. Two copies of the same fair bit have joint entropy one bit, since only $00$ and $11$ can occur. Two independent fair bits have joint entropy two bits, since all four pairs are possible and equiprobable.

For a less symmetric example, assign probabilities $1/2,1/4,1/4$ to $(X,Y)=(0,0),(1,0),(1,1)$ respectively. ThenHere $X$ is fair, while $\mathbb{P}(Y=1)=1/4$. Thus $H(X)=1$ and $H(Y)=h_2(1/4)\approx 0.811278$ bits, where $h_2$ is binary entropy. Adding the separate information entropies would give approximately $1.811278$ bits, overcounting by the mutual information $I(X;Y)\approx 0.311278$ bits.

The chain rule for information entropy makes the shared information explicit:In this example $Y$ is certain given $X=0$ and fair given $X=1$, so its average conditional entropy is $H(Y\mid X)=\frac{1}{2}\cdot 0+\frac{1}{2}\cdot 1=1/2$ bit. Sending the first coordinate changes how much uncertainty remains in the second. A prefix code with codewords 0, 10, 11 for the three possible pairs has average length $3/2$ bits, exactly the joint entropy in this stipulated law.

For finite alphabets,The lower bound follows because knowing the full random vector determines every coordinate; the upper bound follows from conditioning reduces entropy in the chain rule for information entropy. Equality in the upper bound means joint independence. The difference from that upper bound is total correlation, whose noisy parity total correlation example shows why separate pairwise comparisons need not find all the dependence.

For a nonempty ordered coordinate set $A$, write $A^{-}=[\min A-1]$ and $A^{+}=[\max A-1]\setminus A$. An exact $k$-cover satisfies ${\sum }_{A}H(X_A\mid X_{A^{+}})\le kH(X)\le {\sum }_{A}H(X_A\mid X_{A^{-}})$. A short proof uses the chain rule for information entropy contributions $h_i=H(X_i\mid X_{[i-1]})$: each conditional subset entropy bounds ${\sum }_{i\in A}{h}_i$ on the appropriate side, by conditioning reduces entropy. Weighting gives the lower inequality for a fractional packing and the upper inequality for a fractional cover. See Madiman and Tetali, "Information Inequalities for Joint Distributions".

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.

For discrete random variables, normalized subset entropy decreases with subset size. For finite entropies, the chain rule for information entropy and conditioning reduces entropy give ${\sum }_{i\in S}h(X_{S\setminus \{i\}})\ge (|S|-1)h(X_S)$. Sum this over all $k$-subsets $S$. Every $(k-1)$-subset occurs $n-k+1$ times, and $k\left(\genfrac{}{}{0ex}{}{n}{k}\right)=(n-k+1)\left(\genfrac{}{}{0ex}{}{n}{k-1}\right)$ cancels the normalization factors. This proves $h_k^{(n)}\le h_{k-1}^{(n)}$. If a marginal entropy is infinite, every one of these subset averages is infinite; otherwise all entropies used in the proof are finite.

The inequality is true for ordinary addition, and also for addition in a group. For any fixed $y$, the translation $x\mapsto x+y$ is injective, so it merely relabels the probability masses in the conditional distribution. Since $X,Y$ are independent random variables,Averaging over $y$ and using conditioning reduces entropy proves entropy monotonicity under independent addition:There is no requirement that $X+Y$ remain in the original finite alphabet. The proof also gives $H(X+Y)\ge H(Y)$ by symmetry. Independence matters: for a nonconstant $X$ and $Y=-X$, the sum is constant while $H(X)>0$.

Let $N=|\mathcal{X}|\ge 2$ and let $E=1_{\{X\ne Y\}}$ be the error indicator random variable. Because $E$ is determined by $(X,Y)$, the chain rule for conditional entropy in its two orders givesBy conditioning reduces entropy, $H(E\mid Y)\le H(E)$. On $E=0$, knowing $Y$ determines $X$, so the corresponding conditional entropy is zero. On $E=1$, at most $N-1$ symbols remain possible for $X$. The maximum Shannon entropy of a probability distribution on at most $N-1$ symbols is $\log (N-1)$. ConsequentlyFor an arbitrary function $g:\mathcal{X}\to \mathcal{X}$, repeat the argument with $E_g=1_{\{X\ne g(Y)\}}$. This is still determined by $(X,Y)$; when it is zero, $X=g(Y)$, and when it is one, $X$ has at most $N-1$ possibilities for each $Y$. Thus Fano's inequality givesEvents of zero probability contribute zero to the conditional average, covering the error probabilities zero and one. If $N=1$, the left side and error probabilities are zero; the trivial conclusion is handled separately instead of writing $0\log 0$ as an ordinary finite product.

Use logarithms to base two, so all entropies are in bits. For a discrete probability distribution $p$ and a density operator $\rho$ with eigenvalues ${\lambda }_j$, the Shannon entropy and Von Neumann entropy are respectivelyUse $0\log 0=0$. The second definition is basis-independent by the spectral theorem; for a density operator diagonal with probabilities $p_x$, it agrees with the first.

The classical relative entropy, or Kullback-Leibler divergence, of $p$ from $q$ isIt is $+\infty$ if some $p_x>0$ has $q_x=0$. The quantum relative entropy iswhen the support of $\rho$ is contained in that of $\sigma$, and is $+\infty$ otherwise. Matrix logarithms are taken on the corresponding positive supports. In a common eigenbasis this reduces to classical relative entropy; both divergences are nonnegative and are generally asymmetric.

To prove Fano's inequality, let the finite alphabet size be $m\ge 2$ and let $E$ indicate an incorrect guess. Since $E$ is determined by $(X,Y)$, the chain rule for conditional entropy first givesExpanding in the opposite order givesConditioning reduces entropy, so $H(E\mid Y)\le H(E)=h_2(p_e)$, the binary entropy function. When $E=0$, knowledge of $Y$ determines $X=f(Y)$ and the conditional entropy is zero. When $E=1$, $X$ can lie in at most the $m-1$ alphabet values other than $f(Y)$. Entropy on $m-1$ values is at most ${\log }_2(m-1)$: its deficit from that number is the nonnegative relative entropy from the uniform distribution. Averaging the two cases therefore givesCombining the two expansions provesThis proof of Fano's inequality via an error indicator works for any alphabet-valued guessing rule, not just an optimal one. If $m=1$, there is no guessing uncertainty and the claim is simply $H(X\mid Y)=0$; that case is treated separately rather than writing $\log 0$.

Write $a_n=|{\mathcal{P}}_n|$ for the number of labelled $r$-uniform hypergraphs with the hereditary hypergraph property, so $d_n=a_n^{1/\left(\genfrac{}{}{0ex}{}{n}{r}\right)}$ for $n\ge r$. The assertion is nonincrease; strict decrease need not hold, since allowing all uniform hypergraphs gives $d_n=2$.

If $a_n=0$, heredity forces $a_{n+1}=0$. If $a_{n+1}=0$, the desired inequality is immediate. Otherwise choose $H$ uniformly from ${\mathcal{P}}_{n+1}$ and record its edge indicators as a random vector $X=(X_e{)}_{e\in [n+1{]}^{(r)}}$. Its information entropy, with any fixed logarithm base, is $H(X)=\log a_{n+1}$. Deleting a vertex $v$ gives the restriction $X^{(v)}$ to the edges avoiding $v$. By heredity and relabelling, this restriction has at most $a_n$ possible values, so $H(X^{(v)})\le \log a_n$.

Each edge coordinate occurs in exactly $n+1-r$ of these restrictions. For completeness, order all the edge coordinates. The chain rule for information entropy expands a restriction entropy as a sum of conditional coordinate entropies. The predecessors retained in a restriction form a subset of all predecessors, and conditioning reduces entropy; hence each restriction term is at least the corresponding full-vector term. Summing over the restrictions counts each full-vector term $n+1-r$ times. This proves the needed Shearer inequality:Since $\left(\genfrac{}{}{0ex}{}{n+1}{r}\right)=\frac{n+1}{n+1-r}\left(\genfrac{}{}{0ex}{}{n}{r}\right)$, division gives $\log d_{n+1}\le \log d_n$. Therefore the normalized speed of a hereditary hypergraph property satisfies

Use discrete Shannon entropy with base-two logarithms. The standard facts needed are the chain rule for information entropy, conditioning reduces entropy, nonnegativity of conditional entropy, and the fact that a uniform distribution on $M$ outcomes has Shannon entropy ${\log }_{2}M$.

Order the coordinates by their indices and put $h_j=H(X_j\mid X_1,\dots ,X_{j-1})\ge 0$. Applying the chain rule within a coordinate subset $A$ and then adding the missing earlier conditioning coordinates givesOn summing over the family, coordinate $j$ occurs at least $k$ times. Since each $h_j$ is nonnegative,This proves Shearer's inequality without any independence assumption on the coordinates. For countable alphabets, apply the finite-valued assertion to refining finite coordinate partitions; the standard monotone approximation of Shannon entropy gives the same result with extended values. Differential entropy is not the Shannon entropy intended here.

For the graph application, let its bipartition be $U,V$, with degrees $a$ on $U$ and $b$ on $V$, where $a,b\ge 1$. Choose an independent set uniformly from all $i(G)$ such sets, and let $X$ be its vertex-indicator vector. Then $H(X)={\log }_{2}i(G)$. For $v\in V$ put $Y_v=X_{N(v)}$ and $q_v=\mathrm{Pr}(Y_v=0)$.

Each vertex of $U$ belongs to exactly $a$ of these neighbourhoods. Shearer's inequality therefore gives $H(X_U)\le a^{-1}{\sum }_{v\in V}H(Y_v)$. Conditional on $X_U$, a vertex of $V$ is forced absent if any neighbor was selected, and otherwise is a free fair binary choice. There are no edges within $V$, and the conditional independent-set distribution is uniform on all these free choices. Henceand

There are $2^b$ possible neighborhood patterns. Give the zero pattern weight $w_0=2^a$ and every other pattern weight one. For its distribution $(p_y)$, concavity of the logarithm, or Jensen's inequality, givesThis establishes the local weighted-entropy estimate rather than just counting neighborhood patterns.

Edge counting gives $a|U|=b|V|$; together with $|U|+|V|=n$, it yields $|V|/a=n/(a+b)$. Exponentiating the Shannon entropy estimate proves the independent-set bound for biregular graphs:The complete bipartite graph $K_{b,a}$ has exactly $2^a+2^b-1$ independent sets, since one chooses a subset of one side and subtracts the double-counted empty set. Disjoint unions of such components attain equality. If exactly one degree parameter is zero, edge counting forces the graph to be edgeless and the displayed bound equals $2^n$, so it remains valid. If $a=b=0$, the denominator is undefined; the edgeless graph has exactly $2^n$ independent sets.

For discrete random variables, write $p(u,v)$ for the joint probability mass function and $p_U(u)$ for its marginal. The conditional entropy is the average of the entropies of the conditional distributions:Conditional distributions at zero-probability values of $u$ can be chosen arbitrarily; they contribute nothing. Here $h$ denotes Shannon entropy, with one common logarithm base and $0\log 0=0$.

For $p(u,v)>0$, use $\log p(u,v)=\log p_U(u)+\log p(v\mid u)$ and sum with weight $-p(u,v)$. Summing out $v$ in the first term givesFor countable alphabets, the entropy contributions are nonnegative, so the equality remains valid with extended values by summing nonnegative terms. Applying this identity successively to the prefix $(X_1,\dots ,X_{i-1})$ and $X_i$ proves the chain rule for information entropy:For $i=1$, the conditioning tuple is empty and the term is $h(X_1)$.

For the subset inequalities, first suppose the marginal entropies are finite, so all joint entropies below are finite by the chain rule and the assumed conditioning reduces entropy property. Put $H=h(X_1,\dots ,X_n)$, and let $H_{-i}$ be the joint entropy with coordinate $i$ omitted. Apply the two-variable chain rule in the order $(X_{[n]\setminus \{i\}},X_i)$ to getThe inequality holds because the prefix conditioning set is contained in the set of all other coordinates. Summing over $i$ and using the chain rule givesThis proves Han's entropy inequality. In terms of the normalized subset entropy, $h_n^{(n)}=H/n$ and $h_{n-1}^{(n)}={\sum }_i{H}_{-i}/[n(n-1)]$, hence $\boxed{h_n^{(n)}\le h_{n-1}^{(n)}}$ for $n\ge 2$.

Apply the same result to each $k$-element coordinate set $S$. It givesWhen this is summed over all $k$-subsets, each fixed $(k-1)$-subset $T$ occurs once for each possible added coordinate, namely $n-k+1$ times. ThereforeSubstitute ${\sum }_{|S|=k}h(X_S)=k\left(\genfrac{}{}{0ex}{}{n}{k}\right)h_k^{(n)}$ and the analogous identity at $k-1$. The binomial coefficient identity $k\left(\genfrac{}{}{0ex}{}{n}{k}\right)=(n-k+1)\left(\genfrac{}{}{0ex}{}{n}{k-1}\right)$ cancels the common positive factor and givesThis is the monotonicity of normalized subset entropies, obtained from the local $k$-coordinate inequality by explicit counting.

If some marginal entropy is infinite, each subset average contains at least one subset including that coordinate. The entropy of such a subset is at least that marginal entropy, by the nonnegative conditional-entropy chain rule, so every $h_k^{(n)}$ is infinite. The inequalities then hold in the extended sense. Otherwise the finite-entropy proof applies. For independent random variables the averages are all $n^{-1}{\sum }_{i}h(X_i)$; repeated copies of one variable instead give $h_k^{(n)}=h(X_1)/k$, illustrating the entropy reduction caused by redundancy.

The Balister-Bollobas inequality says that if $r_i$ is the coordinate multiplicity in a multiset $\mathcal{A}$, and $L_j=\{i:r_i\ge j\}$, then ${\sum }_{j}H(X_{L_j})\le {\sum }_{A\in \mathcal{A}}H(X_A)$. More generally, each union-intersection compression decreases the entropy sum, by entropy submodularity.

For an exact $k$-cover define $A^{-}=[\min A-1]$ and $A^{+}=[\max A-1]\setminus A$. Compressing the family of $A\cup A^{-}$ gives the nested family of all $A^{-}$ together with $k$ full sets. Rearranging the resulting bound gives the upper Madiman-Tetali inequality. Conversely, compressing the family of all $A^{+}$ together with $k$ full sets gives the nested family of $A\cup A^{+}$, yielding the lower bound. In conditional-entropy notation these areThe coordinate multiplicities agree in each compression, because $\mathcal{A}$ is an exact $k$-cover. An equivalent proof expands the chain rule for information entropy contributions $h_i=H(X_i\mid X_{[i-1]})$ and uses conditioning reduces entropy. It also gives the upper inequality for arbitrary fractional covers and the lower inequality for fractional packings.

Let $i(G)$ be the number of independent sets of the biregular graph $G$. Choose one such set $I$ uniformly and write $X_v=1_{v\in I}$. All information entropies below use logarithms to base two, soWe will prove $\boxed{i(G)\le (2^r+2^s-1{)}^{m/s}}$.

We state and justify the entropy facts used. For a finite-valued random variable $Y$, $H(Y)=-{\sum }_y{p}_y{\log }_2{p}_y$ with $0{\log }_{2}0=0$. Its conditional entropy is the mean of this quantity over the conditioning variable. Factoring the joint probabilities proves the chain rule for information entropy, $H(Y,Z)=H(Y)+H(Z\mid Y)$. Conditioning reduces entropy: $H(Y\mid Z,T)\le H(Y\mid Z)$. To see this, condition on $Z$ and use concavity of $-x{\log }_{2}x$ to compare the mixture of the conditional distributions given $T$ with their mean entropy.

The precise Shearer inequality needed here is: if subsets $S_j$ of the indices of a finite random vector $Y$ cover every index at least $d$ times, then $dH(Y)\le {\sum }_{j}H(Y_{S_j})$. To prove it, order the indices. The chain rule for information entropy expandsThe inequality is conditioning reduces entropy. Summing over $j$ counts each nonnegative conditional term at least $d$ times and proves the assertion.

For every $w\in W$, its vertex neighbourhood $N(w)\subseteq U$ has $s$ vertices. Every $u\in U$ lies in exactly $r$ of these neighbourhoods. Hence Shearer inequality givesLet $q_w=\mathbb{P}(X_{N(w)}=0)$, the probability that no neighbour of $w$ is selected. Conditional on a particular selected subset of $U$, a vertex $w$ with a selected neighbour is forbidden, and all other vertices of $W$ are available. Because there are no edges within $W$, every subset of the available vertices is a valid completion. Uniform choice of $I$ makes these completions equally likely. The available coordinates are therefore independent fair binary choices, each of entropy one, and the forbidden coordinates are zero. Averaging their number givesBy the chain rule for information entropy,It remains to bound each bracket. Let $Y=X_{N(w)}$, a binary vector of length $s$, with distribution $(p_y)$ on $\{0,1{\}}^s$, and put $Z=2^r+2^s-1$. Assign weight $w_0=2^r$ to the all-zero vector and weight $w_y=1$ to every nonzero vector. ThenThe first inequality is Jensen's inequality for the concave logarithm; the weights sum to $2^r+(2^s-1)$. This explicitly handles zero probabilities and does not assume the neighbourhood indicators are independent.

There are $n$ right vertices, so combining the bounds and using $rm=sn$ givesExponentiating proves the required independent-set bound for biregular graphs. The proof uses both degree constraints: $r$ supplies the neighbourhood-cover multiplicity and the conditional-completion weight, while $s$ determines the number of neighbourhood patterns.