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 positive-integer geometric distribution $P(N=j)=p{q}^{j-1}$ with $q=1-p$, the capped time has masses $p{q}^{j-1}$ for $1\le j<k$ and $q^{k-1}$ at $k$. The last mass includes all later arrivals, not only $N=k$. Its probability generating function and expected value areThe expectation follows either by differentiating the PGF or summing the tail probabilities up to $k$.

A capture-recapture model is a statistical model for repeated observations of identifiable individuals, including those missed on some occasions. A closed-population capture-recapture model estimates a fixed population cardinality; models allowing individuals to enter or leave can instead describe survival and recruitment. The sampling assumptions determine which likelihood function is appropriate.

For the two-sample closed-population capture-recapture model, condition on the sample sizes $M$ and $C$. If the second sample selects $C$ distinct individuals from $N$ by simple random sampling, then the overlap $R$ has the hypergeometric distribution:Here $r$ is an integer and the probability mass function is zero outside these bounds. The binomial coefficients count choices of $r$ marked and $C-r$ unmarked individuals, divided by all equally likely size-$C$ subsets. The hypergeometric distribution has expected valueEquating the observed overlap with this expected value gives the Lincoln-Petersen estimator. The underlying sampling without replacement, probability mass function, and expected value are developed in Raymond P. Guiteras, MIT 14.30 hypergeometric distribution handout, §§1–4 and 8.

For the toy counts $M=20$, $C=25$, and $R=5$, hold the observations fixed and vary the unknown integer $N$. The likelihood function isValues below forty cannot contain the observed set union. Exact comparison of consecutive likelihoods gives two tied maximum-likelihood estimates, $N=99$ and $N=100$. The Lincoln-Petersen estimator returns $100$; the Chapman estimator returns $90$ and is a different rule for estimation.

The vertical scale is $L(N)/{\max }_{n\ge 40}L(n)$. This relative likelihood compares how well candidate statistical parameters explain the same observations; it is not a posterior probability. The displayed range $40\le N\le 300$ is only a plotting window. The likelihood function remains positive for every integer $N\ge 40$ and tends to zero as $N$ increases, so the curve has a continuing right tail. The data do not justify truncating statistical inference at three hundred. The conditional hypergeometric distribution formulation also appears in Louis-Paul Rivest and Mamadou Yauck, Small Sample Estimators for Two-way Capture Recapture Experiments, §3, equation (5).

Zero recaptures require care. With $R=0$ and positive $M,C$, the Lincoln-Petersen estimator has no finite ratio, but the capture-recapture model still gives a valid likelihood function:This likelihood function increases toward one as $N$ grows, so there is no finite maximum-likelihood estimate. For the same sample sizes twenty and twenty-five with zero overlap, forty-five distinct individuals would be observed. Lack of overlap supplies a lower bound but very weak information about large population cardinalities.

In more elaborate capture-recapture models, a first-recapture array $m_{ij}$ counts individuals released at occasion $i$ and next observed at $j$. A probability of survival ${\varphi }_j$ and a probability of detection $P_{j+1}$ contribute a no-observation continuation factor ${\varphi }_j(1-P_{j+1})$. The resulting likelihood function depends on both survival and detection; these probabilities need not be separately identifiable at the last observation interval. Missing-count EM for capture-recapture describes one way to fit such a model, and identifiability remains a separate issue from computing an estimator output.

A categorical distribution describes one trial with one of $k$ labelled outcomes and probabilities $p_1,\dots ,p_k$ summing to one. The labels need not be numbers or have an order. It is the single-trial building block of the multinomial distribution: $n$ independent draws with the same categorical distribution produce multinomial category counts.

For a trial choosing labels $A,B,C$ with probabilities $1/2,3/10,1/5$, the category-indicator random vector is $(1,0,0)$, $(0,1,0)$, or $(0,0,1)$. Its expected value is $(1/2,3/10,1/5)$; its components are dependent because exactly one is one. A numerical encoding of $A,B,C$ is a separate modelling choice: the category labels themselves do not define an arithmetic mean.

