Chapter 24: Information-Theoretic and Entropy Methods

Can partial observations bound the size of an entire family?

Suppose an object has three coordinates, but an observer sees only selected coordinate pairs. How many complete objects could be consistent with small observed families? Counting each coordinate separately can lose correlations; overlapping observations may give a stronger bound without revealing every object.

Entropy turns this question into a probability argument. Choose an object uniformly from the family. Its entropy is the logarithm of the family size, while each observation has entropy bounded by the logarithm of its possible values. Information inequalities then connect the whole object to those observations.

We use finite probability, conditional expectation, and elementary logarithms. Shannon entropy will always use base-2 logarithms and be measured in bits. The optional concentration section explicitly changes to natural logarithms for a different entropy functional. No general probability course is required to follow the finite examples.

24.1 Shannon entropy fundamentals

For a finite random variable $X$ with probabilities $p(x)$, define its Shannon entropy by

$$ H(X)=-\sum_xp(x)\log_2p(x). $$

Use $0\log_20=0$, justified by continuity. An outcome's information content is $-\log_2p(x)$; entropy is its average. A deterministic variable has entropy zero, a fair bit has entropy one, and a uniform variable on $M$ outcomes has entropy $\log_2M$.

If the support contains $M$ positive-probability outcomes, then

$$ 0\le H(X)\le\log_2M. $$

For the upper bound, concavity of the logarithm gives $\mathbb E\log_2(1/p(X))\le\log_2\mathbb E[1/p(X)]=\log_2M$. Equality holds precisely for a uniform distribution on the support. Thus a support bound controls entropy even when the observed variable is not uniform.

For finite $X,Y$, define conditional entropy by

$$ H(X\mid Y)=\sum_y\Pr(Y=y)H(X\mid Y=y). $$

The chain rule is $H(X,Y)=H(Y)+H(X\mid Y)$. It follows by factoring $p(x,y)=p(y)p(x\mid y)$ and splitting its logarithm. More generally,

$$ H(X_1,\ldots,X_n)=\sum_{i=1}^nH(X_i\mid X_1,\ldots,X_{i-1}). $$

Conditioning reduces entropy on average:

$$ H(X\mid Y,Z)\le H(X\mid Y)\le H(X). $$

To see this, the distribution of $X$ is a mixture of its conditional distributions, and entropy is concave because $-u\log_2u$ is concave. Apply this fact separately at each value of $Y$ for the first inequality. It does not assert that every particular conditioning value reduces entropy.

Solved example. Let $X$ be a fair bit and $Y=X$. Then $H(X)=H(Y)=1$, $H(X,Y)=1$, and $H(Y\mid X)=0$. Two recorded bits carry only one bit of information because the second is a copy. For independent fair bits instead, $H(X,Y)=2$.

The binary entropy function is $h(p)=-p\log_2p-(1-p)\log_2(1-p)$. A bit equal to 1 with probability $1/4$ has entropy $h(1/4)\approx0.8113$, below one bit. The foundational source is Shannon, A Mathematical Theory of Communication.

Exercise. A variable has probabilities $1/2,1/4,1/4$. Find its entropy. Hint: the information contents are 1,2,2 bits. Solution: $H=(1/2)1+(1/4)2+(1/4)2=3/2$ bits, below $\log_23$.

24.2 Entropy proofs of counting inequalities

The basic entropy counting template has three steps: sample uniformly from the desired family, upper-bound its entropy using easier observations, and exponentiate. Uniformity is needed for the full object's entropy to equal the logarithm of the number being counted; the observations usually need not be uniform.

Subadditivity. For arbitrary finite variables,

$$ H(X_1,\ldots,X_n)\le\sum_iH(X_i). $$

This is the chain rule followed by conditioning reducing entropy. Equality holds when the coordinates are mutually independent. For a nonempty family $\mathcal F\subseteq A_1\times\cdots\times A_n$, it gives $|\mathcal F|\le\prod_i|A_i|$. The bound is elementary, but the entropy proof makes clear where stronger constraints could enter.

A binomial estimate. Let $X$ be a uniform binary word of length $n$ with exactly $k$ 1s, for $0\le k\le n$. There are $\binom nk$ such words. By symmetry each coordinate is 1 with probability $k/n$, so

