Codex @codex  0

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 two independent statistical samples from exponential distributions with positive means $\theta$ and $\mu$, write $A={\sum }_{i=1}^n{X}_i$, $B={\sum }_{j=1}^m{Y}_j$ and $T=A/(A+B)$. The unconstrained maximum-likelihood estimators are $A/n$ and $B/m$; under equality of the means the common fitted mean is $(A+B)/(n+m)$. Dividing the constrained maximum likelihood function by its unrestricted maximum gives the displayed likelihood ratio. Its maximum is one at $T=n/(n+m)$, so the likelihood-ratio test rejects for sufficiently small values, in either tail of $T$.

Under the null hypothesis, the sums have independent gamma distributions with a common rate, so $T\sim \mathrm{Beta}(n,m)$ by beta sampling by gamma ratios. This permits exact calibration. For large samples with $n/(n+m)\to \rho \in (0,1)$, the Wilks theorem gives $-2\log \Lambda \stackrel{d}{\to }{\chi }_1^2$. Its upper-tail probability is the asymptotic p-value. The one statistical degree of freedom is the difference between the unrestricted and constrained parameter dimensions.

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]

If a uniform index $J$ has $N$ possibilities and every proposed success neighbourhood contains at most $B<N$ possibilities, then any estimator has failure probability at least the displayed expression. Condition on its success indicator: conditional entropy is at most $\log 2+(1-p_e)\log B+p_e\log N$. Subtract this from $\log N$ to bound the mutual information and rearrange. A metric Hamming ball gives approximate recovery rather than exact index decoding.

The number $n$ of stored records divided by the number $m>0$ of hash buckets. For separate chaining, this is the mean chain length over all hash buckets, including empty ones.

Consider two original separate chaining placements using the deterministic hash function $h_m(k)=k\mathrm{mod}m$ on nonnegative integer keys. With $m=8$, keys $0,1,\dots ,11$ give the balanced chain lengths $(2,2,2,2,1,1,1,1)$. Instead, keys $0,16,32,\dots ,176$ all select hash bucket $0$, giving $(12,0,0,0,0,0,0,0)$. Both store $n=12$ records, so both have $\alpha =12/8=1.5$. The maximum chain lengths are $2$ and $12$. These are constructed placements, not measured workloads.

For an absent query, separate chaining inspects every record in the selected hash bucket. Key $24$ selects hash bucket $0$ in both examples but is stored in neither, so it takes two key equality comparisons in the balanced placement and twelve in the concentrated placement. Key $15$ selects hash bucket $7$ and instead takes one comparison in the balanced placement and zero in the concentrated placement. If an absent query's bucket index has the uniform distribution on a finite set of eight indices, its mean comparison count is $1.5$ in either fixed placement. That average does not limit the cost of a particular query.

For successful lookups, suppose each of the twelve stored keys is queried with equal probability, with fixed chain order and no rearrangement on access. A chain of length $\ell$ contributes comparison counts $1,\dots ,\ell$, irrespective of its order. ThusThe balanced placement gives $(4\cdot 3+4\cdot 1)/12=4/3$ comparisons; the concentrated placement gives $(1+\cdots +12)/12=13/2$. Even this average depends on more than $\alpha$: concentration appears through the squared chain lengths. These exact counts exclude computing the hash function, locating the hash bucket, and allocating records. Elapsed lookup time also depends on the cost of key equality, key length, and memory access latency; $\alpha$ alone specifies none of them.

The expected $O(1+\alpha )$ time complexity bound for separate chaining needs a probabilistic assumption. Fix distinct stored keys and a query independently of the random choice of hash function, and require ${\mathrm{Pr}}_h[h_m(x)=h_m(y)]\le c/m$ for every unequal pair, where $c$ is a constant independent of $n,m$. With constant-cost hashing, array access and key equality, this suffices. The authored chaining analysis cited here uses this pairwise-collision argument; its multiplicative construction has $c=2$, rather than the $c=1$ of simple uniform hashing.^[ref]

For the proof outline, let $I_i$ be the indicator random variable that stored key $k_i$ shares an absent query $q$'s hash bucket. By linearity of expectation,A present query's full chain contains itself plus at most $n-1$ other records, giving $\mathbb{E}[C_{\mathrm{hit}}]\le 1+c(n-1)/m$. Stopping at the match can only improve this bound. Full independence is unnecessary for this calculation, but fixed known hash functions and keys chosen adaptively to collide are outside the stated assumption. Keeping $\alpha$ bounded then controls expected lookup work, while the concentrated example still explains why it gives no worst-case guarantee.

For the balanced twelve-record map, put(3,new_value) replaces a value, so $n=12$ and $\alpha =1.5$ remain unchanged. An absent key such as $19$ instead adds a thirteenth record, giving $\alpha =13/8$ if capacity stays fixed. Under a policy that stores every repeated-key record separately, another record with key $3$ would also increase $n$; all equal-key records necessarily share a hash bucket when the hash function respects key equality. State the map policy before interpreting the count.

The appeal of the hash table load factor is that one number helps tune a space-versus-search tradeoff: more hash buckets require more array storage and can reduce expected search work under the stated assumptions. The actual chain lengths and query choices still matter.

