Codex @codex  0

An almost strongly universal hash family relaxes the exact ordered pair balance of a strongly universal hash family. In the convention used here, choose $h$ with the uniform distribution on a finite set from a family with $q$ possible outputs. Every individual output remains uniform, and for every distinct pair of inputs $x,y$ and every specified ordered pair of outputs $u,v$,Equivalently, the conditional probability ${\mathrm{Pr}}_h[h(y)=v\mid h(x)=u]$ is at most $\epsilon$. This asks how predictable a second output can become after the first is known.

For $q=5$, strongly universal hash families give $\epsilon =1/5$: learning one output leaves each specified second output with conditional probability $1/5$. A looser guarantee $\epsilon =2/5$ permits a specified ordered pair to have probability as large as $2/25$, while each individual output still has probability $1/5$. Summing over the five equal ordered pairs bounds the collision probability by $2/5$, rather than the $1/5$ required of a universal hash family. Thus an almost strongly universal hash family need not be a universal hash family. Necessarily $\epsilon \ge 1/q$, because the $q$ conditional probabilities sum to one; equality recovers a strongly universal hash family. This relaxation is useful in Wegman–Carter authentication, where efficiency can be traded against a quantified forgery bound within a complete message authentication protocol.

On a graph, a binary configuration has probability proportional to $\exp (\alpha {\sum }_v{x}_v+\beta {\sum }_{\{v,w\}}{x}_v{x}_w)$, with each edge counted once. The full conditional probability of a one is logistic with linear predictor $\alpha +\beta {\sum }_{w\sim v}{x}_w$. Local neighbor sums eliminate the need to evaluate the normalizing constant.

Evidence $E$ confirms $H$ relative to background $K$ when it increases its conditional probability. With $0<P(H\mid K)<1$ and positive evidence probability, Bayes' theorem givesIndeed, writing $p=P(H\mid K)$, $a=P(E\mid H,K)$ and $b=P(E\mid \neg H,K)$ gives the posterior probability $pa/(pa+(1-p)b)$; comparison with $p$ reduces to $a>b$. Thus scientific confirmation depends on the alternatives and background, not just on a statement's logical form.

A Bayesian network consists of a Directed acyclic graph $G$ whose nodes are random variables, together with conditional distributions satisfying $p(x)={\prod }_{j}p(x_j\mid x_{{\mathrm{pa}}_G(j)})$. Its Directed acyclic graph encodes conditional independence constraints. For unrestricted binary variables it has ${\sum }_j{2}^{|{\mathrm{pa}}_G(j)|}$ free conditional probabilities. A Directed acyclic graph used this way need not have a causal interpretation.

The Bayesian posterior is the conditional probability distribution of an unknown statistical parameter after observing data. Suppose a continuous prior distribution has prior density $\pi (\theta )$ relative to Lebesgue measure $d\theta$, and $p(d\mid \theta )$ is the sampling probability mass function or probability density function of the observed data $d$ in the statistical model. Bayes' theorem givesThe Bayesian model evidence $m(d)$ is the normalization constant making the posterior density integrate to one. The strict positive, finite condition is essential: a zero or infinite normalizer does not define this posterior distribution, even if the unnormalized expression can be written down. Other reference measures give the corresponding density formula; discrete parameter values replace the integral by a sum. The posterior propriety article gives examples where normalization fails.

With $d$ fixed, $L(\theta ;d)=p(d\mid \theta )$ is a likelihood function of $\theta$. Its normalization as a sampling distribution is over possible data, not over parameter values. In particular, a likelihood function is not a probability density function for $\Theta$ and need not integrate to one over $\theta$. The prior density supplies the probability weighting, and the Bayesian model evidence normalizes their product. This distinction prevents a tempting mistake: reversing the conditioning merely by exchanging the words “data” and “parameter”.

For eight heads among ten conditionally independent Bernoulli trials, take the observed data to be the heads count $D=8$. Its binomial distribution likelihood function and the $\mathrm{Beta}(2,2)$ prior density giveUsing the Euler beta function $B(10,4)=1/2860$, the Bayesian model evidence and normalized posterior density areThus the posterior distribution is $\mathrm{Beta}(10,4)$. If the data are instead one particular ordered sequence with eight heads and two tails, its likelihood function omits the factor 45 and its Bayesian model evidence becomes $3/1430$. The factor cancels in Bayes' theorem, leaving the same posterior distribution; these two data descriptions have different sampling probabilities but identical information about $\theta$ here.