$$ \log_2\binom nk=H(X)\le n h(k/n),\qquad \binom nk\le2^{n h(k/n)}. $$

The endpoints have both sides equal to 1. For $0\lt k\lt n$, this supplies the correct exponential scale while omitting smaller factors; it is not an exact formula for the binomial coefficient.

Solved instance. For $n=6,k=2$, the exact count is 15 and the entropy bound is

$$ 2^{6h(1/3)}=\frac{3^6}{2^4}=\frac{729}{16}. $$

This is below the unrestricted count $2^6=64$, but well above 15. The fixed-weight condition makes the coordinates dependent, and subadditivity does not capture all of that dependence.

Exercise. Why can a projection of a uniform family fail to be uniform? Hint: compare fiber sizes. Solution: an observed value's probability equals the number of family members projecting to it divided by the family size. Unequal fiber sizes give unequal probabilities.

24.3 Shearer's lemma

For $X=(X_1,\ldots,X_n)$ and a coordinate set $S\subseteq[n]$, write $X_S$ for the corresponding subvector. Let $S_1,\ldots,S_m$ be a list of coordinate sets, allowing repetitions, and assume each coordinate appears in at least $k\ge1$ of them. Shearer's lemma states

$$ kH(X)\le\sum_{j=1}^mH(X_{S_j}). $$

There is no independence hypothesis on the coordinates. The list's coverage condition is the essential combinatorial input.

Complete proof. Expose coordinates in the order $1,\ldots,n$. For any $S$, the chain rule and conditioning reducing entropy give

$$ H(X_S)=\sum_{i\in S}H(X_i\mid X_{S\cap\{1,\ldots,i-1\}}) \ge\sum_{i\in S}H(X_i\mid X_1,\ldots,X_{i-1}). $$

Summing over the observation sets counts each right-hand conditional entropy at least $k$ times. These quantities are nonnegative, so the sum is at least $kH(X)$ by the full chain rule. Extra coverage can only increase this lower bound.

Solved three-coordinate case. Use $S_1=\{1,2\}$, $S_2=\{1,3\}$, $S_3=\{2,3\}$. Every coordinate is covered twice, yielding

$$ 2H(X_1,X_2,X_3)\le H(X_1,X_2)+H(X_1,X_3)+H(X_2,X_3). $$

For the opening family, the two sides are 4 and $3\cdot(3/2)=9/2$ bits. The inequality is strict. If the three coordinates are independent fair bits, both sides equal 6, so the factor 2 cannot be improved generally.

The SVG displays the coverage rather than assuming independence. Each row is an observed coordinate set, each dot an inclusion, and each column has two dots. Its numerical panel uses the exact distribution from the worked example. For general projection and entropy inequalities, see Balister and Bollobás, Projections, Entropy and Sumsets.

Exercise. For four coordinates, observe all four triples obtained by omitting one coordinate. What is the coverage $k$? Hint: each coordinate is omitted once. Solution: $k=3$, so $3H(X)\le\sum_{i=1}^4H(X_{[4]\setminus\{i\}})$.

24.4 Entropy and combinatorial projections

For a nonempty finite family $\mathcal F\subseteq A_1\times\cdots\times A_n$, define its projection $\pi_S(\mathcal F)$ as the set of distinct coordinate subvectors occurring on $S$. Projection size counts observed values, not the number of original objects producing them.

Sample $X$ uniformly from $\mathcal F$. If coordinate sets $S_1,\ldots,S_m$ cover each coordinate at least $k$ times, Shearer and the support bound imply

$$ k\log_2|\mathcal F|\le\sum_jH(X_{S_j}) \le\sum_j\log_2|\pi_{S_j}(\mathcal F)|. $$

Exponentiating proves the projection inequality

$$ |\mathcal F|^k\le\prod_j|\pi_{S_j}(\mathcal F)|. $$

The observation sets overlap, but the coverage factor corrects for repeatedly accounting for the same coordinates. Multiplying their sizes without that correction gives a valid but often weaker elementary bound when the joint observations identify each object.

Fractional version. If nonnegative weights $w_j$ satisfy $\sum_{j:i\in S_j}w_j\ge1$ for every coordinate $i$, the same chain-rule proof gives

