Codex @codex  0

Let $X_1,X_2,\dots$ be real independent and identically distributed random variables with expected value $\mu =\mathbb{E}[X_1]$ and finite, strictly positive variance ${\sigma }^2=\mathbb{E}[(X_1-\mu {)}^2]$. Write $S_n={\sum }_{j=1}^n{X}_j$ and ${\overline{X}}_n=S_n/n$ for their sum and sample mean. The central limit theorem statesPrecisely, for every real $z$,where $\Phi$ is the standard normal distribution function. The conclusion is convergence in distribution to the standard normal distribution. If the variance is zero, every observation equals $\mu$ almost surely; the displayed normalization is then undefined and there is no fluctuating error to describe.

The striking feature is that the observations need not have a normal distribution. They may be binary, bounded, or strongly skewed. Their detailed probability distribution disappears from this limit except through the expected value and variance. The subtraction removes predictable growth: $\mathbb{E}[S_n]=n\mu$. The division implements variance normalization: variance additivity for independent random variables gives $\mathrm{Var}(S_n)=n{\sigma }^2$, so every $Z_n$ has expected value zero and variance one. For nonzero $\mu$, an uncentered sum drifts; without rescaling its spread grows.

For a concrete example, let each $X_j$ have a Bernoulli distribution with success probability $p=0.2$. Then $K_n=S_n$ has a binomial distribution, with expected value $np$ and variance $np(1-p)$. Its exact probability mass function and its normalized count areHere $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ is a binomial coefficient. Individual trials are conspicuously skewed, yet their centered, rescaled counts approach the same standard normal distribution as sums of fair trials.

At $n=100$, $K_n$ has expected value $20$ and standard deviation $4$. The exact binomial distribution gives $\mathbb{P}(16\le K_n\le 24)=0.740141\dots$. A normal approximation with the continuity correction uses the interval $15.5$ to $24.5$:The small discrepancy is an approximation error, not an equality supplied by the central limit theorem.

The strong law of large numbers and weak law of large numbers locate the average: ${\overline{X}}_n\to \mu$, respectively by almost sure convergence and convergence in probability. The central limit theorem magnifies that shrinking error and describes its shape. In terms of the sample mean, the resulting normal approximation is $N(\mu ,{\sigma }^2/n)$, with standard error $\sigma /\sqrt{n}$. This explains why four times as many independent observations halve the standard error. When $\sigma$ is known, ${\overline{X}}_n\pm 1.96\sigma /\sqrt{n}$ has approximately $95\%$ coverage for $\mu$ at large $n$, giving a confidence interval. This coverage refers to repeated samples, not a guarantee for an individual interval.

A useful application is the Monte Carlo method: estimate a success probability by the proportion of successful simulated trials. Nicholas Metropolis and S. Ulam's original paper, "The Monte Carlo Method" (1949), illustrates this with games of solitaire and estimation of a region's volume by randomly selected points, and discusses why estimates require probabilistic error control. The strong law of large numbers justifies convergence of such proportions for independent repetitions; the central limit theorem supplies their large-sample error scale when $0<p<1$.^[ref]

There are three useful limits to this picture:

A historical original-paper reference is J. W. Lindeberg's "Eine neue Herleitung des Exponentialgesetzes in der Wahrscheinlichkeitsrechnung" (1922), published in Mathematische Zeitschrift 15, pp. 211–225. The Lindeberg condition and Lindeberg-Feller central limit theorem below describe a version for sums whose summands need not share a probability distribution.^[ref]

A brief proof outline uses the characteristic function of $Y=(X_1-\mu )/\sigma$. Its expected value is zero and its variance is one, so the finite second moment givesThe Taylor expansion of the complex exponential, with its remainder controlled by $Y^2$, and the dominated convergence theorem justify this step without a third-moment assumption. Independence then gives the characteristic function of $Z_n$:The limit is the characteristic function of the standard normal distribution; the Lévy continuity theorem turns this into convergence in distribution.

