Codex @codex  0

A probability measure is invariant for a Markov process with transition semigroup $P_t$ when starting with that law gives the same law at every later time. Equivalently, $\int P_{t}fd\nu =\int fd\nu$ for every bounded measurable function. Invariant laws may be constructed by weak convergence of probability measures of evolved laws when the Feller semigroup property permits passing the semigroup through the limit, as for the extremal invariant measures of the contact process.

For a Boolean function $f:\{0,1{\}}^n\to \{0,1\}$ under the uniform probability measure, some coordinate has influence of a variable at least $c\mathrm{Var}(f)\log (n)/n$, where $c>0$ is an absolute constant and $I_i(f)$ is the probability that flipping coordinate $i$ changes $f$. For variance bounded below, this is order $\log (n)/n$. The tribes function shows that this order cannot be improved for general balanced Boolean functions.

For probability measures defined as Borel measures on Polish spaces and a nonnegative sequentially lower semicontinuous cost, the minimum cost over transport plans equals the supremum of $\int ud\mu +\int vd\nu$ over integrable Kantorovich potentials satisfying $u(x)+v(y)\le c(x,y)$. The primal minimum is attained; a dual maximum needs additional assumptions. Compact metric spaces and a finite continuous cost suffice for attainment of both extrema.

On a Polish space $(X,\rho )$, probability measures with finite first moments satisfyThe supremum runs over functions with Lipschitz constant at most one. Fixing $f(x_0)=0$ ensures integrability from the moment assumption.

For probability measures on ${\mathbb{R}}^d$ with finite second moments, a transport plan minimizes the quadratic cost exactly when it is concentrated on the graph of the subdifferential of a sequentially lower semicontinuous proper convex function.

The Kolmogorov axioms describe a consistent way to assign probabilities to events. Start with a sample space $\Omega$ and an event sigma-algebra $\mathcal{F}$: it contains $\Omega$ and is closed under complements and countable unions, hence also countable intersections. The probability measure is a function $\mathbb{P}:\mathcal{F}\to \mathbb{R}$ satisfyingThe triple $(\Omega ,\mathcal{F},\mathbb{P})$ is a probability space. The third axiom is countable additivity; the infinite series means the limit of a sequence of nonnegative partial sums. It applies to pairwise disjoint events, not to overlapping events and not to arbitrary uncountable unions.^[ref]

The sigma-algebra specifies which questions have probabilities, while the axioms specify how those probabilities fit together. For a finite sample space one can take the entire power set; a continuous model commonly uses a Borel sigma-algebra. Nonnegativity and normalization do not require equally likely outcomes or independence: those are additional modelling choices.

For an exact six-outcome model, take $\Omega =\{1,2,3,4,5,6\}$, $\mathcal{F}=\mathcal{P}(\Omega )$, and assign $\mathbb{P}(\{k\})=k/21$. The total is one because $1+2+3+4+5+6=21$. Define the probability of an event by summing the weights of its outcomes. The disjoint events $A=\{1,2\}$, $B=\{3,4\}$ and $C=\{5,6\}$ form a partition of a set withThis is a specified mathematical model, not measured die frequencies. The figure makes probability literal area: each region has the same height and a width proportional to its assigned mass. Regrouping disjoint events preserves their total area.

Several familiar rules are consequences, not further axioms. Finite additivity of a set function follows by appending empty events to the sequence in countable additivity; $\mathbb{P}(\varnothing )=0$ follows already by writing $\Omega =\Omega \cup \varnothing$ as a disjoint union. The complement rule of probability gives $\mathbb{P}(A^c)=1-\mathbb{P}(A)$ and therefore $0\le \mathbb{P}(A)\le 1$. Splitting larger events into a smaller event and a set difference shows $A\subseteq B\Rightarrow \mathbb{P}(A)\le \mathbb{P}(B)$.

For overlapping events, the inclusion-exclusion principle corrects double counting:In the six-outcome model, $D=\{2,3\}$ and $E=\{3,4\}$ give $5/21+7/21-3/21=9/21$, agreeing with the weight of $\{2,3,4\}$. This decomposition is useful because a complicated event can be assembled from simpler questions with known probabilities.