$$ H(X)\le\sum_jw_jH(X_{S_j}),\qquad |\mathcal F|\le\prod_j|\pi_{S_j}(\mathcal F)|^{w_j}. $$

For the three coordinate pairs, take every weight $1/2$. Fractional coverage is useful when observations have unequal sizes or when a cover cannot be represented efficiently by one integral multiplicity.

Solved limitation. The even-parity family $\{000,011,101,110\}$ has four words, but every coordinate pair projects onto all four binary pairs. The projection-size bound therefore allows eight words. Pair observations do not expose the three-way parity restriction when used only through their supports. Entropy inequalities are bounds, not guaranteed reconstructions of all hidden constraints.

Exercise. Pair projection sizes are at most 2,3,4 in a three-coordinate family. What integer size bound follows? Hint: square the full-family size. Solution: $|\mathcal F|^2\le24$, hence $|\mathcal F|\le4$.

24.5 Loomis–Whitney inequality

The discrete Loomis–Whitney inequality states that for any finite family $\mathcal F$ in a product of $d\ge2$ coordinate sets,

$$ |\mathcal F|^{d-1}\le\prod_{i=1}^d|\pi_{[d]\setminus\{i\}}(\mathcal F)|. $$

If the family is empty, the statement is immediate; otherwise choose uniformly from it. The $d$ observations each omit one coordinate, so every coordinate appears $d-1$ times. Section 24.4 then proves the inequality completely. No geometry, independence, or equal coordinate alphabets are required for this discrete form.

Solved equality case. Let $\mathcal F=A\times B\times C$ with sizes 2,3,2. Then $|\mathcal F|=12$ and its pair projections have sizes 6,4,6. Thus $12^2=6\cdot4\cdot6=144$. Cartesian boxes attain equality because independent uniform coordinates make the entropy and support bounds exact.

For a general box with side sizes $a_1,\ldots,a_d$, each $a_i$ occurs in exactly $d-1$ of the projected products, explaining equality algebraically. Removing points can change the projections unevenly and introduce entropy dependence, so equality should not be assumed for every family with the same enclosing box.

Exercise. A three-dimensional finite family has three pair projections of sizes 4,4,4. Bound its size and give an example attaining the bound. Hint: a binary box has these projection sizes. Solution: $|\mathcal F|\le8$, attained by $\{0,1\}^3$.

24.6 Entropy compression

Entropy compression proves that a randomized construction cannot keep failing if its random inputs can be reconstructed from a sufficiently small record of failures and a final state. The decisive condition is injectivity: different input streams must not silently collapse to the same recorded description. A shorter-looking log without a decoding proof gives no counting contradiction.

We give a complete elementary example for proper graph coloring. It proves the familiar $\Delta+1$ color guarantee; its purpose is to make reconstruction transparent. More sophisticated applications erase larger configurations and require more elaborate records. A primary example is Dujmović, Joret, Kozik, and Wood, Nonrepetitive Colouring via Entropy Compression.

Let $G$ be a fixed simple graph on ordered vertices $1,\ldots,n$, of maximum degree $\Delta\ge1$. Give each vertex a fixed ordered neighbor list and use $q\gt\Delta$ colors. Begin with every vertex uncolored. At each step, choose the smallest uncolored vertex $v$ and sample a color uniformly from $[q]$.

• If no colored neighbor has that color, keep it and record 0.
• Otherwise choose the first conflicting neighbor in the fixed list, record its list position $j\in[\Delta]$, and erase only the new color of $v$.

The retained partial coloring is always proper. A successful step colors one new vertex; a failure leaves the state unchanged. Stop when all vertices are colored.

Reverse decoding. From the record, the attempted vertex at each step is known: it is one plus the number of earlier successful records, because colored vertices always form a prefix. Start from the final partial coloring and reverse the steps. For a record 0, the sampled color is the current color of that vertex; recover it and uncolor the vertex. For a failure record $j$, the sampled color was the color of the recorded neighboring vertex, which is present in the reconstructed pre-step state. Read it; the partial state itself needs no change. Thus the full consumed random stream is determined by the log and final state.

Counting nontermination. Fix an input length $T$. A run that has not finished by then has at most $n-1$ successful records. The number of possible logs is at most