Assign each of $N\sim \mathrm{Pois}(\lambda )$ claims with independent category labels to one of finitely many categories with probabilities $p_i$. Conditional counts have a multinomial distribution with probability generating function $({\sum }_i{p}_i{z}_i{)}^N$. Averaging over $N$ gives $\exp (\lambda ({\sum }_i{p}_i{z}_i-1))={\prod }_i\exp (\lambda p_i(z_i-1))$. This proves independent category counts and supports discrete-severity compound Poisson distribution representations.

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.

An oven supplies a collimated caesium beam. State-selecting magnets precede and follow two coherent microwave interaction regions; a weak static magnetic field separates sublevels. The clock transition connects $F=3,m_F=0$ and $F=4,m_F=0$. Transferred atoms reach a heated ionizing collector. A detector scan identifies the resonance before locking.^[ref]

Here $F$ labels the total angular momentum and $m_F$ its projection. The selected pair is a two-level system inside a larger set of atomic energy levels; treating every oven atom as a prepared qubit would overstate the preparation. A measured detector signal may be modeled as $S(\nu )=S_{\mathrm{bg}}+A\overline{P}(2\pi ({\nu }_0-\nu ))$, with background $S_{\mathrm{bg}}$ and gain $A>0$. Background subtraction and stable transmission are necessary before interpreting the signal as a transition probability. The velocity-averaged Ramsey line provides one explicit ideal example; its chosen dimensions are not historical specifications.

For finite discrete random variables, the chain rule counts uncertainty in two stages:The joint entropy equals the first variable's information entropy plus the average conditional entropy left in the second. All logarithms here have base two, so the unit is the bit; zero-probability terms contribute zero. The identity holds without assuming independence.^[ref]

Iterating gives $H(X_1,\dots ,X_n)={\sum }_{i}H(X_i\mid X_1,\dots ,X_{i-1})$. The first summand means $H(X_1)$, with no earlier observations. Each later summand counts only the new uncertainty after the preceding random variables are known. For independent random variables, every term is its ordinary information entropy; for dependent ones, adding those ordinary information entropies can count shared uncertainty repeatedly. This is the reason the chain rule for information entropy is useful in lossless source coding and in calculating an entropy rate.

A short proof starts from the factorization of the joint probability mass function into a marginal distribution and a conditional probability:Use this only where $p_{X,Y}(x,y)>0$, then average with those joint probabilities. Summing over $y$ in the first term gives $H(X)$; the second is precisely $H(Y\mid X)$. Repeating the same step with a longer random vector proves the iterated identity. Reversing the order also gives $H(X,Y)=H(Y)+H(X\mid Y)$: the two contributions can change with the order, but their total cannot.

When all conditioning events have positive probability, repeatedly apply the definition of conditional probability to factor a joint event into successive conditional factors. For a sequence of discrete responses, this yields the product of conditional masses along the actual outcome path. It requires no unconditional independence assumption.

A constraint imposed with a specified probability when data or demands are random. Distributional assumptions can turn it into a deterministic condition on decision variables. The choice of strict versus non-strict event matters when the distribution has atoms, as in the deterministic boundary in an upper-tail chance constraint.

For a random variable $X$ with probability density function $f_X$ on an interval, let $Y=h(X)$, where $h$ is a diffeomorphism onto another interval. The change of variables formula givesIndeed, integrating the right-hand side over an outcome interval gives the probability that $X$ lies in its inverse image. The absolute derivative preserves positive probability when $h$ reverses orientation. A gravity deflection of an atomic beam is a physical example: its speed-to-height transformation changes the probability density and its mode.

Channel capacity is the best reliable information rate available through a specified communication channel. For a discrete memoryless channel with finite input and output alphabets, fixed transition probabilities $W(y\mid x)$, and no input-cost constraint, it isin bits per channel use, when the mutual information uses base-two logarithms. The maximization varies the input probability distribution, while keeping the communication channel fixed. A large input alphabet or a large output information entropy alone does not determine how much information gets through: the receiver needs information about the input, rather than merely unpredictable output.

