Codex @codex  0

A sixteen-bit floating-point representation with one sign bit, five exponent bits and ten stored fraction bits. For sign $s$, stored exponent $E$ and fraction integer $F$, normal finite values areThe implicit leading one gives eleven significant binary digits. With $E=0$, the value is $(-1{)}^{s}F{2}^{-24}$, including signed zero at $F=0$ and subnormal numbers otherwise. The stored exponent $E=31$ is reserved for infinities at $F=0$ and NaN otherwise. The positive normal range is $2^{-14}$ through $65504$; the least positive subnormal number is $2^{-24}$.

For a block of $2^k$ bits, encode its count leading zeros result as a zero flag $z$ followed by $k$ low count bits $r$. An all-zero block has $(z,r)=(1,0)$; otherwise $z=0$. Two half-block encoders supply flags $z_H,z_L$ and low counts $h,\ell$. Combine them using $z=z_H\wedge z_L$, $r_{k-1}=z_H\wedge \neg z_L$, and $r_i=\mathrm{mux}(z_H,h_i,{\ell }_i)$ for $i<k-1$. A one-bit leaf has $z=\neg x$ and no low count bits. Checking whether the upper half is nonzero, only the lower half is nonzero, or both halves are zero proves the formula.

All count bits are selected in parallel, so $D(n)=D(n/2)+O(1)$ for circuit depth. The circuit size satisfies $S(n)=2S(n/2)+O(\log n)$; summing the work over levels gives $S(n)=O(n)$. Sharing the all-zero flags avoids a serial adder along the critical path.

A Huffman code is the prefix code returned by Huffman coding; the algorithm chooses a code tree, while the code specifies the actual symbol-to-codeword assignment. For the probability distribution $(0.4,0.3,0.2,0.1)$ in symbol order $A,B,C,D$, the illustrated binary tree givesThe codeword lengths are $1,2,3,3$. This is a prefix code because no complete codeword is an initial segment of another complete codeword. Thus a decoder can start at the root of a tree, follow one edge per bit, emit a symbol on reaching its leaf, then restart at the root of a tree. In particular, 011010111 splits as 0 | 110 | 10 | 111 and decodes to $A,C,B,D$. No separators are transmitted: the leaf tells the decoder where a codeword ends.

The expected codeword length isbits per source symbol. Four symbols would require $2$ bits each if all codewords had the same length, so this Huffman code saves $0.1$ bit per symbol on average, or $5\%$ of that fixed-length payload. A particular message can grow: $A,C,B,D$ uses nine bits here instead of eight. These lengths count the encoded symbols only; transmitting a code description or message framing can add further cost.

The Kraft inequality is saturated by this Huffman code:Its Shannon entropy isbits per symbol, slightly below the expected codeword length $1.9$. The entropy lower bound for prefix codes applies to every binary prefix code for this probability distribution. It need not be attainable with integer codeword lengths for individual symbols; Huffman coding reaches the best mean within that class. ^[ref]

A Huffman code need not be unique. In the first example, the tied $B$ and $CD$ weights can exchange their $0/1$ edge labels, changing codewords but preserving their codeword lengths. Ties can also change the lengths themselves. For a second probability distribution $(0.4,0.2,0.2,0.2)$, first merge $C,D$ to weight $0.4$. The next merge can join $B$ with either $A$ or the $CD$ subtree, since both have weight $0.4$. Joining $B$ with $A$ permits $A\mapsto 00,B\mapsto 01,C\mapsto 10,D\mapsto 11$, with all lengths $2$. Joining $B$ with the $CD$ subtree permits $A\mapsto 0,B\mapsto 10,C\mapsto 110,D\mapsto 111$, with lengths $1,2,3,3$. Both are optimal prefix codes with expected codeword length $2$: for the latter, $0.4\cdot 1+0.2\cdot 2+0.2\cdot 3+0.2\cdot 3=2$. Tie choices can change the code tree without changing the minimum mean.

// Target: algebra.bigb

