Codex @codex  0

Harris' inequality states that, for a product measure on $\{0,1{\}}^n$ with independent Bernoulli random variables of parameters $p_i\in [0,1]$, increasing events $E,F$ satisfyIn particular, the uniform probability measure on the Boolean lattice gives $|E\cap F|\ge |E||F|/2^n$. We give a direct mathematical induction proof, so no stronger correlation theorem is assumed.

Prove more generally that $\mathbb{E}[fg]\ge \mathbb{E}[f]\mathbb{E}[g]$ for real coordinatewise increasing functions $f,g$ on the finite cube. For $n=0$ both are constant and equality holds. For the inductive step let $p=p_n$, and let $f_j,g_j$ be the restrictions obtained by setting the last coordinate equal to $j\in \{0,1\}$. Write $a_j=\mathbb{E}[f_j]$, $b_j=\mathbb{E}[g_j]$, using the product measure on the other coordinates. Monotonicity gives $a_0\le a_1$, $b_0\le b_1$. By the inductive hypothesis and conditional expectation,The nonnegative correction term also handles $p=0$ and $p=1$. Taking indicator functions $f=1_E$, $g=1_F$ proves Harris' inequality.

For later use, an increasing event $E$ and a decreasing event $G$ have negative correlation of increasing and decreasing events. The complement $G^c$ is an increasing event, so

For probability measures on $(\Omega ,\mathcal{F})$, absolute continuity of measures means preservation of null sets in one direction:Equivalently, by the Radon-Nikodym theorem, there is an $\mathcal{F}$-measurable Radon-Nikodym derivative $Z\ge 0$ with ${\mathbb{E}}_{\mathbb{P}}Z=1$ and $\tilde{\mathbb{P}}(A)={\mathbb{E}}_{\mathbb{P}}[Z{1}_A]$. The derivative may vanish, so absolute continuity of measures does not require equivalence of the two probability measures. In particular, the reverse null-set implication is not part of the definition.

The relevant fact is uniform convergence on compacts in probability under an absolutely continuous measure change. Write $Z=d\tilde{\mathbb{P}}/d\mathbb{P}$. For any event $E$ and $K>0$,The last term tends to zero as $K\to \infty$ because $Z$ is integrable. Consequently, $\mathbb{P}(E_n)\to 0$ implies $\tilde{\mathbb{P}}(E_n)\to 0$. Apply this to $E_n=\{{\sup }_{t\le T}|C_t^n-[M,N{]}_t|>\epsilon \}$ for each finite $T$ and $\epsilon >0$. The given dyadic sums therefore have the same uniform convergence on compacts in probability limit under the new probability measure.

This proves quadratic covariation under an absolutely continuous measure change:Taking $N=M$ proves the corresponding quadratic variation assertion directly; it has not been assumed. The ceiling in the printed sum includes one grid interval extending beyond $t$. This does not affect the limit: on $[0,T]$ the resulting extra product is bounded by the product of the two path oscillations on mesh $2^{-n}$, which tends to zero by uniform continuity on $[0,T+1]$.

The bracket under the new probability measure must be understood as the quadratic covariation of continuous semimartingales. Semimartingale stability under an absolutely continuous measure change ensures this class is preserved; the local martingale property need not be. For example, on a finite horizon, weighting Brownian motion by $\exp (\mu B_T-{\mu }^{2}T/2)$ makes $B_t-\mu t$ a Brownian motion by the Girsanov theorem, so $B$ has nonzero drift under the new measure even though its quadratic variation is still $t$. The PDF additionally assumes that $M,N$ remain local martingales under the new probability measure, so its bracket is also defined directly by the local martingale characterization.

Define a probability measure on the same full measurable space byThe Radon-Nikodym derivative is positive and has expectation one, so this is a probability measure and even equivalent to $\mathbb{P}$, in particular ${\mathbb{P}}^T\ll \mathbb{P}$. For $t\le T$ its density on ${\mathcal{F}}_t$ is $\mathbb{E}[Z_T\mid {\mathcal{F}}_t]=Z_t$.