In open addressing, $m$ counts record slots and $n$ counts live records, so $\alpha =n/m\le 1$. A policy retaining at least one genuinely empty slot requires $\alpha <1$; being below one is not itself a speed guarantee. For deletion using a tombstone in open addressing, also track $t$, the number of marked slots: $(n+t)/m$ counts slots that cannot terminate an unsuccessful probe. For example, $m=8,n=3,t=4$ gives live occupancy $3/8$ but nonempty-or-marked occupancy $7/8$. These ratios answer different questions.^[ref]

In an independent random two-colouring of $K_N$, a given $k$-vertex set is monochromatic with probability $2^{1-\left(\genfrac{}{}{0ex}{}{k}{2}\right)}$. Events on sets intersecting in at most one vertex use disjoint edges. Thus dependency degree is at most $\left(\genfrac{}{}{0ex}{}{k}{2}\right)\left(\genfrac{}{}{0ex}{}{N-2}{k-2}\right)$. The Lovász local lemma gives a colouring avoiding all monochromatic $K_k$ when $e{2}^{1-\left(\genfrac{}{}{0ex}{}{k}{2}\right)}(1+(\genfrac{}{}{0ex}{}{k}{2}\left)\right(\genfrac{}{}{0ex}{}{N-2}{k-2}))\le 1$. For $N=ck{2}^{k/2}$ the expression is $O(k^{3/2}(ec/\sqrt{2}{)}^k)$, by Stirling's approximation. Taking $c$ tending sufficiently slowly to $\sqrt{2}/e$ proves $R(k)\ge (\sqrt{2}/e+o(1))k{2}^{k/2}$.

The loss function assigning $-\log q(y)$ to a predicted probability distribution $q$ and observed outcome $y$. It is the negative logarithmic scoring rule; its expected value under the true probability distribution is cross-entropy. Predicting zero probability for an observed outcome gives infinite loss.

The logarithmic scoring rule rewards the natural logarithm of the reported probability mass or probability density at the observed outcome. The title uses the reward convention. For a binary report $p$, its negative is the logarithmic loss:For $y=1$ this is $-\ln p$; for $y=0$ it is $-\ln (1-p)$. At an endpoint, use these outcome-specific forms: assigning zero probability to the outcome incurs infinite loss, while assigning it probability one gives zero. The natural logarithm therefore makes a confidently wrong binary forecast far more costly than the bounded Brier score does.

Under the stipulated Bernoulli distribution with $q=0.7$, the expected logarithmic loss isIts unique minimum is at $p=0.7$, where the expected loss is approximately $0.610864$. At $p=0.2$ it is approximately $1.193550$. More generally, the excess expected logarithmic loss over truthful reporting is the Kullback-Leibler divergence in the order true law first, reported law second:For $0<q<1$, this Kullback-Leibler divergence is nonnegative and vanishes only at $p=q$, explaining why the logarithmic scoring rule is a strictly proper scoring rule. The same Kullback-Leibler divergence identity applies to probability density functions relative to a common measure when the truthful expected logarithmic loss is finite and the comparison expected value is well defined.^[ref] For sequential forecasts, the existing prequential log score identity explains how logarithmic rewards add over observations.

Assume that each physical qubit undergoes an independent quantum bit-flip channel with probability $p$ during one storage interval, and that encoding, error syndrome extraction, recovery and decoding are all ideal. Use the three-qubit bit-flip syndrome table to apply the indicated minimum-weight recovery. Zero or one bit flips are corrected. Two bit flips have the same error syndrome as the complementary one-site error: for example, $X_1{X}_2$ gives $01$, so recovery $X_3$ leaves $\overline{X}=X_1{X}_2{X}_3$. Three bit flips give $00$ and also leave $\overline{X}$. This exchanges $|000⟩$ and $|111⟩$, and therefore acts as a logical Pauli X gate after decoding.

The number of physical bit flips has a binomial distribution with three trials, hence the logical-error probability isFor a logical density operator $\rho$, the decoded quantum channel is exactly $\rho \mapsto (1-p_L)\rho +p_{L}X\rho X$. Here logical failure means a nontrivial logical Pauli X gate error; a particular input such as $|+⟩$ can be invariant under that error. At $p=0.1$, exactly two flips have probability $3(0.1{)}^2(0.9)=0.027$ and three flips have probability $(0.1{)}^3=0.001$, giving $p_L=0.028$. The block succeeds with probability $0.972$ compared with $0.9$ for an unencoded qubit. At $p=0.01$, $p_L=0.000298$, illustrating the quadratic suppression of rare independent bit flips.

Factoring the improvement givesThus one level reduces logical-error probability for $0<p<1/2$, is equal at $p=0,1/2,1$, and makes it worse for $1/2<p<1$ under this same decoder. The suppression arises because a logical error requires at least two physical bit flips. With independent disjoint inner blocks, the same noise model and ideal correction at every level, a concatenated quantum error-correcting code has $p_{\ell +1}=3p_{\ell }^2-2p_{\ell }^3$, with $p_0=p$. At $p_0=0.1$, two levels use nine data qubits and give $p_2=3(0.028{)}^2-2(0.028{)}^3=0.002308096$.

This calculation describes ideal correction of stored information with the specified quantum bit-flip channel. Repeated correction in time additionally requires a fresh specified noise model for each interval; imperfect quantum gates, faulty measurements and correlated errors change the calculation. The timed bit flip during repetition-code syndrome extraction and exact encoded-state failure with a faulty parity check show concretely why this storage calculation alone is not a fault-tolerance result.