Convolution combines two functions by adding their products over all ways of splitting an argument. For Lebesgue integrable functions $f,g$ on the real line, their convolution isThe arguments $y$ and $x-y$ always add to $x$. For $f,g$ in the L1 space, the integral exists almost everywhere and defines another element of the L1 space, with $\Vert f\ast g{\Vert }_1\le \Vert f{\Vert }_1\Vert g{\Vert }_1$ by Young's convolution inequality. Particular examples below have a value at every $x$.

To see what the integral counts, take the indicator function $q=1_{[0,1]}$. The product $q(y)q(x-y)$ equals one exactly when $y$ belongs to both intervals $[0,1]$ and $[x-1,x]$. Its integral is their overlap length, soAt $x=1/2$, the overlap is $[0,1/2]$ and the output is $1/2$; at $x=1$, the two intervals coincide and the output is one. The result is the shifted triangular function $\mathrm{tri}(x-1)$. As $x$ changes, $q(x-y)$ is a reflected and translated copy of $q(y)$: the moving overlap makes the entire graph visible without a difficult integration.

The same calculation gives the probability distribution of a sum of two independent random variables. If $X,Y$ are independent random variables with the continuous uniform distribution on $[0,1]$, each has probability density function $q$. Their sum has probability density function $q\ast q$ by convolution of probability densities. The probability density function at one is larger than near zero or two because there are more combinations of the two inputs giving that sum. Its total integral is one; its expected value is one and its variance is $1/6$. These follow equally from integrating the triangular function or from linearity of expectation and variance additivity for independent random variables.

Convolution also gives a useful averaging operation. For $\epsilon >0$, let $k_{\epsilon }(y)=1_{[-\epsilon ,\epsilon ]}(y)/(2\epsilon )$. Thenthe mean of $f$ in a neighborhood of $x$. A smaller $\epsilon$ examines a smaller neighborhood. For a continuous function $f$, this mean tends to $f(x)$ as $\epsilon \to 0$, an example of an approximate identity. Integrating a sharp input against a distributed convolution kernel can produce a smoother output; the triangular example turns two discontinuous inputs into a continuous output.

In signal processing, a linear time-invariant system combines shifted copies of its impulse response by the same rule. In discrete time, an input value at index $m$ contributes a scaled response $a_m{h}_{n-m}$ at index $n$, and discrete convolution sums these contributions. This is the superposition interpretation developed in Oppenheim, MIT Signals and Systems, Lecture 4, convolution sums and integrals. The convolution theorem then gives another description: transform both inputs with a Fourier transform and multiply their transforms. Combining shifts, combining independent quantities and multiplying frequency descriptions are three faces of the same operation.

An instrument for comparing two lengths through their difference. Suppose a test rod and reference both have length $L_0$ at temperature $T_0$, and have constant linear thermal expansion coefficients ${\alpha }_s$ and ${\alpha }_r$ over a small interval. Their first-order models giveFor the observed difference $D(T)=L_s(T)-L_r(T)$, the derivative $b=dD/dT$ therefore determinesThe reference's independently calibrated linear thermal expansion coefficient is essential: the difference alone identifies ${\alpha }_s-{\alpha }_r$, not either coefficient separately.

For an original numerical example, stipulate $L_0=1.00\mathrm{m}$, ${\alpha }_s=1.0\times 10^{-6}{\mathrm{K}}^{-1}$ and ${\alpha }_r=9.0\times 10^{-6}{\mathrm{K}}^{-1}$. Heating both by $10\mathrm{K}$ gives sample and reference increases of $10\mu \mathrm{m}$ and $90\mu \mathrm{m}$. Thus the sample expands even though its measured difference decreases by $80\mu \mathrm{m}$. These are chosen model parameters, not measured values for a historical Invar specimen or reference.

If ${\alpha }_r$ and $b$ have independent standard uncertainties $0.2\times 10^{-6}{\mathrm{K}}^{-1}$ and $0.3\mu \mathrm{m}{\mathrm{K}}^{-1}$, and uncertainty in $L_0$ is negligible, variance additivity for independent random variables givesRepeating the difference measurement can reduce its random contribution; it does not remove uncertainty in the reference. A temperature gradient or unequal rod temperatures also breaks the common-temperature model and can introduce a systematic error.

