Probability inequality

Probability inequalities bound event probabilities from limited information, such as moments, without requiring a complete probability distribution. Markov's inequality uses a nonnegative random variable's expected value; Chebyshev's inequality uses a variance to bound deviations from a mean. The attraction is a guarantee that applies to many possible probability distributions. Their bounds can be conservative for a particular model, and distributions attaining equality show when the available information really cannot give more.

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.

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.

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.

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>0$ and ${\sigma }^2>0$, place probabilitiesTheir weighted deviations cancel, giving expected value $\mu$; their weighted squared deviations give variance ${\sigma }^2$. Only the upper point belongs to $X-\mu \ge a$, so its tail probability attains Cantelli's inequality. With $a=2$, ${\sigma }^2=1$, $\mu =0$, the locations are two and $-1/2$, with masses $1/5$ and $4/5$. The optimized shift makes the lower point zero before squaring, explaining equality in the Markov's inequality step.

The threshold convention matters: this example has $\mathbb{P}(X-\mu >a)=0$. For a strict threshold, placing the upper point at $a+\epsilon$ instead gives probabilities approaching the same bound as $\epsilon \downarrow 0$, with the prescribed mean and variance retained. Extra restrictions on the support of a probability distribution can change which extremal models are allowed.

The first moment method uses the expected value of a count to control whether any counted occurrence exists. For a random variable $N$ taking nonnegative integer values, Markov's inequality givesConsequently, $\mathbb{E}N<1$ implies $\mathbb{P}(N=0)\ge 1-\mathbb{E}N>0$, proving that an outcome with no counted occurrence exists. For a sequence of such counts, $\mathbb{E}N\to 0$ shows that $N=0$ with probability tending to one. The first moment method uses information about the average count, while the complementary second moment method also uses its variance.

The second moment method uses a random variable's expected value and second moment to establish that a counted or measured quantity is positive with substantial probability. It is useful when a positive average alone could be caused by extremely large values on very rare outcomes. Controlling the variance rules out too much of that concentration in rare outcomes.

For a nonnegative random variable $N$ with $m=\mathbb{E}N>0$ and finite second moment, the second-moment bound for positivity givesEquivalently, $\mathbb{P}(N=0)\le \mathrm{Var}(N)/(m^2+\mathrm{Var}(N))$. The method also includes the simpler Chebyshev's inequality bound $\mathbb{P}(N=0)\le \mathrm{Var}(N)/m^2$. Thus a sequence of such random variables with $\mathrm{Var}(N)/(\mathbb{E}N{)}^2\to 0$ has $N>0$ with probability tending to one. These statements require no independence assumption. The variance argument and its use for random counts are developed in Zhao's lecture notes. ^[ref].

For an original toy count, let $N$ count successes in ten independent Bernoulli trials with success probability $p=1/10$. The binomial distribution givesConsequently $\mathbb{P}(N>0)\ge 10/19\approx 0.526316$. The exact probability is $1-(9/10{)}^{10}\approx 0.651322$. The first moment method and union bound only give the upper bound $\mathbb{P}(N>0)\le \min \{1,\mathbb{E}N\}=1$ here. First and second moments therefore answer complementary existence questions.

For a sum of indicator random variables, the variance of a sum isIndependence makes the covariances vanish, but the formula itself also covers dependent counts. For the same ten success probabilities, let every trial share a single Bernoulli random variable $B$: then $N=10B$, with mean one, variance nine, and $\mathbb{P}(N>0)=1/10$. The second-moment lower bound is exactly $1/10$. Ignoring the positive covariances would produce the false independent-count conclusion. Zhao's discussion of sums of indicators explains why overlapping counted structures require these pairwise terms. ^[ref].

For a nonnegative random variable $N$ with positive expected value and finite second moment, write $N=N{1}_{\{N>0\}}$. The Cauchy-Schwarz inequality giveswhich proves the bound in second moment method. It is the zero-threshold case of the Paley-Zygmund inequality. Equality occurs when $N$ is a fixed positive value on the event $N>0$ and zero elsewhere, almost surely. For $N=10B$ with $B$ a Bernoulli random variable of parameter $1/10$, $(\mathbb{E}N{)}^2/\mathbb{E}{N}^2=1/10$ equals the exact positivity probability.

The variance identity $\mathbb{E}{N}^2=(\mathbb{E}N{)}^2+\mathrm{Var}(N)$ turns the lower bound into a statement about variance relative to the squared mean. A small ratio forces positivity to be likely. A positive expected value alone does not do so: keeping $\mathbb{E}N=1$ while taking $N=1/q$ with probability $q$ and zero otherwise makes the positivity probability as small as any chosen $q>0$.

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.

