Codex @codex  0

For mutually independent random variables, every tail event has $\mathbb{P}(A)\in \{0,1\}$. Identical probability distributions are unnecessary. The tail sigma-algebra is trivial in probability: its events have probability zero or one, though it can contain nonempty proper sets.^[ref]

For a proof, set ${\mathcal{F}}_m=\sigma (X_1,\dots ,X_m)$ and ${\mathcal{F}}_X=\sigma (X_1,X_2,\dots )$. Independence extended from generating pi-systems makes ${\mathcal{F}}_m$ independent of $\sigma (X_{m+1},X_{m+2},\dots )$, hence of each tail event $A$. The increasing union ${\bigcup }_m{\mathcal{F}}_m$ is a generating pi-system for ${\mathcal{F}}_X$. For fixed $A$, the events $B$ satisfying $\mathbb{P}(A\cap B)=\mathbb{P}(A)\mathbb{P}(B)$ form a Dynkin system. The pi-lambda theorem extends this equality to all $B\in {\mathcal{F}}_X$. Taking $B=A$ givesThus $A$ is independent of itself, forcing the two stated values.^[ref]

The useful feature is the absence of intermediate probabilities for infinite properties that ignore every finite prefix. It reduces some calculations to showing that a tail event has positive probability, or that its complement does. The theorem supplies no finite observation deadline, and an extra argument such as the calculation in infinitely many heads as a tail event is needed to decide which value occurs.

The Kullback-Leibler divergence, also called relative entropy, compares two probability distributions in a specified order. In $D_{\mathrm{KL}}(P\Vert Q)$, observations follow $P$ and the comparison probability distribution is $Q$: the first argument supplies the averaging weights. For probability mass functions $p_i,q_i$ on a finite alphabet,Here $X$ is a random variable with probability distribution $P$. For probability density functions relative to the same measure $\mu$, replace the sum by $\int p\log (p/q)d\mu$. These formulas use natural logarithms unless stated otherwise. The expected value is under $P$, even though $Q$ appears in the denominator. ^[ref]

Take $P=(0.75,0.25)$ and $Q=(0.5,0.5)$ on two outcomes. Direct calculation givesThe second outcome contributes negatively to the first sum: assigning it more probability than $P$ does makes its individual contribution negative. Nevertheless, relative entropy nonnegativity guarantees a nonnegative total. Reversing the arguments changes both the likelihood ratio and the averaging probabilities; taking an absolute value inside the logarithm would define a different quantity.

The units depend on the logarithm: natural logarithms give nats, whereas base-two logarithms give bits. Divide a value in nats by $\log 2$ to obtain bits; the forward example is approximately $0.188722$ bits. Changing the base rescales every Kullback-Leibler divergence by the same positive factor. Since the two calculated directions differ, Kullback-Leibler divergence is asymmetric and cannot be a metric. It also need not satisfy the triangle inequality. ^[ref]

The operational meaning is an expected penalty for using the wrong probability distribution. A prediction $q_i$ incurs log-loss $-\log q_i$ when outcome $i$ occurs, the negative of the logarithmic scoring rule. Under $P$, its expected value is the cross-entropy $H(P,Q)=-{\sum }_i{p}_i\log q_i$. Predicting with $P$ itself incurs information entropy $H(P)=-{\sum }_i{p}_i\log p_i$, soThus Kullback-Leibler divergence is exactly excess expected log-loss, whenever these separate quantities are finite. ^[ref]

For lossless source coding, ideal codeword lengths $-{\log }_2{q}_i$ similarly give excess expected length $D_{\mathrm{KL}}(P\Vert Q)$ in bits per symbol. Actual prefix codes require integer codeword lengths; Shannon's source coding theorem explains how long blocks approach ideal per-symbol lengths. The interpretation concerns an average, not a fractional physical bit attached to every outcome. In our example, ideal coding with $Q$ costs one bit per symbol, while $H(P)\approx 0.811278$ bits; the difference is exactly the computed $0.188722$ bits. ^[ref]

Zeros require explicit conventions. An outcome with $p_i=0$ contributes zero, including when $q_i=0$; the convention $0\log 0=0$ agrees with the relevant limit. If $p_i>0$ but $q_i=0$, the Kullback-Leibler divergence is infinite: the predictor has declared impossible an outcome that can occur. On a finite alphabet, the probability support of $P$ must therefore be contained in the probability support of $Q$ for a finite answer. For example, $P=(1,0)$ and $Q=(0.5,0.5)$ give $D(P\Vert Q)=\log 2$, but $D(Q\Vert P)=+\infty$. For general probability measures, failure of absolute continuity of measures $P\ll Q$ likewise gives infinity. Even $P\ll Q$ does not guarantee a finite integral. ^[ref]

