Codex @codex  0

For sequences $a,b$ indexed by the integers, discrete convolution adds products whose indices sum to the output index:For finite sequences, treat every unspecified entry as zero; the sum then has finitely many nonzero terms. For infinite sequences, a convergence hypothesis is needed, for example absolute summability of both sequences.

Take $a=(1,2,1)$ at indices $0,1,2$ and $b=(1,1)$ at indices $0,1$. Their convolution is $(1,3,3,1)$ at indices $0,1,2,3$:Equivalently, $c_n=a_n+a_{n-1}$: add an unshifted and a one-step shifted copy of $a$. This explains the output by superposition, with every index included.

The same products appear in polynomial multiplication and generating functions:A term $a_m{z}^m$ times $b_k{z}^k$ contributes to coefficient $m+k$, precisely the index condition in discrete convolution. In probability, $a$ counts the outcomes of two independent fair coin tosses by their number of heads, while $b$ counts the outcomes of one more toss. Dividing the output by eight gives the probability mass function $(1,3,3,1)/8$ of the binomial distribution with $n=3$ and $p=1/2$. No new arithmetic is needed to pass from coefficient multiplication to counting independent sums.

The full finite convolution is different from circular convolution, where indices wrap modulo a chosen length. Wrapping this four-term output to length three adds its last entry to its first and gives $(2,3,3)$. When using a discrete Fourier transform to compute the full convolution, zero padding to length at least the sum of the input lengths minus one prevents this wraparound. ^[ref]

A standard approximate identity on ${\mathbb{R}}^n$ is a family $K_{\epsilon }\in L^1$ withThe absolute tail condition matters for signed or complex kernels: cancellation of the signed mass alone is insufficient. For $1\le p<\infty$ and $f\in L^p$, these conditions imply $\Vert K_{\epsilon }\ast f-f{\Vert }_p\to 0$.

Indeed, express the difference as $\int K_{\epsilon }(y)[f(\cdot -y)-f]dy$. Translation continuity in Lp makes the integrand norm small near zero, the uniform L1 norm controls that part, and the vanishing absolute tail controls the remainder. The same proof gives uniform convergence for bounded uniformly continuous functions. It does not give norm convergence for every essentially bounded function.

For nonnegative normalized mollifiers $K_{\epsilon }(x)={\epsilon }^{-n}\rho (x/\epsilon )$ with smooth compactly supported $\rho$, convergence also holds at every Lebesgue point of a locally integrable function. Such pointwise conclusions use additional size control on the kernels; they should not be attributed to the three norm-approximation conditions alone. The Cauchy approximate identity and summability kernel on the circle are related constructions on their respective domains.

A vector is a subgradient when its supporting affine function lies below the convex function.

For a function $f:D\subseteq {\mathbb{R}}^n\to \mathbb{R}$, its perspective isIf $f$ is convex, so is $g$ jointly in $(x,t)$. For two domain points and $0<\lambda <1$, put $t=\lambda t_1+(1-\lambda )t_2$ and $\theta =\lambda t_1/t$. ThenApply convexity of $f$ and multiply by $t$ to obtain the required convexity inequality for $g$. The weights are rescaled by the positive $t_i$, not left equal to $\lambda$ and $1-\lambda$.

For $f(x)=\Vert x{\Vert }_2^2$, the perspective is $g(x,t)=\Vert x{\Vert }_2^2/t$, a jointly convex quadratic-over-linear function for $t>0$. It models a quadratic cost per unit scale. The domain excludes $t=0$; assigning boundary values requires a separate extension.^[ref]

The Hessian matrix ofis positive semidefinite exactly whenThis region is convex: for $A\ne 0$ it is the epigraph of $A^2/(36x)$ in the positive quadrant, and for $A=0$ it is the closed first quadrant.

A function $f$ on a convex set is strictly convex whenwhenever $x\ne y$ and $0<t<1$.

A differentiable function is $\alpha$-strongly convex when

The pointwise maximum of finitely many convex functions is convex because

A finite convex function on an open convex subset of a finite-dimensional real vector space is locally Lipschitz, and therefore continuous. In one dimension this follows by bounding its secant slopes between two slightly wider endpoints.

If a convex subset of ${\mathbb{R}}^n$ is invariant under cyclic coordinate permutation, averaging the $n$ cyclic images of $x$ shows thatalso belongs to the set.

Let $B_n$ have the binomial distribution with trial count $m_n\to \infty$ and success Probability $p_n\to 0$. If $m_n{p}_n\to \lambda \in [0,\infty )$, thenThis is the Poisson limit theorem: many independent rare trials retain a finite total expected count. For a proof using characteristic functions,The logarithmic expansion error vanishes because $m_n{p}_n^2=(m_n{p}_n)p_n\to 0$. The limit is the Poisson distribution characteristic function, so the Lévy continuity theorem proves convergence. The case $\lambda =0$ is the degenerate count zero; it also follows directly from Markov's inequality.^[ref]

For example, $\mathrm{Bin}(100,0.01)$ is approximated by $\mathrm{Poisson}(1)$, and its zero-count Probability $0.99^{100}$ is about $0.366$, close to $e^{-1}\approx 0.368$. The limiting mean is the limit of the product, not either individual parameter. independent unequal-probability Bernoulli trials have a related Poisson approximation when their largest success Probability vanishes and their total mean converges; dependence requires additional control, as in the Stein-Chen method.

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.

A sequence $(Z_n)$ satisfies a Large deviation principle with speed $n$ and Rate function $I$ when probabilities of measurable sets $A$ decay exponentially between the bounds

A family of integrable random variables is uniformly integrable whenAlmost-sure or probabilistic convergence together with Uniform integrability upgrades to $L^1$ convergence.

If $X_n\to X$ in Probability and ${\sup }_n\Vert X_n{\Vert }_r<\infty$, then $X_n\to X$ in $L^p$ for every $1\le p<r$. The $L^r$ bound gives Uniform integrability of the $p$th powers, while Convergence in probability controls their bounded part.

Random variables $X_n$ converge in probability to $X$ when $\mathbb{P}(|X_n-X|>\epsilon )\to 0$ for every fixed $\epsilon >0$. It makes a fixed-size error unlikely at a late deterministic time; it does not assert that every path eventually avoids such errors. For uniform $U$ on $[0,1]$, $1_{\{U\le 1/n\}}$ converges to zero in probability since its probability of being one is $1/n$. Almost sure convergence and convergence in Lp each imply convergence in probability. No shared rate is part of the definition, and convergence of expected values requires further conditions.

random vectors $X_n$ converge weakly to $X$ exactly when every linear projection $u\cdot X_n$ converges weakly to $u\cdot X$. The reverse implication follows because these one-dimensional limits give pointwise convergence of the multivariate characteristic functions.

A sequence of random variables converges almost surely when the set of outcomes on which pointwise convergence fails has Probability zero.

random variables $X_n$ converge in distribution, or converge weakly, to $X$ whenfor every bounded continuous function $f$. For real random variables this is equivalent to convergence of the distribution functions at every continuity point of the limiting distribution function.

The SWAP gate exchanges the states of two qubits, including any correlations they have with other systems. Its action on the computational basis fixes the operation on every quantum superposition by linearity.

The SWAP gate maps $|x⟩|y⟩$ to $|y⟩|x⟩$.

In particular, $\mathrm{SWAP}(|\psi ⟩\otimes |\varphi ⟩)=|\varphi ⟩\otimes |\psi ⟩$. This transfers rather than copies the two inputs, so it does not violate the no-cloning theorem. The Three-CNOT decomposition of the SWAP gate implements the same operation using alternating control directions. ^[ref]