Let $Z$ be a nonnegative integer-valued random variable with $\mathbb{E}Z=A/q$, where $A\ge 0$ and $q\ge 1$ are integers. On $Z>A/q$, the integer $qZ$ is at least $A+1$. Markov's inequality gives $\mathrm{Pr}(Z>A/q)\le A/(A+1)$. Independent restarts therefore need at most $A+1$ attempts in expected value to achieve $Z\le \mathbb{E}Z$. The denominator bound on the expected value matters for this runtime guarantee.

If $X$ is an integrable random variable and $Z$ is a finite, strictly positive $\mathcal{G}$-measurable random variable, thenIndeed, $0\le Z{1}_{\{|X|\ge Z\}}\le |X|$. Monotonicity of conditional expectation and the measurable-factor rule for conditional expectation giveDivision by the strictly positive $Z$ proves the claim. Only the displayed product needs to be an integrable random variable; neither $Z$ nor $|X|/Z$ needs to have finite expected value. The measurable threshold represents information already available before asking how likely the remaining exceedance is.

For a finite-expected value nonnegative random variable and $a>0$, equality in the uncapped Markov's inequality holds exactly when $Y$ takes only $0$ and $a$ almost surely. Indeed the nonnegative difference $Y-a{1}_{\{Y\ge a\}}$ has zero expected value exactly when it vanishes almost surely. Giving $a$ probability $p$ yields $\mathbb{E}Y=pa$ and $\mathbb{P}(Y\ge a)=p$. This shows the bound cannot generally be reduced using only the nonnegative random variable's expected value.

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.

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

Equip the symmetric group $S_n$ with its uniform probability measure and unnormalized Hamming distance. If $f$ has Lipschitz constant $K$, it obeys the displayed two-sided bound, and each one-sided tail has the same exponential without the factor two. Reveal a uniform permutation one image at a time. Two possible next images have completion sets paired by swapping those two values, changing exactly two coordinates. Thus the corresponding conditional means differ by at most $2K$. Each increment of the Doob exposure martingale has conditional range length at most $2K$. Applying the conditional Hoeffding lemma gives $\mathbb{E}{e}^{\lambda (f-\mathbb{E}f)}\le e^{n{\lambda }^2{K}^2/2}$; optimizing the exponential Markov bound proves the bound. A mere absolute-increment bound of $2K$ gives a weaker constant, so using the range length matters.

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.

Let the largest last-coordinate section have probability $a$, and another section probability $ar$. Mix mismatch vectors from these two sections with weights $\lambda ,1-\lambda$. Their squared norm is at most $\lambda d_1^2+(1-\lambda )d_2^2+(1-\lambda {)}^2$. Hölder's inequality and induction bound that section's exponential integral by $a^{-1}{\inf }_{\lambda }{r}^{-\lambda }{e}^{(1-\lambda {)}^2/4}$. The scalar estimate for Talagrand product induction makes it at most $(2-r)/a$. Average over sections and use $m(2-m)\le 1$ with $m=\mathrm{Pr}(A)/a$ to close the induction.

For $a\in [0,1]$,where the endpoint $t=1$ is used directly if $a=0$. Put $L=-\log a$. For $L\le 1/2$, choose $t=2L$ and set $h(L)=\log (2-e^{-L})-L+L^2$. Then $h(0)=h^{\prime }(0)=0$ and $h^{\prime \prime }(L)=2-2e^L/(2e^L-1{)}^2\ge 0$, proving the bound. For $L\ge 1/2$, take $t=1$; the result follows from the already proved boundary case and monotonicity of $2-a$. This estimate closes the section-by-section induction for the exponential Talagrand convex distance moment.

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.

Here ${\mathrm{Ent}}_{\mu }(h)=\int h\log hd\mu -(\int hd\mu )\log \int hd\mu$ for a probability measure. The coefficient depends on the normalization of the energy. With the joint energy $-⟨Lg,g⟩$ for $L=D^2-xD$, standard Gaussian measure has optimal constant two.

// Target: analysis.bigb

Differentiate $\log \Vert u{\Vert }_q$ with $u=P_{t}f$ and a changing exponent. The derivative is $q^{\prime }\mathrm{Ent}(u^q)/(q^2\int u^q)-\mathcal{E}(u^{q-1},u)/\int u^q$. Apply the logarithmic Sobolev inequality to $u^{q/2}$ and the power inequality for symmetric Markov energies. Choosing $q^{\prime }=4(q-1)/c_{\mathrm{LS}}$ makes the upper bound zero.

// Target: probability-and-statistics.bigb

