Codex @codex  0

For a function $f:[0,1]\to \mathbb{R}$ and an integer $n\ge 1$, its Bernstein polynomial isThe Bernstein basis supplies nonnegative weights whose sum is one. Equivalently, the weights are the probabilities of a binomial distribution, and the result is an expected value. At a given $x$, this averages the sampled values $f(k/n)$ with weights concentrated near $k/n=x$.^[ref]

The endpoints are exact: $B_{n}f(0)=f(0)$ and $B_{n}f(1)=f(1)$. Interior sampled points need not be interpolated. For example, binomial distribution moments give $B_n(x)=x$ and $B_n(x^2)=x^2+x(1-x)/n$. Thus every affine function is reproduced exactly, whereas $x^2$ is generally changed. Bernstein polynomial degree preservation is a statement about degree of a polynomial, not equality of the entire polynomial.

For a continuous $f$, the uniform continuity of $f$ and the variance $\mathrm{Var}(K/n)=x(1-x)/n\le 1/(4n)$ explain uniform convergence. Split the expected value of the error into $|K/n-x|<\delta$, where uniform continuity makes the change small, and its complement, whose probability is at most $1/(4n{\delta }^2)$ by Chebyshev's inequality. The bounded function $f$ bounds the remaining error. This proves convergence without assuming differentiability.

For $f\in C([0,1{]}^d)$, the tensor-product Bernstein polynomial is the expected value of $f(X_1/n,\dots ,X_d/n)$ for independent random variables $X_j\sim \mathrm{Bin}(n,x_j)$. The same uniform continuity and coordinatewise variance estimates give uniform convergence for each fixed finite $d$.

Unit-radius Brownian exit time has finite variance, since independent unit-time increments give an exponential upper tail. The Brownian exit-time skeleton clock after $2^{2n}$ radius-$2^{-n}$ exits has mean $\mathbb{E}{\sigma }_1$ and variance $2^{-2n}\mathrm{Var}({\sigma }_1)$. Chebyshev's inequality and the Borel-Cantelli first lemma yield the displayed pathwise convergence. Independence between different rows indexed by $n$ is unnecessary.

Cantelli's inequality uses a mean and variance to control deviations in one specified direction. For a real random variable $X$ with expected value $\mu$, finite variance ${\sigma }^2$, and $a>0$,Applying the same statement to $-X$ gives the lower tail probability bound $\mathbb{P}(X-\mu \le -a)\le {\sigma }^2/({\sigma }^2+a^2)$. No independence or particular probability distribution is required. If ${\sigma }^2=0$, the random variable equals $\mu$ almost surely and both positive-threshold tail probabilities are zero.

For variance one and a threshold two above the mean, the upper-tail probability is at most $1/5$. Applying the two-sided Chebyshev's inequality to contain that upper event would give the weaker bound $1/4$. For the standard normal distribution, the actual upper tail probability at two is about $0.0227501$, much smaller than either bound. Yet the two-point probability distribution in equality in Cantelli's inequality attains $1/5$, showing why the smaller Gaussian value cannot be promised from these two moments alone.

A short explanation is to centre $Y=X-\mu$ and choose a nonnegative shift $b$. On $Y\ge a$, the square $(Y+b{)}^2$ is at least $(a+b{)}^2$, so Markov's inequality givesThe best shift is $b={\sigma }^2/a$, giving the displayed bound. Choosing the shift before squaring exploits the direction of the deviation; squaring the unshifted random variable treats both directions together. This shifted-square proof is also the strategy requested in the University of Utah's 2005 qualifying problem on Cantelli's inequality. ^[ref].

The one-sided improvement should be used for a one-sided question. Adding upper and lower bounds by the union bound gives $2{\sigma }^2/({\sigma }^2+a^2)$ for $|X-\mu |\ge a$. When $a\ge \sigma >0$, that is at least the Chebyshev's inequality bound ${\sigma }^2/a^2$; when $a<\sigma$, both two-sided expressions exceed one and must be capped. The separate one-sided bounds generally cannot be attained simultaneously by the same probability distribution.