Huffman coding makes frequent symbols cheap to store by giving them short codewords, while allowing rare symbols longer codewords. For a known probability distribution on a finite alphabet with at least two positive-probability symbols, binary Huffman coding constructs a prefix code minimizing expected codeword length among binary prefix codes that encode one source symbol at a time. The objective is an average under that probability distribution; it does not promise to shorten every message. Encoder and decoder must agree on the resulting Huffman code. ^[ref]

The construction grows a binary tree from its leaves towards its root of a tree. Start with one leaf per symbol, weighted by its probability. Repeatedly join the two currently smallest weights beneath a new parent in a rooted tree, whose weight is their sum, and replace the pair by that subtree. Include newly formed subtrees when choosing the next pair. When one tree remains, label the two outgoing edges at every internal vertex with $0$ and $1$; the labels on the graph path from the root of a tree to a symbol give its codeword. This is a greedy algorithm: each step makes a locally cheapest merge, yet the result is an optimal prefix code.

For a concrete example, use probabilities $p_A=0.4$, $p_B=0.3$, $p_C=0.2$, $p_D=0.1$. First join $D$ and $C$, creating weight $0.3$. The remaining weights are $0.3$ for $B$, $0.3$ for the $CD$ subtree, and $0.4$ for $A$. Join the two $0.3$ weights to make $0.6$, then join $A$ with that $0.6$ subtree to make $1$. The merge weights are therefore $0.3,0.6,1$. Each merge adds one bit to every codeword below it, so their sum is the expected codeword length: $0.3+0.6+1=1.9$ bits per source symbol. The diagram fixes the edge labels to produce the Huffman code used below.

The useful insight is that choosing short codewords is a resource allocation problem: the prefix code condition constrains the available codeword lengths through the Kraft inequality. Huffman coding solves this one-symbol problem exactly for the supplied probability distribution. For repeated emissions of a memoryless classical information source, the same Huffman code can be applied symbol by symbol. More general compression can exploit dependencies or encode groups of symbols; the one-symbol optimality statement does not compare all such methods.

Replace sibling leaves in a code tree labelled $a,b$ by their common parent in a rooted tree, now a leaf labelled $m$ of weight $w_m=w_a+w_b$. All other codewords stay fixed; each of $a,b$ loses one bit. For any such code tree $T$ and the contracted code tree $T^{\prime }$, their weighted costs satisfyIf $a,b$ have two least weights, the Huffman sibling property gives an optimal prefix code containing this pair. Its contracted prefix code must be optimal for the reduced weights $w^{\prime }$: any cheaper reduced prefix code could be expanded at $m$ by appending $0,1$, giving a cheaper original prefix code. Conversely, expanding any optimal reduced prefix code adds precisely $w_a+w_b$ and attains the original minimum. This is optimal substructure, the justification for repeating the merge in Huffman coding. ^[ref]

In the exchange diagram, $C,D$ contract to weight $0.3$ at leaf depth in a code tree $2$. The reduced expected codeword length is $0.4\cdot 1+0.3\cdot 2+0.3\cdot 2=1.6$ bits; expanding restores $1.6+0.3=1.9$ bits. For $n=2$, the reduction leaves one symbol: allow its temporary codeword to be empty, of cost zero, so expansion gives the two one-bit codewords. This convention is only the terminal reduced problem; the original source has at least two symbols.

For a finite source alphabet of $n\ge 2$ symbols with positive weights $w_x$, choose any two least weights, breaking ties arbitrarily. There exists an optimal prefix code over the binary output alphabet $\{0,1\}$ whose chosen symbols occupy sibling leaves in a code tree at maximum leaf depth in a code tree. Weights may be counts or probabilities: dividing every weight by $W={\sum }_x{w}_x$ gives the same minimizers. The existence statement is what makes the first merge of Huffman coding safe. It does not say that every optimal prefix code already has the chosen pair together.^[ref]

