Stat.Minimax

Le Cam testing bound. For probability measures μ and ν on the same space, any measurable rejection region A yields a total testing error — the probability of A under μ plus the probability of the complement of A under ν — that is at least 1 − tvDist(μ,ν).

Given two probability laws and a common Markov reconstruction channel, applying that channel to both laws cannot increase their total variation distance.

For two probability laws and a common Markov kernel, the joint input-output laws obtained from that kernel have exactly the same total variation distance as the input laws.

For two probability measures on a countable measurable space with measurable singletons, total variation is at most one half of the ℓ¹ distance between their real singleton masses. The result is the half-ℓ¹ upper bound on total variation.

n-fold i.i.d. tensorization of the χ²-divergence on a finite sample space. For probability measures μ, ν on a finite space Ω with μ absolutely continuous with respect to ν, the χ²-divergence of the n-fold i.i.d. product laws satisfies 1 + χ²(μ^⊗n ‖ ν^⊗n) = (1 + χ²(μ‖ν))^n.

Two-point testing-error floor from a finite χ²-budget. For probability measures P, Q such that P is absolutely continuous with respect to Q and the squared density deviation (dP/dQ − 1)² is Q-integrable, if C is nonnegative and the χ²-divergence chiSqDiv P Q is at most C, then for every measurable test region A, the combined testing error is at least 1/(4(C + 1)): P(Aᶜ) + Q(A) ≥ 1/(4(C + 1)). This is the positive two-point testing floor that powers χ²-budget minimax lower bounds — no test can separate P from Q better than this when their χ²-divergence is bounded.

Le Cam two-point testing floor under a χ²-budget (uniform-constant form). Two statements share this structure: for every χ²-budget C ≥ 0 there is a single floor constant c > 0, fixed before the laws are chosen, such that every pair of probability laws with Q-integrable squared density deviation and χ²-divergence at most C has combined testing error P(Aᶜ) + Q(A) at least c on every measurable test region A; and for every per-observation χ²-budget c0 ≥ 0 there is a single floor c' > 0 such that whenever the single-observation χ²-divergence is at most c0/m, the m-fold i.i.d. product experiment retains that same constant testing floor c', by the product χ²-identity 1 + χ²(P^{⊗m}‖Q^{⊗m}) = (1 + χ²)^m ≤ exp(c0).

Two-point reduction to the minimax value. For a risk, a candidate lower bound, and two models, if every estimator has at least that much risk at one of the two models, then the minimax value is at least the candidate bound.

Restricting the model class cannot raise minimax risk. If a map between model classes makes the first risk no larger than the second risk under pointwise domination, then the first minimax value is no larger.

Two-point reduction to the minimax value. Fix two models θ₀ and θ₁ from the parameter class. If every estimator's risk is bounded above across the parameter class and for each estimator, the larger of its risks at the two fixed models is at least c, then the minimax value of the problem is at least c.

For a map φ from the parameter class of the first problem to that of the second, if the first problem's risk is nonnegative, the second problem's risk is nonnegative, each estimator's risk is bounded above across the second parameter class, and the first risk at any model is dominated by the second risk at that model's image under φ, then the minimax value of the first problem is at most that of the second.

Le Cam two-point bound for a real-valued parameter. If two candidate values θ₀, θ₁ : ℝ are 2s-separated, then for any measurable estimator est : Ω → ℝ, the worst-case probability of missing the truth by ≥ s is at least ½(1 − tvDist P₀ P₁). Specialization of half_one_sub_tvDist_le_max_error to Θ = ℝ with dist a b = |a − b|.

n-sample structure-agnostic two-point bound. Given two single-observation laws P₀, P₁ and a real functional τ such that the functional values τ P₀, τ P₁ are 2s-separated, then for any measurable estimator est built from n i.i.d. samples (data law Measure.pi (fun _ ↦ Pⱼ)), the worst-case miss probability, using τ P₀ and τ P₁ as the two parameters, is at least ½(1 − tvDist) between the two n-fold product laws.

χ²-form two-point lower bound. For a measurable estimator est, if two candidate values θ₀, θ₁ are 2s-separated, P₀ is absolutely continuous with respect to P₁, the squared density deviation (dP₀/dP₁ − 1)² is P₁-integrable, and the χ²-divergence chiSqDiv P₀ P₁ is at most c, then the worst-case miss probability is at least (1 − ½√c)/2, via tvDist ≤ ½√χ². Since chiSqDiv tensorizes over i.i.d. samples (chiSqDiv_prod) and is computable for explicit families, this is the form used to certify minimax rates.

Assouad's lemma (average form). Assume each coordinate's decoded-bit event is measurable. If every hypercube vertex's law is within total variation β of each of its d neighbouring vertices' laws, then the average Hamming risk over the cube is at least (d / 2)(1 − β). Choosing the dimension d large and the per-coordinate divergence β small forces a large number of mis-decoded coordinates.

Assouad's lemma (existence form). Under the same hypotheses — each coordinate's decoded-bit event is measurable and every vertex's law is within total variation β of each of its d neighbours — some vertex τ forces Hamming risk at least (d / 2)(1 − β): no cube estimator can decode every vertex's coordinates reliably when neighbouring laws are statistically close.

Assouad's lemma in parameter-risk form. For hypercube laws, parameter vertices, a nonnegative separation scale, an estimator, and a measurable nearest-vertex decoder, if vertices are separated by twice the scale times Hamming distance and neighboring laws have total variation at most β, then some vertex has expected metric loss at least (d*s/2)(1-β).