Probability inequality

Probability inequalities bound event probabilities using moments or other tractable quantities.

For a random variable $Z$ and exponents $0<r<s$, the absolute moment norms satisfy $(\mathbb{E}|Z{|}^r{)}^{1/r}\le (\mathbb{E}|Z{|}^s{)}^{1/s}$, allowing infinity. For a finite $s$th moment, apply the Jensen inequality to the concave function $t^{r/s}$ and $|Z{|}^s$. The formula is for positive exponents; $r=0$ requires a separately defined limiting quantity.

For a random variable $X$ of finite variance and $a>0$,

For a finite-variance random variable, shift its centred version by $b>0$ and apply Markov inequality to the square. Minimizing $({\sigma }^2+b^2)/(a+b{)}^2$ at $b={\sigma }^2/a$ proves the bound. A two-point distribution attains equality. If the variance is zero, the centred variable vanishes almost surely.

For a nonnegative integer-valued random variable $N$, Markov inequality givesConsequently, $\mathbb{E}N<1$ proves that some outcome has $N=0$, while $\mathbb{E}N\to 0$ shows that $N=0$ with probability tending to one.

For a nonnegative random variable $N$, Chebyshev's inequality givesHence $\mathrm{var}(N)/(\mathbb{E}N{)}^2\to 0$ implies that $N>0$ with probability tending to one.

For a nonnegative random variable $Y$ and $a>0$,

Applying Markov's inequality to $e^{tX}$ givesOptimizing this expression is the basic Chernoff-bound method.

A concentration inequality bounds the probability that a random variable differs substantially from a typical value such as its expected value or median.

For an event $A$ in a product of finitely many probability spaces with its product measure, take the closed convex hull of the mismatch vectors $(1_{x_i\ne y_i}{)}_i$, $y\in A$. The distance of this hull from zero is $d_T(x,A)$. Equivalently it is the supremum, over nonnegative coordinate weights of squared sum at most one, of their minimum mismatch sum. Averaging mismatch patterns is the feature that distinguishes this quantity from ordinary Hamming distance.

On a finite product of standard probability spaces, for any measurable event $A$ of positive probability,Consequently $\mathbb{P}(A)\mathbb{P}(d_T(X,A)\ge s)\le e^{-s^2/4}$. Here $d_T$ is the Talagrand convex distance. The distance-event conclusion can be read with outer probability when necessary.

For a nonnegative integrable random variable $Z$, the entropy functional isIt is the unnormalized relative entropy of the measure with density proportional to $Z$ relative to the original probability measure.

If independent random variables satisfy $a_i\le X_i\le b_i$, thenwith the same bound for the lower tail.

If $a\le X\le b$ almost surely, then

If independent centered random variables satisfy $X_i\le b$ and ${\sum }_i\mathbb{E}{X}_i^2\le v$, then

For a binomial distribution with $p_n\to 0$ and $n{p}_n\to \infty$, the Bennett inequality at $C$ standard deviations tends to $2e^{-C^2/2}$, whereas the Hoeffding inequality tends to two. The raw Bennett inequality bound is eventually smaller for any fixed $C>0$; after clipping at one it is nontrivial in the limit only when $C>\sqrt{2\log 2}$.

The Bennett rate function has Taylor expansion $\varphi (u)=u^2/2-u^3/6+O(u^4)$ near zero. It is the optimized exponent in the Chernoff bound based on the moment-generating function estimate for the Bennett inequality.

A probability distribution $\mu$ has Poincaré constant $C_P$ when every sufficiently regular $f$ satisfies

For standard Gaussian measure $\gamma$, the sharp Poincaré constant is one:

If each probability measure ${\mu }_i$ has Poincaré constant $C_i$, then the product measure ${⨂}_i{\mu }_i$ has Poincaré constant at most ${\max }_i{C}_i$. This follows by iterating the law of total variance and applying Jensen inequality to derivatives of conditional expectations.

If $\mu$ has Poincaré constant $C$ and $\varphi$ is $L$-Lipschitz, then the pushforward measure ${\varphi }_{\ast }\mu$ has Poincaré constant at most $C{L}^2$. Apply the original inequality to $g\circ \varphi$ and use the chain rule.

For the uniform distribution on $[0,1]$,The constant $1/{\pi }^2$ is sharp and is the mean-zero Poincare-Wirtinger inequality on the interval.