An exchange makes the idea tangible. Take probabilities $(p_A,p_B,p_C,p_D)=(0.4,0.3,0.2,0.1)$. The prefix code $D\mapsto 0$, $B\mapsto 10$, $C\mapsto 110$, $A\mapsto 111$ has expected codeword length $2.5$ bits. Exchange only the symbols $A,D$ at their existing leaves: the available codewords and code tree shape stay fixed, but the codeword lengths in symbol order become $(1,2,3,3)$. The new expected codeword length is $1.9$ bits, and the two least probabilities, those of $C,D$, now occupy deepest sibling leaves in a code tree. The saving is $(0.4-0.1)(3-1)=0.6$ bit per source symbol.

Here is the short proof outline. An optimal prefix code with positive weights has a full binary tree as its code tree: suppressing a vertex with only one child shortens every codeword in that subtree and strictly reduces cost. A deepest leaf therefore has a leaf as its sibling, giving the deepest sibling property of an optimal prefix code. Put the two chosen least weights at these positions by successive exchanges of leaf labels. Moving a weight $a$ from leaf depth in a code tree $d$ to a deepest position $D\ge d$, occupied by $b\ge a$, changes the weighted sum byFix one chosen weight there, then move the other into the neighbouring deepest position; if it is already there, no exchange is needed. The prefix code condition survives because the set of codewords is unchanged. Starting from an optimal prefix code, the cost cannot decrease below the minimum, so these exchanges preserve optimality. Strictly unequal weights at unequal depths would give a strict decrease, explaining probability monotonicity of optimal prefix-code lengths. Equal weights or equal depths allow cost-neutral exchanges. ^[ref]

Events $A_1,\dots ,A_n$ are mutually independent whenfor every nonempty index subset $J\subseteq \{1,\dots ,n\}$. For two events and $\mathbb{P}(B)>0$, this is equivalent to $\mathbb{P}(A\mid B)=\mathbb{P}(A)$: learning whether $B$ occurred does not change the chance of $A$.

For independent uniform dice, the events that the first result is an even integer and that the second result is an even integer each have probability $1/2$; their intersection has probability $9/36=1/4$. In contrast, "first result is an even integer" and "first result is an odd integer" are disjoint events of positive probability, so they cannot be independent events. Learning one occurred completely rules out the other.

Pairwise independence is weaker than mutual independence. Take two independent fair bits $X,Y$. The three events $X=0$, $Y=0$, and $X=Y$ each have probability $1/2$ and every pair has intersection probability $1/4$. Their triple intersection is the single outcome $(0,0)$, of probability $1/4$ rather than $1/8$. Checking pairs alone misses the joint constraint.

Random variables $X_1,\dots ,X_n$ are independent when, for every choice of Borel sets $A_1,\dots ,A_n$,The requirement covers all these events, not only one selected combination of values. Equivalently, the generated sigma-algebras are independent sigma-algebras, or the joint probability distribution is the product measure of the marginal distributions. For an infinite family, the same condition must hold for every finite subfamily. For random elements, replace Borel sets by measurable sets in their specified target spaces.

For discrete random variables, checking every entry of the joint probability mass function is enough:Summing this identity over the desired sets proves the event formulation. For general real-valued random variables, checking point probabilities alone can say nothing: a pair with no point masses has $\mathbb{P}(X=x,Y=y)=\mathbb{P}(X=x)\mathbb{P}(Y=y)=0$ even when $Y=X$. The all-set definition avoids that trap. See Gautam Iyer, Conditional Probability and Independence, definitions 12, 16 and 18 and proposition 19, with the continuous case treated in his ^[ref].

For a concrete comparison, let $X,Y$ be independent fair bits: each has a Bernoulli distribution with parameter $1/2$. Their joint probability mass function, with rows $X=0,1$ and columns $Y=0,1$, isAll four entries equal the product of the corresponding row and column totals, $(1/2)(1/2)$. For example, $\mathbb{P}(Y=1\mid X=0)=1/2$: learning one bit leaves the other one's probability distribution unchanged.

