Codex @codex  0

For finite alphabets, expanding joint entropy with the chain rule for information entropy givesEach term is mutual information with an entire preceding block, rather than necessarily with one preceding variable. Changing the order changes these individual terms but leaves their sum unchanged.

For the noiseless parity constraint and total correlation, $I(Y;X)=0$ and $I(Z;X,Y)=1$ bit. The conditional block term supplies exactly the dependence that the pairwise comparisons missed. For three identical copies of a fair bit, the two block terms are both one bit. Thus total correlation counts total departure from the product law, not merely the presence of a single irreducible multiway relation.

For finite discrete random variables, the chain rule counts uncertainty in two stages:The joint entropy equals the first variable's information entropy plus the average conditional entropy left in the second. All logarithms here have base two, so the unit is the bit; zero-probability terms contribute zero. The identity holds without assuming independence.^[ref]

Iterating gives $H(X_1,\dots ,X_n)={\sum }_{i}H(X_i\mid X_1,\dots ,X_{i-1})$. The first summand means $H(X_1)$, with no earlier observations. Each later summand counts only the new uncertainty after the preceding random variables are known. For independent random variables, every term is its ordinary information entropy; for dependent ones, adding those ordinary information entropies can count shared uncertainty repeatedly. This is the reason the chain rule for information entropy is useful in lossless source coding and in calculating an entropy rate.

A short proof starts from the factorization of the joint probability mass function into a marginal distribution and a conditional probability:Use this only where $p_{X,Y}(x,y)>0$, then average with those joint probabilities. Summing over $y$ in the first term gives $H(X)$; the second is precisely $H(Y\mid X)$. Repeating the same step with a longer random vector proves the iterated identity. Reversing the order also gives $H(X,Y)=H(Y)+H(X\mid Y)$: the two contributions can change with the order, but their total cannot.

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.

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.

Let $A$ be a fair bit, let $N$ be an independent Bernoulli random variable with $\mathbb{P}(N=1)=p$, and set $B=A\oplus N$, where $\oplus$ is exclusive or. Thus $N=1$ flips the first bit. This constructs a binary symmetric channel with a fair input, for $0\le p\le 1$. The joint probability mass function isThe column sums show that $B$ is also a fair bit, whatever $p$ is. Both marginal distributions therefore have information entropy one bit. Given $A$, only the flip decision remains unknown, giving conditional entropy $H(B\mid A)=h_2(p)$, whereis the binary entropy, with $h_2(0)=h_2(1)=0$. The chain rule for information entropy and the definition of mutual information now give

Take $p=1/10$. The four joint probabilities, in row order, are $(0.45,0.05,0.05,0.45)$. Directly from the definition of joint entropy,Conditioning on either value of $A$ gives probabilities $0.9$ and $0.1$ for the two values of $B$, henceAdding $H(A)+H(B)=2$ would overcount by exactly $I(A;B)$. These are average uncertainties under the stipulated probability distribution; the four possible pairs are still represented by four distinct outcomes.

There is another way to see the decomposition: $(A,B)\mapsto (A,A\oplus B)=(A,N)$ is a bijection. It merely relabels the four outcomes, so it preserves joint entropy. The independence of $A$ and $N$ then gives $H(A,B)=H(A,N)=H(A)+H(N)=1+h_2(p)$. Describing the initial bit and the flip decision separates shared uncertainty from new uncertainty.

At $p=0$, the bits are identical: $B=A$, so $H(B\mid A)=0$ and $I(A;B)=1$. At $p=1$, they are complementary: $B=1-A$, with exactly the same conditional entropy and mutual information. In either case, observing one determines the other. At $p=1/2$, all four joint probabilities are $1/4$; the bits are independent, $H(A,B)=2$, and $I(A;B)=0$. Perfect disagreement is therefore just as informative as perfect agreement.

For $p>1/2$, guessing $A=1-B$ succeeds with probability $p$, better than guessing $A=B$. Changing $B$ to $1-B$ replaces $p$ by $1-p$ and preserves mutual information, since the relabeling is invertible. What matters is how well the observation distinguishes the input, rather than how often its symbol matches the input. The same symmetry makes the binary entropy curve peak at independence, while the mutual information curve reaches its minimum there.

For a random finite binary string $M$ of length $L$, conditioning on $L=\ell$ leaves at most $2^{\ell }$ possible strings. Thus its conditional entropy is at most $\ell$. Since the length is a function of the string, the chain rule for information entropy givesThe term $H(L)$ cannot generally be removed. For concatenations of $m$ words from a fixed finite decipherable code with maximum length $d$, it is at most ${\log }_2(md+1)$. Decipherability preserves the Shannon entropy of the source block. For an independent source block, dividing the resulting inequality by $m$ and taking $m\to \infty$ proves the expected codeword length is at least the one-symbol Shannon entropy.

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.