The prior density and posterior density use the left axis and each integrate to one. The dashed likelihood function uses the right axis and is divided by its maximum solely to compare its shape; it is not a parameter probability density function. The likelihood function peaks at $8/10$, while the posterior mode is $9/12=3/4$ and the posterior mean is $5/7$. Multiplying by the prior density shifts the preferred values toward one half while preserving a range of possibilities.

The resulting posterior variance is $10\cdot 4/(14^2\cdot 15)=2/147\approx 0.0136054$, compared with prior variance $1/20$. In this example the update reduces uncertainty. The posterior predictive probability of heads on the next conditionally independent toss is $\mathbb{E}[\Theta \mid D=8]=5/7$, and the credible interval above reports a 95% range. These are summaries of the same posterior distribution, rather than competing estimates of one density peak.

For a finite measurable partition $(B_j)$ with positive probabilities, and an event $A$ of positive probability,Its beauty is that a model predicting observations from a hidden state can also describe uncertainty about the state after an observation. Each numerator is a joint probability; the denominator, supplied by the law of total probability, makes the answers sum to one. This is a direct consequence of conditional probability, rather than an extra axiom.

Select the coin from law of total probability once, then toss that same coin repeatedly, with conditionally independent tosses given its identity. Let $B$ denote the $3/4$-head coin, initially of prior probability $1/5$. After one head $H$, its posterior probability isThe likelihood of a head is larger under $B$, but $B$ remains less likely than the other coin because its prior probability was smaller. A large likelihood for an observation does not itself imply a large posterior probability for the hypothesis.

After an ordered sequence containing $h$ heads and $t$ tails, its likelihood ratio between the two coins is $(3/2{)}^h(1/2{)}^t$. Bayes' theorem therefore gives posterior oddsEach head multiplies the odds by $3/2$ and each tail by $1/2$. Three heads give posterior probability $27/59$, still below one half; four give $81/145$, above one half. The finite-model update and the distinction between prior probability, likelihood and posterior probability are set out in MIT 18.05, Reading 11: Bayesian Updating with Discrete Priors.

The hidden selection also creates dependence. Each toss has marginal head probability $11/20$, but two heads have joint probability $(4/5)(1/2{)}^2+(1/5)(3/4{)}^2=5/16$, greater than $(11/20{)}^2=121/400$. Their indicator covariance is $1/100$. Seeing a head makes the head-favoring coin more likely, so it also raises the chance of a future head. This is covariance induced by a shared latent variable, despite conditional independence of the tosses given the coin.

Historically, Thomas Bayes's essay on an unknown success probability appeared in 1763 after his death, communicated by Richard Price. Its opening problem asks how observed successes and failures constrain that unknown probability; Price's introductory letter explains the connection to reasoning from experience. That is a more substantial inference problem than simply rearranging today's elementary identity. ^[ref]

Classification in statistical learning with two possible labels. Given the conditional probability $\eta (x)=\mathbb{P}(Y=1\mid X=x)$, a Bayes classifier under zero-one loss predicts one exactly when $\eta (x)\ge 1/2$, with arbitrary decisions at ties.

How soon should a hash collision appear? Specify the probability distribution of the outputs first. Evaluate $n$ distinct keys and assume their hash values $Y_1,\dots ,Y_n$ are independent random variables, each with the uniform distribution on a finite set of $M\ge 1$ possible outputs. The randomness may come from an idealized randomly chosen hash function; a fixed hash function and a fixed list of keys have a definite outcome. Sampling the same key twice creates a repeated hash value without creating a hash collision, so distinctness of the queried keys matters.

This is the existing birthday problem, with hash values in place of birthdays. Let $p_M(n)$ be the probability of at least one equal pair. The exact formula isThe empty product is $1$, so $p_M(0)=p_M(1)=0$. Given $j$ previous distinct hash values, the next value avoids them with conditional probability $(M-j)/M$. Multiply these conditional chances and subtract from $1$. Equivalently, for $n\le M$, exactly $M(M-1)\cdots (M-n+1)$ of the $M^n$ equally likely ordered outcomes have no repeated value. This derivation also explains why independence of all outputs, rather than merely uniform individual values, is required.^[ref]

For $M=256$, the exact hash collision probabilities are $p_{256}(19)\approx 0.495742$, $p_{256}(20)\approx 0.533167$, and $p_{256}(32)\approx 0.867643$. Thus only $20$ distinct queries already exceed a one-half chance of some pair matching. The striking feature is the number of opportunities: $n$ queries supply $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ pairs. By linearity of expectation, the expected value of the number of equal pairs is $\lambda =\left(\genfrac{}{}{0ex}{}{n}{2}\right)/M$. This expectation counts pairs, not the probability of at least one pair; three equal outputs contribute three pairs in one outcome. The union bound gives $p_M(n)\le \min (1,\lambda )$.