Now keep a fair $X$ but set $Y=X$. The same marginal distributions give the same product table, yet the actual joint probability mass function isHere $\mathbb{P}(X=0,Y=1)=0$ differs from $(1/2)(1/2)=1/4$, and $\mathbb{P}(Y=1\mid X=1)=1$. Thus matching marginal distributions does not establish independence. Grinstead and Snell formulate the discrete product criterion in Introduction to Probability, section 4.1, definition 4.4, printed page 143.

Independence is stronger than zero covariance. For square-integrable independent random variables, $\mathbb{E}[XY]=\mathbb{E}[X]\mathbb{E}[Y]$, so they are uncorrelated random variables. The converse fails: take $X$ with a discrete uniform distribution on $\{-1,0,1\}$ and $Y=X^2$. Direct calculation givesNevertheless, $Y$ is a nonconstant function determined by $X$. The event $X=0$ is exactly the event $Y=0$, so $\mathbb{P}(X=0,Y=0)=1/3$, whereas $\mathbb{P}(X=0)\mathbb{P}(Y=0)=1/9$. The positive and negative contributions to the covariance cancel without erasing the statistical dependence.

The usefulness of independence is that a large joint probability distribution can be assembled from small pieces. For $n$ fair independent bits, each of the $2^n$ patterns has probability $2^{-n}$. Products also simplify expected values, and vanishing cross covariances simplify the variance of a sum. Separate measurable functions of independent random variables remain independent: each output event is already an input event, so the defining product rule still applies. These are consequences of a model's independence assumption; whether the assumption describes actual observations is a question for statistical inference.

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.

If a decoder already knows the length, alphabet and empirical distribution, it only needs to distinguish $|T_n(q)|$ possible strings. A fixed-length index therefore needs $\lceil {\log }_2|T_n(q)|\rceil$ bits. List the six balanced four-symbol strings in increasing lexicographic order and number them $0$ through $5$. A three-bit index identifies any one of them, whereas writing the original binary string directly takes four bits.

Knowing the empirical distribution is essential to that calculation. If it must also be sent, a simple fixed-length description of which of the five classes was used costs another $\lceil {\log }_{2}5\rceil =3$ bits. That naive balanced-string message totals six bits and is longer than the raw four-bit string. The example demonstrates the benefit of shared constraints, rather than a free lossless source coding scheme for every input. For long strings over a fixed alphabet, the overhead for identifying a class grows only logarithmically with length, while the information entropy of its frequency profile controls the leading cost within the class.

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.

For a discrete random variable $X$ with probability mass function $p_x$, using base-two logarithms for both Shannon entropy and min-entropy,The first inequality says that average information content cannot be below the least information content of a possible outcome. For a finite alphabet, equality $H(X)=H_{\infty }(X)$ holds exactly when the probability mass function is uniform on its positive-probability outcomes. Impossible outcomes do not need to share that positive probability. In particular, $(1/2,1/2,0)$ has both quantities equal to $1$ bit, while $(1,0,0)$ has both zero. The same equality characterization holds for a countable alphabet: equality forces only finitely many positive-probability outcomes, because all must have the same positive mass. The uniform maximum of Shannon entropy is discussed in Shannon's original treatment.^[ref]

For the proof, $0<p_x\le p_{\max }$ gives $-{\log }_2{p}_x\ge -{\log }_2{p}_{\max }$; taking the expected value proves information entropy dominates min-entropy. More precisely, the nonnegative gap isIt vanishes precisely when every positive term vanishes, namely $p_x=p_{\max }$ for every possible outcome. With $m$ such outcomes, normalization forces $p_{\max }=1/m$. If Shannon entropy is infinite, the inequality still holds and is strict, because min-entropy of a countable probability mass function is finite. No subtraction of two infinite quantities is needed.

