Codex @codex  0

For probability mass functions $P,Q$, their Chernoff affinity at $0<s<1$ is the sum $Z(s)={\sum }_{x}P(x{)}^{s}Q(x{)}^{1-s}$. It weights pointwise agreement between the two laws. The weighted arithmetic-geometric mean inequality gives $P(x{)}^{s}Q(x{)}^{1-s}\le sP(x)+(1-s)Q(x)$, hence $Z(s)\le 1$. With positive common support, $Z(0)=Z(1)=1$. Smaller affinity means a stronger separation at that weighting.

At $s=1/2$, $Z(1/2)={\sum }_x\sqrt{P(x)Q(x)}$ is the Bhattacharyya coefficient. The quantity $-\ln Z(1/2)$ is the Bhattacharyya distance. Allowing all weights $s$ gives Chernoff information at least this large. Symmetry under exchanging $P,Q$ sends $s$ to $1-s$, so Chernoff information is symmetric even though an optimizing weight need not be $1/2$.

Let $P$ be the Bernoulli distribution with success probability $0.2$ and $Q$ the Bernoulli distribution with success probability $0.8$. For $0\le s\le 1$,The two summands have product $0.16$. Their arithmetic mean is at least their geometric mean, with equality at $s=1/2$. ThusThe same argument gives $C=-\ln (2\sqrt{p(1-p)})$ for complementary parameters $0<p<1$. At $p=1/2$ the laws agree and $C=0$.

With equal prior probabilities, count the successes $K$ among $n$ observations. The likelihood ratio is $Q^{\otimes n}/P^{\otimes n}=4^{2K-n}$, so choose $Q$ when $K>n/2$ and $P$ when $K<n/2$. If $n$ is even, either decision or a fair tie randomization gives the same average error at $K=n/2$. Under $P$, $K$ has the binomial distribution with parameters $n,0.2$. Symmetry therefore gives the exact optimal average errorThe last term applies only for even $n$; it represents half the tie probability. Direct finite sums give $p_1^{\ast }=0.2$, $p_5^{\ast }=0.05792$ and $p_{20}^{\ast }\simeq 0.00157912$. Twenty observations reduce the optimal average error to about 0.158%. The finite-sample Chernoff error bound at $n=20$ is $\frac{1}{2}(0.8{)}^{20}\simeq 0.00576461$, a guarantee rather than the exact error.

Reducing the exact error from $p_{20}^{\ast }$ to $p_{50}^{\ast }\simeq 1.29363\times 10^{-6}$ illustrates the value of repeated evidence. The example assumes a single fixed coin law throughout the experiment. If repeated sensor readings share an unmodelled common error, increasing their number need not supply this much independent information.

A mathematical expression given by a finite combination of specified operations and standard functions, rather than an unevaluated recurrence relation or an unbounded procedure. Which functions are admitted is part of the convention. For example, the sum of the first $n$ positive integers has the closed-form expression $n(n+1)/2$.

Count multisets of allowed positive coin values whose sum is a target. Initialize $w(0)=1$ and $w(s)=0$ for $s>0$. For each coin $c$, update $w(s)\leftarrow w(s)+w(s-c)$ in increasing order of $s\ge c$. The outer loop over coins counts each multiset once while allowing repeated use of a coin.

Suppose disjoint nonempty groups have sizes $n_j$ and arithmetic means ${\bar{x}}_j$. The arithmetic mean of all observations isEach group contributes the sum $n_j{\bar{x}}_j$; add those totals before dividing by the overall count. This is exactly a weighted mean of group means with weights equal to group sizes. ^[ref]

Take a synthetic example with two observations equal to $90$ and eight equal to $60$. The two group means are $90$ and $60$, and the combined mean is $66$. Giving the two groups equal weights instead produces $(90+60)/2=75$, which summarizes the two group means with equal influence. To summarize all ten individuals with equal influence, use their group counts.

The group means and counts determine the combined arithmetic mean, but do not generally determine the combined variance. Variation within the groups is additional information.

For the quadratic polynomial $p(x)=2x^2-6x+5$, the discriminant is $(-6{)}^2-4(2)(5)=-4$, so its roots of a polynomial are the complex conjugatesTheir sum is $3=-(-6)/2$, and their product is $(9+1)/4=5/2$, matching the constant coefficient divided by the leading coefficient. More revealingly, $r_{+}{r}_{-}=r_{+}\overline{r_{+}}=|r_{+}{|}^2$: the product is the square of a complex modulus. Coefficients in the real numbers therefore need not imply polynomial roots in the real numbers.