The finite-horizon Girsanov theorem says that if $W$ is a Brownian motion and $\mathcal{E}(\int hdW)$ is a true martingale through $T$ defining the density, then $W_t-{\int }_0^t{h}_{s}ds$ is a Brownian motion under that density for $t\le T$. Here $h_s=\mu$, and the stochastic exponential is exactly $Z$. The previous part verifies the necessary martingale property; alternatively the Novikov condition is $e^{{\mu }^{2}T/2}<\infty$. Hence $B_t-\mu t$ is a standard Brownian motion on $[0,T]$ relative to the same filtration under ${\mathbb{P}}^T$.

Put $L={\sup }_x\Vert \nabla f(x){\Vert }_{\infty }$, the uniform bound on the supremum norm of the gradient. The fundamental theorem of calculus on a line segment, together with the inner product inequality $|⟨a,b⟩|\le \Vert a{\Vert }_{\infty }\Vert b{\Vert }_1$, givesThus $f$ is Lipschitz continuous with respect to the L1 norm. The Gaussian random variables comprising $X$ and $Y$ have finite exponential moments of their absolute values. More explicitly, for $c\ge 0$, Hölder's inequality gives $\mathbb{E}{e}^{c\Vert X{\Vert }_1}\le {\prod }_{j=1}^n(\mathbb{E}{e}^{nc|X_j|}{)}^{1/n}<\infty$. Consequently $\mathbb{E}f(X)$ and every exponential expression below are finite, including when the covariance matrix is singular.

Use the convex function $\Psi (v)=e^{\lambda |v|}$. Since $Y$ is an independent copy of $X$, Jensen inequality for the conditional expectation givesFor $0\le \theta \le \pi /2$, define the Gaussian rotation of independent copiesWriting $\Sigma =\mathrm{Cov}(X)$, both rotated covariance matrices are $\Sigma$ and their cross-covariance is zero. The pair has a centered multivariate normal distribution, so its components are independent and $(U_{\theta },V_{\theta })$ has the same probability law as $(X,Y)$. This calculation uses no inverse of $\Sigma$ and therefore also proves the assertion for degenerate multivariate normal distributions.

The path $\theta \mapsto U_{\theta }$ runs from $Y$ to $X$. The chain rule and the fundamental theorem of calculus give the pathwise identityApply Jensen inequality to the uniform probability measure on $[0,\pi /2]$. Then use Tonelli theorem and the Gaussian rotation of independent copies to obtainThis proves the Gaussian rotation interpolation inequality in the required form:The stated almost-sure domination now gives an exponential moment of an absolute standard normal variable bound. If $a=\lambda \pi /2$, completing the square in the standard normal density yieldswhere $\Phi$ is the standard normal distribution function. Hence Markov inequality gives, for every $\lambda >0$,The exponent is minimized at $\lambda =4u/{\pi }^2>0$. Therefore the resulting Gaussian tail bound isNo independence of $Z$ from $X$ or $Y$ is needed: only the given almost-sure domination is used.

The Mazur theorem states that the weak closure and norm closure of a convex set $C$ in a normed vector space coincide:Norm closure is contained in weak closure because the weak topology is coarser. Conversely, if $x\notin {\overline{C}}^{\Vert \cdot \Vert }$, the Hahn-Banach separation theorem provides a continuous real linear functional strictly separating $x$ from that closed convex set. In a complex space this is the real part of a continuous complex linear functional. A weak neighborhood of $x$ then misses $C$, so $x\notin {\overline{C}}^w$. This proves the equality. It also gives the usual Mazur lemma: if $x_n\rightharpoonup x$, then $x$ lies in the norm closure of the convex hull of each tail, so one can choose tail convex combinations $y_n$ with $\Vert y_n-x\Vert <1/n$.

Now let $K$ be a weakly compact set in a normed space $X$. Each $\phi \in X^{\ast }$ is bounded on $K$ because it is weakly continuous. The family $\{Jx:x\in K\}$ in $\mathcal{B}(X^{\ast },\mathbb{F})$, where $J$ is the canonical embedding into the bidual, is therefore pointwise bounded. The space $X^{\ast }$ is Banach even if $X$ is not. Apply the Uniform boundedness principle and use $\Vert Jx\Vert =\Vert x\Vert$ to obtainThis proves that a weakly compact set is norm bounded without assuming completeness of the original space.