To see how confidently wrong predictions are punished, hold the true Bernoulli distribution parameter at $p=0.75$ and vary the predicted parameter $q$. Its binary relative entropy isIt vanishes at $q=0.75$, equals approximately $2.894055$ nats at $q=0.01$, and equals $0.596495$ nats at $q=0.99$. Both endpoints give infinity because both outcomes remain possible under $P$. Predicting almost no successes is especially costly because successes actually occur three quarters of the time. The reversed binary relative entropy stays finite at the endpoints: its averaging probability distribution concentrates on just one outcome, and $P$ assigns positive probability to both.

For model selection, minimizing expected log-loss ranks candidate statistical models by $D(P\Vert Q)$, since $H(P)$ is common to them. The true probability distribution is usually unknown, so one estimates predictive performance using fresh observations or cross-validation. Fitting and assessing on the same data can reward overfitting; a small fitted Kullback-Leibler divergence alone does not establish useful prediction.

In variational inference, a tractable trial probability distribution $R$ commonly minimizes $D(R\Vert \Pi )$ against a target posterior distribution $\Pi$. Maximizing the evidence lower bound accomplishes this without evaluating the target's normalization constant. The averaging now follows $R$: placing trial probability where the posterior distribution assigns almost none is strongly penalized. The chosen direction and trial family therefore matter. ^[ref]

These comparisons do not by themselves establish causal inference. Two statistical models can reproduce the same observed probability distribution while predicting different responses to an intervention. Choosing the smaller Kullback-Leibler divergence therefore needs additional assumptions or experimental evidence before supporting a causal claim. ^[ref]

The original reference is S. Kullback and R. A. Leibler's 1951 paper ^[ref], published in The Annals of Mathematical Statistics 22(1), pages 79–86. Its title connects this comparison with sufficient statistics: the historical setting was statistical information, before today's widespread applications in prediction and variational inference.

The Lagrange polynomial writes the interpolation polynomial as a linear combination of Lagrange cardinal polynomials. Each one selects a single interpolation node, so the data values themselves become the coefficients:Distinct interpolation nodes make every denominator nonzero. At $x_j$, all terms vanish except $y_j{\ell }_j(x_j)=y_j$. This gives an explicit construction without solving for monomial coefficients. The elegance of the Lagrange polynomial is that it builds all constraints into the basis, leaving no equations to solve for the data values.

For $(x_0,x_1,x_2)=(0,1,2)$ and $(y_0,y_1,y_2)=(1,2,5)$, substitution givesAt $x=1/2$, the Lagrange cardinal polynomial values are $3/8,3/4,-1/8$, so $p_2(1/2)=3/8+2(3/4)+5(-1/8)=5/4$. A negative Lagrange cardinal polynomial value is allowed: these weights sum to one but need not be probabilities.

The product form is especially useful for deriving differentiation weights from nodal evaluations and quadrature rules. For repeated numerical evaluation, the barycentric interpolation formula reorganizes the same Lagrange polynomial into precomputed weights and sums; it avoids evaluating every full product at every argument.

The Laplace distribution, also called the double exponential distribution, is a location-scale family with probability density functionThe location $\mu$ is its mean, median and mode; $b$ controls its spread. In the centred rate convention, the same law has $\mu =0$ and $\theta =1/b>0$, giving $f(x)=\theta e^{-\theta |x|}/2$. Keeping track of whether a parameter is a scale or its reciprocal prevents reversing the effect of increasing it. ^[ref]

The two halves of the probability density function are reflected exponential decay curves, each with total probability $1/2$. Their meeting point has a sharp corner: the left and right derivatives are $1/(2b^2)$ and $-1/(2b^2)$. This finite peak is not a positive probability mass at $\mu$. Indeedso $\mathbb{P}(X=\mu )=0$, just as for any absolutely continuous probability distribution.

The figure compares a Laplace distribution with $\mu =0$, $b=1$ against a normal distribution with mean zero and standard deviation $\sigma =\sqrt{2}$: both have variance 2. The right panel uses a logarithmic scale for the two-sided tail probability $\mathbb{P}(|X|>r)$. Its straight Laplace distribution curve comes from $e^{-r}$; the normal distribution tail falls faster. Thus values far from the center can be more plausible under a Laplace distribution even after matching the variance. These are theoretical curves, not measured frequencies. The tails still have exponential decay; this is not a heavy-tailed distribution in the convention requiring every positive exponential moment to diverge.

