Foundations

For square-integrable X, Var(X)=E[Var(X|Y)]+Var(E[X|Y]).

M_X(t)=E[eᵗˣ] is an MGF when it is finite on an open interval about zero.

In the shape–rate convention Gamma(α,β) has density βᵅxᵅ⁻¹e⁻ᵝˣ/Γ(α) for x>0, α,β>0.

For estimator T of θ, bias is EθT−θ and MSE is Eθ[(T−θ)²]=Varθ(T)+bias².

An estimator sequence Tₙ is consistent for θ when Pθ(|Tₙ−θ|>ε)→0 for every ε>0.

For a differentiable scalar iid model with score sθ=∂θlog fθ(X), Fisher information is I(θ)=Eθ[sθ²].

For fixed full-column-rank X and Y=Xβ+ε with Eε=0 and Cov ε=σ²I, least squares gives β̂=(XᵀX)⁻¹XᵀY, Eβ̂=β and Cov β̂=σ²(XᵀX)⁻¹.

With independent Bernoulli Yᵢ, logistic regression assumes log[pᵢ/(1−pᵢ)]=xᵢᵀβ.

A DFA consists of finite states Q, finite alphabet Σ, total transition δ:Q×Σ→Q, start q₀ and accepting states F.

Regular expressions built from letters, the empty word and empty language using union, concatenation and star describe exactly the DFA/NFA-recognizable languages.

A context-free grammar has finite variables, terminal alphabet, rules A→w with one variable on the left, and a start variable.

A nondeterministic pushdown automaton augments finite control with one unbounded last-in-first-out stack.

A recognizer accepts every member of its language but may run forever on a nonmember.

Every nontrivial property of the language recognized by a Turing machine is undecidable from its machine description.

For finite X,Y, H(X|Y)=Σy p(y)H(X|Y=y) and H(X,Y)=H(Y)+H(X|Y).

For finite distributions p,q, D(p‖q)=Σx p(x)log₂[p(x)/q(x)]≥0, with equality exactly when p=q.

If finite X→Y→Z form a Markov chain, meaning Z is conditionally independent of X given Y, then I(X;Z)≤I(X;Y).

A binary prefix code has no whole codeword as another's initial segment, permitting immediate sequential decoding.

Repeatedly merge the two least-probable source symbols or accumulated nodes, then label the two branches 0 and 1; root-to-leaf labels are codewords.

For iid finite-alphabet X₁,…,Xₙ, −n⁻¹log₂p(X₁,…,Xₙ) converges in probability to H(X₁).

The entropy rate is limₙ H(X₁,…,Xₙ)/n when the limit exists.

For a real density f with defined integral, h(X)=−∫f(x)log₂f(x)dx.

For Y=X+Z with iid real Gaussian noise Z∼N(0,N), N>0, independent of input, and average input power E[X²]≤P, capacity is C=(1/2)log₂(1+P/N) bits per channel use.

For continuous real f with f(a)f(b)<0, test the midpoint and retain a half interval with opposite endpoint signs, unless the midpoint is a root.

At distinct nodes t₀,…,tₙ, p(x)=Σyₖℓₖ(x), ℓₖ(x)=∏_(i≠k)(x−tᵢ)/(tₖ−tᵢ), is the unique interpolant of degree at most n.

A differentiable function has zero gradient at an interior local extremum.

For C¹ real f,g, a local constrained extremum of f on g(x)=c at a point where ∇g≠0 must satisfy ∇f=λ∇g together with g=c.

A differentiable function on an open convex domain is convex exactly when f(y)≥f(x)+∇f(x)·(y−x) for all domain points.

For differentiable convex f₀,fᵢ on Rⁿ and affine equalities Ax=b, feasible x is optimal if λ≥0, λᵢfᵢ(x)=0 and ∇f₀(x)+Σλᵢ∇fᵢ(x)+Aᵀν=0.

For a smooth rapidly decreasing f whose derivatives also decrease faster than any power, define f̂(ξ)=∫Rⁿe⁻ⁱˣ·ξf(x)dx.