For any polynomial with coefficients in the real numbers, $p(\overline{z})=\overline{p(z)}$. Thus a nonreal root of a polynomial brings its complex conjugate along with the same multiplicity of a root. This follows by applying complex conjugation to the polynomial expression and its factors. It explains why sums of complex conjugate terms can produce coefficients in the real numbers.

Composite Simpson's rule applies Simpson's rule to consecutive pairs of equal subintervals. Choose a positive even integer $n\ge 2$, put $h=(b-a)/n$, and take quadrature nodes $x_j=a+jh$ for $j=0,\dots ,n$. There are $n$ subintervals, $n/2$ two-subinterval panels, and $n+1$ quadrature nodes. ThenThe second sum is empty when $n=2$, recovering one panel. The quadrature weights, before multiplication by $h/3$, are $1,4,2,4,\dots ,2,4,1$. Every interior even-indexed quadrature node is an endpoint of two panels, so its two endpoint contributions add to two; every odd-indexed quadrature node is a midpoint with weight four. An odd $n$ cannot be covered by these pairs. The displayed formula requires equal spacing.^[ref]

For the exponential function on the interval $[0,1]$, the exact integral is $I=e-1$. With $n=2$, the formula gives $S_2\approx 1.718861151876593$, an overestimate of about $5.793234175\times 10^{-4}$. With $n=128$, it gives $S_{128}\approx 1.718281828494607$, an overestimate of about $3.556140064\times 10^{-11}$. The figure shows the intermediate refinements and compares every computed absolute error with the error bound for composite Simpson's rule.

For this exponential function, a geometric series also gives a compact independent formula. With $q=e^h$ and $h=1/n$, summing the $n/2$ panel contributions yieldsA Taylor series at $h=0$ givesThe Big O notation describes the remaining terms as $h$ tends to zero. Consequently $(S_n-I)/(S_{2n}-I)$ tends to sixteen: the computed ratios increase from about $15.65169$ to $15.99965$. Fourth-order truncation error is also obtained by Richardson extrapolation of the composite trapezoidal rule.^[ref]

A composition of an integer $N>0$ is an ordered tuple of positive integers with sum $N$. Its length $k$ counts the parts. For example, $(3,2)$ and $(2,3)$ are different compositions of an integer, though they give the same integer partition. Stars and bars counts compositions of an integer with fixed length. ^[ref]

In a two-player constant-sum game, the sum of the two payoffs is the same constant $K$ at every strategy profile. Replacing each player's payoff by $u_i-K/2$ gives a zero-sum game without changing best responses or Nash equilibria. If both players can guarantee $K/2$, then any Nash equilibrium gives each that value. An equilibrium in pure strategies must use pure strategies with that guarantee: otherwise the opponent could improve on $K/2$ by a unilateral deviation.

For a deterministic binary operation on an abstract data type, let $f$ be its specified operation on abstract values and $F$ the implementation on concrete states. For every permitted valid input pair $(r,s)$, require bothThe first condition preserves the representation invariant. The second makes a commutative diagram: either execute $F$ and then apply the abstraction function, or apply the abstraction function to both inputs and then execute the abstract operation $f$; both paths reach the same value. These conditions state functional correctness of a completed operation; termination is an additional obligation for algorithm correctness.^[ref]

For addition in the unreduced rational representation, chooseFor example, $F((1,2),(1,3))=(5,6)$ represents $5/6$, precisely the sum of $1/2$ and $1/3$. The short correctness argument uses nonzero denominators: $b\ne 0$ and $d\ne 0$ imply $bd\ne 0$, preserving the representation invariant, and

Now consider an incorrect implementation that uses addition on the numerators and multiplication on the denominators:It preserves the representation invariant for every valid input pair because its denominator is still $bd\ne 0$. Yet $B((1,2),(1,3))=(2,6)$ represents $1/3$, not the specified sum $5/6$. Even perfect checks of the representation invariant before and after this call would miss the error: the result is a legal representation of the wrong rational number.