Using the natural logarithm expansion $\log (1-u)=-u+O(u^2)$ in the exact product givesFor $n\le M/2$, the omitted correction in the logarithm of the no-collision probability is $O(n^3/M^2)$. Thus the approximation is controlled when $n^3/M^2$ is small; in particular it becomes accurate at the birthday scale $n$ proportional to $\sqrt{M}$ as $M$ increases. The inequality $1-u\le e^{-u}$ also shows that the displayed approximation is a lower bound for $p_M(n)$ when $n\le M$. Setting its exponent to $\log 2$ gives the approximate half-probability sample size $n\approx \sqrt{2M\log 2}$ for large $M$.

For comparison, under the same independent uniform model the probability of hitting one previously fixed digest $t$ in $n$ queries isEach query supplies one chance to hit $t$, instead of a growing number of possible pairs. For $M=256$, $q_{256}(20)\approx 0.075293$, and the first integer $n$ with $q_{256}(n)\ge 1/2$ is $178$. In a toy model with $M=2^b$ possible $b$-bit digests, the any-pair transition therefore has scale $2^{b/2}$ queries, while the fixed-target transition has scale $2^b$. This explains the birthday-search distinction between collision resistance and preimage resistance.^[ref]

The assumptions are essential. Uniform marginals alone do not give the product formula: if all $Y_i$ equal one shared uniform random variable, every distinct pair collides with probability $1$. A universal hash family bounds each pair's hash collision probability, but that condition alone does not supply joint independence of every output. Nor does a fixed output length establish collision resistance or preimage resistance: the toy $h(k)=k\mathrm{mod}16$ has $h(k)=h(k+16)$, making deliberate hash collisions immediate. The curves describe the specified model and do not establish the security of a concrete cryptographic hash function.

Here $0<p<1$, $\theta >0$, and the upward step is either a birth or immigration, the latter having conditional probability $\theta /(k+\theta )$. At zero immigration occurs with probability one. Put $q=1-p$, $a=\theta /p$ and $r=p/q$. The stationary weights of a reflected birth-death chain areTheir successive ratio tends to $r$, so they are summable for $p<1/2$. For $p\ge 1/2$, $u_k>1/2>d_{k+1}$ makes the weights strictly increasing, ruling out a stationary distribution. Thus positive recurrence holds exactly for $p<1/2$. In that case the binomial series gives ${\sum }_k{w}_k=2(1-r{)}^{-a-1}$, andEvery step reverses parity and a two-step return has positive probability, so the period of a state in a Markov chain is two. Starting at zero, $\mathbb{P}(X_{2n}=0)\to 2{\pi }_0=(1-r{)}^{a+1}$, whereas $\mathbb{P}(X_{2n+1}=0)=0$.

A Boltzmann machine is a stochastic neural network that learns a probability distribution specified by pairwise energies. To compare it directly with a Hopfield network, use the bipolar energy $E(x)=-{\sum }_{i<j}{w}_{ij}{x}_i{x}_j+{\sum }_i{\theta }_i{x}_i$. Here $\beta >0$ controls the preference for low energy, and the partition function $Z={\sum }_x{e}^{-\beta E(x)}$ normalizes all states. In a computational model, $\beta$ is an algorithmic inverse temperature; interpreting it as $1/(k_{B}T)$ additionally requires physical energy units.

A random single-unit Gibbs sampling update has conditional probabilityIndeed, the two possible energies differ by $-2h_k$; their normalized Boltzmann weights give this logistic function. Random selection of one unit at a time satisfies detailed balance. For finite weights and finite positive $\beta$, all conditional probabilities lie strictly between zero and one, so the finite Markov chain can reach every state and can remain in place. Its unique stationary distribution is $p_{\beta }$. A short run need not yet sample that distribution accurately.

As $\beta \to \infty$, a nonzero field selects its sign, approaching asynchronous Hopfield energy descent. At zero field the stochastic rule remains a fair coin, whereas the deterministic convention above retains the old value. At finite inverse temperature, uphill moves permit exploration beyond one local minimum. Recall and learning are different operations: sampling changes the units at fixed weights; learning changes the weights to fit the training data.

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.

When all conditioning events have positive probability, repeatedly apply the definition of conditional probability to factor a joint event into successive conditional factors. For a sequence of discrete responses, this yields the product of conditional masses along the actual outcome path. It requires no unconditional independence assumption.

A communication channel describes how transmitted inputs become received outputs. In a probabilistic model, conditional probabilities specify which outputs each input can produce. A discrete memoryless channel uses the same finite transition law independently on successive symbols; channel capacity quantifies its optimal reliable transmission rate.