The operational meaning comes from the Shannon second coding theorem. A block code represents one of $M$ possible messages by a word of length $n$, giving a rate ${\log }_{2}M/n$ bits per use. Take the message label from the uniform distribution on a finite set of those $M$ choices when measuring average decoding-error probability. For every fixed rate $R<C$, there are sequences of such block codes whose decoding-error probability tends to zero as $n$ grows; a rate above $C$ cannot have vanishing decoding-error probability. This is an asymptotic limit, rather than a promise that an arbitrary finite block code at a rate below $C$ works well. See MIT 18.310, Shannon's Noisy Coding Theorem, sections 1–2.

For a binary symmetric channel with crossover probability $p=0.1$, the binary symmetric channel capacity is approximately $0.53100441$ bits per use. Thus a binary code rate $R=1/2$ lies below the limit, while $R=3/4$ lies above it. At $R=1/2$, two transmitted symbols represent one message bit on average; the redundancy helps distinguish messages after noise. This does not split individual physical symbols into fractional pieces.

The result is useful because it separates two tasks. Computing channel capacity establishes the target imposed by the transition probabilities; constructing an effective block code attempts to approach that target with acceptable delay and decoding effort. The surprise is that reliability can improve indefinitely without forcing every positive rate to disappear. In his 1948 paper, Shannon defines noisy channel capacity in section 12 and develops its operational significance in section 13, Theorem 11. His original formulation uses information per unit time; the fixed-duration channel-use convention here expresses the same rate question per symbol. ^[ref].

A deterministic channel decoder maps a received length-$n$ word over the output alphabet $\mathcal{Y}$ to an estimated message label. Given message $m$, successful decoding means $g(Y^n)=m$, where $Y^n$ is the random received word after the communication channel acts on the channel encoder's word $f(m)$. The channel decoder can recover a message despite changed symbols because it uses the relationships among complete codewords. The Shannon second coding theorem concerns choosing both maps so that the decoding-error probability becomes small at a specified rate.

The characteristic function of a real random variable $X$ isIt determines the probability distribution of $X$.

Here $t\in \mathbb{R}$ and $i^2=-1$. By Euler's formula, its real part and imaginary part are $\mathbb{E}[\cos (tX)]$ and $\mathbb{E}[\sin (tX)]$. The complex exponential has absolute value one, so this expected value exists for every real random variable, even without finite absolute moments. Moreover,The bound uses the triangle inequality for a vector-valued integral; the last identity is complex conjugate symmetry.^[ref] Consequently the real part is an even function and the imaginary part is an odd function.

For a discrete probability distribution with values $x_j$ and probabilities $p_j$, the characteristic function is ${\sum }_j{p}_j{e}^{it{x}_j}$: a weighted average of points on the unit circle in the complex plane. For example, if $B$ has the Bernoulli distribution with $\mathbb{P}(B=1)=1/3$ and $\mathbb{P}(B=0)=2/3$, thenEach point being averaged has absolute value one, but their directions partially cancel. At $t=\pi$, the same average is $1/3$; at $t=2\pi$, it returns to one. The characteristic function is thus neither a probability density function nor a probability mass function: its argument is a frequency parameter, and its values can be complex numbers. This Bernoulli distribution has no probability density function with respect to Lebesgue measure, yet its characteristic function is defined at every frequency.

For a probability density function $f$, the same definition becomes ${\phi }_X(t)={\int }_{\mathbb{R}}{e}^{itx}f(x)dx$, the Fourier transform with the displayed sign convention. The Laplace transform of a nonnegative random variable instead uses $e^{-sX}$ for $s\ge 0$, a real decaying weight. For the Bernoulli distribution above, it is $2/3+e^{-s}/3$; neither transform is the probability density function. The uniqueness theorem for characteristic functions explains why the oscillating averages still retain the entire probability law, while the characteristic function of a sum of independent variables turns combining laws into multiplication. These two properties make the representation useful even when directly computing a sum's probability distribution is cumbersome.

Independence makes the characteristic function of a sum equal the product of the individual characteristic functions.

For mutually independent random variables $X_1,\dots ,X_n$, write $S_n={\sum }_{j=1}^n{X}_j$. ThenThis is the expectation of a product of independent random variables applied to bounded complex exponentials; no moment hypothesis is needed.^[ref]