For a real random variable $X$ with finite variance ${\sigma }^2$, expected value $\mu$, and a threshold $a>0$, Chebyshev's inequality givesOne can also cap this upper bound at one, since a probability cannot exceed one. If $\sigma >0$, taking $a=k\sigma$ gives $\mathbb{P}(|X-\mu |\ge k\sigma )\le 1/k^2$. For example, at least $3/4$ of the probability lies strictly within two standard deviations of the mean. This statement needs only the finite variance assumption. If the variance is zero, $X=\mu$ almost surely and every positive deviation threshold has zero tail probability.

Consider a random variable uniformly distributed on $\{-2,-1,0,1,2\}$. Its expected value is zero and its variance is $(4+1+0+1+4)/5=2$. At $a=2$ the actual tail probability is $2/5$, while Chebyshev's inequality gives $2/2^2=1/2$. At $a=3$ the actual tail probability is zero, while the bound is $2/9$. A valid bound need not describe the exact shape or bounded support of a particular probability distribution.

For the standard normal distribution, the actual tail probabilities beyond two and three standard deviations are approximately $0.0455003$ and $0.0026998$, whereas the general bounds are $1/4$ and $1/9$. More knowledge of the probability distribution can therefore improve the estimate. The comparison does not diminish the guarantee: the three-point example in equality in Chebyshev's inequality attains it exactly.

The proof is a one-line use of Markov's inequality on the nonnegative random variable $Y=(X-\mu {)}^2$. The event $|X-\mu |\ge a$ equals $Y\ge a^2$, and $\mathbb{E}Y={\sigma }^2$. This explains why the denominator is squared and why a finite variance supplies the necessary information. ^[ref].

One important use is control of a sample mean. For independent and identically distributed random variables with finite variance ${\sigma }^2$, the variance of a sample mean is ${\sigma }^2/n$. HenceFor every fixed tolerance, the bound tends to zero as the sample size grows, proving the finite-variance case of the weak law of large numbers. For ${\sigma }^2=1$ and $\epsilon =0.1$, $n=2000$ makes the bound $0.05$. This is a sufficient bound under the stated assumptions, rather than an optimal required sample size.

An early historical source is Pafnuty Chebyshev's 1867 paper “Des valeurs moyennes”, published in French translation by N. de Khanikof. Its opening theorem bounds deviations of sums using their expected values and second moments, linking averages with control of exceptional outcomes. ^[ref].

An unbiased coefficient estimator with known variance $v$ gives a conservative level-$\alpha$ test of a zero coefficient by rejecting when its absolute value is at least $\sqrt{v/\alpha }$. Chebyshev's inequality bounds the null rejection probability by $\alpha$. This test needs the variance assumptions but no Gaussian error distribution; a normal-reference test requires additional distributional justification.

Equip the Boolean hypercube with uniform probability measure and graph distance divided by its graph diameter. These spaces form a Lévy family of graphs. The vertex-isoperimetric inequality in the discrete cube reduces the complement of a positive-density set's radius-$\epsilon n$ graph neighbourhood to a binomial distribution tail. For fixed density $\delta >0$, Chebyshev's inequality puts a lower density quantile at least $n/2-C_{\delta }\sqrt{n}-O(1)$. After enlarging by $\epsilon n$, the omitted mass is at most $n/[4(\epsilon n-C_{\delta }\sqrt{n}-O(1){)}^2]$, which tends to zero.

For $n$ balls in $n$ uniformly and independently chosen boxes, put $p_n=(1-1/n{)}^n$. The empty-box indicators in uniform allocation have negative pairwise covariance, so $\mathrm{var}(K_n)\le n{p}_n(1-p_n)\le n/4$. Chebyshev's inequality givesSince $p_n\to e^{-1}$, this proves the displayed convergence in probability. The centring and the negative covariance are essential to this short proof; an expectation limit alone would not establish concentration.

