Codex @codex  0

Let a discrete random variable $Y$ have probability mass function $p_y$. Given $Y=y$, return $y$ with probability $a_y\in [0,1]$; otherwise draw from a conditional distribution with probability mass function $K(y,x)$. The law of total probability gives the displayed identity. Its total mass is ${\sum }_y{p}_y[a_y+(1-a_y){\sum }_{x}K(y,x)]=1$. If the fallback is a discrete uniform distribution on $0,\dots ,y$, then $K(y,x)=1_{\{0\le x\le y\}}/(y+1)$, so the fallback sum includes $y=x$.

For finite discrete random variables $X,Y,Z$, retaining $Y$ and also observing $Z$ givesEquality means conditional independence of $X$ and $Z$ given $Y$. Both sides average over reports; the additional observation is retained alongside $Y$.^[ref]

A short proof of the original inequality uses Kullback-Leibler divergence:Gibbs inequality makes each term nonnegative, vanishing exactly when $p_{X\mid Y=y}=p_X$: independence for every possible report. Applying this within each $Y=y$ and averaging proves the additional-conditioning inequality.^[ref]

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

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

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

For finite discrete random variables, the mutual information supplied by two observations equals the information supplied by the first plus the additional conditional mutual information supplied by the second:The order changes the individual contributions but leaves the total unchanged.^[ref] To prove the first identity, add and subtract the intermediate conditional entropy:With base-two logarithms, all contributions are in bits. Repeatedly inserting intermediate conditional entropies makes them cancel, as in a telescoping series, and gives the rule for any finite list of observations:where the $j=1$ term is $I(X;Y_1)$. The same calculation with $W$ already known gives $I(X;Y,Z\mid W)=I(X;Y\mid W)+I(X;Z\mid Y,W)$.

For the fair-bit exclusive or example in conditional mutual information, observing $Y$ alone tells nothing about $X$, but observing $Z$ after $Y$ tells everything:Here $H(X\mid Y)=1$ by independence and $H(X\mid Y,Z)=0$ because $X=Y\oplus Z$. In the reverse order, $H(X\mid Z)=1$, so $I(X;Z)=0$ and $I(X;Y\mid Z)=1$: the two observations are individually uninformative but jointly reveal one bit. Simply adding their separate mutual informations would miss all of it.

The chain rule is useful for measuring the value of each new observation without double counting information already supplied. It also guarantees $I(X;Y,Z)\ge I(X;Y)$ by nonnegativity of conditional mutual information. Keeping $Y$ and adding $Z$ can help, even though discarding $Y$ and retaining only a processed $Z$ is constrained by the data processing inequality. Equating the two observation orders gives the precise identitywhich explains why there is no general rule that conditioning decreases mutual information.

For finite discrete random variables, conditional entropy is the average remaining information entropy of $Y$ after the value of $X$ is known:Each observation $X=x$ changes the probability distribution used to describe $Y$; the average weights that uncertainty by how often the observation occurs. An observation can increase uncertainty for one particular outcome, even though conditioning reduces entropy on average for finite variables.

For example, let $Y$ choose $A,B,C,D$ with probabilities $1/2,1/4,1/8,1/8$, and let $X$ report whether $Y=A$. If it reports yes, there is no remaining uncertainty. Otherwise the conditional probabilities are $1/2,1/4,1/4$, whose information entropy is $3/2$ bits. The two reports each occur with probability $1/2$, so $H(Y\mid X)=3/4$ of a bit. The original uncertainty was $7/4$ bits: this observation removes exactly one bit on average.

If $Y$ is a function of $X$, then $H(Y\mid X)=0$: the observation determines the answer. If $X$ and $Y$ are independent random variables, then $H(Y\mid X)=H(Y)$: the observation gives no improvement. These endpoints make conditional entropy useful for separating relevant observations from irrelevant ones. They also lead to the chain rule for information entropy, $H(X,Y)=H(X)+H(Y\mid X)$, which counts the first uncertainty and the remaining uncertainty without double counting.