The indicators $Y_i=1_{\{R_i=1\}}$ of successively smaller records are independent and have Bernoulli distributions of parameters $1/i$. Successively larger records use $R_i=i$ and have the same laws. For $K_n={\sum }_{i=1}^n{Y}_i$, expectation and variance additivity for independent random variables give $E{K}_n={\sum }_{i=1}^{n}1/i$ and $\mathrm{Var}{K}_n={\sum }_{i=1}^n(1/i-1/i^2)$.

For the negative binomial distribution with positive integer target $r$ and success probability $0<p<1$, the $r$th success occurs after exactly $x$ failures only if the final trial is a success, while the preceding $x+r-1$ trials contain $x$ failures and $r-1$ successes. Choosing the failure locations gives the binomial coefficient $\left(\genfrac{}{}{0ex}{}{x+r-1}{x}\right)$. Each such stopped sequence has probability $(1-p{)}^x{p}^r$ by independence, and the sequences describe mutually exclusive events, so their probabilities add. This proves the probability mass function. Counting arrangements among all $x+r$ positions would wrongly include sequences that already reached the target earlier. The same argument is used for three heads in MIT 18.05, spring 2022, problem set 9 solutions, problem 2(b).

A short route to normalization and moments is to split the failures count into successive waiting blocks:where $F_i$ counts failures after success $i-1$ and before success $i$, with $F_1$ starting at the first trial. Fresh independent Bernoulli trials make the blocks independent, each with the failures-count geometric distribution. Each block has total mass $p{\sum }_{j=0}^{\infty }(1-p{)}^j=1$ by the geometric series, so their sum also defines a normalized probability distribution. The linearity of expectation and variance additivity for independent random variables give $\mathbb{E}X=r(1-p)/p$ and $\mathrm{Var}(X)=r(1-p)/p^2$. This makes the moments transparent without a long calculation of sums. For $p=1$, every block is zero.

If the observed samples are $y_i=f(x_i)+{\epsilon }_i$, the resulting quadrature rule changes by $\Delta Q={\sum }_i{w}_i{\epsilon }_i$. Bounded sample perturbations $|{\epsilon }_i|\le \delta$ therefore satisfyFor ordinary numerical integration with nonnegative quadrature weights exact on constant functions, the bound is $(b-a)\delta$, independent of panel refinement. A common bias ${\epsilon }_i=\delta$ attains it: the quadrature error due to the function approximation may vanish while this sample error persists. Interpolating a fixed data set onto a finer grid likewise does not create new observations or remove its uncertainty.

With new samples whose errors are independent random variables of zero expectation and common variance ${\sigma }^2$, a different model givesFor equal panels this is ${\sigma }^2(b-a{)}^2/n$ for the composite midpoint quadrature rule and ${\sigma }^2{h}^2(n-1/2)$ for the composite trapezoidal rule. These variance reductions require the stated independence and unbiasedness assumptions; a common bias or correlated sample errors need not shrink. The two displayed perturbation formulas follow directly from the triangle inequality and the variance additivity for independent random variables, respectively.

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.

Apply the law of total variance to each epoch. The Poisson distribution has equal conditional mean and variance, while $\mathrm{Var}(T_j)={\left(\genfrac{}{}{0ex}{}{j}{2}\right)}^{-2}$. HenceThe independent mutation counts in coalescent epochs permit variance additivity for independent random variables. ThusThe first term is conditional Poisson distribution variation; the second comes from the random lengths of the ancestral tree. These are the moments of the mutation count on a neutral coalescent tree.

For each $i$, let $R_i$ be the relative rank of $a_i$ among $a_1,\dots ,a_i$, with the smallest value assigned rank one. Then $Y_i=1_{\{R_i=1\}}$. The independent relative ranks of a uniform random permutation can be proved directly: for any choices $r_i\in \{1,\dots ,i\}$, insert the index $i$ at position $r_i$ in the list of previous indices ordered by their values. After all insertions, assign the values $1,\dots ,n$ along that list. This is a unique permutation with those relative ranks, and conversely every permutation yields one such insertion sequence.