For the real-valued dual and integral formulas that follow, take $X$ to be real, as in the PDF. In a complex space the norming formula uses real parts, and the integral identities use complex-valued functionals instead.

If the separable Banach space $X$ is nonzero, choose a norm-dense sequence $(u_n)$ in its unit sphere. By the Hahn-Banach theorem, choose ${\phi }_n\in X^{\ast }$ with $\Vert {\phi }_n\Vert =1$ and ${\phi }_n(u_n)=1$. For any unit vector $u$, arbitrarily close $u_n$ satisfyScaling gives the countable norming family identityFor $X=\{0\}$ use the constant sequence of zero functionals. If $f:\Omega \to X$ is norm-Borel measurable, every ${\phi }_n\circ f$ is measurable, so its countable supremum $\Vert f(\cdot )\Vert$ is measurable. Equivalently, this also follows directly from continuity of the norm.

For any $\phi \in X^{\ast }$, continuity makes $\phi \circ f$ measurable, andThus the assumed integrability of the norm implies scalar integrability, anddefines a bounded linear functional on $X^{\ast }$. Use the granted weak-star continuity of $T_f$. By the continuous dual of a weak-star topology, $T_f$ is evaluation at a vector of $X$. Indeed, continuity gives finitely many $x_1,\dots ,x_m$ and $\epsilon >0$ such that $|T_f(\phi )|<1$ whenever $|\phi (x_j)|<\epsilon$ for all $j$. Scaling shows that $T_f$ vanishes on the common kernel of these evaluations. It therefore factors through their finite-dimensional coordinate map, so $T_f(\phi )={\sum }_j{a}_j\phi (x_j)=\phi ({\sum }_j{a}_j{x}_j)$. The Hahn-Banach theorem makes this representing vector unique. HenceIn this separable setting the vector is the Bochner integral.

Return to a weakly compact set $K\subseteq X$ and its inclusion $f:K\to X$. For each fixed $a\in X$, the identity $\Vert x-a\Vert ={\sup }_n{\phi }_n(x-a)$ makes $x\mapsto \Vert x-a\Vert$ weakly Borel measurable. Norm balls are consequently weakly Borel measurable. Separability gives a countable base of such balls, so every norm-open set is weakly Borel measurable. This proves measurability of $f$, and establishes the equality of the weak and norm Borel sigma-algebras in a separable Banach space.

Put $M={\sup }_{x\in K}\Vert x\Vert <\infty$. For every finite signed Borel measure $\mu$ on $K$,For positive measures this is the integral in the question. For signed measures, the correct integrability condition uses the variation measure; define the integral by taking the difference of the positive and negative integrals. The printed $\Omega$ in this clause should be $K$, the domain of the inclusion.

The Riesz-Markov-Kakutani representation theorem now defines the bounded linear mapFor each $\phi \in X^{\ast }$ the restriction $\phi {|}_K$ is in $C(K)$, andThe right side is weak-star continuous in $\mu$. The defining property of the weak topology therefore proves that $T$ is weak-star-to-weak continuous, for arbitrary nets. For a Dirac measure, $\boxed{T({\delta }_x)=x}$.

If $K\ne \varnothing$, let $\mathcal{P}(K)$ be its regular probability measures. This is a weak-star closed subset of $B_{C(K{)}^{\ast }}$: its conditions are $\mu (1)=1$ and $\mu (g)\ge 0$ for every nonnegative $g\in C(K)$. It is compact by Banach-Alaoglu theorem. Thus $T(\mathcal{P}(K))$ is weakly compact and convex, and contains $K$ because it contains all $T({\delta }_x)$. It is weakly closed, hence norm closed, so it contains $C={\overline{\mathrm{conv}K}}^{\Vert \cdot \Vert }$. By Mazur theorem, $C$ is weakly closed. Therefore it is a closed subset of the weakly compact set $T(\mathcal{P}(K))$, provingThe empty case is immediate. In fact $T(\mathcal{P}(K))=C$: a barycenter of a measure on a Banach space outside $C$ would be strictly separated by a functional $\phi$, contradicting $\phi (T(\mu ))={\int }_K\phi d\mu \le {\sup }_K\phi$.