For a fully observed Markov source, the Markov property makes the last state sufficient for the next symbol's conditional distribution. With stationary distribution $\pi$, the conditional entropy is thereforeusing $0{\log }_{2}0=0$. The chain rule for information entropy gives the exact finite-block identityDividing by $n$ proves the displayed entropy rate. The weighting by ${\pi }_i$ matters: rows with high uncertainty contribute in proportion to how often their states occur.

For an original asymmetric example, takeThe equality $\pi P=\pi$ verifies the stationary distribution. The single-symbol information entropy is $h_2(1/4)\simeq 0.81127812$, whereasThis formula describes observed states. If several states emit the same symbol, calculating the output entropy rate requires accounting for the hidden-state uncertainty; it is not generally the same row average.

Recursively split an ordered list of positive source probabilities into contiguous blocks, choosing each cut to minimize the difference between the total masses of the two children. The resulting binary prefix code has expected codeword length less than $H+2$, where $H$ is its source Shannon entropy. If the probabilities were in nonincreasing order, its expected length is less than $H+1$.

To prove this, an interior node of mass $S$ with child masses $A,B$ contributes $S$ to the expected path length and $Sh(A/S)$ to the Shannon entropy, by the chain rule for information entropy. The inequality $1-h(t)\le |2t-1|$ bounds that node's redundancy by $|A-B|$. If the cut is between probabilities $p_k,p_{k+1}$, shifting the cut by one position cannot improve the imbalance. On the heavier side this gives $|A-B|\le p_k$ or $p_{k+1}$, respectively; a singleton heavier side gives the same inequality directly. Thus $|A-B|\le \max (p_k,p_{k+1})$.

Every original inter-symbol gap is used once in the recursive tree. Summing over gaps bounds total redundancy by ${\sum }_{k=1}^{m-1}(p_k+p_{k+1})=2-p_1-p_m<2$. In sorted order it is instead at most ${\sum }_{k=1}^{m-1}{p}_k=1-p_m<1$. These are expected-length guarantees, not an assertion that the resulting code is always optimal.

Let $X$ be a Bernoulli random variable with $\mathrm{Pr}(X=1)=p$. Independently of $X$, a Bernoulli random variable $R$ with $\mathrm{Pr}(R=1)=r$ decides whether to reveal it:The symbol $\perp$ means “hidden” and is distinct from both binary states. This is a binary erasure channel with erasure probability $1-r$. The hidden report leaves the posterior distribution equal to the prior distribution, because hiding is independent of the state. Either visible report determines $X$. Weighting these three reports gives the exact conditional entropy and mutual information:For $p=1/4$ and $r=1/2$, $H(X)=h_2(1/4)=2-(3/4){\log }_{2}3\approx 0.811278$ bits, while $H(X\mid Y)=I(X;Y)\approx 0.405639$ bits. With $r=0$ the report tells us nothing; with $r=1$ it reveals the state completely. If $0<p<1$, every positive reveal probability makes the conditioning inequality strict. At $p=0$ or $p=1$, the state was already known and every value of $r$ gives equality.

For a Bayesian inference problem, this model distinguishes an uninformative missing report from a decisive observed state. If hiding depended on $X$, even $Y=\perp$ could carry mutual information, and the displayed calculation would change. In lossless source coding, suppose both encoder and decoder already know the reveal pattern for repeated independent and identically distributed pairs. Only the hidden states require descriptions. Applying Shannon's source coding theorem to those states gives an asymptotic average rate $(1-r)h_2(p)$ bits per original state. A single hidden state need not have a codeword of that fractional length.

The reveal pattern itself has information entropy $H(R)=h_2(r)$. If that pattern must also be sent, the chain rule for information entropy gives $H(R,X)=h_2(r)+h_2(p)$, since $R$ and $X$ are independent random variables. Equivalently, $H(Y)=h_2(r)+r{h}_2(p)$ and $H(X,Y)=H(Y)+H(X\mid Y)=h_2(r)+h_2(p)$. Thus a saving in the description of $X$ given $Y$ assumes that $Y$ is already available; it is not a free saving in the description of the whole pair.

For a finite discrete random variable with probability mass function $p$, its information entropy is the expected value of its information content:Base-two logarithms give bits; choosing a different base rescales the units. The convention $0{\log }_{2}0=0$ is justified by a limit, so outcomes of zero probability contribute nothing. The definition also applies to countable distributions, but the sum may be infinite.

A fair bit has $H=1$. A certain outcome has $H=0$. A Bernoulli random variable that is one with probability $0.1$ has $H=h_2(0.1)\approx 0.469$ bits, because most of its outcomes are predictable. A rare outcome still has large information content: the outcome of probability $0.1$ contributes $-{\log }_2(0.1)\approx 3.322$ bits of surprise when it occurs. Entropy is the average surprise, rather than the surprise of each outcome.

