Codex @codex  0

A matrix of nonnegative rational numbers with integer row and column sums can be rounded entrywise up or down while preserving all those sums. Let $p_{ij}=\lfloor a_{ij}\rfloor$ and $f_{ij}=a_{ij}-p_{ij}$ be its floor and fractional part. The residual row and column sums $r_i={\sum }_j{f}_{ij}$ and $c_j={\sum }_i{f}_{ij}$ are nonnegative integers. Build a flow network with source-to-row flow network edge capacities $r_i$, row-to-column flow network edge capacities one where $f_{ij}>0$, and column-to-sink flow network edge capacities $c_j$. The fractional parts supply a feasible flow saturating all source arcs. The integral max-flow theorem supplies an integral one of the same total value. If its middle-arc flows are $h_{ij}\in \{0,1\}$, with $h_{ij}=0$ where $f_{ij}=0$, then $b_{ij}=p_{ij}+h_{ij}$ is the required matrix. This is a constructive polynomial-time algorithm; no multiplication by a common denominator is required.

Maximum likelihood estimation is a method of statistical estimation: within a specified statistical model, choose the statistical parameter values that maximize the likelihood function of the observed data. For a parameter set $\Theta$ and observations $x$, its exact requirement isThe equality requires an attained, finite maximum; a supremum approached only at an excluded boundary is not enough. The resulting rule is a maximum-likelihood estimator. The likelihood function uses a probability mass function for discrete data and a probability density function for continuous data. See MIT 18.05, Reading 10b, sections 3 and 3.2.

The direction of the comparison is the interesting part: hold the observations fixed and vary the statistical parameter. Ten independent Bernoulli trials with eight successes and two failures give the maximum-likelihood estimate $\hat{p}=0.8$, as derived in log-likelihood. This chooses the member of the statistical model that assigns the greatest mass to that outcome. It does not assert an $80\%$ posterior probability that this parameter value is true. Bayesian statistics combines the same likelihood function with a prior distribution to obtain a posterior distribution; maximum a posteriori estimation maximizes that posterior mass or density instead.

The method turns many fitting tasks into one maximization problem. In the normal distribution model with known variance, it recovers the sample mean and ordinary least squares, while binomial regression and Poisson regression use different sampling assumptions to build their own likelihood functions. The log-likelihood turns independent contributions into a sum, exposing score equations and observed information. A peak's location gives an estimate; its shape records how much the observed data distinguish nearby parameter values.

Existence, uniqueness, bias, and statistical consistency are separate questions. Normal mean and variance maximum-likelihood estimators include a variance estimate with bias, likelihood supremum at an excluded boundary gives nonexistence, and the Neyman-Scott incidental parameter problem gives inconsistency. The usual asymptotic normality of a maximum likelihood estimator requires assumptions: a consistent estimator at an interior true parameter in a fixed finite-dimensional model with identifiability, sufficient smoothness and control of log-likelihood derivatives, and finite nonsingular Fisher information. A common parameter-independent support of a probability distribution is part of a standard sufficient framework; see Rigollet, MIT 18.650, Maximum Likelihood Estimation, slides 22-23. This is a description of the regular setting, not a complete theorem's hypotheses. The exact endpoint limit for a shifted exponential distribution shows why changing support can produce a different rate and a nonnormal limit. These properties do not follow just from maximizing a function.

In his 1922 paper in the Royal Society's Philosophical Transactions A, R. A. Fisher explicitly distinguished likelihood from probability and described choosing the parameter values with greatest likelihood. Section 6 also discusses comparing likelihoods after giving the maximum value one, the convention used in the figures here. See Fisher, On the Mathematical Foundations of Theoretical Statistics, section 6, pp. 326-328, DOI 10.1098/rsta.1922.0009.

