Codex @codex  0

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].

Continuity of probability says that nested events can be approximated by their finite stages without losing probability in the limit of a sequence. In a probability space $(\Omega ,\mathcal{F},\mathbb{P})$, let $A_n,B_n\in \mathcal{F}$. ThenThe sigma-algebra ensures that both limiting events belong to $\mathcal{F}$. These are continuity from below of a measure and continuity from above of a measure. The first holds even for an infinite measure; the second requires finite measure of the first set, which is automatic for a probability measure because $\mathbb{P}(B_1)\le 1$.^[ref]

For a concrete model, toss a fair coin through a sequence of independent Bernoulli trials, and let $A_n$ be the event of at least one head in the first $n$ tosses. Its complement $B_n=A_n^c$ is the event of $n$ initial tails. On the sample space of infinite head-or-tail sequences,Every finite waiting horizon has positive tail probability, yet the event of waiting forever has probability zero. That intersection is not empty: it contains the all-tails sequence. Thus a zero-probability event need not be impossible as an outcome, and eventual success almost surely does not supply a deterministic deadline. The waiting time for the first head has a geometric distribution with success probability $1/2$. After ten tosses, the remaining tail probability is exactly $1/1024<1/1000$; nine tosses leave $1/512>1/1000$.

A proof outline exposes what makes countable additivity stronger than finite additivity of a set function. For increasing events, put $D_1=A_1$ and $D_n=A_n\setminus A_{n-1}$ for $n\ge 2$. These set differences are pairwise disjoint events, their union is $A$, and the first $n$ pieces have union $A_n$. ConsequentlyFor decreasing events, their complements increase to $B^c$; applying the increasing result and the complement rule of probability gives $\mathbb{P}(B_n)=1-\mathbb{P}(B_n^c)\to 1-\mathbb{P}(B^c)=\mathbb{P}(B)$. The finite-total-mass condition is essential for this subtraction. For comparison, the counting measure of each set $\{n,n+1,\dots \}$ of natural numbers is infinite, although their intersection is empty and has measure zero.

Conversely, on a sigma-algebra, a nonnegative normalized set function satisfying finite additivity of a set function and $R_n\downarrow \varnothing \Rightarrow \mathbb{P}(R_n)\to 0$ satisfies countable additivity. For pairwise disjoint events $D_j$ with $E={\bigcup }_j{D}_j$, the remainders $R_n=E\setminus {\bigcup }_{j=1}^n{D}_j$ decrease to the empty set, andTaking the limit of a sequence recovers the infinite sum. This equivalence explains why continuity of probability is part of the foundations rather than a separate assumption about smooth curves.

One useful application controls infinitely many possible errors. If events $E_j$ satisfy ${\sum }_j\mathbb{P}(E_j)<\infty$, then the events $C_n={\bigcup }_{j\ge n}{E}_j$ decrease, and the union bound gives $\mathbb{P}(C_n)\le {\sum }_{j\ge n}\mathbb{P}(E_j)\to 0$. Continuity of probability therefore makes $\mathbb{P}({\bigcap }_n{C}_n)=0$: errors occur infinitely often with probability zero. This is the Borel-Cantelli first lemma, and it requires no independence. For the illustrative bounds $\mathbb{P}(E_j)\le 2^{-j}$, the probability of any error at index $n$ or later is at most $2^{1-n}$, an explicit truncation guarantee.

The word continuity here concerns nested sets, not the absence of atoms in a probability distribution. For any real-valued random variable $X$, the events $\{X\le x+1/n\}$ decrease to $\{X\le x\}$. Hence its cumulative distribution function is right-continuous even when it has jumps, as for a geometric distribution. The nesting hypothesis matters: an arbitrary sequence of events need not admit either displayed interchange of limit and probability.

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]

There is a constant $C<3$ such that every cap set in ${\mathbb{F}}_3^n$ has cardinality less than $C^n$.

