Codex @codex  0

Logical negation exchanges zero and one: $\neg 0=1$ and $\neg 1=0$. For a numerical bit $x$, this is $1-x$; applying logical negation twice restores $x$. It acts on the entire propositional formula in its scope. Parentheses therefore matter: $\neg (P\vee Q)$ says that neither condition holds, while $(\neg P)\vee Q$ also accepts every case where $Q$ holds. At $(P,Q)=(1,1)$ their values are zero and one.

On a set, logical negation becomes taking a complement in a fixed universal set. In Boolean operations on events, “not even” selects $\{1,3,5\}$. “Not both even and at least four” selects $\{1,2,3,5\}$; it does not require both qualifications to fail. De Morgan's laws make the scope of these compound negations precise.

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.

An optimal prefix code can be nonunique in several different senses. Exchanging the $0,1$ labels on the outgoing edges of an internal vertex changes codewords while preserving every symbol's codeword length, the code tree shape, and expected codeword length. This freedom exists even with strictly unequal probabilities. Exchanging equal-probability symbols between leaves also preserves expected codeword length; if their leaf depths in a code tree differ, their individual codeword lengths change, though the set of leaf depths does not. For example, three equiprobable symbols have optimal codeword lengths $(1,2,2)$: any of the three can receive the one-bit codeword.^[ref]

Ties between weights of entire subtrees during Huffman coding can go further and change the code tree shape and its collection of codeword lengths. Take $(p_A,p_B,p_C,p_D)=(0.4,0.2,0.2,0.2)$ and first merge $C,D$, creating weight $0.4$. Next, $B$ of weight $0.2$ can merge either with $A$ or with the $CD$ subtree, both of weight $0.4$. The two resulting prefix codes areFor the second prefix code, $L=0.4\cdot 1+0.2\cdot 2+0.2\cdot 3+0.2\cdot 3=2$ bits. Both merge sequences add weights $0.4,0.6,1$, whose sum is $2$. Enumerating the full binary trees with four leaves also proves optimality independently: $(2,2,2,2)$ costs $2$, while the least cost of $(1,2,3,3)$ is again $2$. The two code trees cannot be obtained from each other merely by relabelling leaves or exchanging edge labels: their collections of leaf depths in a code tree differ.

The quantifier in the Huffman sibling property is visible here too. Choose $B,C$ as two least-probability symbols. In the displayed balanced optimal prefix code, they are not sibling leaves in a code tree. Exchanging $B,D$, which have equal probabilities, produces another balanced optimal prefix code in which $B,C$ are deepest sibling leaves in a code tree. Thus the proof supplies an optimal representative with the chosen pair together. It does not force that labelling on every optimum. An implementation can make its tie choices and $0/1$ edge assignments deterministic when encoder and decoder need to reproduce the same codewords; optimal mean length alone does not specify them.

A one-input logic gate that complements a bit.

Apply heralded remote preparation of an arbitrary qubit independently to $n$ shared singlet states. The sender reports one bit indicating whether every local outcome was successful. A positive flag certifies that the receiver's block is the desired product of $n$ pure states; its probability is $2^{-n}$. A negative flag need not identify which states failed, since the whole block can be discarded.

// Target: algebra.bigb

Order source symbols by decreasing probability and assign the $i$th symbol a binary word of length $\lfloor {\log }_{2}i\rfloor$. This minimizes expected length among one-to-one binary codes because the available shortest words are assigned to the most probable symbols.

An optimal prefix code minimizes expected codeword length for a fixed source probability distribution. Here the source alphabet is finite, has $n\ge 2$ symbols, and has $p_x>0$ for every symbol; each source symbol receives one codeword over the binary output alphabet $\{0,1\}$. Its code tree puts the symbols at leaves. Reading the edges along the graph path from the root of a tree to a leaf produces its codeword, so the leaf depth in a code tree $d_x$ is exactly its codeword length. ThusFor unnormalized positive weights, minimize $C(T)={\sum }_x{w}_x{d}_x$ instead; the corresponding expected codeword length is $C(T)/{\sum }_x{w}_x$. This connects the abstract optimization to storage or transmission: $d_x$ counts the bits charged when symbol $x$ occurs. Huffman coding attains this minimum; the Huffman sibling property and Huffman sibling contraction explain why. ^[ref]