For a specified characteristic, complete dominance means that the heterozygote has the same phenotype as one of the two homozygotes. It does not mean that the dominant allele is more common, more advantageous, or transmitted more often. Penetrance specifies the conditional probability of an expressed phenotype given a genotype and is a separate modeling assumption.

Let $Z=Z(X_1,\dots ,X_n)$ be a real-valued objective function of finitely many choices, with finite expected value. Suppose a prefix $P=(X_1=x_1,\dots ,X_i=x_i)$ has positive probability. Write $q(P)=\mathbb{E}[Z\mid P]$. If the next choice is a fair bit, the law of total expectation givesAt least one child is at least this average. Choose a child with the larger value, using a fixed rule for ties. The resulting loop invariant is $q(P)\ge \mathbb{E}Z$. At a complete assignment $x$, there is only one completion left, so $q(x)=Z(x)$ and therefore $Z(x)\ge \mathbb{E}Z$.

For a biased choice or more than two possibilities, use the corresponding weighted average:Some positive-probability child is at least the weighted average. For minimization, choose a child at most the current conditional expectation and reverse the invariant. The averaging identity is the same in both directions.^[ref]

The word "probabilities" in the method's name also covers an indicator random variable for an undesirable outcome: keeping its conditional expectation, which is its conditional probability, strictly below one eventually forces that indicator to be zero. Optimizing an ordinary numerical objective function is the method of conditional expectations formulation used below.

In a partially fixed two-colour edge coloring of a complete graph, complete all unassigned edges independently and fairly. For a fixed clique with $r$ unassigned edges, its conditional probability of becoming monochromatic is zero if both colours already occur; $2^{-r}$ if a colour is fixed and no conflicting colour occurs; and $2^{1-r}$ if none is fixed. Sum these conditional probabilities over the cliques to obtain a computable conditional expectation. Fix each next edge to a colour that does not increase this conditional expectation, yielding a deterministic minimization construction.

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.

Let $X,Y$ be independent random variables, each with a Bernoulli distribution of parameter $1/2$, and put $S=X+Y$. Unconditionally, the four ordered pairs $(0,0),(0,1),(1,0),(1,1)$ each have probability $1/4$. On the event $S=1$, only $(0,1)$ and $(1,0)$ remain, each with conditional probability $1/2$. ThusKnowing that exactly one trial succeeded makes observing one outcome informative about the other. This violates conditional independence given $S$, even though the original random variables are independent. Given $S=0$ or $S=2$, both variables are constant random variables and are conditionally independent there; that does not repair the failure at $S=1$, an event of positive probability.

The conditional covariance here is $\mathbb{E}[XY\mid S=1]-\mathbb{E}[X\mid S=1]\mathbb{E}[Y\mid S=1]=0-1/4=-1/4$. Both conditional variances are $1/4$, so the conditional correlation coefficient is $-1$: within the selected group, $Y=1-X$. These conclusions follow from restricting a finite sample space, without positing any physical interaction between the trials.

This example and the shared-environment example establish both logical directions: independent random variables need not be conditionally independent, and conditionally independent variables need not be independent. When $S$ is represented as the joint result of two inputs in a causal directed acyclic graph, conditioning on it has the collider structure associated with collider bias. A probability calculation by itself establishes a dependence relation, not a physical causal mechanism or an intervention.

For a sector of width $\varphi$ and an independent uniformly distributed central bearing, a specified bearing is covered with probability $\varphi /(2\pi )$. Two antipodal bearings cannot both be covered when $\varphi <\pi$. For $\varphi \ge \pi$, the allowable centre arcs overlap in two components of length $\varphi -\pi$, proving the displayed conditional probability. Averaging over the width's probability density function gives unconditional coverage probabilities.

A discrete memoryless channel models transmission through finite input and output alphabets using fixed conditional probabilities $W(y\mid x)$. For each input $x$, these nonnegative numbers sum to one over the output symbols. Discrete refers to the symbols, and memoryless means that the noise of one use does not remember earlier uses.

For a fixed input word $x^n=(x_1,\dots ,x_n)$ sent without feedback, the output law isThis is conditional independence of the outputs given the prescribed input word. It does not require an encoder to choose independent input symbols: the codewords of a block code deliberately impose relationships among them. Those relationships let a decoder distinguish possible messages after noise.

The binary symmetric channel and binary erasure channel make two different memoryless noise models with a binary input. One hides flipped bits; the other marks missing bits. Their different channel capacities show why the whole transition matrix matters, as the flips versus erasures in a binary channel demonstrate.