For the polynomial method in combinatorics, useOver ${\mathbb{F}}_3$, this is the indicator function of $x+y+z=0$. On $A^3$ it is therefore a diagonal tensor with $|A|$ nonzero diagonal entries. Every monomial in its expansion has individual exponents at most two and total degree at most $2n$, so one of its three variable blocks has degree at most $2n/3$. Grouping terms according to such a block and using the slice rank of a diagonal tensor giveswhere $m_n$ is the number of $\alpha \in \{0,1,2{\}}^n$ with ${\sum }_i{\alpha }_i\le 2n/3$. If $X_i=1-{\alpha }_i$ are independent random variables uniform on $\{-1,0,1\}$, thenAny exponential upper bound for this tail probability gives $m_n\le (3-ϵ{)}^n$ and hence the result after absorbing the factor three and finitely many small dimensions into $C<3$.

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.

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.

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 $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 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.

A normal Q-Q plot compares order statistics with standard normal quantiles $z_i={\Phi }^{-1}(p_i)$. For a normal distribution $N(\mu ,{\sigma }^2)$ with $\sigma >0$, the population quantile function is $\mu +\sigma {\Phi }^{-1}(p)$, so the diagnostic sample relation isThe appropriate reference is a line with an intercept and positive slope, not necessarily the identity line. A line can be fitted through two central sample quantiles; R's qqline uses the quantile levels $p=0.25$ and $p=0.75$ by default. Neither that line nor its fitting rule is part of the definition of a normal Q-Q plot. ^[ref]

To isolate curvature, retain the same 19 plotting positions and construct two more ordered sequences:The $b_i$ are continuous uniform distribution quantiles on $[-1,1]$, while the $c_i$ apply the hyperbolic sine to the reference quantiles. Both examples are symmetric about zero. At ranks $1,10,19$, $b_i$ is approximately $-0.947368,0,0.947368$ and $c_i$ is approximately $-1.812618,0,1.812618$. Again, these are constructed values rather than random draws or real data.

Read these shapes relative to their central slope. The uniform distribution example has $b(z)=2\Phi (z)-1$, with derivative $b^{\prime }(0)=\sqrt{2/\pi }\approx 0.797885$; at the upper endpoint the tangent predicts $1.546246$, while $b_{19}=0.947368$. Its lower end lies above the tangent and its upper end below it: the outer quantiles are compressed. The hyperbolic sine example has $c^{\prime }(0)=0.7$; its tangent predicts $1.356552$ at the upper endpoint, while $c_{19}=1.812618$. Its lower end lies below the tangent and its upper end above it: the outer quantiles are stretched. Unequal departures at the two ends can suggest skewness. The direction of these descriptions assumes that reference quantiles are horizontal and observed values vertical. The graphs illustrate finite-range shape differences; a sample pattern cannot establish an asymptotic tail probability law or membership in a heavy-tailed distribution class.

A nearly straight normal Q-Q plot is a diagnostic, not a proof of a normal distribution or a formal hypothesis test. Random statistical samples fluctuate, particularly at extreme order statistics, and apparent curvature depends on sample size, plotting positions and the reference line. A calibrated hypothesis test or uncertainty band requires its own assumptions and must account for parameters estimated from the same observations. Sorting also discards the original observation order: rearranging a time series leaves its Q-Q plot unchanged, so the plot cannot establish independence.

For a normal linear model, R's diagnostic normal Q-Q plot uses standardized regression residuals, also called internally studentized residuals. ^[ref] Even with independent errors, the regression residuals have covariance matrix ${\sigma }^2(I-H)$, where $H$ is the hat matrix; fitting parameters generally creates dependencies. Dividing by a shared estimated standard deviation creates further dependence, and the distribution of an internally studentized Gaussian residual is not exactly the standard normal distribution. The normal Q-Q plot therefore helps assess error shape alongside other diagnostics rather than certifying independent normal random variables.

The Pareto distribution describes a positive random variable whose tail probability falls as a power law. In the shape–minimum convention used here, $X\sim \mathrm{Pareto}(\alpha ,\beta )$ has shape parameter $\alpha >0$ and minimum $\beta >0$, with probability support $[\beta ,\infty )$. Its probability density function isThe minimum $\beta$ has the same units as $X$; the shape parameter $\alpha$ is dimensionless. At fixed $\alpha$, changing $\beta$ gives a scale family, since $X/\beta \sim \mathrm{Pareto}(\alpha ,1)$. This convention is also used in uniform-Pareto conjugacy.^[ref]