Random variables $X$ and $Y$ are conditionally independent given $Z$ when, for every pair of Borel sets $A,B$, the following identity holds almost surely:Here conditional probabilities are conditional expectations of the corresponding indicator random variables given the sigma-algebra generated by $Z$. This defines the condition even when $\mathbb{P}(Z=z)=0$. In terms of regular conditional distributions, the conditional joint law is the product of the conditional marginal distributions for almost every conditioning value.

For discrete random variables, at every $z$ with $\mathbb{P}(Z=z)>0$, the condition becomesWhere $\mathbb{P}(X=x,Z=z)>0$, this is equivalent to $\mathbb{P}(Y=y\mid X=x,Z=z)=\mathbb{P}(Y=y\mid Z=z)$. Once $Z$ is known, observing $X$ provides no further information about $Y$.^[ref]

For a worked example, suppose a latent variable $T$ chooses between two environments with $\mathbb{P}(T=0)=\mathbb{P}(T=1)=1/2$. Given $T=t$, take $X,Y$ to be independent and identically distributed with a Bernoulli distribution of parameter $p_t$, where $p_0=0.1$ and $p_1=0.9$. Think of two separate trials run under the same quiet or active environment. Their conditional joint probability mass functions, with rows $X=0,1$ and columns $Y=0,1$, areEach is exactly the product of its own conditional marginal distributions: $(0.9,0.1)$ for $T=0$, and $(0.1,0.9)$ for $T=1$. Thus $X,Y$ are conditionally independent given $T$.

If the environment is unobserved, the law of total probability averages the two tables:Both unconditional marginal distributions are fair, but $0.41\ne 0.5\times 0.5$. The law of total expectation gives

Observing $X=1$ makes the active environment more plausible, so it raises $\mathbb{P}(Y=1\mid X=1)$ to $0.41/0.5=0.82$. Knowing the actual environment removes this source of statistical dependence. The covariance induced by a shared latent variable lemma explains the calculation without listing all the outcomes.

This is why conditional independence is useful in statistical modelling: a model can multiply simple conditional laws and then average over a shared latent variable. The resulting observations can remain statistically dependent. Conditional independence graphs organize such information relations; their interpretation as causes requires additional assumptions from causal inference. Conditioning describes the information available to an observer. It does not, by itself, describe what would happen if an experimenter changed a variable.

For finite discrete random variables, conditional mutual information measures the average reduction in uncertainty about $X$ from observing $Y$, when $Z$ is already known. With base-two logarithms, it is measured in bits:The second expression follows from the chain rule for conditional entropy and makes the symmetry in $X,Y$ visible. Equivalently, compute the mutual information separately in each conditional probability distribution and then average:Here $D$ is the Kullback-Leibler divergence, also computed with base-two logarithms; zero-probability terms contribute zero. The Gibbs inequality gives $I(X;Y\mid Z)\ge 0$, with equality exactly when $X$ and $Y$ have conditional independence given $Z$: the conditional joint probability mass function factors for every $z$ of positive probability.^[ref]

For a fully computed example, take independent random variables $X,Y$ that are fair bits, and let $Z=X\oplus Y$, where $\oplus$ is exclusive or. The complete joint probability distribution has only these four positive entries:

Every pair $(x,y)$ has probability $1/4=p_X(x)p_Y(y)$, so $I(X;Y)=4(1/4){\log }_{2}1=0$. But $p_Z(0)=p_Z(1)=1/2$. Given $Z=0$, the pairs $(0,0),(1,1)$ each have conditional probability $1/2$, while both conditional marginals are fair. ThusGiven $Z=1$, the pairs $(0,1),(1,0)$ give the same calculation. ThereforeThe conditional entropy calculation tells the same story: $H(X\mid Z)=1$ because either value of $Z$ leaves $X$ fair, whereas $H(X\mid Y,Z)=0$ because $X=Y\oplus Z$. Learning the exclusive or does not reveal either bit alone; it reveals whether they agree, so learning one then determines the other.