On a finite sample space, a family of pairwise disjoint events has only finitely many nonempty members, so finite additivity of a set function already handles every countable disjoint union. On an infinite sample space, the countable axiom additionally controls what is left beyond every finite stage. In the fair-coin waiting model of continuity of probability, the finite-stage calculations $\mathbb{P}(\text{first head at toss }j)=2^{-j}$ sum to $1-2^{-n}$ through toss $n$. Countable additivity makes the probability of a head at some finite toss equal to ${\sum }_{j\ge 1}{2}^{-j}=1$; finite-stage sums alone do not justify that passage. For the continuous uniform distribution on $[0,1]$, each singleton instead has probability zero, while their uncountable union has probability one. Countable, rather than unrestricted, additivity accommodates both models.

Historically, Kolmogorov's 1933 book Grundbegriffe der Wahrscheinlichkeitsrechnung established the influential axiomatic framework connecting probability theory with measure theory. The three conditions above are the modern presentation on a sigma-algebra. Shafer and Vovk's historical study explains that the original presentation began with finite additivity on an algebra of sets and added continuity for decreasing events with empty intersection, which supplies the countable extension.^[ref]

Consistent probability distributions on finite collections of coordinates in standard Borel spaces determine a unique probability measure on the product sigma-algebra. Consistency means that discarding coordinates by marginalization agrees with the law already assigned to the smaller collection, and relabeling coordinates relabels the law. The theorem turns finite recipes into a complete stochastic process. In particular, products of one fixed probability distribution construct an independent and identically distributed sequence; putting one common random variable in every coordinate constructs the perfectly shared process above. The theorem supplies a law on the coordinate space, but does not by itself ensure continuous sample paths.

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.

A Lévy family of graphs consists of finite connected graphs with their uniform probability measures and graph distances divided by their diameters, whose concentration of measure functions vanish at every fixed positive normalized radius. Equivalently, every family occupying at least half the vertices has a radius-$\lfloor \epsilon D_n\rfloor$ neighbourhood occupying a proportion tending to one, uniformly over such families. Harper theorem and binomial distribution tail bounds prove this for the hypercube graphs.

For integrable real-valued functions $f,g$ on a measure space $(X,\mu )$ and fixed real numbers $a,b$, their linear combination $af+bg$ is integrable, and the Lebesgue integral satisfiesThe same rule applies to any finite summation: ${\int }_X{\sum }_{j=1}^n{a}_j{f}_{j}d\mu ={\sum }_{j=1}^n{a}_j{\int }_X{f}_{j}d\mu$ for integrable functions $f_j$ and fixed scalars $a_j$. Finite signed values matter: integrability ensures all these integrals are finite, so no undefined $\infty -\infty$ occurs.

This is the distributive property of finite summation carried into integration: a fixed factor can be pulled out, and a finite sum can be integrated term by term. For simple functions, distribute the finite sums of value times measure; approximation extends additivity to nonnegative measurable functions, and splitting into a positive part and negative part gives the integrable signed case. See Lecture 12: Lebesgue Integrable Functions, the Lebesgue Integral and the Dominated Convergence Theorem (Proposition 122: linearity for integrable functions). For example, ${\int }_0^1(2x-3)dx=2{\int }_0^{1}xdx-3{\int }_0^{1}1dx=-2$. With a probability measure, linearity of integration gives linearity of expectation.

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.

For continuous functions $f,g$ on a compact metric space satisfying $f(x)+g(y)\le d(x,y)$, set $h(x)={\min }_y(d(x,y)-g(y))$. The triangle inequality makes $h$ $1$-Lipschitz, while the constraint gives $f\le h$ and evaluation at $y=x$ gives $g\le -h$. Thus the feasible pair $(h,-h)$ has at least as large an objective against any two probability measures. This explains why metric optimal transport duality reduces to a single $1$-Lipschitz function.

The Lyapunov moment inequality says that higher positive absolute moments give no smaller absolute moment sizes on a probability space. For a real random variable $Z$ and $0<r<s$,allowing an infinite value. For $r\ge 1$ the left expression is an Lp norm; below one it is a quasi-norm, so the usual triangle inequality terminology needs that distinction. The comparison uses a probability measure of total mass one; arbitrary unnormalized measure spaces need a factor depending on their total mass.