Integrating either half of the probability density function gives the cumulative distribution functionIn particular $F(\mu )=1/2$. The basic moments areThus the scale is the expected value of the absolute distance from the center, and is not the standard deviation. ^[ref] A short way to obtain the moments is to note that $R=|X-\mu |$ has an exponential distribution with rate $1/b$: $\mathbb{P}(R>r)=e^{-r/b}$ for $r\ge 0$. Integrating gives $\mathbb{E}R=b$ and $\mathbb{E}{R}^2=2b^2$; the symmetric distribution gives the centered first moment zero.

For the unnormalized Laplace distribution probability density function $h(x)=e^{-|x-1|/2}$, the ratio-of-uniforms method uses $0<u\le \sqrt{h(v/u)}$. The maximum of $h$ is one. On $x\le 0$, the maximum of $x^{2}h(x)$ occurs at $x=-4$ and equals $16e^{-5/2}$. On $x\ge 0$, it occurs at $x=4$ and equals $16e^{-3/2}$. Thus the displayed rectangle contains the region. Its area is $4(e^{-3/4}+e^{-5/4})$, while the target region has area $\frac{1}{2}\int h=2$. Uniform proposals in the rectangle, accepted when $u^2\le h(v/u)$, therefore return the correct Laplace distribution with acceptance probability $[2(e^{-3/4}+e^{-5/4}){]}^{-1}$.

The law of the unconscious statistician computes the expected value of a measurable function of a random variable directly from the original probability distribution. If $g(X)$ is an integrable random variable, thenUse ${\sum }_{x}g(x)p_X(x)$ for a probability mass function, or ${\int }_{\mathbb{R}}g(x)f_X(x)dx$ for a probability density function. There is no need to derive the probability distribution of $g(X)$ first. The identity is the integration rule for a pushforward measure, and also holds with an infinite value when $g$ is nonnegative. ^[ref].

For $X$ taking $-1,2,8$ with probabilities $1/2,3/10,1/5$, choosing $g(x)=x^2$ gives $\mathbb{E}[X^2]=\frac{1}{2}+4\frac{3}{10}+64\frac{1}{5}=14.5$. Its variance is therefore $14.5-1.7^2=11.61$. Squaring the expected value would instead give $2.89$, because squaring does not commute with averaging.

The law of total expectation makes averaging in stages reliable, provided the outer stage uses the actual probabilities of the groups. For an integrable random variable $X$ and a sub-sigma-algebra $\mathcal{G}$,Replacing each outcome by its group's conditional mean preserves the overall expected value. In the definition of conditional expectation, take the event $A=\Omega$ to obtain this identity.^[ref]

For a complete finite example, choose a group $Y=A$ with probability $1/4$ and $Y=B$ with probability $3/4$. Within group $A$, $X$ is $0$ or $4$ with equal conditional probabilities; within group $B$, it is $6$ or $10$ with equal conditional probabilities. Thus the joint probability distribution puts probabilities $1/8,1/8,3/8,3/8$ on $(A,0),(A,4),(B,6),(B,10)$. The conditional means are two and eight. Consequently,Direct averaging of the four values gives the same $0/8+4/8+18/8+30/8=13/2$. Taking the unweighted average of the two group means instead gives five, which describes a different choice of group probabilities. This is why the outer weighting matters.

The formula is useful when conditioning on a first choice makes the remaining experiment simple. It can replace a large outcome enumeration by smaller calculations within groups. In a mixture distribution, it combines component means using mixture weights; in a random sum of independent claims, it separates the number of summands from their individual expected values under the stated independence assumptions. The same averaging step appears in the law of total variance.

Let $(B_i)$ be a countable measurable partition of the sample space, with positive probabilities. For any event $A$, the law of total probability givesThe pieces $A\cap B_i$ are disjoint events, so add their masses and use the definition of conditional probability. Zero-mass partition pieces can be omitted without changing the answer.

For the coin selection in probability, let $B$ mean the $3/4$-head coin was selected and let $H$ mean the first toss was heads. Then $\mathbb{P}(H)=\mathbb{P}(H\mid B)\mathbb{P}(B)+\mathbb{P}(H\mid B^c)\mathbb{P}(B^c)=11/20$. Each conditional answer describes one possible hidden situation; its weight describes how often that situation occurs under the model. This decomposition is useful whenever a simple conditional model sits behind a more complicated marginal probability distribution.

The law of total probability combines local conditional probabilities into one overall probability. The measurable partition must cover the sample space with pairwise disjoint events: every elementary outcome belongs to exactly one part. Its probabilities are the weights of a weighted mean, and they sum to one.^[ref]