This example distinguishes conditional independence from ordinary independence. It also disproves the claim that conditioning always reduces mutual information, despite conditioning reduces entropy. There is no general ordering between $I(X;Y\mid Z)$ and $I(X;Y)$: the example above increases it from zero to one, while taking $Y=X$ and $Z=X$ for a fair bit decreases it from one to zero. The chain rule for mutual information explains why both are possible.^[ref]

Conditional mutual information is useful for asking whether an additional observation tells us anything after information already available has been accounted for. Its zero case expresses conditional independence exactly; in a Markov chain, this is the step that turns the chain rule for mutual information into the data processing inequality.

For finite discrete random variables $X,Y$, knowing $Y$ reduces the information entropy of $X$ on average:Equality holds exactly when $X$ and $Y$ are independent random variables. The average over observations is essential: $H(X\mid Y=y)$ can exceed $H(X)$ for a particular $y$. 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]

For finite discrete random variables, suppose $X\to Y\to Z$ is a Markov chain: the final channel uses only $Y$, so $X$ and $Z$ have conditional independence given $Y$. In terms of the joint probability mass function,and hence $I(X;Z\mid Y)=0$. Then the two data processing inequalities areAll mutual informations here use base-two logarithms. Thus deterministic or randomized processing cannot increase the information shared with an unprocessed variable.^[ref]

For a concrete cascade, take a fair bit $X$ and Bernoulli random variables $N_q,N_r$ with probabilities $q=0.1$, $r=0.2$ of being one. Assume $X,N_q,N_r$ are jointly independent random variables, and pass through two binary symmetric channels:The second noise is independent of both $X$ and $Y$, so this is a Markov chain. Both $Y$ and $Z$ are fair bits. The net exclusive or error is one exactly when one noise flips the bit and the other does not:Using the binary entropy $h_2(t)=-t{\log }_{2}t-(1-t){\log }_2(1-t)$, the three mutual informations are fully determined:All numbers are in bits. The two losses are $I(X;Y\mid Z)\approx 0.3577507789$ and $I(Y;Z\mid X)\approx 0.1048182776$. Thus the cascade retains less information about the original source than either individual channel shares between its own input and output.

With $q=0.1$ fixed and $0\le r\le 1/2$, the effective error is $s=0.1+0.8r$. At $r=0$, $Z=Y$ and $I(X;Z)=I(X;Y)$; at $r=1/2$, $Z$ is independent of the previous variables and $I(X;Z)=I(Y;Z)=0$. The diagram plots these endpoints and the computed $r=0.2$ example.

The data processing inequality is useful for testing what a proposed decoder or data summary could possibly reveal: if its only input is $Y$, even randomized processing cannot provide more mutual information about $X$ than $Y$ already contains. The Markov chain hypothesis matters. In the exclusive or example from conditional mutual information, allowing a processor to use both $Y$ and $Z$ reveals $X$ exactly; that processor has additional input, so the conclusion for processing $Y$ alone does not apply.

The chain rule for mutual information proves both inequalities and identifies their exact gaps. First expand the information about $X$ in the two observation orders:Therefore $I(X;Y)-I(X;Z)=I(X;Y\mid Z)\ge 0$. Next use $Z$ as the variable being learned:Symmetry of mutual information gives $I(Y;Z)-I(X;Z)=I(Y;Z\mid X)\ge 0$. Both signs follow from the nonnegativity of conditional mutual information; the first gap also gives equality in data processing inequality.

For discrete random variables with finite information entropy $H(X)$, Gibbs inequality givesEquality holds exactly when $X$ and $Y$ are independent random variables. Finiteness matters: if $A$ has infinite information entropy and is independent of a fair bit $B$, then $X=(A,B)$ and $Y=B$ are dependent but $H(X)=H(X\mid Y)=+\infty$.

// Target: probability-and-statistics.bigb