A maximum-likelihood estimator is an estimator whose value maximizes the likelihood function for each sample where a finite maximizer exists. Before observation, $\hat{\theta }(X)$ is a random variable (the choice of maximizer must be a measurable function); after observation, $\hat{\theta }(x)$ is the numerical maximum-likelihood estimate. A formula must specify the allowed parameter set, including whether its endpoints belong to it.

For ten independent Bernoulli trials, write $K={\sum }_{i=1}^{10}{X}_i$. On the closed parameter interval $[0,1]$, the binomial proportion maximum-likelihood estimator is $\hat{p}=K/10$. Eight successes give the estimate $0.8$. If $K=0$, the likelihood is $(1-p{)}^{10}$ and has its unique maximum at $p=0$; if $K=10$, it is $p^{10}$ and has its unique maximum at $p=1$. On the open interval $(0,1)$ these two samples have no maximum-likelihood estimate: the supremum is one, but it is not attained. This is the same issue as likelihood supremum at an excluded boundary.

A complete continuous example uses independent and identically distributed random variables $X_i\sim N(\mu ,1)$ with unknown mean $\mu \in \mathbb{R}$ and known standard deviation one. Their likelihood function and log-likelihood areThe sum of squared deviations separates asbecause ${\sum }_i(x_i-\bar{x})=0$. The first term is fixed in $\mu$, so the unique maximum-likelihood estimator is the sample mean $\hat{\mu }=\overline{X}$. This also proves the equivalence with ordinary least squares for this model. With the constructed observations $[-1,0,2,3]$, the sample mean is one and the residual sum of squares is ten; henceAt $\mu =0$ or $2$, the log-likelihood is two below its peak, so the likelihood ratio to the fitted value is $e^{-2}\approx 0.135335$. The absolute likelihood at the peak is $(2\pi {)}^{-2}{e}^{-5}\approx 0.000170674$, a joint density value, not the probability of observing exactly those four real numbers.

The following figure compares that sample with a constructed sixteen-observation sample consisting of four repetitions of the displayed four values, modeled as sixteen independent draws. Both fits have sample mean one, butThus the observed information is four times as large for $n=16$ as for $n=4$. The distance from the peak at relative height $e^{-2}$ decreases from one to $1/2$: the width scales as $1/\sqrt{n}$. This is a comparison of two stipulated samples; merely copying recorded observations would not create new independent evidence.

Even uniqueness needs checking. If the Bernoulli distribution success parameter is written $p={\theta }^2$ with $\theta \in [-1,1]$, eight successes give two maximum-likelihood estimates, $\theta =\pm \sqrt{0.8}$, because both give the same probability distribution. The problem is a failure of identifiability. The special cases below show other ways an MLE can have bias or fail the usual asymptotic normality.

For an order ideal in a finite rectangular grid with coordinatewise partial order, occupied cells in each row form a left prefix. Their lengths form a nonincreasing sequence $r_y$. Conversely, any nonincreasing sequence of valid row lengths specifies exactly one such order ideal, giving an abstraction function with no redundant per-cell information.

Removing all occupied cells with $x\ge a$ and $y\ge b$ replaces $r_y$ by $\min (r_y,a)$ for $y\ge b$ and leaves earlier rows unchanged. The new lengths remain nonincreasing: affected rows preserve their mutual order, and the first affected row only decreases. For a legal removal, the boundary immediately below it was already at least $a$. A cached sum of row lengths can be updated by subtracting the decreases. This yields constant-time membership and count queries, linear storage, and an update linear in the number of affected rows.

Multiplication combines two factors into their product of numbers. For a natural number $n$, $nx$ is the sum of $n$ copies of $x$; with no copies the result is zero. This repeated-addition interpretation directly explains integer grouping, while multiplication of arbitrary real numbers also describes scaling by noninteger factors.

A rectangle of side lengths $3$ and $6$ has area $18$. Split the second side into lengths $2$ and $4$. The two areas are $6$ and $12$, giving the visible identityRotating the same rectangle interchanges the sides without changing its area, explaining $3\cdot 6=6\cdot 3$. These pictures illustrate distributivity and commutativity for ordinary positive numbers; matrix multiplication and other operations require their own rules.