The Hoeffding inequality turns finite interval bounds and independence into exponentially small tail probabilities for a sum. It requires neither a normal distribution nor identical probability distributions. Let $X_1,\dots ,X_n$ be independent essentially bounded real random variables, with deterministic finite bounds $a_i\le X_i\le b_i$ almost surely. Define the centered sum and its squared-width budget byFor $V>0$ and $t>0$,The union bound therefore gives $\mathbb{P}(|S_n|\ge t)\le \min \{1,2e^{-2t^2/V}\}$. If $V=0$, every $X_i$ is constant almost surely, so $S_n=0$ and both positive-threshold tail probabilities vanish. The equal-width version is stated in the authored Stanford notes.^[ref]

The quantity $V$ is a sum of squared interval widths, not the variance of $S_n$. Centering changes the endpoints to $a_i-\mathbb{E}{X}_i$ and $b_i-\mathbb{E}{X}_i$, leaving each width unchanged. For example, independent random variables in $[-2,1]$ and $[4,5]$ have $V=3^2+1^2=10$, whatever their expected values or probability distributions. A deviation at least three above their total expected value has probability at most $e^{-18/10}\approx 0.165299$. If all widths equal $b-a>0$, the sample mean ${\overline{X}}_n=n^{-1}{\sum }_i{X}_i$ satisfies

Independence is essential to this general guarantee. Take one Bernoulli random variable $B$ with success probability $1/2$ and set every $X_i=B$. Each lies in $[0,1]$, but for every $n$ the sample mean is either zero or one. Thus $\mathbb{P}(|{\overline{X}}_n-1/2|\ge 1/4)=1$, whereas incorrectly inserting these dependent observations into the formula would give $2e^{-n/8}$, less than one for $n\ge 6$. Some special dependent models have their own valid concentration inequalities; arbitrary statistical dependence cannot be ignored.

For the short proof, apply Markov's inequality to $e^{\lambda S_n}$ with $\lambda >0$, factor the expectation using independence, and apply the Hoeffding lemma to each factor:Minimizing this quadratic polynomial at $\lambda =4t/V$ gives the upper tail probability; applying it to $-S_n$ gives the lower one. This is the Chernoff bound method. The original 1963 article is Probability Inequalities for Sums of Bounded Random Variables by Wassily Hoeffding; its publisher record identifies the article, but its full text was unavailable during this source check. The argument above is a direct derivation rather than a claim to have inspected that article's proof.

Let $n$ be even and let $X_1,\dots ,X_n$ be independent Bernoulli variables with parameter $1/2$, arranged on a circle. The probability that some consecutive half-circle $I$ has $|{\sum }_{i\in I}{X}_i-{\sum }_{i\notin I}{X}_i|\ge w$ is at most $2n\exp (-2w^2/n)$. For a fixed $I$, the variable $Z_I={\sum }_{i\in I}{X}_i+{\sum }_{i\notin I}(1-X_i)$ has the binomial distribution $\mathrm{Bin}(n,1/2)$, and the signed imbalance is $Z_I-n/2$. Apply Hoeffding inequality to this single binomial variable, then take a union bound over the at most $n$ intervals. Consequently $w=c\sqrt{n\log n}$ suffices for uniform balance with probability tending to one whenever $c>1/\sqrt{2}$.

Let $B_1,\dots ,B_n$ be independent and identically distributed Bernoulli random variables with success probability $p$, and let ${\hat{p}}_n=n^{-1}{\sum }_i{B}_i$ be their observed frequency, a sample mean. Since every interval width is one, $V=n$. Substituting $t=n\epsilon$ into the Hoeffding inequality givesFor tolerance $0<\epsilon <1$ and failure probability $0<\delta <1$, solving $2e^{-2n{\epsilon }^2}\le \delta$ yields the sufficient sample sizeHere $\log$ is the natural logarithm. For $\epsilon =0.05$ and $\delta =0.05$, $n=738$ guarantees an error smaller than $0.05$ with probability at least $0.95$, for every $p\in [0,1]$. The two-sided bound at this sample size is approximately $0.0499440$. A specified single direction instead needs $n\ge \lceil \log (1/\delta )/(2{\epsilon }^2)\rceil$, or $600$ for these choices. Halving the tolerance multiplies the unrounded sufficient sample size by four; reducing the failure probability tenfold adds $\log (10)/(2{\epsilon }^2)$ before rounding.

This is a conservative sufficient sample size, not a necessary minimum. For a specified $p$, the count $K={\sum }_i{B}_i$ has a binomial distribution, whose exact upper tail probability isFor $k>np$, the Hoeffding inequality bounds this by $\exp [-2(k-np{)}^2/n]$. An arbitrary frequency threshold uses $k=\lceil n(p+\epsilon )\rceil$; if $k>n$, the event is impossible. The discreteness of the count and its variance $np(1-p)$ can make the exact tail probability substantially smaller. At $n=100$, $p=1/2$, $k=60$, the exact upper tail probability is about $0.0284440$, while the bound is $e^{-2}\approx 0.135335$. At $p=1/10$, $k=20$, the same deviation $\epsilon =0.1$ gives the same bound but an exact upper tail probability about $0.00197856$.

