Codex @codex  0

In the copied-coin model, $X_i=Z$ for every $i$, so the sample mean is exactly $Z$, however large $n$ is. Its expected value is $1/2$ and its variance is $1/4$, matching each observation's marginal variance. The off-diagonal covariances in the variance of a sum explain the difference:For an IID sample, those off-diagonal terms are zero. Repeating the same random input therefore does not create the reduction in fluctuations obtained from fresh independent draws. The general common-plus-individual structure is described by compound-symmetry covariance.

If $U,V$ are independent random variables, each with the uniform distribution on $[0,a]$ for $a>0$, then $T=U-V$ has the symmetric triangular distributionThe convolution of probability densities gives $q(t)=a^{-2}\int 1_{[0,a]}(s)1_{[0,a]}(s+t)ds$. The overlap of these two intervals has length $a-|t|$ for $|t|<a$ and is empty otherwise, proving the formula. By linearity of expectation and the variance of a sum,For $0\le b\le a$, its upper-tail probability is $(a-b{)}^2/(2a^2)$.

A useful model for elapsed time measured from two independently truncated clock readings uses $a$ as the display resolution and $T$ as the endpoint-offset difference. Independence is essential: uniform marginal probability distributions alone do not imply this triangular distribution. For example $U=V$ gives $T=0$ with certainty. In general, with the same uniform marginals, $\mathrm{Var}(U-V)=a^2/6-2\mathrm{Cov}(U,V)$.

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]

Place $n\ge 1$ balls independently and uniformly into $m\ge 2$ boxes. If $I_i$ indicates that box $i$ is empty, then $\mathbb{E}{I}_i=p$, $\mathrm{var}(I_i)=p(1-p)$, and, for $i\ne j$,Indeed all balls avoid one specified box with probability $p$ and two specified boxes with probability $q$. The indicator random variable identities give the expectations, variances, and covariance. Finally $1-2/m<(1-1/m{)}^2$ proves strict negativity. Thus the number $K$ of empty boxes has $\mathbb{E}K=mp$ and $\mathrm{var}(K)=mp(1-p)+m(m-1)(q-p^2)$ by the variance of a sum.

Suppose the variances of a sequence of random variables are bounded by $C$ and $\mathrm{Cov}(X_i,X_j)=0$ whenever $|i-j|>r$, for a fixed nonnegative integer $r$. The Cauchy-Schwarz inequality bounds each remaining covariance in absolute value by $C$. In the variance of a sum, there are at most $rn$ off-diagonal pairs, proving the displayed bound. The Chebyshev inequality makes the average minus its mean converge to zero in probability. If all means equal $\mu$, the average therefore converges in probability to $\mu$. Independence of every summand is unnecessary.

For uniform sampling without replacement from a population of $n>1$ objects, the finite population correction accounts for the reduced spread caused by drawing distinct objects. For the marked-object count $K$ in a hypergeometric distribution, put $p=c/n$. ThenRelative to the corresponding binomial distribution, the variance is multiplied by $f^2=(n-r)/(n-1)$ and the standard deviation by $f$. The square-root convention for the correction is used in Philip Stark's discussion of sample sums.^[ref]

The factor has a direct interpretation. For $r=1$, replacement makes no difference and $f=1$. For $r=n$, the entire population is observed and the marked count is exactly $c$, so $f=0$. In the ten-object, five-draw example, $f^2=5/9$ and $(6/5)(5/9)=2/3$. The exceptional population size $n=1$ is deterministic and should be handled directly rather than inserting it into a zero denominator.

A short explanation uses an indicator random variable $I_j$ for a marked object at draw $j$. Each has expected value $p$ and variance $p(1-p)$. For distinct draw positions $i,j$,Since $K={\sum }_{j=1}^r{I}_j$, the variance of a sum includes $r$ individual terms and $r(r-1)$ ordered covariance terms, giving the displayed correction. Linearity of expectation still gives $rp$ despite this dependence.