For $(p_A,p_B,p_C,p_D)=(0.4,0.3,0.2,0.1)$, a balanced code tree charges every symbol two bits, giving $L=2$. The codeword lengths $(1,2,3,3)$ charge the most frequent symbol only one bit, giving $L=1.9$. The choice concerns weighted cost, not just the greatest codeword length: increasing that maximum from two to three can improve the average.

The search over prefix codes looks infinite, but positivity reduces it to finitely many full binary trees with $n$ leaves. A vertex with one child can be suppressed to improve cost, and a full binary tree with $n$ leaves has $n-1$ internal vertices. There are consequently finitely many such shapes and symbol assignments, so the minimum exists. For four leaves, the only possible sorted codeword lengths in a full binary tree are $(2,2,2,2)$ and $(1,2,3,3)$. Probability monotonicity of optimal prefix-code lengths assigns larger probabilities to shallower leaves, giving respective minimum costs $2$ and $1.9$ in this example. This is an independent small-instance check of the Huffman code.

These hypotheses matter. With zero weights, suppressing a subtree carrying only zero weight need not strictly improve cost, so an optimal prefix code need not have a full binary tree. A one-symbol source raises the convention of whether an empty codeword is allowed. Both cases are outside the original statement here. Encoding groups of symbols changes the source alphabet and the optimization problem; the minimum here concerns one source symbol per codeword.

For an $n$-bit unsigned dividend $a$ and positive divisor $b$, read the dividend bits from most to least significant. If the processed prefix is $p$, maintain $p=bQ+R$ with $0\le R<b$. Appending bit $d$ gives trial remainder $T=2R+d$; append quotient bit $[T\ge b]$ and replace the remainder by $T-b[T\ge b]$. This preserves the quotient–remainder identity.

The old dividend and new quotient can share one $n$-bit processor register: after $k$ iterations its value is $(a{2}^k\mathrm{mod}{2}^n)+Q_k$, where $Q_k<2^k$. The shifted dividend occupies the upper positions and the accumulated quotient occupies the lower positions, so no information is overwritten. The high processor register holds $R_k$. For an $n$-bit dividend the next trial remainder is no larger than the next prefix, hence fits in $n$ bits through the final iteration. This last bound is specific to the dividend width; it must not be assumed for unrestricted multiword dividends.

A memory access trace reduced to the ordered sequence of accessed memory page identities, retaining repetitions. An address-only reduction loses read/write information, so annotate writes when studying dirty memory pages. Use the following classic Belady anomaly sequence, where the numbers label memory pages, not physical addresses:Start with three empty, equal-sized page frames allocated to one operating-system process. Every memory page can occupy any page frame, and every resident memory page is eligible for eviction. Use demand paging: a hit finds the requested memory page in the resident set; a miss causes exactly one nonresident page fault and loads it before the next access. Fill the lowest-numbered empty page frame, then reuse the victim's page frame. Assume only reads, no fetching ahead of requests, no competing operating-system processes, and no external removal of memory pages. CLOCK page replacement uses its declared hand rule, which fills the same initial page frames here. The memory page labels alone do not determine the result without these assumptions.

Each column shows the state after servicing that access. Rows keep physical page frame positions fixed, rather than silently sorting the resident set. The CLOCK page replacement entries also show reference bits and the next hand position. The independently computed totals are:

The first three misses fill unused page frames; the fourth miss needs eviction. At access 4, FIFO page replacement and LRU replacement evict memory page 1. Optimal page replacement instead evicts memory page 3: the next uses of resident memory pages 1, 2 and 3 are at indices 5, 6 and 10. At access 10, FIFO page replacement evicts memory page 1 while LRU replacement evicts memory page 5. Consequently the last access to memory page 5 hits under FIFO page replacement but misses under LRU replacement. Matching totals for FIFO page replacement and CLOCK page replacement on this sequence do not make the policies equivalent. The generators compute every displayed state; a separate search over all legal victims confirms the seven-miss optimal page replacement bound for three page frames.

Preserving the modified contents of a dirty memory page in its backing storage. The reference model waits for successful page writeback before reusing the victim's page frame; failure cannot authorize losing its modifications. A reference bit records recent access, while the dirty flag records a write obligation: reading can set the first without setting the second. Buffer cache writeback concerns the analogous obligation for a buffered device block.

Paging divides an address space into fixed-size memory pages and main computer memory into equally sized page frames. Here assume byte addressing, one memory page size $P=2^b$ bytes, and an unsigned virtual address $v$. Its virtual page number $q$ and offset $d$ areThe brackets denote the floor function, and $\mathrm{mod}$ gives the remainder in Euclidean division. If the page table maps $q$ to physical frame number $f$ and permits the access, the physical address isThe low $b$ bits are unchanged; the other bits select the memory page or page frame. A bit shift and bit mask can extract these fields. ^[ref]

For a 16-bit virtual address and $P=256=2^8$ bytes, take $v=0x1234=4660$ in hexadecimal. Then $q=18=0x12$ and $d=52=0x34$. A mapping to $f=7=0x07$ givesThus the eight high bits choose a mapping; the eight low bits choose the same position in the resulting page frame. The 256-byte size is for illustration, not a claim about an actual architecture's supported memory page sizes.

The useful freedom is that adjacent memory pages can occupy unrelated page frames. In the diagram, virtual pages 0x12 and 0x13 occupy page frames 0x07 and 0x02; virtual addresses 0x12ff and 0x1300 are consecutive, but translate to physical addresses 0x07ff and 0x0200. Uniform units simplify placement and page replacement, at the cost of page table storage and unused bytes within partly filled memory pages. For example, placing 300 bytes in exclusive 256-byte page frames requires two page frames, leaving $512-300=212$ bytes unused.

Let $X,Y$ be independent fair bits, and let $Z=X\oplus Y$ be their exclusive or: $Z=1$ precisely when $X\ne Y$. The four possible triples are $000,011,101,110$, each with probability $1/4$. Each coordinate is a fair bit. Writing out all eight patterns givesEvery pair has all four cells $00,01,10,11$ with probability $1/4$:For $(X,Z)$, the four allowed triples project to $00,01,11,10$; for $(Y,Z)$ they project to $00,11,01,10$. Each projection lists each pair exactly once, proving pairwise independence. But $\mathbb{P}(X=0,Y=0,Z=0)=1/4$ differs from the product $1/8$, so the three are not independent random variables. Indeed, any two determine the third. A single coordinate reveals nothing about another, while two coordinates together reveal it completely.

The exclusive or example is the complementary-bit version of the two-toss exercise in Grinstead and Snell, Introduction to Probability, section 4.1, exercise 7, printed page 151. It is a compact reason to check the full product rule whenever a calculation uses three-way or higher events.

Pairwise independent events describe a subtle kind of uncertainty: learning that one event occurred leaves each other event's probability unchanged, yet learning that two occurred can reveal a third completely. Checking every pair therefore answers a weaker question than checking the whole collection. The parity construction of pairwise independent bits makes this distinction visible with just four equally likely outcomes.

A family of events $A_i$ is pairwise independent whenIf $\mathbb{P}(A_j)>0$, this is equivalent to the conditional probability identity $\mathbb{P}(A_i\mid A_j)=\mathbb{P}(A_i)$. The product definition also handles events of probability zero. Independent events, meaning mutually independent events, require the same product rule for every finite subfamily, including triples. For three events, the three pair equations and the triple equation are four separate requirements. ^[ref].