For standard Gaussian measure $\gamma$,

For bounded smooth positive $h$ bounded away from zero, differentiation and Gaussian integration by parts give the displayed identity. The Ornstein-Uhlenbeck gradient commutation identity and weighted Cauchy-Schwarz inequality bound its right side by $e^{-2t}\int |h^{\prime }{|}^2/hd\gamma$. Integrating and setting $h=f^2$ proves the Gaussian logarithmic Sobolev inequality. Positive clipped approximation extends it to functions of finite Gaussian Dirichlet energy.

For independent random variables supported on $[0,1]$ and a differentiable convex function $f$,

For every $\lambda >0$, Markov inequality applied to $e^{\lambda X}$ givesOptimizing over $\lambda$ gives the Chernoff bound in terms of the moment-generating function of $X$.

For a $d\times p$ matrix of independent standard normal entries and $0<t<1$, diagonal entries of $A^{T}A/d-I$ have two-sided tails bounded by $2e^{-d{t}^2/8}$, while off-diagonal entries have tails bounded by $2e^{-d{t}^2/4}$. A union bound over $p$ diagonal entries and $p(p-1)/2$ distinct off-diagonal entries controls their common entrywise maximum norm.

A function $f(x_1,\dots ,x_n)$ has bounded differences with constants $c_i$ when changing only $x_i$ changes its value by at most $c_i$.

If $X_1,\dots ,X_n$ are independent random variables and $f$ has bounded differences constants $c_i$, thenand the same bound holds for the lower tail.

If a function of independent coordinates has one-sided squared-difference proxy at most $v$, Talagrand's one-sided inequality gives a Gaussian lower-tail bound $\mathbb{P}(Z-\mathbb{E}Z\le -t)\le e^{-t^2/(2v)}$. Applied to the negative of a concave function, it gives the corresponding upper-tail bound.

An integer-valued function $f$ is $g$-certifiable when every input $x$ with $f(x)=k$ has a set of at most $g(k)$ coordinates whose values alone guarantee that $f\ge k$.

Talagrand's product-space inequality gives sub-Gaussian-type concentration for a bounded-differences, certifiable function, with a variance scale controlled by the certificate size.

The entropy method combines a coordinatewise certificate with tensorization of entropy to bound the moment-generating function of a certifiable random quantity and hence its tails.

A nonnegative function $f$ of independent coordinates is self-bounding when there are coordinate-deleted versions $f_i$ such that $0\le f-f_i\le 1$ andThese inequalities make the natural variance proxy no larger than the function itself.

A nonnegative function $f$ is weakly self-bounding when coordinate-deleted functions $f_i$ satisfy $f_i\le f$ andThe squared coordinate sensitivity is then controlled by the observed value of the function itself.

For a weakly self-bounding function $Z=f(X_1,\dots ,X_n)$ of independent random variables, the coordinatewise variance inequality giveswhere $Z_i=f_i(X^{(i)})$.

The entropy method givesfor $\lambda \ge 0$. Consequently the Chernoff bound yields $\mathbb{P}(Z-\mathbb{E}Z\le -t)\le \exp [-t^2/(2\mathbb{E}Z)]$.

For a nonnegative function $Z$ of independent random variables, entropy is at most the sum of its conditional coordinate entropies. This tensorization is a basic step of the entropy method.

If $Z=f(X_1,\dots ,X_n)$ for independent coordinates and $Z_i^{\prime }$ replaces $X_i$ by an independent copy, then

For independent coordinates $X_1,\dots ,X_n$ and square-integrable $f$,For Bernoulli coordinates, each conditional variance is an explicit squared coordinate difference.

A modified logarithmic Sobolev inequality bounds the entropy of $e^{\lambda Z}$ by a one-sided coordinate-difference energy. For independent coordinates and arbitrary coordinate-deleted functions $f_i$, tensorization givesIf that energy is at most $v$, one common normalization is

The Herbst argument integrates a logarithmic Sobolev bound on $\lambda H^{\prime }(\lambda )-H(\lambda )$ to control the centered cumulant-generating function $H$, then applies a Chernoff bound to obtain concentration.

A transport-entropy inequality controls an optimal expected transportation cost between probability distributions by their Kullback-Leibler divergence.