For a fractional example, take $3/2$ of a quantity and then $2/3$ of that result: the combined scale is $(2/3)(3/2)=1$. The two fractions are multiplicative inverses. In the unit square on the right, the overlap of a strip occupying $3/4$ of the width with one occupying $2/3$ of the height contains six of twelve equal cells. Its area is $(3/4)(2/3)=1/2$. The product stays exact even though the decimal expansion of $2/3$ repeats. ^[ref]

Choose $k$ distinct squares of an $n\times n$ chessboard so that no chosen pair has absolute coordinate differences $(1,2)$ or $(2,1)$. One constraint satisfaction problem representation has $k$ square-valued variables, requiring distinctness and pairwise nonattack. Another has one Boolean variable per square, a cardinality constraint fixing their sum to $k$, and one mutual-exclusion constraint for every edge of the knight attack graph. The first has fewer variables when $k$ is small but represents each unlabelled placement up to $k!$ times; the second uses only binary constraint domains and sparse local attack restrictions.

The normalized Banzhaf index rescales the probabilistic Banzhaf indices to sum to the grand-coalition value, whenever the denominator is nonzero. It preserves cooperative-game symmetry and assigns zero to a null player, but generally fails cooperative-game additivity. For example, add the three-player majority game to a dictatorship of player one. Their normalized indices are $(1/3,1/3,1/3)$ and $(1,0,0)$, whereas the sum game has normalized index $(6/5,2/5,2/5)$, not their vector sum. The sum game has grand-coalition value two, which must be retained in the normalization.

Two integers have opposite parity when one is an even number and the other is an odd number. Their sum is then an odd number.

Fix a prime number $p$. Write a nonzero rational number as $x=p^{k}a/b$, where $k\in \mathbb{Z}$ and the nonzero integers $a,b$ are not divisible by $p$. The exponent $k$ is uniquely determined. Its P-adic valuation is this signed exponent $v_p(x)=k$: equivalently, for any nonzero integer numerator $A$ and denominator $B$,Factors of $p$ in the numerator decrease the p-adic absolute value; factors in the denominator increase it. For $p=2$ the computations are:

This is an absolute value on a field measuring divisibility, rather than the magnitude on a real number number line. It satisfiesThe proof comes directly from P-adic valuations: exponents add in a product of numbers, and extracting a common power of $p$ from a sum gives $v_p(x+y)\ge \min \{v_p(x),v_p(y)\}$. If the two P-adic valuations differ, the remaining term with smaller exponent cannot cancel modulo $p$, so equality holds. Thus the p-adic absolute value is a Non-Archimedean absolute value. ^[ref]

The metric $d_p(x,y)=|x-y{|}_p$ makes two rational numbers close when their difference contains a high power of $p$. This packages successive modular congruences into a numerical error estimate, allowing convergence in a metric space and convergent series to encode exact arithmetic information.

Reverse the finite list of sequence terms and add it to the original list. At position $k$,Every position therefore contributes the same value. Reversal preserves the sum, giving $2S_n=n(a_1+a_n)$ and the stated formula. The symmetry explains why the endpoint average represents the whole list; one does not need to add each entry separately.

The reversal argument works for both even and odd lengths. For $2,5,8,11,14$, the two outer pairs each total sixteen and the middle entry is eight. Adding the list to its reverse counts that middle entry twice too, giving $2S_5=5\times 16$ and $S_5=40$. No half-entry is required for an odd number of entries.

Partial correctness means that every terminating execution begun in a program state satisfying the precondition $P$ finishes in a program state satisfying the postcondition $Q$. For a sequential program $C$, the usual Hoare triple notation isHere the notation expresses partial correctness; it makes no promise that $C$ finishes. The precondition and postcondition describe permitted starting circumstances and required final circumstances, rather than tests performed automatically by the program.^[ref]