Assume in addition that the probability space is a metric space, continuous integrable functions are dense in $L^1$, and the diameters of its partition cells tend to zero at each point. For a continuous $g$, the oscillation average tends to zero because every point in $M_k(x)$ is within its diameter of $x$. For $h=f-g$, the upper limit of the oscillation of $f$ is bounded by the partition maximal function of $h$ plus $|h(x)|$. The first-crossing maximal inequality for refining partitions and Chebyshev's inequality bound the measure where this exceeds $2\epsilon$ by $2\Vert h{\Vert }_1/\epsilon$. Approximation proves the displayed almost everywhere assertion. Refinement supplies the maximal estimate; shrinking diameter supplies the approximation argument. Without shrinking diameter, a constant partition generally converges only to its cell averages.

The Efron–Stein inequality bounds the variance of a complicated output by the effect of replacing one input at a time. Let $X_1,\dots ,X_n$ be mutually independent random variables, not necessarily identically distributed, and $Z=f(X_1,\dots ,X_n)$ for a measurable function $f$, with $\mathbb{E}{Z}^2<\infty$. Take $X_1^{\prime },\dots ,X_n^{\prime }$ with $X_i^{\prime }$ having the same probability distribution as $X_i$, all $2n$ inputs mutually independent. DefineUse the same function $f$, keeping every other input fixed. ThenThe expected value averages over both the original inputs and their replacements. An infinite right side gives a trivial bound; under the stated square-integrable condition every term is finite.^[ref]

For a concrete four-state example, take independent Bernoulli random variables with $\mathbb{P}(X_1=1)=0.3$ and $\mathbb{P}(X_2=1)=0.6$, and set $Z=\max \{X_1,X_2\}$. This output records whether either input is one. The states $(0,0),(1,0),(0,1),(1,1)$ have respective probabilities $0.28,0.12,0.42,0.18$, soReplacing $X_1$ changes $Z$ only when $X_2=0$ and $X_1^{\prime }\ne X_1$. A fresh Bernoulli draw can repeat the old value: the replacement is not a forced flip. By independence, the expected value of the squared change isSimilarly,Thus Efron–Stein inequality gives $0.2016\le (0.168+0.336)/2=0.252$. The larger second contribution reflects both its replacement probability and how often the other input leaves the output sensitive to it.

For the same inputs, consider instead $W=X_1+2X_2$. The variance of a sum of independent random variables givesHere $\mathbb{E}[(W-W_1^{\prime }{)}^2]=0.42$ and $\mathbb{E}[(W-W_2^{\prime }{)}^2]=1.92$, so the Efron–Stein inequality is exact: $(0.42+1.92)/2=1.17$. More generally, for $W=c+{\sum }_i{g}_i(X_i)$ with square-integrable summands, each contribution $\frac{1}{2}\mathbb{E}[(W-W_i^{\prime }{)}^2]$ equals $\mathrm{Var}(g_i(X_i))$ and these variances add exactly.

Independence is essential. Let $X_1=X_2=B$ for a single Bernoulli random variable with parameter $1/2$, and take $W=X_1+X_2=2B$. Its variance is one. If each coordinate is nevertheless replaced by an independent draw from its marginal Bernoulli distribution, each squared-change expected value is $1/2$, giving the false proposed upper bound $1/2$. Replacement now creates off-diagonal states $(0,1)$ and $(1,0)$ that the original input never visits. The original coordinates fail the hypothesis of Efron–Stein inequality.

The attraction is local calculation: a function may involve many inputs, yet changing one can have a simple effect. Each half squared-change expected value supplies a coordinate's contribution to an upper budget for the total variance. Applying Chebyshev's inequality then bounds a tail probability using that budget. These contributions need not partition the actual variance, as the maximum example shows.