If each coordinate law satisfies the same convex transport-entropy inequality, then the product law satisfies the sum-cost version. Sequentially couple conditional coordinates, apply Jensen inequality, and use the chain rule for relative entropy.

A centered random variable $X$ is sub-Poisson in the right tail with variance parameter ${\sigma }^2$ whenfor every $\lambda \ge 0$.

A centered random variable $X$ is sub-Gamma in the right tail with variance parameter $v$ and scale parameter $c$ whenfor $0\le \lambda <c^{-1}$.

For independent centered variables $X_i\le b$ and $v={\sum }_i\mathbb{E}{X}_i^2$,

Suppose independent centered sub-exponential random variables satisfy $\log \mathbb{E}{e}^{\lambda X_i}\le v_i{\lambda }^2/(2(1-b|\lambda |))$ for $|\lambda |<1/b$, and put $v={\sum }_i{v}_i$. Independence adds the log moment-generating functions. The Chernoff bound with $\lambda =t/(v+bt)$ gives the displayed two-sided tail. If each variable has common scale $K$, one may take $v_i\le C{K}^2$ and $b\le CK$, giving $\mathbb{P}(|n^{-1}{\sum }_i{X}_i|>t)\le 2e^{-cn\min \{t^2/K^2,t/K\}}$. This form of Bernstein's inequality allows unbounded variables with factorial moment control, including the centered square of a sub-Gaussian random variable.

For independent centered variables and $p\ge 2$, the $p$th moment of their sum is bounded, up to a constant depending only on $p$, by the sum of their $p$th moments plus the $p/2$ power of their total variance.

The union bound says $P({\bigcup }_i{A}_i)\le {\sum }_{i}P(A_i)$.

The FKG inequality gives positive association under a log-supermodular probability measure on a finite distributive lattice.

This lattice condition on configuration masses is the hypothesis of the FKG inequality. A product measure on a finite Boolean lattice satisfies it with equality, since in each coordinate the minimum and maximum retain the original two coordinate values. It implies positive association of random variables for increasing functions.

Increasing events under a product probability measure are positively associated: $\mathbb{P}(A\cap B)\ge \mathbb{P}(A)\mathbb{P}(B)$.

For two increasing events of equal probability $a$ under a product measure, positive association of their complements gives $1-P(A\cup B)\ge (1-a{)}^2$. Hence $a\ge 1-\sqrt{1-P(A\cup B)}$. For $r$ equal-probability increasing events, the same reasoning gives $a\ge 1-(1-P({\bigcup }_j{A}_j){)}^{1/r}$.

If increasing events $A_1,\dots ,A_k$ have a common probability, applying the Harris-FKG inequality to their decreasing complements gives $\mathbb{P}(A_1)\ge 1-(1-\mathbb{P}({\bigcup }_i{A}_i){)}^{1/k}$.

Harris' inequality states that two increasing events under an independent Bernoulli product measure are positively correlated.

Under a product measure on a finite Boolean lattice, an increasing event $E$ and a decreasing event $G$ obey the displayed inequality. The complement $G^c$ is an increasing event, so Harris' inequality gives $\mathbb{P}(E\cap G^c)\ge \mathbb{P}(E)\mathbb{P}(G^c)$. Subtract from $\mathbb{P}(E)$ to obtain the result. This implication includes degenerate Bernoulli distribution parameters $0$ and $1$.

An event in a partially ordered configuration space is increasing when changing coordinates upward cannot make a configuration leave the event.

An event is decreasing when closing additional edges cannot destroy it. Its complement is an increasing event.

For increasing containment events $A_i$ in a Bernoulli product space, let $X={\sum }_i{1}_{A_i}$, $\mu =\mathbb{E}X$, andwhere the sum is ordered and dependency means overlapping coordinate supports. ThenIn particular it is at most $e^{-\mu /2}$ when $\Delta \le \mu$, and at most $e^{-{\mu }^2/(2\Delta )}$ when $\Delta \ge \mu$.

The Janson dependency sum adds $\mathbb{P}(A_i\cap A_j)$ over ordered pairs of distinct containment events whose coordinate supports overlap.

For containment-event indicators $I_1,\dots ,I_m$ in a Bernoulli product space,It follows by exposing the avoidance events in sequence, separating disjoint coordinate supports, and applying Harris' inequality to the remaining decreasing events.

For independent symmetric random variables in a normed vector space and partial sums $S_k$,