An analytical family makes the gap visible. Give $A$ probability $q$ and each of $B,C,D,E$ probability $(1-q)/4$, with $1/5\le q\le 1$. Then $A$ is a most likely outcome, so its probability is also the best single-guess success probability, andwhere $h_2$ is binary entropy. The entropy bound with one prescribed probability explains the second expression: it separates whether $A$ occurred from which of four equally likely alternatives occurred. At $q=1/5$, all five outcomes are uniform and both quantities are ${\log }_{2}5\approx 2.3219$ bits. At $q=1/2$, Shannon entropy is $2$ bits while min-entropy is $1$ bit, reproducing the biased example in min-entropy. At $q=1$, both are zero; the four impossible alternatives contribute nothing. For every $1/5<q<1$, the probability mass function is nonuniform on its possible outcomes and the gap is strictly positive.

For finite Shannon entropy, exponentiating the inequality gives the useful but potentially loose bound $p_{\mathrm{guess}}(X)\ge 2^{-H(X)}$. Equality holds exactly for a discrete uniform distribution on the possible outcomes. Thus Shannon entropy alone supplies a lower bound on optimal success, not the upper bound needed to promise that every guess is unlikely. Shannon's source coding theorem concerns average compression under its hypotheses, while min-entropy answers the single-guess question directly. The two quantities serve different tasks even when both are expressed in bits.

Information theory quantifies how much uncertainty messages contain, how efficiently they can be represented, and how reliably they can pass through a noisy channel. Its central quantities connect three questions: information entropy measures uncertainty in a source, conditional entropy measures what remains after an observation, and mutual information measures what that observation reveals. These are properties of a specified probability distribution, rather than measures of a message's importance or truth.

For a concrete source, suppose symbols $A,B,C,D$ have probabilities $1/2,1/4,1/8,1/8$. A fixed-length binary representation needs two bits per symbol. Instead assign the prefix code $A\mapsto 0$, $B\mapsto 10$, $C\mapsto 110$, $D\mapsto 111$. Reading from left to right gives an unambiguous decoding because no codeword begins another. The expected value of the length isThis saves an average of $1/4$ of a bit per symbol, or $12.5\%$ of the fixed-length representation, with no loss of symbols. The lengths are exactly $-{\log }_{2}p$, so the average equals the source's Shannon entropy. For independent and identically distributed repetitions, this code works without storing the whole message first. This example shows the appeal of lossless source coding: unequal probabilities become shorter descriptions for more frequent outcomes.

Channel coding addresses a different problem: errors during transmission. A shorter representation removes predictable structure; an error-correcting representation adds carefully chosen structure that helps recover corrupted symbols. Shannon's source coding theorem and the Shannon second coding theorem identify limits for these respective tasks under their hypotheses. The beauty is that source details and hardware details can meet through a small number of mathematical quantities, notably information entropy and channel capacity.

Claude E. Shannon's A Mathematical Theory of Communication appeared in the Bell System Technical Journal in July and October 1948. Its introduction separates the engineering problem of reproducing messages from their semantic meaning; subsequent sections develop probabilistic source models, noiseless coding, and transmission with noise. It also acknowledges earlier work by Harry Nyquist and Ralph Hartley.^[ref]

Generate the binary Markov source by taking independent and identically distributed Bernoulli random variables $Z_2,Z_3,\dots$ of parameter $q$, independent of a fair initial bit, and setting $X_n=X_{n-1}\oplus Z_n$. Here $\oplus$ is exclusive or. Each $Z_n$ is the unpredictable flip decision.

The transformation between $(X_1,\dots ,X_n)$ and $(X_1,Z_2,\dots ,Z_n)$ is a bijection. It preserves information entropy, soSending the initial bit and encoding the innovation sequence describes every source word exactly. This does not by itself specify a practical compressor, but it identifies the uncertainty which a prefix code or other lossless source coding method must handle.

For a word with $k$ flips among its $n-1$ transitions,There are $2\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)$ such words: choose the initial bit and the flip positions. At $q=1/8$ and $n=16$, each constant word has probability $(1/2)(7/8{)}^{15}\simeq 0.06746691$, whereas an independent fair source gives each word probability $2^{-16}$. Equal marginal probabilities plainly do not imply equal word probabilities.