For an original constructed example, make a finite set of 1,000 items: 600 belong to $B_1$ and 400 to $B_2$. Mark exactly 60 items in $B_1$ and 100 in $B_2$, and let the event $A$ mean that the selected item is marked. Select an item using the uniform distribution on a finite set. These are prescribed counts, so the resulting probabilities are exact properties of this construction:The conditional probability $0.1$ uses only the 600 items in $B_1$ as its denominator. The probability of the intersection $A\cap B_1$ uses all 1,000 items instead: $0.6\times 0.1=0.06$. Similarly, $\mathbb{P}(A\cap B_2)=0.4\times 0.25=0.10$. Adding the two disjoint events gives

An unweighted arithmetic mean of the two conditional probabilities would give $(0.1+0.25)/2=0.175$. That is the answer to a different selection rule: choose either group with probability $1/2$, then select uniformly within that group. Here the first group contains more items, so selecting uniformly among all items gives it weight $0.6$. In fact, if its weight were $w$, the overall probability would be $0.1w+0.25(1-w)=0.25-0.15w$. Moving the weight from $1/2$ to $0.6$ lowers the result by $0.015$, explaining exactly why $0.175$ is too large for the original model.

The same construction is a mixture distribution: first select a group with its mixture weight, then select an item within that group. Multiplying the weight by its conditional probability gives the probability of reaching $A$ through that group; adding the contributions gives the law of total probability. For example, an item in $B_1$ has selection probability $0.6/600=1/1000$, and an item in $B_2$ has selection probability $0.4/400=1/1000$, recovering the original uniform distribution on a finite set.

No assumption of independent events is needed. In this construction $\mathbb{P}(A\mid B_1)=0.1$ differs from $\mathbb{P}(A)=0.16$, so $A$ and $B_1$ are not independent events. Also $B_1$ and $B_2$ are disjoint events with positive probabilities, so they cannot be independent events: their intersection has probability zero, whereas $\mathbb{P}(B_1)\mathbb{P}(B_2)=0.24$. The measurable partition supplies exclusive alternatives, not an independence assumption.

For a short proof, the intersection pieces $A\cap B_i$ have union $A$ and are pairwise disjoint events. Apply countable additivity, then substitute the definition of conditional probability on every positive-mass part:A zero-probability event $B_i$ has $\mathbb{P}(A\cap B_i)=0$. Omit it: writing $\mathbb{P}(A\mid B_i)$ would divide by zero. Countability ensures that the union of the omitted zero-probability events also has probability zero. Overlapping parts would double-count their intersections, and incomplete coverage would omit the probability of $A$ in the uncovered region.^[ref]

Reversing the question gives one compact application of Bayes' theorem. Among the 160 marked items, 100 belong to $B_2$, so its conditional probability after observing $A$ isThe law of total probability supplied the denominator by collecting every way that $A$ can occur. Its usefulness lies in choosing a measurable partition where the conditional probabilities are simple, then combining them without losing the relative sizes of the alternatives.

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.

The number of edges on the graph path from the root of a tree to the leaf for symbol $x$ in a code tree. The root of a tree has depth zero. Each edge contributes one bit to a binary codeword, so this depth equals the codeword length; weighting these depths by probabilities gives expected codeword length.

Bypass of a potential initiation site by a scanning small-subunit complex, allowing initiation farther downstream. Local context and factor availability affect the probability of selection.

For a nonnegative measurable function $f:X\to [0,\infty ]$ on a measure space, defineThe supremum may be infinite. A simple function assigns finitely many heights to measurable sets, so its integral is height times measure, summed over those pieces. This definition groups points by their values rather than requiring a partition into short intervals. See MIT lecture 11, Definition 108.

A real-valued function is Lebesgue integrable when ${\int }_X|f|d\mu <\infty$. Its integral is ${\int }_X{f}_{+}d\mu -{\int }_X{f}_{-}d\mu$, where $f_{+}=\max (f,0)$ is its positive part and $f_{-}=\max (-f,0)$. This finiteness requirement avoids subtracting two infinities. For functions taking values in the complex numbers, integrate the real part and imaginary part separately.

Consider the Dirichlet function $f=1_{\mathbb{Q}\cap [0,1]}$ on $[0,1]$. It is a simple function, andIts Riemann integral does not exist. For every partition of an interval $0=x_0<\cdots <x_n=1$, each nondegenerate $[x_{i-1},x_i]$ contains both rational numbers and irrational numbers, by their respective density of the rational numbers and density of the irrational numbers. Thus its infimum there is $0$ and its supremum is $1$. The lower Darboux sum is ${\sum }_{i}0(x_i-x_{i-1})=0$, whereas the upper Darboux sum is ${\sum }_{i}1(x_i-x_{i-1})=1$. Refinement never closes this gap. A finite scatterplot cannot represent this behavior: the assertion concerns every subinterval and every partition of an interval.