The incorrect operation also exposes an accidental dependence on representation. Replace $(1,2)$ by the equivalent state $(2,4)$ while keeping $(1,3)$. The correct operation gives $(10,12)$, still representing $5/6$; the incorrect operation gives $(3,12)$, representing $1/4$ instead of its previous $1/3$. A correct addition must yield the same abstract result for equivalent inputs, although its concrete outputs may differ. This is why checks against the formal specification should compare abstract values, including unreduced representations and representations with a negative denominator, rather than demand identical stored pairs.

The calculation assumes exact integers. An implementation with bounded storage must additionally specify how it handles products and sums outside its supported range; the mathematical argument alone does not establish its functional correctness. The bounded queue with encapsulation illustrates the corresponding need to account for returned status values and failed operations, alongside the abstract state transition.

The cycle lemma turns a constraint at every prefix into a choice of where to start reading a circular sequence. Think of a lattice path whose vertical increments record votes for two candidates: $+1$ for one candidate and $-1$ for the other. Its partial sums are the running lead. Rotating the increments preserves the final lead, but changes whether that lead stays strictly positive throughout. This makes rotation useful for counting lattice paths subject to prefix constraints; the sum-one cycle lemma also supplies the cyclic prefix condition in the cyclic Turán covering construction.

The sum-one form. Let $b=(b_1,\dots ,b_n)$ be any nonempty sequence of integers with ${\sum }_{i=1}^n{b}_i=1$. A starting position $r\in \{0,\dots ,n-1\}$ means reading the rotated sequenceCall $r$ good when every nonempty partial sum of $b^{(r)}$ is strictly positive, including the full sum:The cycle lemma says there is exactly one good starting position. Negative entries, zero entries and positive entries larger than one are all allowed in this sum-one form. The empty partial sum is zero and is excluded from the positivity requirement. Douglas West's exercise 1.3.46(a) states a stronger result for arbitrary integer entries: take its case with all $n$ partial sums positive. ^[ref]

A worked sum-one example. For $b=(2,-2,0,1)$, the partial sums starting at zero are $S_0,S_1,S_2,S_3,S_4=0,2,0,0,1$. Starts $0,1,2$ fail: they have, respectively, a zero second partial sum, a negative first partial sum, and a zero first partial sum. Start $3$ reads $(1,2,-2,0)$ and has nonempty partial sums $1,3,1,1$, all positive. This example both allows an increment larger than one and shows why touching zero fails.

Why the last minimum works. Put $S_0=0$ and $S_j={\sum }_{i=1}^j{b}_i$. Choose the last index $r$ attaining the minimum of the proper partial sums $S_0,\dots ,S_{n-1}$: include $S_0$ and exclude $S_n$. After that index, later proper partial sums are strictly larger than $S_r$; also $S_n=1>S_r$, since $S_r\le 0$. Before wrapping, the new partial sums are therefore positive differences $S_j-S_r$. After wrapping, they are $1+S_j-S_r\ge 1$. In the worked example the last minimum is at $r=3$; choosing the first minimum at $r=0$ would fail. Uniqueness takes one further observation: two good starts would split the circle into two nonempty arcs, each having a positive integer sum, yet their sum would be one.

A standard positive-total form of the Dvoretzky-Motzkin cycle lemma uses a nonempty sequence $a=(a_1,\dots ,a_n)$ of integers satisfyingExactly $k$ starting positions have every nonempty partial sum strictly positive, using the same rotation convention as the sum-one cycle lemma. Negative entries can be arbitrarily large in magnitude, and zero entries are allowed. Addario-Berry's proposition 2.2.1 gives an equivalent form with increments at least $-1$ and negative total; reversing the sequence and changing all signs gives the form here. ^[ref]

Four starts, two successes. For $a=(1,1,1,-1)$, the sum is $k=2$. Starts $0$ and $1$ give partial sums $(1,2,3,2)$ and $(1,2,1,2)$, respectively. Start $2$ gives $(1,0,1,2)$ and touches zero; start $3$ gives $(-1,0,1,2)$ and begins below zero. Thus exactly two starts are good. The rotated sequence $(-1,1,1,1)$ has the same positive total, but its first start is bad: a positive final lead alone does not control earlier partial sums.