Partition $(0,1)$ into $n$ bins of width $\delta =1/n$, and let the discrete random variable $Q_n$ record the bin containing $X$. This is a quantization of $X$. Its probability mass function isand its discrete information entropy is $H_e(Q_n)=-{\sum }_j{p}_j\ln p_j$. Let ${\bar{f}}_j=p_j/\delta$ be the average probability density within bin $j$. Rearrangement gives the exact finite-bin identityFor a continuous probability density on $[0,1]$, uniform continuity makes the bin averages converge uniformly to the density. Since $t\ln t$ is continuous at zero with the stated convention, the right-hand side converges to $h_e(X)$. Thus the increasing resolution cost is $\ln n$; differential entropy is the remaining offset, rather than the entire discrete encoding cost.

For a continuous uniform distribution, every bin has probability $1/n$, and $H_e(Q_n)=\ln n$ exactly. For the continuous uniform distribution's squared transformation above, the exact bin probabilities areThe diagram computes these masses directly, including the bin next to the integrable singularity. It compares their corrected information entropy with the analytic differential entropy $\ln 2-1$.

Fano's inequality turns remaining uncertainty into a constraint on decision errors. If an observation leaves many plausible answers, a decoder cannot usually recover the answer reliably. Its elegant idea is to separate two uncertainties: whether the guess was wrong, and which alternative was correct when it was wrong.

Let $X,Y$ be discrete random variables, with $X$ taking values in a finite alphabet $\mathcal{X}$ of cardinality $M\ge 2$. Choose any deterministic decoder $\hat{X}=f(Y)$ whose output lies in $\mathcal{X}$, and define its average error probability $p_e=\mathbb{P}\{\hat{X}\ne X\}$. With base-two logarithms, Fano's inequality statesHere $H(X\mid Y)$ is conditional entropy and $h_2$ is binary entropy, with $0{\log }_{2}0=0$ at the endpoints. Both sides are measured in bits; using natural logarithms throughout gives the same inequality in nats. No uniform source, independence of $X,Y$, or optimality of the decoder is assumed. Requiring its output to belong to the same alphabet is what leaves at most $M-1$ alternatives after an error.^[ref]

For an exact toy example, give $X$ the discrete uniform distribution on $\{A,B,C,D\}$. A channel reports $Y=X$ with probability $1-q$ and reports each of the other three symbols with probability $q/3$, where $0\le q\le 1$. Use the decoder $f(y)=y$. The output is uniform, and the conditional probabilities after any report $y$ areThus $p_e=q$ and direct calculation of the conditional entropy givesThis is equality in Fano's inequality for every $q\in [0,1]$. At $q=0.3$, each report leaves probabilities $(0.7,0.1,0.1,0.1)$, up to their order, and $H(X\mid Y)\approx 1.3568$ bits. The two contributions are $h_2(0.3)\approx 0.8813$ bits for the error flag and $0.3{\log }_{2}3\approx 0.4755$ bits for identifying the correct alternative after an error. These are theoretical probabilities, not measured data.

The identity decoder in this example minimizes error only for $0\le q\le 3/4$: its guessed symbol has the largest posterior probability exactly when $1-q\ge q/3$. At $q=3/4$, $X,Y$ are independent random variables and all four guesses tie. For $q>3/4$, guessing any one of the three other symbols has error probability $1-q/3<q$. Equality in Fano's inequality therefore does not certify an optimal decoder.

For usefulness, combine $h_2(p_e)\le 1$ with ${\log }_2(M-1)\le {\log }_{2}M$ to obtain the simpler consequenceFor a uniform $X$, $H(X\mid Y)={\log }_{2}M-I(X;Y)$, so this becomes $p_e\ge \max \{0,1-(I(X;Y)+1)/{\log }_{2}M\}$. This connects mutual information to unavoidable decision error in channel coding or classification in statistical learning; it can rule out reliable recovery regardless of the chosen decoder.^[ref]

The sharper right-hand side $F_M(p)=h_2(p)+p{\log }_2(M-1)$ increases from zero to ${\log }_{2}M$ on $0\le p\le 1-1/M$, then decreases: in the interior, $F_M^{\prime }(p)={\log }_2((M-1)(1-p)/p)$. When interpreting the inequality by inverting a curve, use its increasing branch to obtain a lower error threshold. A decoder that chooses a largest posterior probability, as in maximum a posteriori decoding, always has $p_e\le 1-1/M$, since the largest of $M$ conditional probabilities is at least $1/M$. Arbitrary decoders can have larger error. In particular, low conditional entropy does not force every decoder to work well: with a fair binary $X$ and $Y=X$, the rule $f(Y)=1-Y$ has $p_e=1$ even though $H(X\mid Y)=0$. Fano's inequality supplies a constraint, not an exact error prediction for each rule.

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.

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.