For a fixed positive sample size $n$ of independent and identically distributed Bernoulli random variables, letThe Hoeffding inequality makes $C_n$ a conservative confidence interval for $p$: ${\mathbb{P}}_p(p\in C_n)\ge 1-\delta$ for every $p\in [0,1]$. Indeed, exclusion from the closed interval implies $|{\hat{p}}_n-p|>r_n$, an event contained in the deviation event bounded by $\delta$. Clipping to $[0,1]$ retains coverage because $p$ already lies there. For $n=738$, $\delta =0.05$, and an observed frequency $369/738=1/2$, $r_n\approx 0.0499924$, giving approximately $[0.450008,0.549992]$.

Coverage concerns repeated independent samples: the unknown $p$ is fixed and the confidence interval is random. This fixed-$n$ guarantee does not justify repeatedly checking the same bound and stopping as soon as it looks favorable. The Hoeffding sample size for Bernoulli frequencies chooses $n$ in advance; guarantees across repeated inspection times require separate control of the additional events, for example through a union bound with an allocated failure probability at each time.

The Hoeffding lemma controls the entire centered moment-generating function using only an interval width. For an essentially bounded real random variable $X$ with finite deterministic bounds $a\le X\le b$ almost surely, every real $\lambda$ satisfiesEquivalently, $\mathbb{E}{e}^{\lambda (X-\mathbb{E}X)}\le e^{{\lambda }^2(b-a{)}^2/8}$. This single-random variable statement needs no independence assumption; independence enters when applying it to the factors for a sum in the Hoeffding inequality. Both signs of $\lambda$ are allowed, and equality holds at $\lambda =0$ or when $a=b$.^[ref]

In the convention $\log \mathbb{E}{e}^{\lambda Y}\le {\lambda }^2{\sigma }^2/2$ for a centered sub-Gaussian random variable $Y$, the Hoeffding lemma supplies ${\sigma }^2=(b-a{)}^2/4$. This upper parameter need not equal the actual variance. For a Bernoulli random variable $B$ of success probability $p$,The actual variance is $p(1-p)$, whereas the supplied parameter is $1/4$ for every $p$. This explains part of the conservatism visible in Hoeffding sample size for Bernoulli frequencies.

A short proof exposes why the constant is $1/8$. Put $Y=X-\mathbb{E}X$ and define exponential tilting byThe tilted probability measure has the same interval of possible values, and differentiating the cumulant-generating function gives ${\psi }^{\prime \prime }(\lambda )={\mathrm{Var}}_{{\mathbb{P}}_{\lambda }}(Y)$. Boundedness justifies these derivatives for every finite $\lambda$. Under any such tilted law, Popoviciu's inequality on variances gives ${\psi }^{\prime \prime }(\lambda )\le (b-a{)}^2/4$: the variance is no larger than the expected value of the squared distance from the interval midpoint, itself at most $(b-a{)}^2/4$. Since $\psi (0)={\psi }^{\prime }(0)=0$, the integral form of Taylor's theorem yieldsThis expression handles either sign of $\lambda$ without changing the argument.

The constant $1/8$ cannot be reduced uniformly over all essentially bounded real random variables. Equal endpoint probabilities at $a$ and $b$ give $Y=\pm (b-a)/2$, a scaled Rademacher random variable, andThus the sharpness is already forced near zero by the variance; the bound need not be equality at nonzero parameters for a particular probability distribution.

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 standard one-dimensional Gaussian measure, $\int e^{sx}d\gamma =e^{s^2/2}$. Thus ${\mathrm{Ent}}_{\gamma }(e^{sx})=(s^2/2)e^{s^2/2}$, while $\int |(e^{sx/2}{)}^{\prime }{|}^{2}d\gamma =(s^2/4)e^{s^2/2}$. Every nonzero $s$ therefore attains ratio two, proving optimality of the Gaussian constant.

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.

Give a graph on $n$ labelled vertices independent edge weights in $[0,1]$, and let $W$ be the maximum total weight of a matching. Put each edge into the block of its lower-numbered endpoint. There are at most $n-1$ independent blocks. Every matching uses at most one edge from any block, since the block's edges share that endpoint. Changing a whole block therefore changes the weight of each fixed matching by at most one. Comparing the old and new maximizing matchings shows the same bound for $W$.

The Doob exposure martingale for these blocks has increments bounded by one, so Azuma's inequality givesThe important feature is grouping independent edge coordinates into vertex-centred blocks. Exposing all edges separately would give a weaker denominator of order $n^2$ on a dense graph. Identical distributions are unnecessary; independence and the common range bound suffice.