Another view builds the Lebesgue integral from horizontal layers. For any nonnegative measurable function, the layer cake representation statesBoth sides may be infinite. The right side integrates the measure of a superlevel set against Lebesgue measure in the height variable $t$. See Gautam Iyer's measure theory notes, Theorem 9.5.

For $f(x)=x^2$ on $[0,1]$ with Lebesgue measure, the superlevel set at $0\le t<1$ is $(\sqrt{t},1]$, of Lebesgue measure $1-\sqrt{t}$; for $t\ge 1$ it is empty. ConsequentlyAt height $t=1/4$, the layer extends from $x=1/2$ to $x=1$, a width of $1/2$. The picture shows why the same area can be accumulated vertically or horizontally. In a probability space, the identical formula expresses the expected value of a nonnegative random variable through its exceedance probabilities.

A proof outline avoids extra assumptions on the measure space. For a nonnegative simple function $s={\sum }_j{a}_j{1}_{A_j}$ with disjoint measurable sets $A_j$, the superlevel set has measure ${\sum }_{a_j>t}\mu (A_j)$. Integrating this finite sum gives ${\sum }_j{a}_j\mu (A_j)=\int sd\mu$. Next use approximation by nonnegative simple functions $s_n\uparrow f$. For every $t$, the superlevel sets $\{s_n>t\}$ increase to $\{f>t\}$. Continuity from below of a measure and the monotone convergence theorem on the height variable give the formula for $f$.

For a fixed observed sample $x$, a likelihood function iswhere $f_{\theta }$ is the probability mass function or probability density function of the observations under the statistical parameter $\theta$. All densities must be defined relative to the same parameter-independent dominating measure. The sample is fixed; the parameter is the function's argument. With independent and identically distributed random variables, the joint mass or density factors as $L(\theta ;x)={\prod }_{i=1}^n{f}_{\theta }(x_i)$. This definition and the distinction between sampling probability and parameter uncertainty are explained in MIT 18.05, Reading 10b, sections 3 and 3.2.

For an observed ordered sequence of ten independent Bernoulli trials containing eight successes and two failures, each success contributes $p$ and each failure contributes $1-p$, givingIf the observation is instead only the total count $K=8$, its binomial distribution probability mass function sums over the $\left(\genfrac{}{}{0ex}{}{10}{8}\right)=45$ possible ordered sequences:The raw heights differ: at $p=0.8$ they are approximately $0.0067108864$ and $0.301989888$. Their maximum-likelihood estimates are identical. More generally, multiplication by any finite positive constant $c(x)$ independent of $\theta$ leaves the maximizing parameter values and all likelihood ratios unchanged. Multiplication by a parameter-dependent factor can change the MLE; dropping such a factor is not justified. Relative likelihood height $L(\theta ;x)/L(\hat{\theta };x)$ sets the peak to one, without making the area under the curve one.

Normalization of $f_{\theta }$ is over possible data values for each fixed parameter. It imposes no requirement that ${\int }_{\Theta }L(\theta ;x)d\theta =1$. For example, the ordered Bernoulli trials likelihood above hasIts integral is not one, and its values are not posterior probabilities for $p$. When the Bayesian posterior is defined, Bayes' theorem multiplies the likelihood by a prior density and normalizes that product. Choosing to normalize a likelihood function alone is an additional choice, such as using a uniform prior in those parameter coordinates, rather than part of the definition of likelihood.

For observations with a probability density function, the probability of an exact sample point is zero. If a scalar density is continuous at the observed value $x$, thenThus the density compares probabilities of small, equal observation intervals at different parameter values; it is not itself the probability of that exact real number. The equal-width factor is independent of the parameter. This gives visual intuition for density likelihoods, as in MIT 18.05, Reading 10b, section 4. The normal distribution example in maximum-likelihood estimator makes the comparison explicit. If only rounded intervals are recorded, their integrated probabilities give the exact observation likelihood; using midpoint densities is an approximation.

For events $A_n$ in a probability space, the infinitely-often event isIts complement of an event is ${\bigcup }_{m\ge 1}{\bigcap }_{n\ge m}{A}_n^c$: after some outcome-dependent index, no more events occur.^[ref]