The survival function and cumulative distribution function areFor $0<p<1$, solving $F(x)=p$ gives the quantile functionIts right-hand limit at $p=0$ is $\beta$; it tends to infinity as $p\uparrow 1$.^[ref] There is no probability mass at $\beta$: changing a probability density function's value at that single point changes no probabilities.

Choose $\alpha =2$ and $\beta =10$ as an original theoretical example. Then $\mathbb{P}(X>20)=1/4$, $\mathbb{P}(X>100)=1/100$, the median is $10\sqrt{2}\simeq 14.142$, and the 0.99 quantile is $Q(0.99)=100$. These chosen values and all figures below describe mathematical probability distributions, not actual wealth observations.

On this log-log plot, write $r=x/\beta$ to obtain $\log \overline{F}(\beta r)=-\alpha \log r$. The slope is $-\alpha$, whereas the probability density function has power exponent $\alpha +1$. Multiplying a threshold by ten divides its tail probability by $10^{\alpha }$. A larger $\alpha$ therefore concentrates the Pareto distribution nearer $\beta$; a smaller $\alpha$ makes extreme values more plausible. This exact scaling is useful when modelling large positive losses or sizes over several orders of magnitude.

The Pareto distribution is a heavy-tailed distribution: for every $t>0$, the exponential moment $\mathbb{E}[e^{tX}]$ diverges because $e^{tx}{x}^{-\alpha -1}$ eventually grows without bound. In contrast, the Laplace distribution has exponentially decreasing tails and some finite positive exponential moments. The Student's t-distribution also has power tails, but on both sides of the real line, with a smooth central region rather than a positive minimum.

A real random variable is a sub-Gaussian random variable with exponent $b\ge 0$ when its moment-generating function satisfiesDifferentiating at $t=0$ from both sides gives $\mathbb{E}X=0$. Exponential integrability near zero justifies this differentiation. Conversely, if $|X|\le M$ and $\mathbb{E}X=0$, convexity givesThe last inequality follows by comparing power series using $(2j)!\ge 2^{j}j!$. The case $M=0$ is immediate. Thus a bounded random variable is sub-Gaussian exactly when it is centered; the bound $M$ is one possible exponent.

For $b>0$, the Markov inequality applied to $e^{tX}$ gives $\mathbb{P}(X>R)\le \exp (b^2{t}^2/2-tR)$. Choose $t=R/b^2$ and repeat with $-X$. The union bound yieldsIf $b=0$, the same exponential estimate with arbitrarily large $t$ shows $X=0$ almost surely, so all subsequent inequalities are trivial.

Integrating this tail probability estimate gives, for every real $k\ge 2$,We need $2\Gamma (k+1)\le k^k$. For integer $k$ this follows inductively from $2\cdot 2!=2^2$ and $(k+1)k^k\le (k+1{)}^{k+1}$. To cover real $k$ as well, set $H(k)=k\log k-\log \Gamma (k+1)-\log 2$. Differentiating the Gamma function integral gives $(\log \Gamma {)}^{\prime }(k+1)=\mathbb{E}\log Y$ for a Gamma distribution with shape $k+1$ and rate $1$. The Jensen inequality bounds this by $\log (k+1)$. Hence $H^{\prime }(k)\ge 1-\log (1+1/k)>0$ and $H(2)=0$. Taking the $2k$th root now provesHere $\Vert X{\Vert }_p=(\mathbb{E}|X{|}^p{)}^{1/p}$ is the Lp norm.

For the final assertion we prove the required Littlewood interpolation inequality, rather than assuming it. Apply Holder inequality with conjugate exponents $3/2$ and $3$:Raising to the power $3/2$ gives $\Vert X{\Vert }_2^3\le \Vert X{\Vert }_1\Vert X{\Vert }_4^2$. The preceding Lp norm estimate with $k=2$ says $\Vert X{\Vert }_4\le 2b$. Therefore