For a worked example, take independent fair bits $U,V$: the sample space is $\{00,01,10,11\}$ with probability $1/4$ per outcome. Set $X=U$, $Y=V$, and $Z=U\oplus V$, using exclusive or, which is one precisely when its inputs differ. The events $A=\{X=1\}$, $B=\{Y=1\}$, and $C=\{Z=1\}$ each contain two outcomes. Their pair intersections areThus each event has probability $1/2$ and each pair intersection has probability $1/4=(1/2{)}^2$: these are pairwise independent events. But $X=Y=1$ forces $Z=0$, soThe three are not independent events. This is the complementary-third-event version of the two-toss example in Tsitsiklis and Jaillet, MIT Introduction to Probability, Lecture 3, slides 7–8.

Another useful diagnostic preserves a special common-intersection case. Suppose three events have common probability $s$ and every pair and triple intersect in the same event, of probability $q$. Pairwise independence requires $q=s^2$, while mutual independence additionally requires $q=s^3$. Both hold only for $s=0$ or $s=1$. For a concrete nontrivial instance, assign probability $1/4$ to each of four outcomes, let all three events contain the first outcome, and give each event one different additional outcome. Then $s=1/2$ and $q=1/4$: the pair equations hold, while the triple equation fails. Unlike the exclusive or example above, this triple intersection is nonempty.

Let $X,Y$ be independent fair bits and set $Z=X\oplus Y$, their exclusive or. The four possible triples are $000,011,101,110$, each with probability $1/4$. Every coordinate is fair, and every pair has all four outcomes with equal probability. Thus each pair's mutual information is zero, as in pairwise independence does not imply joint independence.

The full random vector has joint entropy ${\log }_{2}4=2$ bits, while the marginal information entropies sum to three bits. ConsequentlyThe product of the marginals predicts probability $1/8$ for every triple, including the four impossible ones. On each possible triple, the ratio of true to product probability is $(1/4)/(1/8)=2$; averaging its base-two logarithm gives the same one bit of relative entropy.

The example gives a concrete use for joint information measures. A lossless source coding scheme that treats the three coordinates separately needs three bits here. If the decoder knows the integer parity rule, the encoder can send just $X,Y$ and let the decoder reconstruct $Z$ exactly. Pairwise independence does not reveal that saving. This is a stipulated source law and an explicit two-bit code, rather than a promise that arbitrary data can be shortened.

The parity construction of pairwise independent bits turns two independent fair bits into three pairwise independent random variables. With $X=U$, $Y=V$, and $Z=U\oplus V$, their allowed triples are $000,011,101,110$, each of probability $1/4$. Every coordinate has the Bernoulli distribution with parameter $1/2$. Every pair has the same joint probability mass function:All twelve pair cells equal the product of the corresponding probabilities in their marginal distributions. This establishes pairwise independent random variables, a requirement involving every pair of value-events, rather than merely one chosen event per coordinate. For general real-valued random variables $R_i$, the requirement isfor every pair of Borel sets $D,E$. For these binary random variables, checking all four cells of each pair suffices: any value-event is a union of the checked cells. In fact, for binary random variables, independence of their one-value events also gives the other cells by taking complements. Siegrist gives the all-set definition and its connection to indicator random variables in Random Services: independence of random variables.

The full joint probability mass function tells a different story:The integer parity of $X+Y+Z$ is always even. Any two bits determine the third: $Z=X\oplus Y$, $X=Y\oplus Z$, and $Y=X\oplus Z$. Each coordinate is independent of either other coordinate individually, but is dependent on the pair together. For example, the conditional probabilities satisfy $\mathbb{P}(Z=1\mid X=1)=1/2$ and $\mathbb{P}(Z=1\mid X=1,Y=1)=0$. See also pairwise independence does not imply joint independence for the general distinction.