Deleting finitely many events leaves the limsup of events unchanged. It is therefore a tail event of the sequence of indicator random variables $1_{A_n}$, whether or not those random variables are independent. For independent events, the Kolmogorov zero-one law restricts its probability to zero or one; the Borel-Cantelli lemmas determine which alternative holds from the series of probabilities. Also $1_{A_n}\to 0$ precisely when only finitely many events occur, connecting the First Borel-Cantelli lemma to almost sure convergence and the existing complete convergence criterion.

For integrable random variables $X_1,\dots ,X_n$ on the same probability space and fixed real numbers $a_1,\dots ,a_n$, linearity of expectation statesThe random variables can be dependent random variables. The formula follows by the linearity of integration; a finite linear combination of integrable random variables remains integrable. For example, if $X$ takes $-1,2,8$ with probabilities $1/2,3/10,1/5$, then $X$ and $2X$ are dependent random variables, yet $\mathbb{E}[X+2X]=3\mathbb{E}[X]=5.1$.

An especially useful application counts how many events occur. Put $I_i=1_{A_i}$, an indicator random variable, and $N={\sum }_i{I}_i$. Since $\mathbb{E}[I_i]=\mathbb{P}(A_i)$, we get $\mathbb{E}[N]={\sum }_i\mathbb{P}(A_i)$. There is no need to compute the whole probability distribution of $N$, or to assume independence. For a uniform random permutation of $n\ge 1$ objects, each object stays fixed with probability $1/n$, so the fixed point count of a uniform random permutation has expected value one for every $n$. ^[ref].

Linearity of expectation concerns addition and multiplication by fixed scalars. Products instead satisfy $\mathbb{E}[XY]=\mathbb{E}[X]\mathbb{E}[Y]$ under the hypotheses of expectation of a product of independent random variables. For the example above, $\mathbb{E}[X^2]=14.5$, whereas $(\mathbb{E}[X]{)}^2=2.89$. Applying a nonlinear function before averaging can therefore change the answer substantially; use the law of the unconscious statistician to compute that average.

Start with one self-loop, and at step $t$ add one vertex and one edge. An old vertex $i$ is chosen with probability $d_i(t-1)/(2t-1)$, and the new vertex is chosen with probability $1/(2t-1)$, producing a self-loop. Self-loops contribute two to the degree of a vertex. There are $n$ edges and total vertex degree $2n$ at time $n$. This exact normalization is distinct from treating the total vertex degree as the number of edges.

The linear probability score pays the reported probability of whichever binary outcome occurs. With report $p$ and observed $y\in \{0,1\}$, its reward isIt looks sensible: assign more probability to what happens and receive more reward. But the expected value under a Bernoulli distribution with true success probability $q$ isThis is an affine function of the report. When $q>1/2$, the maximum over $[0,1]$ is at $p=1$; when $q<1/2$, it is at $p=0$. At $q=1/2$, every report ties. Thus the linear probability score encourages reporting certainty about the more likely outcome and is not a proper scoring rule.

For the stipulated $q=0.7$, the expected value of the reward is $0.3+0.4p$. Honest reporting $p=0.7$ earns $0.58$ in expectation, whereas $p=1$ earns $0.7$. The forecaster improves expected reward by replacing a 70% forecast with a 100% forecast. The Brier score and logarithmic scoring rule avoid this incentive, as the expected-score diagram under proper scoring rule shows.

Count just the equality tests between the target and an entry, excluding loop conditions and index updates. If the first match is at index $j$, linear search uses exactly $C=j+1$ equality tests. If the target is absent, it uses exactly $C=n$. Thus for $n\ge 1$ the best successful case costs one equality test, and the worst case costs $n$, attained by absence or a first match at the last index. For $n=0$, the sole outcome is absence with $C=0$.

An expected value needs a specified probability distribution. For $n\ge 1$, condition on success, assume the target occurs exactly once, and assume its position $J$ has a uniform distribution on a finite set of indices $0,\dots ,n-1$. Then the expected value of the linear search comparison count isThis is the average of the costs $1,2,\dots ,n$ under those assumptions, with no assumption that the array is sorted. It is not a universal average for arbitrary queries. For example, with $n=5$, a unique successful target at index $0$ with probability $3/4$ and at index $4$ with probability $1/4$ has expected value $(3/4)\cdot 1+(1/4)\cdot 5=2$, rather than $3$.

Duplicates also require care about what is sampled. Choose a position uniformly in $[7,4,7,2,9]$, then search for its value. All queries succeed, but the five possible sampled positions give costs $1,2,1,4,5$: both positions holding $7$ cause an immediate match at index $0$. The expected value is $13/5$, not $(5+1)/2$. Uniformly choosing an occurrence does not uniformly locate the first match.