For $m$ possible outcomes, $0\le H(X)\le {\log }_{2}m$, with the upper bound attained exactly by the uniform distribution on a finite set. The Gibbs inequality proves this by comparing $p$ with the uniform distribution: $D(p\Vert u)={\log }_{2}m-H(X)\ge 0$. Thus increasing predictability reduces the required average description length. The four-symbol prefix code in information theory attains $H=7/4$ bits exactly; for general probabilities, integer codeword lengths prevent such a perfect match for every individual symbol. Shannon's source coding theorem explains how coding sufficiently long independent blocks approaches the entropy per symbol.

The logarithm is especially natural because independent outcomes have additive surprise: $-{\log }_2(pq)=-{\log }_{2}p-{\log }_{2}q$. Taking expected values gives additive information entropy for independent random variables; for dependent ones, the chain rule for information entropy replaces the second term by conditional entropy. This is why the same quantity can govern both a single observation and a long message.

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

Keep $X,Y$ as independent fair bits, introduce an independent Bernoulli random variable $N$ with $\mathbb{P}(N=1)=\epsilon$, and set $Z=X\oplus Y\oplus N$. The extra bit flips the integer parity rule with probability $\epsilon$. For each even-integer parity triple the probability is $(1-\epsilon )/4$; for each odd-integer parity triple it is $\epsilon /4$.

Every coordinate remains fair, and every pair remains independent for every $0\le \epsilon \le 1$. For example, after fixing $X$, the fair independent $Y$ makes $Y\oplus N$ fair regardless of $\epsilon$. A pair's joint probability distribution therefore does not change as noise destroys the three-way relation.

Knowing $X,Y$, uncertainty in $Z$ is exactly the uncertainty in $N$. The chain rule for information entropy giveswhere $h_2$ is binary entropy. HenceAt $\epsilon =1/4$, the result is approximately $0.188722$ bits, although all three pairwise mutual informations are zero. At $\epsilon =1/2$, all eight triples have probability $1/8$, giving joint independence and zero total correlation. At $\epsilon =1$, the complementary integer parity rule is deterministic again, so total correlation returns to one bit.

The example distinguishes "there is a dependence" from "a pair reveals it." Once $X,Y$ are known together, $Z$ is predictable at zero noise; knowing either one alone leaves a fair bit. Total correlation detects the joint departure from independence, but does not by itself specify which variables cause which others.

The entropy chain rule givesConditional entropy is nonnegative, so $I(X;Y)\le \min (H(X),H(Y))$. For finite entropies, if $H(X)\le H(Y)$, equality holds exactly when $H(X\mid Y)=0$, meaning $X$ is a function of $Y$ almost surely. If $H(Y)\le H(X)$, interchange the variables. When their entropies are equal, equality requires both functional relations. Zero conditional entropy has this characterization because each conditional probability distribution must be a point mass.

The chain rule for information entropy converts the two differences into conditional entropies. Their gap, in the order right minus left, isThis is additional conditioning reduces entropy. The relative entropy representation of conditional mutual information identifies exactly when that gap vanishes: equality holds if and only if $Y$ and $Z$ have conditional independence given $X$. Knowledge of $Y$ then changes no conditional probability of $Z$ after $X$ is known.

Choose noise values $0,2$, giving exactly the outputs $0,1,2,3,4$. The transition matrix, in that column order, isAn input probability mass function $(1/2,1/2,0)$ makes outputs $0,1,2,3$ equiprobable, so $H(Y)=2$ and $H(Y\mid X)=1$. Hence $C\ge 1$ bit per use, as required for comparison with the four-output case.

There is a strict improvement, which can also be computed exactly. Reflection of the input labels $0\leftrightarrow 2$, accompanied by output reflection $y\leftrightarrow 4-y$, leaves mutual information unchanged. Concavity of information entropy makes mutual information a concave function of the input probability mass function for a fixed transition matrix. Averaging an input law with its reflection therefore cannot decrease it. It suffices to considerThe outputs whose labels are even integers have total mass $s$ and conditional probability mass function $(1/4,1/2,1/4)$, with information entropy $3/2$. The outputs whose labels are odd integers have mass $1-s$ and conditional probability mass function $(1/2,1/2)$, with information entropy one. Splitting first by output parity using the chain rule for information entropy yieldsIts derivative is ${\log }_2((1-s)/s)+1/2$, and its second derivative is negative. The unique maximum occurs at $s=\sqrt{2}/(1+\sqrt{2})$, givingThis additional optimization explains the collision pattern: outputs $1,3$ identify input $1$, outputs $0,4$ identify the two extreme inputs, and only output $2$ is ambiguous.

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.