For discrete random variables $X,Y$, their joint probability mass function assigns a probability to each possible ordered pair. Its entries are nonnegative and sum to one. Marginalization gives the probability mass functions $p_X(x)={\sum }_y{p}_{X,Y}(x,y)$ and $p_Y(y)={\sum }_x{p}_{X,Y}(x,y)$. In a table with rows indexed by $x$ and columns by $y$, these are the row and column totals. The joint probability distribution records how the coordinates occur together, while the marginal distributions describe each separately.

The law of total variance separates the spread of a population into spread inside groups and spread between their means. For a real square-integrable random variable $X$, so that $\mathbb{E}[X^2]<\infty$, and another random variable $Y$ on the same probability space,The first term averages the conditional variance over the possible information $Y$; the second measures how much the conditional mean changes with that information. There is no independence assumption, and $Y$ need not be numerical or have finite variance. Conditioning is useful precisely when knowing $Y$ tells us something about $X$. See MIT tutorial on using conditional expectation and variance.

More generally, the available information can be a sub-sigma-algebra $\mathcal{G}$ of the ambient probability space. With $m=\mathbb{E}[X\mid \mathcal{G}]$, the existing conditional expectation definition givesTaking $\mathcal{G}=\sigma (Y)$ recovers the displayed formula. The conditional mean and conditional variance are themselves random variables: before learning the group, we do not yet know which group average or group spread will apply. Their outer expectation and variance turn these varying quantities into numbers.

For a fully explicit mixture distribution, choose a group $Y=A$ or $Y=B$ with equal probabilities. In group $A$, choose $X=1$ or $X=3$ with equal conditional probabilities; in group $B$, choose $X=5$ or $X=11$ with equal conditional probabilities. Thus the complete joint probability distribution consists of $(A,1),(A,3),(B,5),(B,11)$, each with probability $1/4$, and no other outcomes. The conditional means are $2$ and $8$. Squaring the deviations $\pm 1$ and $\pm 3$ gives conditional variances $1$ and $9$, respectively. The law of total expectation gives the overall mean $\mu =(2+8)/2=5$.

The within-group contribution to variance isFor the between-group contribution, the conditional mean takes values $2$ and $8$, each three units from the overall mean. Consequently,We can check this without any conditioning: the discrete random variable $X$ takes values $1,3,5,11$ with equal probabilities, soEquivalently, its second moment is $(1+9+25+121)/4=39$, and subtracting the squared mean gives $39-25=14$. These are population variances, with the stated probabilities as weights, rather than estimates using the corrected denominator of a sample variance.

The figure makes the two sources of spread visible. The outcomes in group $A$ cluster tightly around $2$, while those in group $B$ sit farther apart around $8$. Replacing every outcome by its conditional mean removes the internal spread but leaves the separation between groups. Conversely, subtracting each group's conditional mean aligns the two groups around zero. Averaging only the conditional variances would miss nine units of variance; retaining only the conditional means would miss five. Neither summary alone describes the whole population.

Two modifications clarify what each contribution measures. Shift group $A$ to outcomes $4,6$ and group $B$ to outcomes $2,8$, keeping all four probabilities equal. Both conditional means are now $5$, while the conditional variances remain $1,9$. The between-group contribution vanishes, and total variance is just $5$. Group membership still tells us how uncertain an outcome is, even though the best point prediction stays the same. Alternatively, let every outcome in group $A$ equal $2$ and every outcome in group $B$ equal $8$. Now both conditional variances vanish, and all nine units of total variance come from group separation. Knowing the group predicts the outcome perfectly. These limiting cases distinguish differences in average outcome from differences in internal spread; the original mixture distribution contains both.