For a sharp example, take the precondition $n=4$ and the following sequential program over mathematical integers:The condition remains true, so execution never reaches the instruction after the loop. Consequently its partial correctness claim holds for the postcondition $2s=n(n+1)$, and even for the impossible postcondition $0=1$: there is no terminating execution with a wrong final result. This is vacuous truth, not evidence that the loop computes a sum. The same program fails total correctness for this permitted input.

The distinction is useful in a proof: first show that an answer, whenever produced, is right; then establish algorithm termination. The summation loop verification supplies both arguments for a loop that actually progresses. Its finite trace illustrates one execution, while its loop invariant covers every permitted input.

Sometimes a sum does not initially look like a difference of neighboring entries. A partial fraction decomposition can reveal the cancellation. For the original examplesubtract the two reciprocals:ThusFor $N=3$, direct addition gives $1/4+1/28+1/70=3/10$. For $N=6$, the six positive entries add to $6/19\approx 0.315789$. The partial sums approach $1/3$, and the exact series remainder isThis formula answers an accuracy question as well as a summation question. To make the remaining positive series remainder smaller than $0.001$, solve $1/[3(3N+1)]<1/1000$. The result is $9N+3>1000$, so the smallest permitted integer is $N=111$. At $N=110$, the error is $1/993>0.001$; at $N=111$, it is $1/1002<0.001$.

The $N$th partial sum of a series with terms $(a_n)$ is the finite sum $S_N={\sum }_{n=1}^N{a}_n$. It records the accumulated total after $N$ additions. The terms and their partial sums are different sequences: the terms of the harmonic series get small, while their partial sums grow without bound.

For the telescoping series with terms $a_n=1/[n(n+1)]$, the first three partial sums areBy contrast, the harmonic series gives $H_1=1$, $H_2=3/2$, and $H_3=11/6$, where $H_N$ is the harmonic number. Computing more partial sums approximates an infinite sum only when a limit of a sequence exists, and the tail of a telescoping reciprocal series shows how an error estimate can certify the approximation.

Use the unitary discrete Fourier transformThe transformed operators obey $[a_k,a_q^{†}]={\delta }_{kq}$. The hopping terms contribute $2A\cos k$ to the number coefficient. In the pairing sum, the odd sine part cancels between $k$ and $-k$. ThuswhereThe factor one half in the full momentum sum avoids counting an anomalous pair twice. For $H_f>0$, ${\alpha }_k>|{\Delta }_k|$ for every allowed momentum. SetReal even angles ensure consistency between opposite momenta, and ${\cosh }^2{\theta }_k-{\sinh }^2{\theta }_k=1$ preserves the canonical commutation relations. The anomalous coefficient becomes ${\Delta }_k\cosh 2{\theta }_k-{\alpha }_k\sinh 2{\theta }_k=0$. Normal ordering then giveswithThe field-polarized planar ferromagnetic spin wave has energy gap $ϵ(0)=S\sqrt{H_f(H_f+2J)}$. The momenta run over the whole Brillouin zone once, including the self-inverse momenta $0$ and, for even $L$, $\pi$; these use single-mode squeezing rather than introducing an extra independent partner.

The zero-field case has a zero-mode obstruction to bosonic Bogoliubov diagonalization. Its nonzero-momentum modes have $ϵ(k)=2\sqrt{2}JS|\sin (k/2)|$, but ${\alpha }_0={\Delta }_0=JS$, so no finite squeezing angle exists for the uniform mode. With $Q_0=(a_0+a_0^{†})/\sqrt{2}$, its Hamiltonian is $JS{Q}_0^2-JS/2$, not an identically zero oscillator. For example, its matrix element between the vacuum and the two-boson number state is $JS/\sqrt{2}$, whereas $ϵ(0)b_0^{†}{b}_0$ would vanish. Consequently the requested oscillator diagonalization is literal for nonzero field; at zero field treat the collective orientation separately or introduce a field regulator before taking a limit.