Identical probability distributions are unnecessary. When the random variables are independent and identically distributed random variables, the product is ${\phi }_X(t{)}^n$. A deterministic rescaling also follows directly from the definition: ${\phi }_{aX+b}(t)=e^{itb}{\phi }_X(at)$ for real $a,b$. Consequently the sample mean has characteristic function ${\phi }_X(t/n{)}^n$, and a sum divided by $\sqrt{n}$ has characteristic function ${\phi }_X(t/\sqrt{n}{)}^n$.

The independence assumption does real work. Let $X$ take $-1$ and $1$ with equal probabilities and set $Y=X$. Both characteristic functions are $\cos t$, but ${\phi }_{X+Y}(t)=\cos (2t)$, not ${\cos }^{2}t$. At $t=\pi /2$ they give $-1$ and zero respectively. Knowing the two marginal probability distributions does not determine the sum without their joint probability distribution.

Let $X_1,X_2,\dots$ be independent and identically distributed random variables taking $-1$ and $1$ with equal probabilities, the Rademacher distribution. The two opposite complex exponentials give ${\phi }_X(t)=(e^{it}+e^{-it})/2=\cos t$. Their expected value is zero and their variance is one. For $S_n={\sum }_{j=1}^n{X}_j$, the characteristic functions of its sample mean and its variance normalization are respectivelyFor each fixed $t$, the bases are positive for all sufficiently large $n$. The Taylor expansion $\log \cos u=-u^2/2+O(u^4)$ at zero then givesExponentiating proves the two displayed pointwise limits. The first limit is the characteristic function of the constant zero; the second is that of the standard normal distribution. The Lévy continuity theorem gives the corresponding convergence in distribution statements. Averaging has variance $1/n$, whereas dividing the sum by $\sqrt{n}$ preserves variance one. This sign calculation illustrates why the law of large numbers and the central limit theorem use different scales; it is not a proof for arbitrary probability distributions.

The charge-transfer efficiency is the fraction of a packet delivered into its intended next site or time slot in one transfer, under stated conditions. It is distinct from quantum efficiency, which concerns conversion of incident photons into collected charge carriers. Define the complementary inefficiency as $ϵ=1-{\eta }_{\mathrm{tr}}$.

In an original model with constant $0\le {\eta }_{\mathrm{tr}}\le 1$, let $N_j$ denote the mean number of original packet electrons still delivered on time after $j$ transfers. Assuming no reinjection into that packet,Repeated substitution proves the result; for different efficiencies the fraction is ${\prod }_{j=1}^n{\eta }_j$. For $ϵ\ll 1$, a Taylor expansion of $\ln (1-ϵ)$ gives ${\eta }_{\mathrm{tr}}^n\simeq e^{-nϵ}$, while the simpler $1-nϵ$ requires $nϵ\ll 1$.

Choose $N_{\mathrm{in}}=10000$ and $n=2000$. For ${\eta }_{\mathrm{tr}}=0.9999$, the expected on-time output is $8187.23$ electrons; for ${\eta }_{\mathrm{tr}}=0.99999$, it is $9801.99$. These are model means, so fractional electron counts do not describe an individual packet. Even a small per-transfer imperfection can imprint distance-dependent image errors.

If every original electron independently stays on time with probability $p={\eta }_{\mathrm{tr}}^n$, a fixed initial count gives a binomial distribution with variance $N_{\mathrm{in}}p(1-p)$. An initial Poisson distribution with mean $\mu$ instead gives an on-time Poisson distribution with mean and variance $\mu p$, by Poisson thinning. A deterministic attenuation formula alone does not specify noise. Real trapping can correlate packets and depends on timing, illumination and temperature; the independent constant-efficiency model then fails.

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

The number of insurance claims in a specified exposure period. Its probability generating function combines with the moment-generating function of an independent claim size through the random-sum transform identity. A Poisson distribution, geometric distribution, or negative binomial distribution provides a possible count model, with different dispersion and zero-claim probabilities.

classical statistical mechanics assigns probability distributions to classical states. For a Hamiltonian particle system the canonical weight is $e^{-\beta H}$ on phase space. The weak-exchange, high-temperature limit of a quantum gas supplies the measure $d^{d}x{d}^{d}p/(2\pi \hslash {)}^d$ per particle and the indistinguishable-particle factor $1/N!$.