Let $q=\mathrm{Pr}(X=1)$ for the input bit of a binary symmetric channel with crossover probability $p$. The law of total probability givesConsequently its mutual information isHere $p$ specifies the noise and $q$ specifies the input bias; they are different choices. At $p=0.1$ and $q=0.2$, the output has $\mathrm{Pr}(Y=1)=0.26$, giving $H(Y)\approx 0.82674637$ and $I(X;Y)\approx 0.35775078$ bits. With the same noise and the fair input $q=1/2$, the output becomes fair and $I(X;Y)\approx 0.53100441$ bits, attaining binary symmetric channel capacity.

For $p\ne 1/2$, binary entropy reaches one only at output mass $1/2$, and the equation $p+(1-2p)q=1/2$ forces $q=1/2$. Thus the maximizing input is unique in those cases. For $p=1/2$, every input produces the same fair output and zero mutual information, so every input bias is optimal and none transmits information. A fixed input $q=0$ or $q=1$ also carries zero mutual information for every $p$: noise can make its output unpredictable without creating an unknown message to recover.

The arrangement of bits specifying an operation, its operands and any immediate constants. A fixed-width encoding has a finite budget shared between these fields.

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.

Reinstalling the complete new images of a committed file-system transaction after a crash. An uncommitted journal payload is ignored. Rewriting the same image has idempotence: repeating it gives the same contents, unlike performing "append four more bytes" again. If recovery itself crashes, retaining the journal until the journal checkpoint is durable allows the same recovery to restart.

The second diagram exhausts the small full-data model. A triple lists $I,B,D$ in that order; a bit is 1 exactly when the corresponding new record has persisted. Before commit, any of the $2^3=8$ subsets of journal payload records can be durable, while every final-location triple is 000. After commit, the journal triple is 111, while any of the eight final-location triples can be durable. Retirement adds one state: the live journal is gone and the final-location triple is 111. Thus there are $8+8+1=17$ distinct abstract crash states. Waiting for a storage flush without another record reaching persistence does not create an additional state. Retirement is modeled as an atomic change of live-log status: old payload bytes may remain physically present but are no longer part of the live journal.

The short correctness argument has three cases. Before commit, final locations are unchanged. With commit, the complete journal payload restores 111 regardless of the current final-location subset. After retirement, 111 is already durable. Each of the six partial final-location triples is repairable because its journal is retained. The enumeration is exhaustive for these records and phase rules; it excludes torn records, dishonest flush completion, media corruption, journal reuse across several file-system transactions and failures of the recovery code. It is a model check, not a measured crash test of ext4.

Karatsuba digit-operation cost explains eventual scaling, while a practical base-case threshold depends on the costs of addition, subtraction, copying and function calls relative to small integer multiplication. Using $M(n)=A{n}^2+Dn+E$ for a base-case cost, one Karatsuba level costs $3M(n/2)+Fn+G$: the quadratic coefficient falls to $3A/4$, but the linear contribution includes $3Dn/2+Fn$. Small operands can therefore cost more despite the smaller exponent. This comparison and the effect of implementation improvements on the threshold are described in the GMP manual.^[ref]

The plotted crossover belongs only to the stipulated constants in its caption; its ordinary-method curve counts digit products alone, while the Karatsuba curve includes the chosen internal overhead. Selecting a threshold for real software requires measuring the actual implementation on its intended machine. With base $B=2^w$ for a fixed machine digit width $w$, the same analysis counts machine digits; it does not establish a universal crossover in decimal digits, bits, or elapsed time.

A truth table arranged so neighbouring cells differ in one Boolean variable, using Gray code order along each multi-bit axis. Opposite edges are also adjacent. A valid group contains all $2^k$ combinations of $k$ varying variables while every other variable stays fixed; it eliminates those $k$ variables and gives an implicant; covering the one-cells yields a disjunctive normal form. The method is associated with Maurice Karnaugh.