An observation can increase entropy 2026-10-14
Consider a binary state and a report with the following joint probability mass function:Before the report, is strongly favored: its information entropy is bits, where is binary entropy. A report makes the two states equally likely, so bit, strictly larger than before. This report occurs with probability . The more common report determines , giving . Therefore the averaged conditional entropy isThe resulting mutual information is bits. The rare report increases uncertainty about the state; that increase does not make the report useless. Together the reports remove uncertainty on average. These are stipulated probabilities in an exact model, not measured frequencies.
Asymptotic equipartition property Created 2026-09-24 Updated 2026-10-14
The asymptotic equipartition property explains why a long message from a source can usually be described using its information entropy per symbol. Individual messages can have very different probabilities, but the messages carrying almost all the total probability have similar logarithmic costs per symbol. The Bernoulli typical-set example makes the distinction between an individual message and a large collection explicit.
For independent and identically distributed random variables on a finite alphabet, let be their probability mass function and . ThenHere means the probability mass of the realized word, evaluated under the source law. The product rule for independent random variables turns its information content into a sum:The strong law of large numbers gives the limit. Zero-probability symbols do not occur; on the positive-probability support of a finite alphabet, these information costs are finite. The corresponding typical set consists of words whose cost per symbol is within a chosen tolerance of .
For a strictly stationary process with a finite alphabet, the constant-limit extension requires ergodicity. The Shannon-McMillan-Breiman theorem then replaces the one-symbol information entropy with the information rate. Stationarity without ergodicity in an information source shows why stationarity alone is insufficient.[ref]
6.441 Information Theory (Spring 2016 lecture notes) by Yury Polyanskiy and others. §8, Theorem 8.1 and Corollary 8.2, printed p. 90: stationary ergodic sources and typical sets
Binary entropy Created 2026-09-24 Updated 2026-10-14
The binary entropy function is the information entropy of a Bernoulli random variable:with endpoint values zero. It is symmetric under , reaches one bit at , and hasin the interior. Its strict concavity expresses why an even mixture of two outcomes has more uncertainty than a strong bias toward either one. The curve in mutual information also shows how this same uncertainty becomes the loss term in binary symmetric channel capacity.
Binary Markov source 2026-10-14
Take the alphabet , fair initial bit , and transition matrixThe stationary distribution is . Every emitted symbol is a fair bit, while the next symbol flips the previous one with probability . For , repeating the previous symbol is the better one-step prediction; for , predicting its opposite is better. The resulting minimum next-symbol error probability is , compared with when no history is used.
Given either state, the next-symbol information entropy is . ThusAt , the best next-symbol prediction succeeds with probability , and the entropy rate is about bits per symbol. The adjacent symbols share mutual information bits. This is useful structure even though the single-symbol counts reveal no bias.
At , the random initial bit is repeated forever; at , it alternates forever. Both have and zero entropy rate. At , the symbols are independent and identically distributed fair bits, giving entropy rate one. Zero rate therefore need not mean that the initial choice was deterministic.
Bit 2026-10-14
A bit is a binary classical symbol with two distinguishable values, zero and one. A uniform random bit has one bit of information entropy, while a biased binary symbol has less. Sending one bit means transmitting one symbol from this binary alphabet; the mutual information it carries about a particular input need not be one.
Chain rule for information entropy Created 2026-09-24 Updated 2026-10-18
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]
A Mathematical Theory of Communication by Claude Shannon. section 6, property 5, reprint p. 12: joint entropy as first entropy plus average conditional entropy
Iterating gives . The first summand means , 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 , then average with those joint probabilities. Summing over in the first term gives ; the second is precisely . Repeating the same step with a longer random vector proves the iterated identity. Reversing the order also gives : the two contributions can change with the order, but their total cannot.
Channel capacity Created 2026-09-24 Updated 2026-10-14
Channel capacity is the best reliable information rate available through a specified communication channel. For a discrete memoryless channel with finite input and output alphabets, fixed transition probabilities , and no input-cost constraint, it isin bits per channel use, when the mutual information uses base-two logarithms. The maximization varies the input probability distribution, while keeping the communication channel fixed. A large input alphabet or a large output information entropy alone does not determine how much information gets through: the receiver needs information about the input, rather than merely unpredictable output.
The operational meaning comes from the Shannon second coding theorem. A block code represents one of possible messages by a word of length , giving a rate bits per use. Take the message label from the uniform distribution on a finite set of those choices when measuring average decoding-error probability. For every fixed rate , there are sequences of such block codes whose decoding-error probability tends to zero as grows; a rate above cannot have vanishing decoding-error probability. This is an asymptotic limit, rather than a promise that an arbitrary finite block code at a rate below works well. See MIT 18.310, Shannon's Noisy Coding Theorem, sections 1–2.
For a binary symmetric channel with crossover probability , the binary symmetric channel capacity is approximately bits per use. Thus a binary code rate lies below the limit, while lies above it. At , two transmitted symbols represent one message bit on average; the redundancy helps distinguish messages after noise. This does not split individual physical symbols into fractional pieces.
The result is useful because it separates two tasks. Computing channel capacity establishes the target imposed by the transition probabilities; constructing an effective block code attempts to approach that target with acceptable delay and decoding effort. The surprise is that reliability can improve indefinitely without forcing every positive rate to disappear. In his 1948 paper, Shannon defines noisy channel capacity in section 12 and develops its operational significance in section 13, Theorem 11. His original formulation uses information per unit time; the fixed-duration channel-use convention here expresses the same rate question per symbol. [ref].
Coloring entropy weight 2026-10-14
Compression of an entropy sum 2026-10-06
A union-intersection compression can only decrease the sum of information entropies for a finite-valued random vector . Each elementary step follows from entropy submodularity; iteration proves the assertion with multiset multiplicities. Uniform coordinate multiplicity gives Shearer inequality by compressing to repeated full sets and empty sets.
Conditional entropy Created 2026-09-24 Updated 2026-10-14
For finite discrete random variables, conditional entropy is the average remaining information entropy of after the value of is known:Each observation changes the probability distribution used to describe ; 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 choose with probabilities , and let report whether . If it reports yes, there is no remaining uncertainty. Otherwise the conditional probabilities are , whose information entropy is bits. The two reports each occur with probability , so of a bit. The original uncertainty was bits: this observation removes exactly one bit on average.
If is a function of , then : the observation determines the answer. If and are independent random variables, then : 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, , which counts the first uncertainty and the remaining uncertainty without double counting.
Conditional entropy rate 2026-10-14
For a strictly stationary process on a finite alphabet, put and for . Each 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 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.
Conditioning reduces entropy Created 2026-09-24 Updated 2026-10-14
For finite discrete random variables , knowing reduces the information entropy of on average:Equality holds exactly when and are independent random variables. The average over observations is essential: can exceed for a particular . All logarithms here have base two, giving bits, and zero-probability terms contribute zero.[ref]
For Bayesian inference, this compares a prior distribution with the posterior distributions produced by possible observations. An unexpected report can make previously unlikely alternatives plausible, while useful reports reduce uncertainty overall. For lossless source coding, an observation shared by encoder and decoder lets them choose descriptions for the appropriate conditional distribution; sending that observation also has a cost. The example below makes both the saving and that cost explicit.
In A Mathematical Theory of Communication by Claude Shannon (1948), the definition of conditional entropy is already an average over observations, followed by the inequality and its independence condition in section 6, property 6. The phrase “knowledge reduces uncertainty” must be read with that averaging convention.[ref]
A Mathematical Theory of Communication by Claude Shannon. p. 12; title page identifies C. E. Shannon and the 1948 journal publication
Correlated binary variables 2026-10-18
Cross-entropy 2026-10-14
Cross-entropy measures the average logarithmic loss incurred when outcomes follow one probability distribution , but a model assigns probabilities using another probability distribution . For a finite alphabet, write their probability mass functions as and . With base-two logarithms,The expectation is under the true or stipulated source law , rather than the model . Terms with contribute nothing. If but for any outcome, the cross-entropy is : the model rules out an event that can occur. The result is measured in bits; natural logarithms give nats.
The useful identity is cross-entropy equals entropy plus relative entropy:The source's information entropy is the baseline uncertainty. The Kullback-Leibler divergence is the extra average cost of a mismatched model, with the true law first and model second. Thus optimizing for a fixed reduces the mismatch, rather than changing the source's own uncertainty. For finite alphabets, the minimum is , attained exactly at .
Take a three-symbol source with . A matched binary prefix code assigns , , , with lengths . A mismatched prefix code instead assigns , , , with lengths , corresponding to . Both prefix codes decode exactly, but the most common symbol is shorter in the matched code. Under the same source ,The mismatched code costs an extra (1/4) bit per source symbol on average. No information is lost; the penalty is inefficient representation of this source. The mismatch penalty in lossless coding explains when this coding interpretation is exact.
Cross-entropy is also useful when evaluating a predictive distribution. A report that places tiny probability on the realized outcome receives a large logarithmic loss, even when it usually predicts the most common outcome correctly. The loss convention is the negative of the reward convention in the logarithmic scoring rule. Its expected loss is uniquely minimized by the correct probability distribution, making it a strictly proper scoring rule. Strictly Proper Scoring Rules, Prediction, and Estimation by Tilmann Gneiting and others treats this connection in §3.1, Example 3; its discussion uses rewards, so the signs are reversed for the losses here.[ref]
I. J. Good's Rational Decisions by I. J. Good appeared in 1952. Its published summary describes a method for encouraging accurate probability estimates and a connection with information theory. Strictly Proper Scoring Rules, Prediction, and Estimation by Tilmann Gneiting and others traces the logarithmic scoring rule at least as far back as this 1952 paper.[ref]
Cross-entropy equals entropy plus relative entropy Created 2026-10-14 Updated 2026-10-25
For finite probability mass functions, with whenever , subtract the two expectations of logarithmic loss:The Gibbs inequality makes the difference nonnegative and zero exactly when . If assigns zero probability to an outcome with positive probability under , both the cross-entropy and the Kullback-Leibler divergence are infinite. The finite information entropy still leaves the displayed identity valid in the extended sense. In more general settings, undefined differences such as cannot be used as a derivation.
Cryptographic leakage 2026-11-05
Cryptographic leakage is information about secret inputs or internal state that an observer obtains through the interfaces or observations admitted by a security model. A model can explicitly permit some disclosures, such as message length, while requiring other information to remain hidden. In universal composability, an ideal cryptographic functionality states such permitted disclosure through information sent to the cryptographic simulator.[ref]
Universally Composable Security: A Tutorial by Ran Canetti. PDF pp. 25–26, ideal-service leakage and wrapper; p. 33, message-hiding service with lengths and timings exposed
A simple cryptographic leakage function writes the disclosed value as , where is a secret random variable. An original example takes uniform on the 256 eight-bit strings and lets reveal its first four bits. Before observing , every complete secret has probability . Afterwards, exactly sixteen secrets remain equally likely, so the best complete-secret guess succeeds with probability . The calculation assumes that the observer has no additional correlated information.
Using information entropy measured in bits, this example givesHere is conditional entropy and is mutual information. Revealing four bits does not make the entire secret known, but it reduces a sixteen-way uncertainty in the first half to certainty. Guessing probability and entropy describe related but different quantities; the simple powers of two arise from this example's uniform conditional distributions.
Length disclosure gives another operational example. Suppose a cryptographic environment privately chooses a uniform bit , then submits a one-byte message when and a two-byte message when . Observing the length reveals exactly, even if the encryption hides all message contents at each fixed length. An ideal service that reveals no such distinction cannot support the same pre-delivery observation. The security specification must either permit length disclosure or require an implementation to conceal it.
The permitted observations must be stated before making a security claim. A cryptographic transcript that omits timing does not itself prove security against timing observations. Likewise, a model that permits a chosen disclosure does not assert that the disclosure is harmless for every application. The useful question is which secrets remain hidden from an observer with that particular view.
Cryptographic salt 2026-11-05
A cryptographic salt is an additional input used by a cryptographic construction to vary or condition its processing of secret material. Its required properties depend on the construction. In HKDF, the salt is the key input to the extraction HMAC, while the initial keying material is the HMAC message. The salt is normally non-secret, and the specification permits reuse and defines a default when no salt is provided.[ref]
HMAC-based Extract-and-Expand Key Derivation Function (HKDF) by Hugo Krawczyk and Pasi Eronen. §2.2 and §3.1, salt definition, optional value and reuse
For HKDF extraction,Fixing both inputs gives a deterministic intermediate key. Changing salt changes the HMAC computation even if the initial material is unchanged. The public salt can therefore distinguish extraction contexts; it does not need to be counted as another secret shared by the participants. The RFC's security discussion also requires attention to how salts are obtained and to adversarial control of inputs.[ref]
An original counting argument separates public variability from secret uncertainty. Suppose secret is uniform over values and independent public salt is uniform over values. There are possible input pairs before either value is known. Once is public, however, only candidate secrets remain. For any deterministic derived key ,where is information entropy and the conditioning uses conditional entropy. Producing a 256-bit key string does not turn that twenty-bit secret source into 256 bits of conditional uncertainty.
The same example shows why per-target guessing and preparing a table for every possible salt are different tasks. A table enumerating every stipulated secret/salt pair would have entries, while enumeration for one known salt still has candidate secrets. This counts the toy input space, not the cost or guarantee of a particular password-processing scheme.
A salt is also distinct from a cryptographic nonce, whose permitted reuse is specified by the consuming algorithm, and from the expansion context used for cryptographic domain separation. Parameter names alone do not make their requirements interchangeable.
Differential entropy Created 2026-10-06 Updated 2026-10-14
Differential entropy describes the spread of a continuous probability distribution relative to the volume scale of its coordinates. For a real random variable with probability density function , use natural logarithms and writeThe convention is . For a finite value, require ; if both positive and negative contributions are infinite, the expression is undefined. Unlike a probability, a probability density can exceed one. Consequently differential entropy can be negative. Base-two logarithms give , in bits instead of nats.[ref]
Chapter 1: Information Measures: Entropy and Divergence. §1.3, Definition 1.5, equation (1.19) and warning, printed p. 18
This quantity does not give the exact number of bits needed to store a real number. A recording device supplies a resolution; equal-width bin entropy connects that resolution to discrete information entropy. The useful continuous quantity is what remains after removing the increasing cost of specifying finer bins. Its dependence on coordinates is visible already in differential entropy of a uniform law.
Differential entropy of a uniform law 2026-10-14
For a continuous uniform distribution on an interval of length , the probability density is . Direct integration givesThus a uniform law on an interval of length has differential entropy , while length two gives . Both laws have total probability one. The shorter interval has larger probability density, making negative; this is neither a negative probability nor a negative discrete information entropy.
Uniform densities can have negative or positive differential entropy
. The two stipulated continuous uniform distributions have density two on an interval of length and density on an interval of length two. Each rectangle has area one. The reported differential entropy is in nats, using the displayed numerical coordinates. Details.If every pair of graphs in a family on has a graph intersection without an isolated vertex, the family has at most members. At each vertex, its possible graph neighbourhoods form an intersecting family, of size at most . Every edge occurs in two such neighbourhood projections. Shearer inequality bounds twice the full information entropy by the sum of their information entropies.