Let $P$ be the Markov kernel and $\mu$ its invariant probability measure. Using the conventiongeometric ergodicity means that there are $r\in (0,1)$ and a finite measurable state-dependent prefactor $M(x)$ such thatHere total variation distance is used, and the rate $r$ does not depend on $x$. The prefactor need not be uniformly bounded; that stronger property is uniform geometric ergodicity. For a deterministic starting state, this estimate must hold at that state. If the definition is made only $\mu$-almost everywhere, the subsequent assertions concern those starting states where the prefactor is finite. The reversible Markov chain assumption means $\mu (dx)P(x,dy)=\mu (dy)P(y,dx)$.

The geometric drift condition requires a measurable $V:\mathcal{X}\to [1,\infty )$, a small set $C$, constants $\lambda \in (0,1)$ and $b<\infty$, andSmallness means that for some $m\ge 1$, $\epsilon >0$, and probability measure $\nu$, $P^m(x,\cdot )\ge \epsilon \nu (\cdot )$ for every $x\in C$. With irreducibility and aperiodicity, this drift-minorisation condition implies geometric ergodicity. The function $V$ controls the chain away from the small set; inside that set the additive constant allows unrestricted bounded drift.

A probability measure $\mu$ is $T$-invariant whenEquivalently, the pushforward measure satisfies $T_{\ast }\mu =\mu$, so $T$ is a measure-preserving transformation.

Because $X=\mathbb{N}$ is a countable set and $\mu (X)=1$, some $x\in X$ satisfies $\mu (\{x\})>0$. Invariance and the inclusion $\{T^{n}x\}\subseteq T^{-1}\{T^{n+1}x\}$ giveIf the forward orbit contained infinitely many distinct points, their disjoint singletons would each have measure at least $\mu (\{x\})>0$, contradicting that $\mu$ is a probability measure. The orbit therefore eventually enters a finite periodic orbit $Y$.

Now $T(Y)=Y$, so $Y\subseteq T^{-1}Y$. Since $\mu$ is invariant,Thus $Y$ belongs to the invariant sigma-algebra modulo null sets. It has positive measure, so the fact that $T$ is an ergodic transformation forcesThis is the ergodic invariant probability on a countable state space has finite cyclic support.

The Kolmogorov axioms for a probability measure $\mathbb{P}$ are nonnegativity, normalization $\mathbb{P}(\Omega )=1$, and countable additivity on pairwise disjoint events. For $\mathbb{P}(B)>0$, conditional probability is defined byBecause the events $A\cap B_i$ are pairwise disjoint and their union is $A$, countable additivity gives the law of total probabilityFor any $j$ with $\mathbb{P}(A)>0$, the definition of conditional probability and this identity give Bayes' theorem:

Give $X\times Y$ the uniform probability measure and let $f$ be the indicator function of the edge set. For partitions $\mathcal{P}=\{X_i\}$ and $\mathcal{Q}=\{Y_j\}$, define the energyBecause conditional expectation is an orthogonal projection in L2 space, $0\le \mathcal{E}\le \Vert f{\Vert }_2^2\le 1$.

Suppose the pair of partitions is not $\epsilon$-regular. For each irregular $(X_i,Y_j)$ choose witnesses $A_{ij}\subseteq X_i$ and $B_{ij}\subseteq Y_j$ withRefine each $X_i$ by all sets $A_{ij}$ and each $Y_j$ by all sets $B_{ij}$. If the old partitions have $r,s$ cells, the refined ones have at most $r{2}^s,s{2}^r$ cells.