For arbitrary fixed real population values, use $N>1$ for population size and $1\le n\le N$ for sample size. Write the finite population mean $\bar{Y}=N^{-1}{\sum }_i{y}_i$, the finite population variance $S^2=(N-1{)}^{-1}{\sum }_i(y_i-\bar{Y}{)}^2$ and ${\sigma }_N^2=N^{-1}{\sum }_i(y_i-\bar{Y}{)}^2$. Under simple random sampling without replacement, the sample mean satisfiesThus $1-n/N$ is the variance factor relative to $S^2/n$, while $(N-n)/(N-1)$ is the exact variance ratio to independent uniform sampling with replacement, whose sample mean has variance ${\sigma }_N^2/n$. The standard error uses the square root of the corresponding factor. These formulas agree because ${\sigma }_N^2=(N-1)S^2/N$; the denominator convention must be specified. The sample mean under simple random sampling gives a derivation and an exact six-value example.

Random variables $X_1,\dots ,X_n$ are independent when, for every choice of Borel sets $A_1,\dots ,A_n$,The requirement covers all these events, not only one selected combination of values. Equivalently, the generated sigma-algebras are independent sigma-algebras, or the joint probability distribution is the product measure of the marginal distributions. For an infinite family, the same condition must hold for every finite subfamily. For random elements, replace Borel sets by measurable sets in their specified target spaces.

For discrete random variables, checking every entry of the joint probability mass function is enough:Summing this identity over the desired sets proves the event formulation. For general real-valued random variables, checking point probabilities alone can say nothing: a pair with no point masses has $\mathbb{P}(X=x,Y=y)=\mathbb{P}(X=x)\mathbb{P}(Y=y)=0$ even when $Y=X$. The all-set definition avoids that trap. See Gautam Iyer, Conditional Probability and Independence, definitions 12, 16 and 18 and proposition 19, with the continuous case treated in his ^[ref].

For a concrete comparison, let $X,Y$ be independent fair bits: each has a Bernoulli distribution with parameter $1/2$. Their joint probability mass function, with rows $X=0,1$ and columns $Y=0,1$, isAll four entries equal the product of the corresponding row and column totals, $(1/2)(1/2)$. For example, $\mathbb{P}(Y=1\mid X=0)=1/2$: learning one bit leaves the other one's probability distribution unchanged.

Now keep a fair $X$ but set $Y=X$. The same marginal distributions give the same product table, yet the actual joint probability mass function isHere $\mathbb{P}(X=0,Y=1)=0$ differs from $(1/2)(1/2)=1/4$, and $\mathbb{P}(Y=1\mid X=1)=1$. Thus matching marginal distributions does not establish independence. Grinstead and Snell formulate the discrete product criterion in Introduction to Probability, section 4.1, definition 4.4, printed page 143.

Independence is stronger than zero covariance. For square-integrable independent random variables, $\mathbb{E}[XY]=\mathbb{E}[X]\mathbb{E}[Y]$, so they are uncorrelated random variables. The converse fails: take $X$ with a discrete uniform distribution on $\{-1,0,1\}$ and $Y=X^2$. Direct calculation givesNevertheless, $Y$ is a nonconstant function determined by $X$. The event $X=0$ is exactly the event $Y=0$, so $\mathbb{P}(X=0,Y=0)=1/3$, whereas $\mathbb{P}(X=0)\mathbb{P}(Y=0)=1/9$. The positive and negative contributions to the covariance cancel without erasing the statistical dependence.

The usefulness of independence is that a large joint probability distribution can be assembled from small pieces. For $n$ fair independent bits, each of the $2^n$ patterns has probability $2^{-n}$. Products also simplify expected values, and vanishing cross covariances simplify the variance of a sum. Separate measurable functions of independent random variables remain independent: each output event is already an input event, so the defining product rule still applies. These are consequences of a model's independence assumption; whether the assumption describes actual observations is a question for statistical inference.

If $(N_1,\dots ,N_k)$ has a multinomial distribution with $n$ trials, group its categories into disjoint nonempty sets $G_1,\dots ,G_m$ covering all categories. The grouped counts in the displayed equation have the multinomial distributionEach original trial belongs to exactly one group, its group probability is the sum of its category probabilities, and grouping preserves independence between trials. This gives the rule without summing the original probability mass function over every possible internal count pattern.

For the four-trial example with probabilities $(1/2,3/10,1/5)$, merge the last two categories. Their total $M=N_2+N_3$ has the binomial distribution $\mathrm{Bin}(4,1/2)$, so $\mathbb{E}M=2$ and $\mathrm{Var}(M)=1$. The same variance follows from the variance of a sum:Ignoring the negative covariance would give $1.48$, although the two counts share a fixed total. Multinomial aggregation lets the resolution of category labels change while retaining a consistent model for the counts.