The name commemorates Bradley Efron and Charles M. Stein. Their 1981 paper The Jackknife Estimate of Variance appeared in The Annals of Statistics, volume 9, issue 3, pp. 586–596.^[ref]

For $a\ge \sigma >0$, assign probability ${\sigma }^2/(2a^2)$ to each of $\mu -a$ and $\mu +a$, and the remaining probability $1-{\sigma }^2/a^2$ to $\mu$. This probability distribution has expected value $\mu$, variance ${\sigma }^2$, and tail probability $\mathbb{P}(|X-\mu |\ge a)={\sigma }^2/a^2$. Thus Chebyshev's inequality is sharp when only these two moments are supplied. For example, $\mu =0$, $\sigma =1$, $a=2$ gives masses $1/8$, $3/4$, $1/8$. Replacing $\ge$ with $>$ would exclude the two extreme points in this example.

Applying Markov's inequality to the positive random variable $e^{tX}$ givesHere $M_X(t)=\mathbb{E}[e^{tX}]$ is the moment-generating function, and the useful bound requires it to be finite at the chosen $t$. Optimizing over $t>0$ gives the Chernoff bound method: an exponential function weights large values more strongly before applying the same average-budget argument.

For example, let $N$ have the Poisson distribution with parameter one. Its expected value and variance are both one, and its moment-generating function is $M_N(t)=\exp (e^t-1)$. At threshold four, choosing $t=\log 4$ givesThis $t$ minimizes the exponent $e^t-1-4t$ because its derivative is $e^t-4$, with positive second derivative. The direct Markov's inequality bound is $1/4$, and the two-sided Chebyshev's inequality bound, applied to a deviation of at least three from the mean one, is $1/9$. The exact Poisson distribution tail probability is $1-e^{-1}(1+1+1/2+1/6)\approx 0.0189882$. These compare three valid bounds obtained from progressively different information; none is an exact tail probability formula for general random variables.

Arrange a uniform random permutation of $n$ distinct ordered elements around a circle, and let $L$ be the greatest number of consecutive entries that appear in increasing order. Put $k_0=\min \{k:k!\ge n\}$. Then $\mathbb{P}(k_0-2\le L\le k_0)\to 1$ as $n\to \infty$.

Let $X_k$ count increasing consecutive blocks of length $k$. Each of the $n$ starting positions succeeds with probability $1/k!$, so $\mathbb{E}{X}_k=n/k!$. For $k\le n/2$, disjoint blocks have independent relative orders; blocks overlapping with a start displacement $s<k$ are both increasing precisely when their length-$k+s$ union is increasing. ThusConsequently Markov's inequality gives $\mathbb{P}(L\ge k_0+1)\le 1/(k_0+1)$, while Chebyshev's inequality gives $\mathbb{P}(L<k_0-2)\le 2/(k_0-1)$ for sufficiently large $n$. The latter uses $n/(k_0-2)!>k_0-1$. Both bounds vanish. These are consecutive cyclic runs; allowing arbitrary skipped entries is a different permutation statistic.

For a nonnegative random variable $Y$ and threshold $a>0$, Markov's inequality givesThe useful case has finite expected value; an infinite right side gives no finite information. The bound also holds if $Y$ is nonnegative almost surely. Combining it with the elementary bound one gives $\mathbb{P}(Y\ge a)\le \min \{1,\mathbb{E}Y/a\}$. Nonnegativity is essential: negative values could otherwise cancel the contribution of large positive values to the expected value.

The idea is an average budget. Every outcome where $Y\ge a$ contributes at least $a$ times its probability to $\mathbb{E}Y$, and the other outcomes contribute nonnegative amounts. Formally, the indicator function gives $Y\ge a{1}_{\{Y\ge a\}}$; taking the expected value proves the bound. ^[ref].