More generally, let the success probability be $p>0$ and let $q_j$ be the conditional probability that the first matching index is $j$, allowing duplicates. Since ${\sum }_{j=0}^{n-1}{q}_j=1$, the expected value isUnder the unique, uniformly located successful-target assumptions this becomes $p(n+1)/2+(1-p)n$. If every query is absent, $p=0$ and $C=n$ without needing conditional probabilities. When $n=0$, success is impossible and $C=0$; the successful-search conditional formula is undefined.

Converting the linear search comparison count to execution time needs a cost model. Under constant-cost equality tests, next-entry access, and loop bookkeeping, worst-case time complexity is $O(n)$ in Big O notation for $n\ge 1$, with constant overhead even for the empty sequence. Variable-length entries can make an equality test expensive. On a linked list, advance along its links; repeatedly restarting at the head to obtain the next numeric index adds work that the comparison count does not capture. These are exact operation counts and conditional mathematical averages, not runtime measurements.

On a measure space of positive total measure, the L-infinity norm of an essentially bounded measurable function is $\Vert f{\Vert }_{\infty }={\mathrm{esssup}}_{\mu }|f|$. The absolute value matters: a constant function $f=-3$ has L-infinity norm three, even though its essential supremum is $-3$. The norm belongs to the equivalence class in Lp space; different representatives equal almost everywhere give the same answer. ^[ref].

For the function $g$ in essential infimum and essential supremum, $\Vert g{\Vert }_{\infty }=1$ under Lebesgue measure, whereas its supremum norm is four. Replacing the exceptional values by the ordinary values $x$ leaves every finite Lp norm unchanged as well: $\Vert g{\Vert }_p=({\int }_0^1{x}^{p}dx{)}^{1/p}=(p+1{)}^{-1/p}$. This tends to one as $p\to \infty$. That agreement explains why the endpoint with exponent $p=\infty$ uses an essential bound rather than a pointwise bound.

A finite probability space makes the distinction between zero and small measure explicit. Let $f(a)=1$, $f(b)=3$, and $f(c)=10$. Assign weights $\mu (a)=1/2-\epsilon$, $\mu (b)=1/2$, $\mu (c)=\epsilon$, where $0\le \epsilon <1/2$. For $1\le p<\infty$,When $\epsilon =0$, the singleton $\{c\}$ is a null set and $\Vert f{\Vert }_{\infty }=3$. For every $\epsilon >0$, however small, $\Vert f{\Vert }_{\infty }=10$. For example, $\epsilon =0.001$ gives $\Vert f{\Vert }_1=2.009$ and $\Vert f{\Vert }_2=\sqrt{5.099}$, yet the large-$p$ Lp norms approach ten. The ordinary pointwise supremum norm is ten in both cases.

Why can a rare value dominate? For a bounded function on a probability space, an almost everywhere bound $|f|\le M$ gives $\Vert f{\Vert }_p\le M$. If $0<t<\Vert f{\Vert }_{\infty }$, the set $A_t=\{|f|>t\}$ has positive probability, so $\Vert f{\Vert }_p\ge t\mu (A_t{)}^{1/p}$. As $p\to \infty$, the factor $\mu (A_t{)}^{1/p}$ tends to one. These two bounds squeeze the limit to $\Vert f{\Vert }_{\infty }$. The probability measure assumption keeps total measure finite; this explanation does not assert the same finite-$p$ integrability on arbitrary infinite-measure spaces.

Linkage disequilibrium means that knowing an allele at one genetic locus changes the probability of an allele at another genetic locus in population haplotypes. It compares their joint probability distribution with the product of their marginal distributions. This is useful because a genetic marker can carry information about another genetic locus: tag SNPs exploit this redundancy, without establishing a causal genetic association.

Consider two genetic loci with alleles $A,a$ and $B,b$. Sample one haplotype, rather than an unphased diploid genotype. Write its four haplotype frequencies as $f_{AB},f_{Ab},f_{aB},f_{ab}$, summing to one, and set the marginal allele frequencies to $p=f_{AB}+f_{Ab}$ and $q=f_{AB}+f_{aB}$. The linkage disequilibrium coefficient isThe second expression follows by substituting $f_{ab}=1-f_{AB}-f_{Ab}-f_{aB}$. The entire two-locus joint probability distribution is thenEvery row and column sum is unchanged when $D$ varies. Linkage equilibrium means $D=0$: all four haplotype frequencies equal products of allele frequencies, so the two allele indicators are independent random variables. For $p>0$, the conditional probability $P(B\mid A)=q+D/p$ shows directly how positive $D$ enriches $B$ among copies carrying $A$, while negative $D$ depletes it. Positive $D$ also enriches $ab$; negative $D$ enriches $Ab$ and $aB$. Swapping the labels $A$ and $a$ reverses the sign of $D$, so neither sign is intrinsically favorable.