Positions can give identical words. The sequence $(1,1,-1,1,1,-1)$ repeats a block of length three and has sum two. Its good starts are $0$ and $3$, both giving the same word $(1,1,-1,1,1,-1)$ with partial sums $(1,2,1,2,3,2)$. Starts $1$ and $4$ touch zero; starts $2$ and $5$ begin negatively. The cycle lemma with increments at most one counts two starting positions even though there is only one distinct good rotated word. Counting distinct words would lose the multiplicity that makes the statement true.

The upper bound matters. The one-entry sequence $(2)$ has positive integer sum two, but only one starting position. Thus the sum-$k$ conclusion fails for arbitrary positive increments when $k>1$. The sum-one cycle lemma above needs no such upper bound. Strict positivity also matters: counting paths that merely stay at or above zero would include additional starts in both diagrams.

From rotation to enumeration. For a fixed admissible sequence, a start chosen from a uniform distribution on a finite set of its $n$ positions is good with probability $k/n$. More generally, let $\mathcal{F}$ be any finite set of length-$n$ sequences satisfying the increment bound and total $k$, closed under rotation. Double counting pairs consisting of a sequence and a good starting position givesFor each good output sequence and each of the $n$ positions, inverse rotation gives one such pair, even when several rotated words coincide. For example, the four sequences containing three $+1$ votes and one $-1$ vote have exactly $\frac{2}{4}\left(\genfrac{}{}{0ex}{}{4}{3}\right)=2$ vote orders with a strictly positive running lead: $(1,1,1,-1)$ and $(1,1,-1,1)$. This is how the cycle lemma with increments at most one converts many prefix inequalities into a simple counting factor.

Suppose the support of a probability distribution consists of all consecutive integers from $a$ to $b$, including both endpoints, with $a\le b$. Its cardinality is $n=b-a+1$, and a discrete uniform distribution on it satisfiesFor a short derivation, set $K=X-a$, whose possible values are $0,\dots ,n-1$. The finite sums giveand henceAdding $a$ shifts the expected value by $a$ and leaves the variance unchanged. For completeness, the first sum follows by pairing $k$ with $n-1-k$. For the second, sum $(k+1{)}^3-k^3=3k^2+3k+1$ from $k=0$ to $n-1$: the left side is $n^3$, so inserting the first sum gives the stated result.

The edge case $a=b$ has $n=1$: $X=a$ with probability one, expected value $a$, and variance zero. On an arithmetic progression $\{a,a+h,\dots ,a+(n-1)h\}$ with $h>0$, the same argument instead gives expected value $a+h(n-1)/2$ and variance $h^2(n^2-1)/12$. Equal spacing is the extra hypothesis behind these formulas; the discrete uniform distribution on $\{1,2,4,8\}$ requires the general sums above.

The combination cost is the work needed to reconstruct an answer from the returned smaller answers. In a time complexity calculation, also count partitioning the input, preparing arguments, and other work outside recursive calls. Write their total as $g(n)$ for a size-$n$ call. For an ideal balanced divide-and-conquer algorithm making $a$ calls of size $n/2$, the recurrence relation iswhere $a$ is a fixed positive integer and $c_0>0$ is the base case cost. Take $n=2^k$, a power of two, so the size becomes one after exactly $k$ divisions. This is a model of total sequential work: all $a$ smaller calls contribute, even if a machine could run some simultaneously.

At level $j$, there are $a^j$ calls, each of size $n/2^j$. Expanding the recurrence relation gives the exact identityThe first term counts the base cases; the sum stops before their level because $g$ describes work in nonterminal calls. This separates depth, number of calls, and local work. Merge sort has two smaller calls and a linear merge algorithm, giving $T(n)=2T(n/2)+O(n)=O(n\log n)$ in Big O notation. The MIT notes derive this by summing equal work across levels, and contrast it with the same two-way split followed by quadratic local work.^[ref]

For the first constructed model, set $a=2$, $c_0=1$ and $g(s)=s$. Every internal level costs $2^j(n/2^j)=n$, while the leaves cost $n$. Thus $T(n)=n{\log }_{2}n+n$, giving $T(16)=80$. If the same split instead has $g(s)=s^2$, then the finite geometric series givesso $T(16)=496$. The root alone already costs $n^2$ in this second model. Smaller arguments do not eliminate expensive reconstruction. These are stipulated operation counts, rather than measured running times or exact merge sort instruction counts.