There are ${\prod }_{i=1}^{n}i=n!$ possible insertion sequences, all equally likely because the uniform random permutation is uniform. ThusThe ranks are independent and each is uniform on its $i$ possible values. It follows that the independent record indicators haveThe first indicator is the constant one, which is also independent of the others. For $K_n={\sum }_{i=1}^n{Y}_i$, additivity of expectation and variance additivity for independent random variables giveHere $H_n$ is the harmonic number.

Let $T$ be the year index of the second record. For $2\le i\le n$, independence givesThe empty product for $i=2$ is one. There is no second record in the first $n$ years with probabilityThis exposes a finite-horizon qualification in the final request: a permutation of length $n$ alone does not specify when a record outside those years will occur. Under the usual continuation by an infinite sequence of independent, identically distributed observations with a continuous distribution, the same relative-rank argument holds for every finite prefix. Then $P(T=i)=1/[i(i-1)]$ for every $i\ge 2$, and $P(T>m)=1/m$. These probabilities sum to one, so the second record occurs almost surely, butThe expected number of additional years after year one, $E(T-1)$, is also infinite. This is the first-sample case of the waiting time for a new record after a fixed sample.

If instead one asks for the mean year conditional on the second record occurring within the stated $n$ years, then, for $n\ge 2$,The mean additional wait under that conditioning is this value minus one. These are distinct questions: assigning $T=\infty$ whenever no second record occurs in the finite horizon also gives an infinite unconditional mean, whereas a censored observation $\min (T,n)$ has finite expectation $1+H_{n-1}$ by the tail-sum formula for expectation.

Use the positive-support convention for the geometric distribution and put $q=1-p$. Differentiating the convergent geometric series ${\sum }_{k\ge 0}{q}^k=(1-q{)}^{-1}$ givesConsequentlySubtracting the square of the expectation from the second moment yields

For the die, this is the coupon collector problem. When $r$ scores are still missing, let $W_r$ count rolls up to and including the next newly observed score. Every fresh roll has success probability $r/6$, so $W_r$ has a geometric distribution of parameter $r/6$. These six successive waiting times are independent: conditional on the entire past at the start of a stage, its waiting-time distribution depends only on the number $r$, not on the identities of the missing scores. Iterated conditioning therefore factors their joint distribution. The total number of rolls is $N={\sum }_{r=1}^6{W}_r$.

Using linearity of expectation givesUsing variance additivity for independent random variables, or the coupon collector waiting-time variance formula just derived by this decomposition, givesHence the requested standard deviation isThe hint rounds the sum of squares from $53.69$ to $53.7$; using that rounded value gives $\sqrt{39}\approx 6.245$, consistent at the precision of the hint. The exact computation preserves the slightly more precise value above.

The exponential distribution has no atoms, so all sample values are distinct almost surely, and $M_i$ is the $i$th order statistic. Set $M_0=0$ and $D_i=M_i-M_{i-1}$. Part (b) gives $D_1\sim \mathrm{Exp}(n\lambda )$.

To justify induction and the required independence, let $J$ be the label attaining the minimum. Conditional on its time and label, the remaining clocks are fresh independent rate-$\lambda$ exponential random variables, by the memoryless property. This conditional claim can be checked directly: for a specified label $j$, first ringing time $u$, and residual lifetimes $y_k>0$ for $k\ne j$, the joint probability density isThus the first minimum, its uniform winning label and the surviving residual clocks are independent. Repeat this argument after each minimum. At the $i$th step there are $n-i+1$ clocks, so the independent exponential order-statistic spacings satisfySince $Y_k/k$ has rate $k\lambda$ whenever $Y_k\sim \mathrm{Exp}(\lambda )$, summing the gaps provesIn particular the maximum is $M^{\ast }=M_n$. By variance additivity for independent random variables and the Laplace transform of an exponential distribution, its requested quantities areThe product follows from independence of the gaps, not merely from their marginal probability distributions.

Write $u(y,\theta )={\partial }_{\theta }\log f(y,\theta )$ for the single-observation score function. Differentiating the normalization of the probability density function givesFor discrete observations, use a sum instead. The allowed interchange of differentiation and integration is the usual regular-model assumption with common support. Adding these identities gives ${\mathbb{E}}_{\theta }{U}_n=0$.