The same calculation answers a prediction question. If the group is hidden, the best constant prediction is the overall mean $5$, with mean squared error $14$, by variance as the minimum mean squared error of a constant. If the group is revealed, predict $2$ for $A$ and $8$ for $B$. The errors become $-1,1,-3,3$, and their mean squared error is $5$. Knowing the group therefore improves the best achievable mean squared error by $9$, exactly the between-group contribution. This is an interpretation relative to the information available: the remaining uncertainty could shrink further if additional information were revealed.

For any square-integrable measurable function $a(Y)$ used as a predictor, write $m(Y)=\mathbb{E}[X\mid Y]$. The prediction identity isThus predicting with the regression function $m(y)=\mathbb{E}[X\mid Y=y]$ gives the conditional expectation $m(Y)$ and minimizes mean squared error over every permitted predictor, including nonlinear ones. This minimizes average squared error, not the error for each individual outcome. See Berkeley Statistics 201A notes, sections 36–37.

Why do the two pieces add cleanly? Put $R=X-m(Y)$. Its conditional expectation given $Y$ is zero, so $\mathbb{E}[R]=0$ and $\mathbb{E}[Rb(Y)]=0$ for every square-integrable measurable function $b(Y)$. In particular, $R$ and $m(Y)$ are uncorrelated random variables. Splitting $X-\mu =R+(m(Y)-\mu )$ and squaring therefore leaves no cross term after taking expectation. Geometrically, the conditional expectation is an orthogonal projection in the L2 space, and the law of total variance is its Pythagorean theorem for centered random variables.

In our example, the four products $R(m(Y)-5)$ are $3,-3,-9,9$, which average to zero. Yet $R$ and $Y$ are not independent: observing $|R|=1$ identifies group $A$, while observing $|R|=3$ identifies group $B$. This is a concrete instance of heteroscedasticity, with different conditional variances despite zero conditional means of the errors. A group can predict uncertainty even when it cannot predict the error's sign.

The law of total variance is useful whenever aggregated data conceal distinct groups. Changing mixture weights changes both contributions, so the weighting must match the population being described. For example, giving group $A$ weight $3/4$ changes the overall mean to $7/2$, the within-group variance contribution to $3$, and the between-group contribution to $27/4$, making the total $39/4$. Group differences account for spread and prediction gains; assigning them a causal explanation requires a separate causal inference argument.

For a discrete random variable $X$ with a finite or countable alphabet and probability mass function $p_x=\mathbb{P}(X=x)$, define $p_{\max }={\max }_x{p}_x$. Its min-entropy, using base-two logarithms, isThe unit is the bit. This is the smallest information content of any possible outcome: it records the easiest outcome to predict, whereas Shannon entropy averages information content over all outcomes. A normalized countable probability mass function has an attained positive maximum, so $H_{\infty }(X)$ is finite even when Shannon entropy is infinite. Outcomes of zero probability cannot minimize the surprise and are omitted from the minimum; including extra impossible symbols changes neither quantity.^[ref]

Suppose someone knows the probability mass function but receives no observation correlated with $X$, and must name exactly one outcome. Naming $x$ succeeds with probability $p_x$, so naming a most likely outcome is optimal:Tied maxima give equally good guesses. Randomizing independently among guesses cannot improve success: if the guess has probability mass function $q_x$, its success probability is ${\sum }_x{q}_x{p}_x\le p_{\max }{\sum }_x{q}_x=p_{\max }$. This is the simplest instance of maximum a posteriori decoding. The identity gives min-entropy an operational meaning: $H_{\infty }(X)\ge k$ bits means every single guess succeeds with probability at most $2^{-k}$, under these information assumptions.^[ref]

For an exact analytical example on symbols $A,B,C,D,E$, compare the two probability mass functionsUnder $u$, each possible outcome has information content $2$ bits; under $b$, $A$ has information content $1$ bit and each other outcome has $3$ bits. Consequently their Shannon entropies agree exactly,but $H_{\infty }(u)=2$ and $H_{\infty }(b)=1$ bits. A best single guess therefore succeeds with probability $1/4$ under $u$ and $1/2$ under $b$. The same average surprise can hide a factor of two in immediate predictability. The zero entry in $u$ contributes zero to Shannon entropy, using $0{\log }_{2}0=0$.