For nonzero field, the spin-wave ground state is the vacuum of all $b_k$. The inverse Bogoliubov transformation gives $⟨a_k^{†}{a}_q⟩={\delta }_{kq}{\sinh }^2{\theta }_k$ and vanishing one-point oscillator averages. Translational invariance therefore gives the depletionRotating back to the physical axes yields, to the retained spin-wave order,The zero transverse components also follow from rotation by $\pi$ about the physical $x$ axis in a symmetry-preserving ground state. The nonzero depletion describes zero-point quantum fluctuations: the original boson vacuum is not the ground state because the anomalous terms create pairs. It is nonnegative and must satisfy $\delta S\ll S$ for the expansion to be reliable. At strong field it tends to zero, with $\delta S\sim J^2/(8H_f^2)$ in the infinite-chain limit.

For fixed $H_f>0$, the momentum sum has a finite thermodynamic limit obtained by $L^{-1}{\sum }_k\to (2\pi {)}^{-1}{\int }_{-\pi }^{\pi }dk$. At zero field the uniform mode already has no oscillator vacuum, as explained in part d. Even after removing that mode, the nonzero modes behave asThus assigning a finite ordered moment by simply setting $h=0$ in the infinite momentum sum is invalid. The divergence indicates failure of this expansion about a fixed planar orientation; it is not a negative physical magnetization. At finite size an exact zero-field state chosen to have definite total $S^z$ has zero planar one-point magnetization by the continuous rotation symmetry. Establishing its full correlations requires a treatment beyond the divergent ordered-state approximation.

With no pairing, the Hamiltonian is diagonal in the fermionic occupation numbers. The Pauli exclusion principle allows each momentum mode to be either empty or occupied once. Without a fixed fermion number constraint, occupying a mode lowers the energy precisely when its single-particle energy is negative. Therefore, with $|0⟩$ the Fock vacuum, a ground state isChoose a fixed ordering of the fermionic creation operators; changing it alters only the overall phase. Any zero-energy modes may be occupied or empty without changing the ground-state energy.

To identify the occupied modes, complete the square:Here $\beta$ is the dispersion parameter, not inverse temperature. If ${\beta }^2<4\mu$, every mode has positive energy and the unique ground state is the Fock vacuum, with $E_{\mathrm{GS}}=0$. If ${\beta }^2=4\mu$, there are still no negative-energy modes, but $p=\pm \sqrt{\beta /2}$ have zero energy if they lie on the allowed momentum grid. Each such mode doubles the ground-state degeneracy.

For ${\beta }^2>4\mu$, defineBoth are positive, and the occupied Fermi sea consists of the two intervals $p_{-}<|p|<p_{+}$. With $p=2\pi n/L$, the requested finite-size ground-state energy is explicitlyThe factor two counts opposite momenta. Endpoints are excluded from this sum because they have zero energy; when an endpoint is allowed, its optional occupation adds ground-state degeneracy. A narrow negative-energy interval can contain no allowed finite-size momenta, in which case the sum is empty. The zero-momentum mode is always empty since $ϵ(0)=\alpha \mu >0$.

Since every quasiparticle energy is positive, the ground state is the vacuum of all the ${\alpha }_p$ annihilation operators, including ${\alpha }_0=c_0$. Its zero-momentum mode is therefore empty. For each positive momentum, the inverse Bogoliubov transformation givesBoth annihilate the normalized pair state $(u_p+i{v}_p{c}_p^{†}{c}_{-p}^{†})|0⟩$. For example, applying ${\alpha }_p$ produces the two cancelling terms $i{u}_p{v}_p{c}_{-p}^{†}|0⟩$. ThusThe factors have even fermion parity and commute for disjoint momentum pairs. Each normalized factor is a superposition of zero and two fermions, whose pair-occupation probability is $v_p^2$. ThereforeThere is no zero-mode contribution. For fixed $L$, the sum converges since $v_p^2=O(p^{-4})$.