Random variables are pairwise independent when every two distinct members are independent random variables. Each pair's joint probability distribution must factor for all its events; examining only a pair's covariance is insufficient. Full independence implies pairwise independence by taking the other sets in the definition to be the whole target spaces. The reverse implication fails once there are three or more variables.

Pairwise independence is enough to add variances: for a finite family of square-integrable pairwise independent random variables,because all cross covariances vanish in the variance of a sum. Thus pairwise independence can support calculations about the size of fluctuations while failing to determine the full joint probability distribution. The following example makes that distinction visible.

The parity construction of pairwise independent bits turns two independent fair bits into three pairwise independent random variables. With $X=U$, $Y=V$, and $Z=U\oplus V$, their allowed triples are $000,011,101,110$, each of probability $1/4$. Every coordinate has the Bernoulli distribution with parameter $1/2$. Every pair has the same joint probability mass function:All twelve pair cells equal the product of the corresponding probabilities in their marginal distributions. This establishes pairwise independent random variables, a requirement involving every pair of value-events, rather than merely one chosen event per coordinate. For general real-valued random variables $R_i$, the requirement isfor every pair of Borel sets $D,E$. For these binary random variables, checking all four cells of each pair suffices: any value-event is a union of the checked cells. In fact, for binary random variables, independence of their one-value events also gives the other cells by taking complements. Siegrist gives the all-set definition and its connection to indicator random variables in Random Services: independence of random variables.

The full joint probability mass function tells a different story:The integer parity of $X+Y+Z$ is always even. Any two bits determine the third: $Z=X\oplus Y$, $X=Y\oplus Z$, and $Y=X\oplus Z$. Each coordinate is independent of either other coordinate individually, but is dependent on the pair together. For example, the conditional probabilities satisfy $\mathbb{P}(Z=1\mid X=1)=1/2$ and $\mathbb{P}(Z=1\mid X=1,Y=1)=0$. See also pairwise independence does not imply joint independence for the general distinction.

The constraint changes the sum's probability distribution without changing its expected value or variance. Let $S=X+Y+Z$. Only $000$ gives $S=0$; each other allowed triple gives $S=2$. Direct calculation givesThe same variance follows from the variance of a sum: each Bernoulli distribution has variance $1/4$, and pairwise independent random variables have zero cross covariances. Linearity of expectation gives the expected value $3/2$ even without independence.

For comparison, the sum $T$ of three mutually independent fair bits has the binomial distribution $\mathrm{Binomial}(3,1/2)$:Both sums have identical expected values and variances, but $S$ never takes the values one or three. Even their third moments differ: $\mathbb{E}[S^3]=6$, whereas $\mathbb{E}[T^3]=27/4$. Pairwise independence preserves these first two sum summaries while allowing a different joint probability distribution and a different sum law. The calculation is an exact finite example.

Use the usual assumption that the two die scores are independent random variables. A fair score has expected value $7/2$ and variance $35/12$. Linearity of expectation and the variance of a sum therefore giveCount the ordered pairs of scores to obtain the probability mass functionsOn these attainable probability supports, the maxima occur at $x=7$ and $y=0$, each with probability $1/6$; the minima occur at $x=2,12$ and $y=-5,5$, each with probability $1/36$. Outside the respective probability support, the mass is zero.

They are not independent: $Y=0$ implies equal die scores and hence $X$ is an even number, so $P(X=7,Y=0)=0$, whereas $P(X=7)P(Y=0)=1/36>0$. In fact $\mathrm{Cov}(X,Y)=\mathrm{Var}(S_1)-\mathrm{Var}(S_2)=0$: this is an example of uncorrelated random variables that are dependent.

Write $p=p(n)$ and let $T$ be the triangle count in a binomial random graph. For every three-element set $S$ of vertices, let $I_S$ be the indicator random variable that its three edges are present. ThenFor two distinct triples $S,R$, their indicator random variables are independent random variables unless they share an edge. Sharing just one vertex still leaves the sets of relevant edges disjoint. If they share an edge, their union has five edges, and thereforeThere are $\left(\genfrac{}{}{0ex}{}{n}{2}\right)\left(\genfrac{}{}{0ex}{}{n-2}{2}\right)$ unordered pairs of distinct triangles in a graph sharing an edge: choose that edge, and then choose their two additional vertices. The variance of a sum consequently gives the exact formulaFor sufficiently large $n$, the hypothesis $np\to \infty$ ensures $p>0$, so $\mu >0$. Dropping negative terms and simplifying the binomial coefficients,Here $n^{2}p=n(np)\to \infty$ as well. The event $T\ge 2\mu$ implies $|T-\mu |\ge \mu$. Applying the Chebyshev inequality from part (i) gives the requested conclusion:Thus the triangle count is concentrated around its expectation throughout this range of the binomial random graph.