For the discrete uniform distribution on $m$ possible outcomes, $H_{\infty }={\log }_{2}m$ bits and the best single guess succeeds with probability $1/m$. A certain outcome has $H_{\infty }=0$ and success probability one. Thus min-entropy is useful when a common outcome could defeat an attempt to make outputs unpredictable, even if rare alternatives raise Shannon entropy.

For cryptography, this unconditional calculation alone does not certify security: an observer might know $X$ already. If a report $Y=X$ reveals a uniform four-outcome source, its unconditional min-entropy remains $2$ bits but guessing after the report succeeds with probability one. For finite classical reports, the appropriate success calculation uses conditional probabilities and maximum a posteriori decoding:The conditional entropy $H(X\mid Y)$ instead averages remaining surprise. A security argument must specify the observer's information and the protocol's required guarantee; neither unconditional min-entropy nor Shannon entropy supplies those assumptions.

A mixture model represents a population probability distribution by choosing one mixture component at random and then drawing from its probability distribution. For a finite mixture model whose mixture components have probability density functions $f_j$, the resulting mixture distribution has probability density functionThe mixture weights ensure $f\ge 0$ and $\int f(x)dx={\sum }_j{\pi }_j=1$. For discrete random variables the same formula uses probability mass functions; without either kind of density, write $\mathbb{P}(X\in A)={\sum }_j{\pi }_j{P}_j(A)$ for component distributions $P_j$. A zero mixture weight makes that mixture component inactive.^[ref]

The mixture components need not occupy disjoint bins of $x$. Two normal distributions both have positive probability density functions everywhere, so the same value can plausibly come from either mixture component. The Two-Gaussian mixture example makes this overlap visible, and its mixture responsibilities quantify the remaining uncertainty about the latent variable. This is useful when a single normal distribution cannot represent the population's shape, but a fitted mixture model alone does not establish that its mixture components are real biological or social groups.

For finite discrete random variables, mutual information is the reduction of information entropy provided by observing the other variable:The last expression makes the symmetry $I(X;Y)=I(Y;X)$ visible. It is nonnegative and is zero exactly when $X$ and $Y$ are independent random variables. One way to see both facts iswhere $D$ is the Kullback-Leibler divergence with base-two logarithms. The Gibbs inequality gives nonnegativity; equality means that the joint probability distribution factors. The statement extends to more general distributions via relative entropy, but differences of infinite information entropies must not be used as if they were finite numbers.

A binary symmetric channel gives a useful example. Let $X$ be a fair bit, let $N$ be an independent Bernoulli random variable with error probability $q$, and set $Y=X\oplus N$, where $\oplus$ is exclusive or. The output is also a fair bit, but knowing the input leaves just the error uncertainty:Here $h_2$ is binary entropy. At $q=0.1$, $h_2(q)\approx 0.469$, so the output carries about $0.531$ bits of mutual information about the input per use. This is an average uncertainty reduction, not a claim that each observed symbol can be divided into fractional physical bits.

At $q=1/2$, every output is equally likely for either input, so $I(X;Y)=0$. At $q=1$, the output is always the inverted input: knowing this rule lets the receiver recover the input exactly, so $I(X;Y)=1$ again. A high raw error rate need not mean low mutual information when the errors are predictable. For this particular channel the fair input is optimal, giving the binary symmetric channel capacity $1-h_2(q)$.

Mutual information detects dependence that ordinary correlation can miss. Let $X$ be uniform on $\{-1,0,1\}$ and $Y=X^2$. Symmetry gives $\mathbb{E}[X]=\mathbb{E}[XY]=0$, hence zero covariance and zero correlation, while $Y$ is completely determined by $X$. Thus $I(X;Y)=H(Y)=h_2(1/3)>0$. This distinction is useful whenever a relationship is nonlinear: knowing one variable can reveal another without a linear trend.