The Pythagorean theorem for the two nested conditional-expectation projections givesInside an irregular $X_i\times Y_j$, the witness rectangle occupies at least an ${\epsilon }^2$ proportion and the mean of the displayed difference over it has magnitude greater than $\epsilon$. The Cauchy-Schwarz inequality therefore gives an energy gain greater thanfrom that pair. Since irregular pairs have total weight greater than $\epsilon$, the complete refinement raises the energy by more than ${\epsilon }^5$.

Energy is at most one, so after at most $\lceil {\epsilon }^{-5}\rceil$ refinements the process stops at an $\epsilon$-regular pair of partitions. Iterating the cell-count bounds $r\mapsto r{2}^s$ and $s\mapsto s{2}^r$ from $r=s=1$ a bounded number of times produces a finite $K(\epsilon )$ independent of $G$. This proves the Bipartite Szemerédi regularity lemma.

For a cost $c:X\times Y\to [0,+\infty ]$ that is a Borel measurable function, a transport map is a measurable $T:X\to Y$ whose pushforward measure satisfiesThe Monge optimal transport problem moves every source point to one destination:The Kantorovich optimal transport problem permits mass to split. Its admissible transport plans are the probability measures on $X\times Y$ with prescribed marginal distributions:Thus a transport plan is a coupling of probability distributions. The set $\Pi (\mu ,\nu )$ is never empty: it contains the product measure $\mu \otimes \nu$. Signed costs can also be used when their integrals are well defined, for example with an integrable lower bound of the form $a(x)+b(y)$.

On the Polish space $\mathbb{R}$, take the Dirac measuresEvery measurable map satisfies $T_{\#}{\delta }_0={\delta }_{T(0)}$, which cannot equal $\nu$. A transport map cannot split an atom of a measure, whereas the transport plan $\frac{1}{2}{\delta }_{(0,-1)}+\frac{1}{2}{\delta }_{(0,1)}$ can.

For every admissible transport map $T$, the pushforward measure condition gives $T(x)\in [1,2]$ for $\mu$-almost every $x\in [0,1]$. Hence $|T(x)-x|=T(x)-x$, andApply the Jensen inequality to the convex function $h$ and the probability measure $\mu$:Translation by one sends the source uniform distribution to the target uniform distribution, so $T^{†}(x)=x+1$ is admissible. Its displacement is constantly one, givingNo monotonicity assumption on $h$ is needed, because all displacements have the same sign. The same argument with a transport plan also gives the identical minimum for the Kantorovich optimal transport problem.

The dual of the Kantorovich optimal transport problem iswhere the Kantorovich potentials are measurable representatives satisfyingOne standard form of the Kantorovich duality theorem assumes that $X,Y$ are Polish spaces, $\mu ,\nu$ are probability measures defined as Borel measures, and $c:X\times Y\to [0,+\infty ]$ is sequentially lower semicontinuous. ThenThe primal infimum is attained; its value may be $+\infty$. Nonnegativity can be replaced by a constant lower bound by shifting the cost. This duality for lower semicontinuous costs is also discussed in Beiglboeck, Leonard and Schachermayer's duality paper.

Equality of values does not by itself assert a dual maximum. A sufficient stronger setting for attainment on both sides is compact metric spaces $X,Y$ and a finite continuous cost $c$; then continuous Kantorovich potentials attain the dual supremum. The general statement above correctly uses a supremum.

The Kantorovich–Rubinstein theorem concerns a Polish space $(X,\rho )$ and probability measures $\mu ,\nu$ with finite first moments, meaning $\int \rho (x,x_0)d\mu (x)+\int \rho (x,x_0)d\nu (x)<\infty$ for one, hence every, $x_0\in X$. It statesHere $\mathrm{Lip}(f)\le 1$ means $|f(x)-f(y)|\le \rho (x,y)$ for every $x,y$. The Wasserstein distance with ground cost $\rho$ therefore equals a supremum over functions with Lipschitz constant at most one. One may normalize $f(x_0)=0$, since adding a constant does not change the difference of integrals. This normalization bounds $|f(x)|$ by $\rho (x,x_0)$, so finite first moments ensure integrability. The supremum is unchanged if an absolute value is placed around the difference, because $-f$ is admissible whenever $f$ is.