$$ \sum_{s=0}^{n-1}\binom Ts\Delta^{T-s}, $$

where $\binom Ts=0$ if $s\gt T$. There are at most $(q+1)^n$ partial color states, including an uncolored symbol. Injectivity therefore bounds the number of failing input streams by the product of these quantities. Since all $q^T$ streams are equally likely,

$$ \Pr(\text{unfinished after }T) \le\frac{(q+1)^n}{q^T}\sum_{s=0}^{n-1}\binom Ts\Delta^{T-s} =O\left(T^{n-1}(\Delta/q)^T\right)\to0 $$

for this fixed graph. The algorithm terminates with probability 1 and a proper coloring exists. The implied constant depends on $n,q,\Delta$; this estimate alone is not a uniform polynomial-time claim. An edgeless graph finishes in exactly $n$ steps and needs no failure count.

Solved trace. On the path with edges 12,23, use colors $1,2,3$ and neighbor lists $N(1)=(2)$, $N(2)=(1,3)$, $N(3)=(2)$.

The final coloring is $(1,2,3)$ and the log is $(0,1,0,1,0)$. Reversing recovers colors $3,2,2,1,1$ in reverse order, hence exactly the original stream. A failure record is a neighbor-list position, not a global vertex number; this distinction is what bounds its alphabet by $\Delta$.

Exercise. Why is counting logs alone insufficient? Hint: consider the first successful color choice. Solution: its log is 0 regardless of which color was sampled. The final partial state retains the information needed to recover successful choices; omitting it loses injectivity.

24.7 Information inequalities in combinatorics

For probability distributions $P=(p_i)$ and $Q=(q_i)$ on a finite alphabet, the relative entropy or Kullback–Leibler divergence in bits is

$$ D(P\Vert Q)=\sum_i p_i\log_2\frac{p_i}{q_i}. $$

Terms with $p_i=0$ are zero; a term with $p_i\gt0$ and $q_i=0$ makes the divergence infinite. Gibbs' inequality states $D(P\Vert Q)\ge0$, with equality precisely when $P=Q$.

Proof. For positive $p_i,q_i$, use $-\ln u\ge1-u$ with $u=q_i/p_i$. Summing gives $\sum_i p_i\ln(p_i/q_i)\ge1-\sum_{i:p_i\gt0}q_i\ge0$. Divide by $\ln2$ to obtain bits. Equality forces every ratio on the positive support to be one and no leftover mass outside it. This also recovers $H(P)\le\log_2M$ by choosing $Q$ uniform on an $M$-symbol alphabet.

The mutual information of $X,Y$ is

$$ I(X;Y)=H(X)+H(Y)-H(X,Y) =H(X)-H(X\mid Y)\ge0. $$

It equals $D(P_{XY}\Vert P_XP_Y)$ and is zero exactly when the variables are independent. Conditional mutual information $I(X;Y\mid Z)$ averages this quantity in the distributions conditioned on $Z$, so it is also nonnegative.

Entropy submodularity. For coordinate sets $A,B$,

$$ H(X_A)+H(X_B)\ge H(X_{A\cup B})+H(X_{A\cap B}). $$

Write the common coordinates as $U$, the coordinates only in $A$ as $V$, and those only in $B$ as $W$. The difference is $I(V;W\mid U)\ge0$, by the chain rule. This explains why overlapping observations cannot generally be treated as independent information packets.

Solved hidden dependence. Let $X,Y$ be independent fair bits and $Z=X\oplus Y$, where $\oplus$ is addition modulo 2. Every pair is independent, so $I(X;Y)=I(X;Z)=I(Y;Z)=0$. But $H(X,Y,Z)=2$, and $Z$ is determined by $(X,Y)$, giving $I((X,Y);Z)=1$. Conditioning on $Z$ also makes $I(X;Y\mid Z)=1$. Pairwise independence misses a global constraint.

Data processing. If $X,Y,Z$ form a Markov chain, meaning $X$ and $Z$ are conditionally independent given $Y$, then $I(X;Z)\le I(X;Y)$. Indeed, the chain rule for mutual information gives

$$ I(X;Y,Z)=I(X;Y)+I(X;Z\mid Y)=I(X;Y), $$