For a nonnegative count, the first moment size is its expected value, while the second is the square root of its second moment. Both ten-trial counts in second moment method have first moment size one. The independent count has second moment size $\sqrt{1.9}\approx 1.37840$, whereas the shared-outcome count $N=10B$ has second moment size $\sqrt{10}\approx 3.16228$. The second moment distinguishes models with the same average because its square increases the influence of rare large counts.

More generally, for $N=10B$ with a Bernoulli random variable $B$ of parameter $1/10$,It rises from one at $r=1$ toward ten as $r\to \infty$. Replacing $1/10$ by a parameter $0<q\le 1$ gives $10q^{1/r}$, which decreases toward zero for a fixed positive exponent when $q\downarrow 0$, making the rare-event and large-exponent limits different questions. For a scaled Rademacher random variable taking values $-2$ and two with equal probabilities, every absolute moment size is exactly two: increasing the exponent does not distinguish signs when the absolute value is constant.

For finite $\mathbb{E}|Z{|}^s$, apply the reversed Jensen's inequality to the strictly concave function $t^{r/s}$ and the nonnegative random variable $|Z{|}^s$:Taking the positive $r$th root proves the claim. Equality in this finite case holds exactly when $|Z|$ is constant almost surely. If the higher moment is infinite, the upper bound is infinite and remains valid. Exponent zero is excluded from the statement; logarithmic or geometric limiting summaries require separately stated conventions, especially when $Z$ can vanish.

A mean-zero function has expectation zero with respect to the specified probability measure. On a finite set with uniform measure this means ${\sum }_{x}f(x)=0$. A balanced subset indicator is an example. In Fourier analysis on a finite group, this is equivalent to vanishing of the component at the trivial representation.

The mean-zero L2 space is the kernel of the bounded linear functional $h\mapsto Ph$ on L2 space for a probability measure $P$. It is a closed subspace of a Hilbert space, with inner product $P(hk)$, and is the natural ambient space for score functions and canonical gradients.

A family of probability measures $K_y$ on a measurable space for which $y\mapsto K_y(A)$ is measurable for every measurable set $A$. This combines measurable dependence on a parameter with a probability measure at each parameter. The conditional measures of a factor form such a kernel, with the additional fiber-support property from disintegration.

A measure space is a set $X$, a sigma-algebra $\mathcal{M}$ of its subsets, and a measure $\mu$ defined on $\mathcal{M}$. Specifying only $X$ leaves both the measurable questions and their weights undetermined.

For a concrete probability space, take $X=\{a,b,c\}$, $\mathcal{M}$ its power set, and weights $1/2,1/3,1/6$. Define $\mu (A)$ by adding the weights of the elements in $A$. ThenA probability measure is exactly a measure normalized by $\mu (X)=1$, usually written $\mathbb{P}(\Omega )=1$. An indicator function has expected value equal to its event's probability. For a different continuous example, $[0,1]$ with the restricted Lebesgue measure is a probability space; the event $[0,1/4]$ has probability $1/4$.

Measure theory studies measures, which assign sizes to measurable sets, and the Lebesgue integral, which accumulates values weighted by those sizes. The same framework describes Lebesgue measure on the real numbers, counting measure on discrete collections, and probability measures on possible outcomes. The choice of measure determines what counts as large; the choice of sigma-algebra determines what can be measured.

A striking example separates size from proximity: the rational numbers in $[0,1]$ form a dense set with Lebesgue measure zero, although the whole interval has Lebesgue measure one. This distinction makes almost everywhere statements useful: exceptional null sets can be ignored in a Lebesgue integral even when they meet every open subinterval. The monotone convergence theorem and dominated convergence theorem then give precise conditions for passing a limit through an integral.

A historical starting point is Lebesgue's 1902 thesis, ^[ref]. Its title connects integration with the geometric task of assigning sizes.