The autocovariance vanishes beyond lag $q$. For an ordinary consecutive sum, variance of a sum givesThe last sum is finite. For $h\ge 0$, $\gamma (h)={\sigma }^2{\sum }_{j=0}^{q-h}{\theta }_j{\theta }_{j+h}$. Counting all coefficient pairs givesFor the odd-indexed sample the lag-$h$ autocovariance is $\gamma (2h)$, so the same finite-sum argument gives ${\sum }_h\gamma (2h)$. Only coefficient pairs of the same parity contribute. If $E={\sum }_{j\mathrm{even}}{\theta }_j$ and $O={\sum }_{j\mathrm{odd}}{\theta }_j$, the odd-subsample limit isThis is the odd-subsample long-run variance of a moving average. Equivalently it is $[f_X(0)+f_X(1/2)]/2$ in the cycles convention. Under the printed invertibility assumption and positive noise variance, the polynomial is nonzero at both $1$ and $-1$, so both limits are positive. The same formulas also hold without invertibility, when cancellations can make a limit zero.

Let $X_i=1_{A_i}$ be the indicator random variable of $A_i$. Then $X={\sum }_i{X}_i$, so linearity of expectation givesUsing variance of a sum andwe obtain

For the circular array, let $X_i$ indicate that bulbs $i$ and $i+1$ are both on, with indices read modulo $n$. Then $\mathbb{E}{X}_i=p^2$. Non-neighbouring indicators are independent, whileThere are $n$ individual terms and $2n$ ordered neighbouring pairs in the double covariance sum, so

The event $B$ is exactly $\{X\ge 1\}$. If $p=n^{-0.6}$, Markov inequality givesIf $p=n^{-0.4}$, then $B^c=\{X=0\}$ implies $|X-\mathbb{E}X|\ge \mathbb{E}X$. By Chebyshev inequality,Therefore $\boxed{\mathbb{P}(B)\to 1}$ in the second regime.

For random variables with finite second moments, the variance of a sum isNo independence assumption is needed.

Write $A_i=Y_{i-1}{Y}_i$, so $S_n={\sum }_{i=1}^n{A}_i$. Each product has mean one, and its variance isAdjacent products share one factor, giving covariance one by part (a)(iii). Products whose indices differ by at least two involve disjoint independent random variables, so their covariance is zero. There are $n-1$ adjacent pairs. By the variance of a sum,

The random variable $T$ is the sum $E+(-S)$. The linearity of expectation givesMultiplication by $-1$ reverses the mean but preserves the variance. Under the independence assumption used in part (b), the variance of a sum givesThus both predictions agree with the direct integrals. For the actual elapsed time, adding twenty-five changes the mean to twenty-five minutes and leaves the variance at $1/6$ minute squared.

Without independence, the correct expression is $\mathrm{Var}(T)=1/6-2\mathrm{Cov}(E,S)$ when both marginals are uniform. This explains why independent endpoint errors must be part of the intended model rather than a consequence of the display format.

For finite second moments, the general variance of a sum formula isEach distinct unordered pair appears once in the second sum and twice when the full square is expanded. No independence assumption is needed.

Assume finite second moments and write $Z_i=X_i-\mathbb{E}{X}_i$. Expanding the squared centered sum givesThis variance of a sum identity does not require independence; the covariance term records the contribution that would otherwise be lost.

Put $Z_i=Y_{i-1}{Y}_i$ for $1\le i\le n$. Independence of the underlying exponentials gives $\mathbb{E}{Z}_i=1$ andBy the covariance of overlapping independent products, adjacent terms have covariance one. Terms separated by at least two indices use disjoint independent factors, so their covariance is zero. There are $n-1$ adjacent pairs. Linearity of expectation and the variance of a sum formula therefore yieldIn particular, the products themselves are not independent merely because the original $Y_i$ are.