while the alternative order gives $I(X;Y,Z)=I(X;Z)+I(X;Y\mid Z)\ge I(X;Z)$. A postprocessed observation cannot gain information about the source unless an additional information source enters.

Exercise. If $Y=X$ is a fair bit and $Z$ is an independently generated fair bit, compute the two mutual informations in the data-processing conclusion. Hint: distinguish copying from resampling. Solution: $I(X;Y)=1$ and $I(X;Z)=0$.

24.8 Concentration via entropy methods

Optional advanced elective. Here the word entropy refers to a functional on nonnegative random weights, using natural logarithms. For $Z\ge0$ with positive finite mean, define

$$ \operatorname{Ent}(Z)=\mathbb E[Z\ln Z]-\mathbb E Z\ln\mathbb E Z. $$

Convexity of $z\ln z$ makes it nonnegative. It is not the Shannon entropy $H(Z)$ of the variable's distribution. If $\mathbb E Z=1$, it is the relative entropy in nats of the measure with density $Z$ relative to the original measure.

For independent finite coordinates, entropy tensorization gives

$$ \operatorname{Ent}(Z)\le\sum_i\mathbb E[\operatorname{Ent}_i(Z)], $$

where $\operatorname{Ent}_i$ averages only coordinate $i$, holding all others fixed. This product-measure theorem is stated without proof here. It and its concentration applications are developed in Boucheron, Lugosi, and Massart, Concentration inequalities using the entropy method.

Bounded-difference application. Let $f$ be a real function of independent finite variables. If changing coordinate $i$ while holding the others fixed changes $f$ by at most $c_i$, put $L=\sum_i c_i^2$. For $L\gt0$ and $t\gt0$, the entropy method yields

$$ \Pr(f-\mathbb E f\ge t)\le e^{-2t^2/L},\qquad \Pr(|f-\mathbb E f|\ge t)\le2e^{-2t^2/L}. $$