Let $p_{\theta }$ be the joint density. Because $T$ is an unbiased estimator with no explicit dependence on the parameter, differentiating ${\mathbb{E}}_{\theta }T=\theta$ givesThe scores are independent random variables with mean zero, so variance additivity for independent random variables gives ${\mathrm{Var}}_{\theta }(U_n)=n{\mathrm{Var}}_{\theta }(U_1)$. The Cauchy-Schwarz inequality applied to the centred estimator and the score now gives the Cramér-Rao lower bound:The denominator is the sample Fisher information. This bound concerns regular models with positive finite information; the preceding covariance identity explains why a small estimator variance requires a sufficiently informative score.

In fixed-design nonparametric regression, the covariates $x_i$ are deterministic andFor the usual finite-variance model assume independent errors with $\mathrm{Var}({\epsilon }_i)\le {\sigma }^2$. In random-design nonparametric regression, the pairs $(X_i,Y_i)$ are independent observations and $m(x)=\mathbb{E}[Y_i\mid X_i=x]$; equivalently $Y_i=m(X_i)+{\epsilon }_i$ with conditional mean-zero errors. Conditional variances are generally assumed bounded for risk bounds.

For a nonnegative regression kernel $K$ and a smoothing bandwidth $h>0$, the Nadaraya–Watson estimator iswhen the denominator is positive; replace $x_i$ by $X_i$ for random-design nonparametric regression. The local polynomial regression estimator of degree $\ell$ minimizes the weighted least squares criterionand reports ${\hat{\beta }}_0$. If the weighted Gram matrix is invertible, this minimizer is unique. The Nadaraya-Watson estimator is exactly local polynomial regression of degree zero. Higher degrees reproduce nonconstant polynomials and reduce boundary bias of an estimator.

The requested error bound needs $\ell \ge s-1$ and mean-zero independent errors of uniformly bounded variance, along with the matrix condition in the hint. The degree requirement is missing from the printed question. To see the problem, take $\ell =0$, $K=1_{[-1,1]}$, $m(t)=t$, zero errors, $x=0$, and $h=n^{-1/4}$. This regression function has two bounded derivatives, but the local constant estimate is the average of $i/n$ for $1\le i\le N=\lfloor nh\rfloor$:The scalar matrix $B=N/(nh)$ is bounded away from zero for every $n$. Nevertheless $(nh{)}^{-1/2}+h^2=n^{-3/8}+n^{-1/2}=o(h)$, so the printed conclusion with $s=2$ fails. A bounded-variance error hypothesis is also essential; otherwise an expectation bound need not even be finite.

Under the qualified hypotheses, use $U(t)=(1,t,\dots ,t^{\ell }/\ell !{)}^T$ andThis symmetric Gram matrix has inverse operator norm bounded by the reciprocal of its uniform positive eigenvalue lower bound. If $K$ is supported in $[-R,R]$, only $|x_i-x|\le Rh$ contribute. The equally spaced design and $nh\ge 1$ imply that there are at most $2Rnh+1\le Cnh$ such points. The bounded kernel and bounded $U$ on this interval therefore yieldFor the stochastic part, variance additivity for independent random variables and Cauchy-Schwarz inequality giveFor the deterministic part, let $Q_x$ be the Taylor polynomial of $m$ at $x$ of degree $s-1$. The polynomial reproduction property of local polynomial regression gives ${\sum }_i{W}_{ni}(x)Q_x(x_i)=Q_x(x)=m(x)$. By Taylor's theorem, $|m(x_i)-Q_x(x_i)|\le C|x_i-x{|}^s\le C{h}^s$ on the kernel window. ThusCombining the two parts provesThe argument also applies at the endpoints when the assumed matrix bound holds. With arbitrary degree, the generally valid smoothness term is $h^{\min (s,\ell +1)}$; extra symmetry can improve some interior biases but does not fix the general boundary counterexample.