The constraint changes the sum's probability distribution without changing its expected value or variance. Let $S=X+Y+Z$. Only $000$ gives $S=0$; each other allowed triple gives $S=2$. Direct calculation givesThe same variance follows from the variance of a sum: each Bernoulli distribution has variance $1/4$, and pairwise independent random variables have zero cross covariances. Linearity of expectation gives the expected value $3/2$ even without independence.

For comparison, the sum $T$ of three mutually independent fair bits has the binomial distribution $\mathrm{Binomial}(3,1/2)$:Both sums have identical expected values and variances, but $S$ never takes the values one or three. Even their third moments differ: $\mathbb{E}[S^3]=6$, whereas $\mathbb{E}[T^3]=27/4$. Pairwise independence preserves these first two sum summaries while allowing a different joint probability distribution and a different sum law. The calculation is an exact finite example.

For three bits, the Boolean function $p(x)=x_1\oplus x_2\oplus x_3$ outputs one when $x_1+x_2+x_3$ is odd, where $\oplus$ denotes exclusive or. Unlike the three-bit majority decision tree, an exact decision tree computing parity must inspect all three bits on every input. If any coordinate is unread, two completions differing only at that coordinate follow the same observed graph path but have opposite parity. A single leaf cannot correctly label both.

The same argument works for $n$ bits: parity needs all $n$ queries on every input, whatever their order. Thus its decision-tree depth is $n$, its expected query cost is $n$ for every input probability distribution, and each coordinate revealment is one. The algorithm remains required to be correct on the whole Boolean cube, even if the chosen probability distribution assigns some inputs zero probability; a promise restricting permitted inputs would be a different computational problem.

For finite-valued random vectors, the conditional entropy is the average of the entropies of the conditional distributions:Use $0{\log }_{2}0=0$ and omit zero-probability conditioning events. Equivalently,The base two makes all information quantities measured in bits; changing the logarithm base scales them by a positive constant and preserves the inequalities.

An instantaneous code can decode each symbol as soon as its final bit arrives, without waiting for later bits. Equivalently it is prefix-free: no codeword is a proper prefix of another, and different symbols receive different codewords.

For nonempty codewords, decoding greedily from the start of the bit string identifies the first codeword unambiguously; repeating identifies the whole sequence. Thus an instantaneous code is uniquely decodable under the ordinary nonempty-word convention.

A binary code assigns a finite binary word $c_k$ to each source symbol $x_k$. In the ordinary unframed convention these codewords are nonempty. It is uniquely decodable when concatenation gives an injective map from finite symbol strings to bit strings:The decoder can recover the entire symbol sequence without being told where codewords end. This is stronger than merely assigning distinct words to individual symbols.

Let $F_k={\sum }_{r<k}{p}_r$ and let $J_k=[F_k,F_k+p_k)$ be the probability cell of symbol $k$. Its midpoint is $G_k=F_k+p_k/2$. Use the binary expansion terminating in zeros at a dyadic rational, so truncation to $l_k$ bits givesThe chosen codeword corresponds to the dyadic interval $D_k=[a_k,a_k+2^{-l_k})$. It contains $G_k$, and its width satisfies $2^{-l_k}\le p_k/2$. ConsequentlyThus $D_k\subseteq J_k$. The probability cells are disjoint, so the code intervals are disjoint. If one binary codeword were a prefix of another, its dyadic interval would contain the other's interval, contradicting this disjointness. Hence the code is instantaneous.

Finally, $l_k=\lceil -{\log }_2{p}_k\rceil +1<-{\log }_2{p}_k+2$. Multiplying by $p_k$ and summing yieldsThis is the Shannon-Fano-Elias code: the extra bit makes the dyadic interval narrow enough to remain inside the cell around its midpoint.