Proof after tensorization. For one coordinate and fixed others, let $a(\lambda)=\ln\mathbb E_i e^{\lambda f}$. Its second derivative is the variance under exponential tilting, at most $c_i^2/4$ because the possible values lie in an interval of width $c_i$. Integrating $(\lambda a'-a)'=\lambda a''$ from zero gives

$$ \frac{\operatorname{Ent}_i(e^{\lambda f})}{\mathbb E_i e^{\lambda f}} \le\frac{\lambda^2c_i^2}{8}\qquad(\lambda\ge0). $$

Tensorization and averaging give the corresponding global bound with $L$ in place of $c_i^2$. Set $\psi(\lambda)=\ln\mathbb E e^{\lambda(f-\mathbb E f)}$. Then

$$ \lambda\psi'(\lambda)-\psi(\lambda)\le\frac{\lambda^2L}{8}, \qquad\left(\frac{\psi(\lambda)}\lambda\right)'\le\frac L8. $$

The centered function has $\psi(0)=\psi'(0)=0$, so integration gives $\psi(\lambda)\le\lambda^2L/8$. Exponential Markov and the choice $\lambda=4t/L$ prove the upper tail. Apply the same argument to $-f$ for the lower tail. This differential step is the Herbst argument. The only omitted general ingredient in this derivation is tensorization.

Solved example. For the number of 1s in 100 independent fair bits, each $c_i=1$ and the mean is 50. The probability of at least 65 ones is at most $e^{-2\cdot15^2/100}=e^{-4.5}$. This reproduces a Chapter 22 bound through a functional entropy argument. The two-sided bound is $2e^{-4.5}$.

Exercise. If a function of 20 independent bits changes by at most 2 when one bit flips, what upper-tail bound follows for deviation 10? Hint: $L=20\cdot2^2$. Solution: $e^{-2\cdot10^2/80}=e^{-5/2}$. Independence and worst-case coordinate influence are hypotheses, not consequences of low Shannon entropy.

24.9 Entropy and random graph enumeration

Optional advanced elective. A graph on $[n]$ is a binary vector indexed by its $N=\binom n2$ possible edges. Entropy of that vector can measure either a random model or the logarithm of a uniform graph-family count. These interpretations require their respective distributions to be specified.

In $G(n,p)$, the edge bits are independent, so

$$ H(G(n,p))=N h(p). $$

In $G(n,m)$, all $\binom Nm$ outcomes are equally likely, giving

$$ H(G(n,m))=\log_2\binom Nm\le N h(m/N). $$

Solved comparison. $G(4,1/2)$ has entropy 6 bits. The uniform model $G(4,3)$ has entropy $\log_220\approx4.3219$ bits despite the same edge marginal probabilities. The fixed edge-count constraint introduces dependence and reduces total information.

Counting a constrained family. Let $\mathcal T_n$ be all labeled triangle-free graphs on $[n]$, with $n\ge3$, and choose uniformly from it. Observe the three edge bits on every three-vertex set. Each observation has at most seven values, since the all-present pattern is forbidden. Each edge-coordinate is observed $n-2$ times. Shearer gives

$$ \log_2|\mathcal T_n|\le\frac{\binom n3}{n-2}\log_27 =\frac{N}{3}\log_27, \qquad|\mathcal T_n|\le7^{N/3}. $$

On four vertices this is $|\mathcal T_4|\le49$; exact enumeration gives 41. The observations concern triangles, but the coordinates being covered are graph edges, not graph vertices.

For a lower bound, fix a balanced bipartition and choose any subset of its $\lfloor n^2/4\rfloor$ crossing edges. All these $2^{\lfloor n^2/4\rfloor}$ graphs are triangle-free. This construction and the entropy upper bound do not coincide; the calculation does not establish an optimal asymptotic enumeration theorem.

Exercise. On three vertices, is the triangle-free entropy count bound exact? Hint: there are three edge bits. Solution: yes. Seven of the eight graphs are triangle-free, and the bound is $7^{3/3}=7$.

24.10 Connections to information theory and coding

An observation or encoding is a map from objects to descriptions. If it is lossless, the original object can be recovered. For a deterministic encoding $Y=f(X)$, the chain rule gives $H(Y)\le H(X)$, with equality when the map is injective on the positive-probability support. This is the information-theoretic counterpart of the reverse-decoding requirement in entropy compression.

A binary prefix code gives every symbol a finite binary word such that no codeword is a prefix of another. If the lengths are $\ell_i$, Kraft's inequality is

$$ K=\sum_i2^{-\ell_i}\le1. $$

The proof views each word as a disjoint cylinder of infinite bit sequences, of probability $2^{-\ell_i}$ under fair bits. Conversely, lengths satisfying this inequality can be assigned prefix codewords. For a symbol distribution $P$, normalize $r_i=2^{-\ell_i}/K$. Gibbs' inequality gives

$$ D(P\Vert r)=\mathbb E\ell-H(P)+\log_2K\ge0, \qquad\mathbb E\ell\ge H(P). $$

The lengths $\lceil-\log_2p_i\rceil$ satisfy Kraft and achieve expected length below $H(P)+1$. Entropy is an average information requirement, not an assertion that every individual symbol has a fractional-bit codeword.

Solved exact code. For probabilities $1/2,1/4,1/8,1/8$, use codewords 0, 10, 110, 111. Their lengths are 1,2,3,3; they are prefix-free and have expected length $7/4$ bits, exactly the entropy. A fixed-length representation of four symbols instead uses two bits per symbol.

Error correction is another constraint. A binary code $\mathcal C\subseteq\{0,1\}^n$ has minimum Hamming distance $d$ if any two distinct codewords differ in at least $d$ coordinates. It corrects up to $t$ bit errors whenever $d\ge2t+1$. The radius-$t$ Hamming balls around codewords are then disjoint, giving the packing bound

$$ |\mathcal C|\sum_{j=0}^t\binom nj\le2^n. $$

Solved repetition code. $\{000,111\}$ has distance 3 and corrects one error. Its two balls each contain $1+3=4$ words and partition the eight binary words, attaining the bound. A uniform transmitted codeword carries one bit of message entropy in three physical bits.

The even-parity code $\{000,011,101,110\}$ carries two uniform message bits in three physical bits. Its minimum distance is 2, so it detects a single bit error but cannot guarantee correcting it. The family $\{000,001,010,100\}$ also has entropy two under uniform sampling but minimum distance 1. Equal cardinality and entropy do not determine error resilience.

Exercise. Can four binary codewords of length three correct every single-bit error? Hint: each radius-one ball has four words. Solution: no. The packing bound would require $4\cdot4\le8$, which fails.

Prove a projection inequality and analyze an entropy-compression argument

The investigation joins two uses of information accounting. Projection bounds upper-bound how many objects partial observations can support. Entropy compression instead rules out too many long failing random streams by constructing a reversible description of each stream. The common requirement is to specify both the information being retained and the distribution or counting space.

Worked projection summary. Projection columns are ordered as 12,13,23. All joint entropies refer to uniform sampling from the full family.

For $\mathcal F$, each pair has entropy $3/2$ bits, so Shearer gives $\log_2|\mathcal F|\le9/4$. Exponentiating and using integrality gives $|\mathcal F|\le\lfloor2^{9/4}\rfloor=4$, a stronger result than the support-only bound 5. The additional input is the actual projected probabilities. For $\mathcal P$, every pair is uniform with entropy 2 bits, leaving the bound 8 and missing the parity constraint. For $\mathcal B$, pair entropies are $\log_26,\log_24,\log_26$, and equality holds throughout.

Universal proof outline. A uniform object has entropy $\log_2|\mathcal A|$. The three coordinate pairs cover every coordinate twice. Apply Shearer, then $H(X_{ij})\le\log_2|\pi_{ij}\mathcal A|$, and exponentiate. No projection independence is assumed. The box witnesses that the inequality's exponent and coverage factor are sharp in general.

Worked compression check. The forward trace yields log $(0,1,0,1,0)$ and state $(1,2,3)$. Reversing first recovers and removes vertex 3's retained color 3; the preceding failure at vertex 3 recovers color 2 from its neighbor 2. Recover and remove vertex 2's retained color 2; its preceding failure recovers color 1 from neighbor 1. Finally recover vertex 1's color 1. The reversed stream matches every sampled input.

Among all length-five streams, exactly 27 are unfinished. The first vertex always succeeds. If none of the next four attempts succeeds, all draws are forced to conflict with the first color, giving three streams. If exactly one of those attempts succeeds, choose its position in four ways, the first color in three ways, and its nonconflicting color in two ways; all failed draws are then determined. This gives $4\cdot3\cdot2=24$ further streams. Two later successes would finish the path. Thus the exact unfinished probability is $27/243=1/9$.

The 27 unfinished streams have 27 distinct log-and-state encodings, and reverse decoding recovers each. A run that finishes early may leave unused random symbols; those are not recoverable from this encoding and are not part of its consumed stream. The nontermination counting argument specifically uses unfinished runs that consumed all $T$ symbols.

For a separate check of the general bound, use $n=3,q=3,\Delta=2,T=30$. Its failure upper bound is

$$ \frac{4^3}{3^{30}}\sum_{s=0}^2\binom{30}s2^{30-s} =7984\left(\frac23\right)^{30}\lt0.05. $$

This guarantees that some length-30 stream finishes, using the reversible record count alone. The bound overcounts many impossible logs and states, so it should not be mistaken for the exact failure probability or an optimal running-time analysis.

Application. Suppose three database relations store distinct allowed pairs for attributes $(x,y)$, $(x,z)$, and $(y,z)$. Let the full join contain exactly the distinct triples compatible with all three relations. Its pair projections lie inside the respective relations, so the projection inequality bounds the number of joined triples by the square root of the product of the three relation sizes. This helps estimate how large a combined data family can be without assuming that its attribute values are independent. Duplicated rows under bag semantics need separate multiplicity accounting.

Lossless coding asks that an object be recoverable from its description; the entropy-compression decoder enforces that same requirement for a construction history. Error-correcting coding additionally separates descriptions far enough to tolerate corruption. Support size, average entropy, and Hamming distance answer different questions, and the three family examples make those distinctions concrete.

Optional extension. Replace the three pair observations by a fractional cover and optimize its weights for known projection sizes, verifying every coordinate's total weight. Or change the sample-and-erase rule to remove more than one vertex after a conflict and determine what extra information the log must retain. Do not claim a stronger coloring bound until reconstruction and record growth are proved; unsuccessful experiments alone supply neither an impossibility theorem nor a research-status claim.