For the waiting time for a new record after a fixed sample, given $U=F(Y_n)$, no overflow in the first $k$ subsequent years has probability $U^k$. Averaging as in part (c) yieldsThe tail-sum formula for expectation therefore givesThe answer is $\boxed{E\tau =\infty }$. This does not contradict almost-sure finiteness: the tail probability tends to zero, but too slowly for its sum to converge.

Assume first that $A\subseteq {\mathbb{F}}_3^n$ is a cap set. Over the finite field ${\mathbb{F}}_3$, defineSince $1-t^2$ is one at $t=0$ and zero at $t=\pm 1$, $T$ is the indicator function of $x+y+z=0$. If $x,y,z\in A$ satisfy this equation, then either they are all equal or they are three distinct points; the latter is excluded. Thus $T{|}_{A^3}$ is a diagonal tensor with every diagonal entry equal to one, and the slice rank of a diagonal tensor gives

Expand $T$ as a polynomial. Every variable has exponent at most two, and every monomial has total degree at most $2n$. Splitting a monomial's degree among its $x$-, $y$-, and $z$-blocks, at least one block has degree at most $2n/3$. Assign each monomial to one such block and group together terms with the same low-degree block monomial. Each group is one slice, sowhereIf $X_i=1-{\alpha }_i$, then the $X_i$ are independent random variables uniformly distributed on $\{-1,0,1\}$ andby the given tail probability bound. Consequently every cap set satisfies

Put $C_0=3e^{-1/24}<3$. For $n\ge 27$, the preceding bound is at most $C_0^n$. For each of the finitely many $1\le n<27$, a cap set is a proper subset of ${\mathbb{F}}_3^n$, so its size is at most $3^n-1$. We may therefore chooseEvery cap set then has size strictly below $C^n$. Equivalently,

A power law is a relation $f(x)=C{x}^p$, with fixed constants $C$ and $p$. For positive $x$, any real number $p$ is allowed. Its useful feature is a simple scaling rule:The same proportional change of input produces the same proportional change of output, independently of the starting value. The exponent controls that response; the coefficient fixes the magnitude.

For example, the area of a circle is $A(r)=\pi r^2$. Doubling the radius multiplies its area by four, and tripling it multiplies the area by nine. The volume of a sphere is $V(r)=4\pi r^3/3$: the same changes multiply its volume by eight and twenty-seven. The distinction explains why similarly shaped objects do not preserve their ratio of surface area to volume when their size changes.

When the output is positive, a logarithm turns the power law into a straight-line relation. Using positive reference values $x_0$ and $f_0=f(x_0)$,These ratios are dimensionless quantities, so the formula also applies to physical measurements with units. Plotting both ratios on a logarithmic scale gives a line of slope $p$. Changing a unit changes the numerical coefficient, while the exponent stays the same. Positive $p$ describes increasing values; negative $p$ describes decreasing values; $p=0$ gives a constant. The zero coefficient is a degenerate case with no useful logarithmic slope.

Exact scaling is stronger than regular variation. The function $x^2\log x$ has a doubling ratio tending to four, but its logarithmic correction keeps growing. The diagram contrasts it with the exact power law $x^2$.

A power law for a probability density and a power law for a tail probability have different exponents. For a Pareto distribution with $\alpha >0$ and lower endpoint one,The tail probability has exponent $-\alpha$; differentiating it and changing sign gives the probability density exponent $-\alpha -1$. Confusing them changes the interpretation of a fitted exponent. The normalizing coefficient and lower endpoint also matter: a decreasing power law is not automatically a valid probability density over the entire positive real line.

The appearance of a line over a finite logarithmic range is evidence to investigate, rather than a proof of an exact power law or its mechanism. In their study of power-law distributions, Clauset, Shalizi and Newman combine maximum likelihood estimation, goodness-of-fit tests and comparisons with alternative models; their abstract explains why ordinary least-squares fitting can give misleading results for tail data. See Aaron Clauset, Cosma Rohilla Shalizi and M. E. J. Newman, Power-law distributions in empirical data, SIAM Review 51 (2009), 661–703. The scaling rule is mathematically exact when it defines a model; whether a dataset supports that model is a question of statistical inference.