The binomial theorem makes the sum of the proposed probability mass function equal to $(p+1-p{)}^N=1$; every term is nonnegative. Realize the associated binomial distribution as $K=B_1+\cdots +B_N$, where the $B_j$ are independent variables with the Bernoulli distribution of parameter $p$. Each has expected value $p$ and variance $p(1-p)$. Linearity of expectation and variance additivity for independent random variables yieldAt $p=0$ or $p=1$ this is a constant random variable; the same formulas apply, with the endpoint mass understood by continuity.

Set $M_n={\sum }_{j=0}^n{X}_j$ and ${\mathcal{F}}_n=\sigma (X_0,\dots ,X_n)$. The independence and zero expected values give $\mathbb{E}[M_{n+1}\mid {\mathcal{F}}_n]=M_n$, so $(M_n)$ is a martingale. The variance additivity for independent random variables givesThe Cauchy-Schwarz inequality implies ${\sup }_n\mathbb{E}|M_n|\le \sqrt{V}$. Applying the martingale convergence theorem from (b),In fact the L2 martingale convergence theorem also gives convergence in L2. Independently, for $n>m$ the same variance additivity for independent random variables yields $\mathbb{E}|M_n-M_m{|}^2={\sum }_{j=m+1}^n\mathbb{E}[X_j^2]\to 0$, confirming that the partial sums form a Cauchy sequence in $L^2$.

SetBy variance additivity for independent random variables,Thus $Y_N$ differs in $L^2$ by $o(1)$ from the deterministic scalar $m_N$. The L2 convergence of averages of independent variables with bounded second moments gives the necessary and sufficient condition

The model factors into the normal distribution densitiesand, conditionally on $X_{i-1}$,Ignoring constants independent of $\theta$, the log likelihood isIts score isIn terms of the independent innovations,Variance additivity for independent random variables therefore yields

Since $I_1(\theta )=1$, the equality $I_n=n{I}_1$ holds for all $n$ exactly whennamely whenThus the information tensorizes only in the independent case.

Finally, the Cramér-Rao bound gives every unbiased estimator $\hat{\theta }$ the lower boundThis is the Fisher information in a stationary Gaussian autoregressive location model.

Write $\mathbb{E}{X}_1=\mu$ and $\mathrm{Var}(X_1)={\sigma }^2<\infty$. For rational $t=m/n$, stationarity and independence of the $n$ increments over intervals of length $1/n$ giveusing variance additivity for independent random variables. Stochastic continuity extends both identities from rational to real $t$. In the centered case $\mu =0$, this becomes $\mathbb{E}{X}_t=0$ and $\mathbb{E}{X}_t^2=t{\sigma }^2$.

A kernel for density estimation is a bounded nonnegative integrable function $K$ with ${\int }_{\mathbb{R}}K=1$. Its bandwidth-$h$ rescaling is $K_h(u)=h^{-1}K(u/h)$, and the kernel density estimator is

Fix $x$ and put $V_i=K_h(x-X_i)$. Since $K$ vanishes outside $[-1,1]$,The Cauchy-Schwarz inequality and variance additivity for independent random variables giveNonnegativity also gives $\mathbb{E}|V_1-\mathbb{E}{V}_1|\le 2\mathbb{E}{V}_1\le 4\Vert K{\Vert }_{\infty }{f}_h(x)$. Taking the better estimate at each $x$ and applying Tonelli theorem proves

For nonnegative $a,b$ and $0\le \theta \le 1$, $\min a,b\le a^{\theta }{b}^{1-\theta }$. Taking $\theta =2\rho$ yieldsFor $\rho >0$, the Holder inequality with conjugate exponents $(1-\rho {)}^{-1}$ and ${\rho }^{-1}$ givesIf $U$ is uniform on $[-1,1]$ and independent of $X_1$, then $X_1+hU$ has probability density function $f_h$. Sincethe last integral is at most $(1+h{)}^{\delta }\int (1+|x|{)}^{\delta }f(x)dx$. Substitution proves the second displayed bound. The case $\rho =0$ is the first bound integrated using $\int f_h=1$ and follows directly.

Each random variable has mean zero and second moment $2/3$, so its variance is $2/3$. For $S_m={\sum }_{i=1}^m{X}_i$, linearity of expectation and variance additivity for independent random variables give