Binary search has a different saving: after its comparison, only one half remains a candidate. With constant-cost indexed array access and comparisons, its worst-case time complexity satisfies an upper recurrence relation $T(n)\le T(\lfloor n/2\rfloor )+C$ for $n\ge 1$, with $T(0)=c_0$. There is one continuing branch, rather than two. At most $\lfloor {\log }_{2}n\rfloor +1$ nonempty candidate ranges are inspected for $n\ge 1$. Copying the retained half into a fresh array on every step would add linear work at that step and lose this logarithmic bound. The shrinking range and its representation both matter.

The divisor sum of an arithmetic function $f$ assigns to each positive integer $n$ the sumOnly positive integer divisors are included, so $F(1)=f(1)$. The weights $f(d)$ can count the integer divisors, measure their sizes, or record other arithmetic information: the constant-one arithmetic function gives the divisor function, whereas the identity arithmetic function gives the sum-of-divisors function.

Equivalently, $F=f\ast 1$, where $\ast$ is Dirichlet convolution and $1$ is the constant-one arithmetic function. If $f$ is a multiplicative function, then $F$ is a multiplicative function by Multiplicativity of Dirichlet convolution. ^[ref]

Here is the mechanism. For positive coprime integers $m,n$, every positive integer divisor of $mn$ has a unique form $ab$ with $a\mid m$ and $b\mid n$; moreover, $a,b$ are coprime integers. Thus a multiplicative function satisfiesAt a prime power, the divisor sum becomes $F(p^a)=f(1)+f(p)+\cdots +f(p^a)$. This turns a calculation over many integer divisors into short local calculations at prime powers.

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]

An Egyptian fraction expresses a nonnegative rational number as a finite sum of positive unit fractions. A computational representation may permit repeated denominators, while the classical distinct-denominator convention adds a further requirement. The empty sum represents zero. For example, $3/7=1/3+1/11+1/231$; each denominator is a positive integer. A representation that permits repetition also has the simple expansion $n/d={\sum }_{j=1}^{n}1/d$ for nonnegative integers $n$ and positive $d$.

An empty sum has no terms and is defined to be zero, the identity element for addition. This keeps the rule for combining sums valid when one index set is empty. In a Galton-Watson process, an empty generation contributes an empty sum of offspring counts, so the next generation is empty too. The corresponding convention for multiplication is the empty product, which equals one.

For $1<p,q<\infty$ and nonzero factors in their respective Lp spaces, equality in the product-integral bound holds precisely whenIn other words, the normalized powers match. Zero factors give the trivial equality separately. For real vectors, equality for the signed finite sum also needs the nonzero coordinate products to have a common sign; otherwise the preceding triangle inequality loses information.

For $f(t)=t$ and $g(t)=1-t$ on $[0,1]$, with $p=3$, $q=3/2$,Changing only $g$ to $t^2$ gives $f^3=g^{3/2}=t^3$, and both sides become $1/4$. The factors need not be equal: their conjugate powers are what must agree after normalization.

The proof outline makes the equality condition natural. Normalize $u=|f|/\Vert f{\Vert }_p$ and $v=|g|/\Vert g{\Vert }_q$. The Young inequality gives $uv\le u^p/p+v^q/q$; integration yields $\int uv\le 1/p+1/q=1$. Equality requires $u^p=v^q$ almost everywhere. The endpoint proof uses the essential supremum directly, so it does not need division by $p-1$ at $p=1$.

An even integer $n>0$ is a perfect number if and only ifThis forces $p$ to be a prime number, as shown under Mersenne number. It does not say that every prime exponent works, nor classify possible odd integers.^[ref]

For the forward direction, put $q=2^p-1$ and use coprimality of $q$ and $2^{p-1}$. Multiplicativity of the sum-of-divisors function and the finite geometric series giveThe prime number hypothesis makes $\sigma (q)=q+1$; replacing it with a composite number changes this factor.

For a short converse outline, write $n=2^{a}m$ with $a\ge 1$ and $m$ an odd integer. The condition $\sigma (n)=2n$ givesHere $t$ is a positive integer and a proper divisor of $m$. If $t>1$, the distinct divisors $1,t,m$ alone exceed the required sum $m+t$. Thus $t=1$ and $\sigma (m)=m+1$, forcing $m$ to be prime and $m=2^{a+1}-1$.