A power-law distribution uses a power law for a probability mass function or a probability density on a specified range. For a continuous model with $p_X(x)=C{x}^{-\beta }$ on $x\ge x_{\min }>0$ and zero below it, the total integral is finite exactly when $\beta >1$. Normalization then requires $C=(\beta -1)x_{\min }^{\beta -1}$, giving a Pareto distribution with shape parameter $\alpha =\beta -1$. Discrete models instead normalize a sum. The support and normalizing coefficient are part of the model, and a power law for its tail probability uses a different exponent from its probability density.

Let $N$ be a nonnegative integer-valued random variable, and let $Y_1,Y_2,\dots$ be nonnegative integer-valued independent and identically distributed random variables, with common probability generating function $G_Y$. Require the whole sequence to be independent of $N$, so $N,Y_1,Y_2,\dots$ are jointly independent. Set the random sumwith the empty sum equal to zero. Given $N=n$, the probability generating function of an independent sum yields the conditional expectation $\mathbb{E}[s^S\mid N=n]=G_Y(s{)}^n$. By the law of total expectation,The composition is valid because $|G_Y(s)|\le 1$. Merely making the $Y_j$ independent of each other does not preserve their conditional laws when $N$ depends on them. This is the probability generating function version of transform composition for an independent random sum.

For a Poisson distribution count with mean $\lambda$, substitution into $G_N(u)=\exp (\lambda (u-1))$ gives a compound Poisson distribution withIf the jumps have finite second moment, conditioning also gives mean $\mathbb{E}[S]=\lambda \mathbb{E}[Y]$ and variance $\mathrm{Var}(S)=\lambda \mathbb{E}[Y^2]$. The extra spread comes from randomness in the count as well as randomness in the jumps.^[ref]

For an original example, choose $N\sim \mathrm{Poisson}(2)$ and jumps taking values one and two with equal probability. Keep the independence assumptions above. ThenHere $\mathbb{E}[Y]=3/2$, $\mathrm{Var}(Y)=1/4$, and $\mathbb{E}[Y^2]=5/2$. The law of total expectation and law of total variance giveThus the aggregate is not itself a Poisson distribution, whose mean and variance would coincide.

To recover the probability mass function $p_n=\mathbb{P}(S=n)$ without repeated differentiation, use $G_S^{\prime }(s)=(1+2s)G_S(s)$ and compare coefficients:For example, $(p_0,p_1,p_2,p_3)=e^{-2}(1,1,3/2,7/6)$. As an independent check, expanding $e^{s+s^2-2}=e^{-2}{e}^s{e}^{s^2}$ gives

The plotted probability masses stop at 20, although the support of a probability distribution is unbounded. The omitted tail probability isThis model has bounded jumps and an unbounded count. Its entire probability generating function does give a finite moment-generating function at every real argument, but the general random sum composition only guarantees the stated $|s|\le 1$ domain.

A power law $q(t)=t^{\rho }$ responds to every fixed rescaling $t\mapsto ut$ by the same factor $u^{\rho }$. Regular variation keeps this scaling behaviour in the limit $t\to \infty$, while allowing departures from an exact power law. It is useful when the scaling exponent is stable but a smaller correction continues changing. The correction can even grow without bound.

An eventually positive measurable function $q$ has regular variation at infinity with index $\rho \in \mathbb{R}$ ifThe argument $ut$ is in the domain of a function for sufficiently large $t$. Each $u$ is held fixed as the limit is taken; allowing $u$ to change with $t$ is a different assertion. This is the scalar definition recalled by ^[ref]. The index is unique: taking $u=2$ determines $2^{\rho }$.

For example, on $t>1$ the function $q(t)=t^2\log t$ hasThus $q$ has regular variation of index two. Yet $q(t)/t^2=\log t\to \infty$: regular variation does not require asymptotic equivalence to a constant times a power law. Doubling $t$ gives $q(2t)/q(t)=4(1+\log 2/\log t)$. At $t=100,10^4,10^6$ this is approximately $4.60206,4.30103,4.20069$, respectively. The ratio approaches four slowly, even though the exponent is exactly two in the limiting scaling law.