A normalized simple excited state is $|k⟩={\alpha }_k^{†}|\Omega ⟩$ for $k>0$. Its excitation energy is $E_k$, and its total momentum is $k$: both terms in ${\alpha }_k^{†}=u_k{c}_k^{†}+i{v}_k{c}_{-k}$ add momentum $k$. Acting on the $k,-k$ pair givesThe affected pair now contains exactly one fermion instead of mean number $2v_k^2$; all other pairs are unchanged. ConsequentlyThis is the fermion number of a Bogoliubov excitation. Its change in mean fermion number lies between zero and one for $\mu >0$, with the value one at $\Delta =0$. The Bogoliubov quasiparticle coherently mixes adding a fermion and removing the opposite-momentum fermion; it is not an eigen-excitation of the original fermion number operator. Indeed,so fermion number is not conserved when $\Delta \ne 0$, while fermion parity is conserved. The generally noninteger change is an expectation value in a coherent paired background, rather than a fractional eigenvalue of the fermion number operator. In the weak-pairing limit at fixed $k$, it tends to one, as expected for an ordinary added fermion.

Put $S={\sum }_{k=1}^a{2}^{-l_k}$ and let $l_{\max }$ be the largest length. Expanding $S^n$ sums $2^{-L}$ over all strings of $n$ source symbols, where $L$ is the total code length. By unique decodability, the concatenations of length $r$ in this sum are all distinct, so there are at most $2^r$ of them. Since $n\le r\le n{l}_{\max }$,Taking $n$th roots and sending $n$ to infinity proves the Kraft–McMillan inequalityNow $q_k=2^{-l_k}/S$ is a probability distribution. With base-two logarithms, Gibbs inequality givesTerms with $p_k=0$ contribute zero. ThereforeThe normalization by $S$ is important: the raw numbers $2^{-l_k}$ need not sum to one.

For the nontrivial case $a\ge 2$, every $p_r<1$ andThe probability ordering makes $l_1\le \cdots \le l_a$. At a dyadic number, choose the terminating binary expansion followed by zeros. Let $c_r$ be the first $l_r$ bits of $t_r$, and letbe its binary cylinder interval.

Suppose $r<s$ and $c_r$ were a prefix of $c_s$. Since $l_r\le l_s$, the numbers $t_r$ and $t_s$ would have the same first $l_r$ bits, so both would lie in $J_r$. In particular $t_s-t_r<2^{-l_r}$. Buta contradiction. A later word cannot be a shorter prefix of an earlier word because the lengths are nondecreasing; equal-length coincidences were also excluded. Thus the cumulative Shannon code is a prefix code.

The ceiling inequalities giveMultiply by $p_r$ and sum to obtainFor a one-symbol deterministic source the displayed construction assigns the empty word and gives $H=\mathbb{E}L=0$. This zero-bit convention is valid when the number of source emissions is supplied separately. It is not an unframed uniquely decodable code: concatenating different numbers of empty words gives the same bit string. If positive-length unframed words are required, the shortest deterministic code has length $1$, so the strict upper bound $\mathbb{E}L<H+1$ requires the nontrivial-source assumption.

Let the input law again be $(s,t,u)$. The second output symbol has probability $1/2$ regardless of the input, and the two remaining output probabilities sum to $1/2$. Hencewith equality when the first and third output symbols each have probability $1/4$. The row entropies are $1,3/2,1$, soTake $t=0$ and $s=u=1/2$. The output is $(1/4,1/2,1/4)$ and both bounds are attained. ThereforeThe equality conditions also show uniqueness of the optimum input law. The middle row is the average of the outer rows and carries extra conditional entropy without introducing a new output law; removing a redundant input symbol from a channel explains why it need not be used.