For measurable functions $f,g$ with values in the real numbers or complex numbers on the same measure space $(X,\mathcal{A},\mu )$, and $1\le p\le \infty$, membership in the same Lp space givesThus adding two functions cannot make their combined Lp norm exceed the sum of their separate Lp norms. The measure need not be finite or a probability measure. The hypotheses require finite Lp norms; $p=\infty$ uses the essential supremum of the absolute value, not an ordinary pointwise supremum. For complex numbers, the absolute value is the complex modulus. As usual, Lp spaces identify functions equal almost everywhere. ^[ref]

The Minkowski inequality makes the Lp norm a workable notion of size: it supplies the triangle inequality needed to turn $d_p(f,g)=\Vert f-g{\Vert }_p$ into a metric on Lp space. Applied to $(f-h)+(h-g)$, it says that travelling through an intermediate function $h$ cannot shorten the direct distance measured by this metric. Applied to two error functions, it gives a bound on the total error even when the errors reinforce one another; Minkowski inequality for error aggregation gives explicit examples.

The geometry is already visible in the Euclidean plane. Under counting measure on two coordinates, the closed unit balls for the L1 norm, Euclidean norm, and L-infinity norm are respectively $|x|+|y|\le 1$, $x^2+y^2\le 1$, and $\max (|x|,|y|)\le 1$. Every one is a convex set: if $u,v$ have Lp norm at most one, the Minkowski inequality and absolute homogeneity of a norm give $\Vert tu+(1-t)v{\Vert }_p\le t+(1-t)=1$ for $0\le t\le 1$. The Euclidean norm has no flat boundary segments, whereas the other two norms do. This is the distinction captured by a strictly convex normed space and developed in equality in Minkowski inequality.

A short Hölder's inequality proof outline handles $1<p<\infty$. First $|f+g{|}^p\le 2^{p-1}(|f{|}^p+|g{|}^p)$, so $f+g$ has finite Lp norm before any division. With conjugate exponents $p$ and $q=p/(p-1)$, set $h=|f+g{|}^{p-1}$; then $\Vert h{\Vert }_q=\Vert f+g{\Vert }_p^{p-1}$. The scalar triangle inequality followed by Hölder's inequality givesDivide if $\Vert f+g{\Vert }_p>0$; otherwise the desired bound is immediate. For $p=1$, integrate $|f+g|\le |f|+|g|$. For $p=\infty$, the almost everywhere bounds $|f|\le \Vert f{\Vert }_{\infty }$ and $|g|\le \Vert g{\Vert }_{\infty }$ give the result by the essential supremum. The same scalar triangle inequality works for real numbers and complex numbers.

Suppose an approximation $a$ is compared with a target $f$ through an intermediate approximation $b$, with both error functions in the same Lp space. The identity $f-a=(f-b)+(b-a)$ and the Minkowski inequality combine two error budgets without any independence assumption. The L1 norm controls aggregate absolute error, the L2 norm controls the square root of aggregate quadratic loss, and the L-infinity norm controls the largest error almost everywhere. For equally weighted samples with the probability measure $1/n$ on each coordinate, the L2 norm is the root mean square error; the inequality still applies when this normalization is used consistently.

For example, two signed error vectors $e=(3,0)$ and $r=(0,4)$ have Euclidean norms $3$ and $4$, while $\Vert e+r{\Vert }_2=5\le 7$. Reinforcing errors $e=(3,0)$ and $r=(4,0)$ attain the bound $7$; opposing errors $e=(3,0)$ and $r=(-3,0)$ cancel completely. The Minkowski inequality always allows reinforcement. A smaller combined budget requires additional information about the errors, not just their separate norms.

Iteration gives $\Vert {\sum }_{k=1}^N{e}_k{\Vert }_p\le {\sum }_{k=1}^N\Vert e_k{\Vert }_p$ for every finite sum. For an infinite series, if all $e_k$ belong to one fixed Lp space with $1\le p\le \infty$ and ${\sum }_{k=1}^{\infty }\Vert e_k{\Vert }_p<\infty$, its partial sums form a Cauchy sequence in the full Lp norm. Completeness of this Banach space then gives norm convergence to an element of the same Lp space. A finite sum bound alone does not establish convergence, and completeness is an additional ingredient beyond the Minkowski inequality. ^[ref]