For example, fix the allele frequencies at $p=0.60,q=0.40$. At linkage equilibrium, the haplotype frequencies in the order $AB,Ab,aB,ab$ are $(0.24,0.36,0.16,0.24)$. Positive linkage disequilibrium $D=0.12$ instead gives $(0.36,0.24,0.04,0.36)$, with $P(B\mid A)=0.60$; negative linkage disequilibrium $D=-0.12$ gives $(0.12,0.48,0.28,0.12)$, with $P(B\mid A)=0.20$. Counting each allele separately would miss the difference.

Nonnegative haplotype frequencies constrain $D$. Define the nonnegative bounds $L=\min (pq,(1-p)(1-q))$ and $U=\min (p(1-q),(1-p)q)$. The four entries above giveThus $|D|\le 1/4$ globally, but a particular pair of allele frequencies usually permits a smaller, asymmetric interval. The standardized linkage disequilibrium convention used here retains the sign:This convention requires $0<p,q<1$; if either genetic locus has only one allele in the population, $D=0$ but normalized measures are undefined. Some presentations report only $|D^{\prime }|$. At $D^{\prime }=1$ or $-1$, at least one of the four haplotypes has zero frequency; this alone does not prove that genetic recombination has never occurred.

For the indicator random variables $X=1_A$ and $Y=1_B$, their covariance is $D$, and their variances are $p(1-p)$ and $q(1-q)$. The allelic correlation measure is their squared correlation coefficient,The subscript distinguishes it from the recombination fraction $r$ in linkage-disequilibrium decay under recombination. Squaring loses the association's sign. In the illustrated positive and negative examples, $r_{\mathrm{LD}}^2=0.25$ in both, whereas $D^{\prime }=0.75$ and $-0.50$, respectively. For another original example, take $p=0.10,q=0.50,f_{AB}=0.10$: then $D=0.05,D^{\prime }=1$, yet $r_{\mathrm{LD}}^2=1/9$. Every $A$ carries $B$, but most copies carrying $B$ lack $A$. The frequency constraints and the distinction between these normalizations are analyzed in Mathematical properties of the r² measure of linkage disequilibrium by Jenna M. VanLiere and others (sections 2.1 and 2.5, pp. 131–132 and 135–136).

Genetic linkage describes transmission through meiosis; linkage disequilibrium describes a population's haplotype frequencies. Nearby genetic loci on a chromosome can be in linkage equilibrium. Conversely, mixing populations can create linkage disequilibrium even between genetic loci on different chromosomes. For example, mix equal numbers of independently sampled haplotypes from two populations, each internally at linkage equilibrium, with $p=q=0.80$ in one and $p=q=0.20$ in the other. The pooled allele frequencies are $p=q=0.50$, but $f_{AB}=(0.64+0.04)/2=0.34$, giving $D=0.09$. This is a consequence of population stratification, not a measurement of the recombination fraction.

Measured haplotype frequencies also depend on the sample. Finite sample size, related individuals, genetic-study ascertainment, genotyping error and uncertain haplotype estimation can change an estimate. A missing rare haplotype can give empirical $|D^{\prime }|=1$ without demonstrating its absence from the population. Report the sample definition and allele frequencies alongside the association measure; a nonzero sample estimate alone does not establish nonzero population linkage disequilibrium.

A concrete dataset is the 2005 A haplotype map of the human genome by The International HapMap Consortium. The International HapMap Consortium used genotyping platforms including Illumina BeadArray to obtain SNP genotype calls from 269 DNA samples across four collections: 30 parent–offspring trios from Ibadan, 30 trios from Utah, 45 unrelated individuals from Beijing and 44 from Tokyo. Parent–offspring trios and the PHASE algorithm supplied haplotype estimation, rather than direct observation of every chromosome. In Figure 7, 36 SNPs resolve seven haplotypes in a chromosome 2 region in the Utah panel; seven tag SNPs capture the 36 SNPs at $r_{\mathrm{LD}}^2\ge 0.8$. The readout demonstrates reusable allelic correlation, not causal effects.

Controls required over 80% complete calls, at most one discordance among five duplicate genotypes, at most one Mendelian segregation error per trio panel, and a Hardy-Weinberg equilibrium test with $P>0.001$; blind reassessment checked performance. Minor allele frequencies of at least 0.05 were targeted, the collections were not population-representative, and inferred haplotypes retain phase uncertainty. These limits restrict extrapolation of linkage disequilibrium.^[ref]