For example, let $Y$ take $0$, $1$, $2$, $5$ with respective probabilities $0.5$, $0.2$, $0.2$, $0.1$. Its expected value is $1.1$. At $a=2$, the tail probability is $0.3$, while the bound is $1.1/2=0.55$. At $a=5$, the tail probability is $0.1$, while the bound is $0.22$. A different probability distribution with the same expected value, putting masses $0.78$ and $0.22$ at $0$ and $5$, attains the bound $0.22$ exactly at $a=5$.

Markov's inequality is useful when a moment is easy to compute but a full probability distribution is difficult to determine. A nonnegative count with expected value less than one must have some positive probability of being zero, giving the first moment method. Applying the same bound to a squared centered random variable gives Chebyshev's inequality. Applying it to an exponential function of a random variable gives an exponential Markov bound, which can exploit more than a single moment.

For independent $Z\sim N(0,1)$ and $\Lambda \sim {\chi }_{\nu }^2$, the displayed ratio has the Student t-distribution with $\nu >0$ statistical degrees of freedom. Equivalently, conditional on $\Lambda =\lambda >0$, $T$ has normal distribution $N(0,\nu /\lambda )$. This is a normal scale mixture representation of Student t: a small latent denominator occasionally produces a much larger spread. The result is a heavy-tailed distribution even though every conditional probability distribution is a normal distribution.

For a short derivation, independence lets us multiply the conditional normal density and the chi-squared distribution's probability density function, then integrate over the unobserved $\lambda$:The resulting gamma function integral has shape $(\nu +1)/2$ and rate $(1+t^2/\nu )/2$, yielding the normalized probability density function above. Also, for $\nu >2$, conditional expectation gives $\mathbb{E}[T^2]=\nu \mathbb{E}[{\Lambda }^{-1}]=\nu /(\nu -2)$. Thus unit scale does not mean unit variance. Finally, $\mathbb{E}[\Lambda /\nu ]=1$ and $\mathrm{Var}(\Lambda /\nu )=2/\nu$ imply convergence in probability to 1 by Chebyshev's inequality; Slutsky's theorem then gives the standard normal distribution limit.

Pafnuty Chebyshev's 1867 paper “Des valeurs moyennes” develops bounds for deviations of sums in terms of their expected values and second moments. This connects his historical work with the modern Chebyshev's inequality and its use in the weak law of large numbers. ^[ref].

Chebyshev's inequality assumes a real random variable $X$ with finite expectation $\mu$ and finite variance ${\sigma }^2$. For every real $a>0$,No independence assumption is needed. Applying Markov's inequality to the nonnegative random variable $(X-\mu {)}^2$ proves the formula, including the zero-variance case.

Let $D_i$ be the result of roll $i$, so $X={\sum }_{i=1}^{100}{D}_i$. Each $D_i$ has the uniform distribution on a finite set $\{1,\dots ,6\}$, givingand hence variance $\mathrm{Var}(D_i)=91/6-(7/2{)}^2=35/12$. The rolls are independent, so linearity of expectation and variance additivity for independent random variables giveAll the required moments are finite. Taking $a=50$ in Chebyshev's inequality now yieldsThis is an upper bound, rather than an exact tail probability.

For a variable $Z$ of finite variance and $t>0$, Chebyshev's inequality isOn that event, $(Z-EZ{)}^2\ge t^2$. Thus $t^{2}P(|Z-EZ|\ge t)\le E[(Z-EZ{)}^2]$, proving the assertion. Equivalently apply Markov's inequality to the squared deviation.

Assume $EX>0$, as required by the denominators. Since each indicator has variance at most its expectation, and independent event pairs have zero covariance,The sum uses ordered pairs, matching the covariance expansion. Chebyshev's inequality now givesIf $EX=0$, $X=0$ almost surely and the divided expression is not the useful form of the bound.

Chebyshev's inequality says that for a random variable $Z$ with finite mean and variance, and every $t>0$,