Pipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Robust Means under Heavy Tails

1 · Prerequisites

2 · Summary

This page separates clean finite-variance estimation from estimation after adversarial sample replacement. Under Countable Choice, the Hilbert geometric median-of-means has a total Borel minimum-norm selector and, for iid Borel data in a separable real Hilbert space with finite second moment, a trace-covariance guarantee. The split-sample univariate estimator has both stated confidence bounds, using the raw centered-tail functional; separate counterexamples distinguish that upper bound from the excess-tail lower-bound functional and refute a source clean-count exponent. Exact count thresholds and wider comparison quantiles provide alternative complete proofs without changing the procedure or its sound constants.

For multivariate trimming, a local entropy and ghost-coordinate argument proves the needed variance-sensitive bounded empirical-process bound. Uniform absolute-tail counts and a symmetric clipped process then give the correct-scale slab event, dyadic nesting and the full covariance-sensitive mean rate. The former four-Q0 radius is refuted explicitly and corrected to sixteen-Q0. The conditional rate lemma retains its original constant as the b=4 specialization and also covers the corrected b=16 event. Totality, measurability and the zero-covariance case remain separate proved suppliers; the stated contamination/confidence domains and absolute-continuity caveat remain explicit.

3 · Logical flowchart

4 · Definitions, theorems and proofs

LemmaStatement: AI-adaptedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

A variance-sensitive bound for bounded empirical suprema

Statement

Let $X_{1}, \dots, X_{n}$ be iid with law $P$ , $n \geq 1$ , and let $F$ be a finite or countable class of measurable real functions containing $0$ . Suppose $∣ f ∣ \leq B$ everywhere and $P f^{2} \leq s^{2}$ for all $f \in F$ , with finite $B, s \geq 0$ . Put $Z = \sup_{f \in F} \sum_{i = 1}^{n} (f (X_{i}) - P f), W = \sup_{f \in F} \sum_{i = 1}^{n} f (X_{i})^{2}, m = E W .$ For every $x > 0$ , $P (Z > E Z + 2 \sqrt{(8 m + 4 n s^{2}) x} + \sqrt{8} B x) \leq e^{- x} .$ The bound uses second moments, not only variances. All suprema are measurable by countability. No choice axiom is assumed.

Facts & Assumptions

Given: The iid sample, countable class containing zero, and boundedness and second-moment hypotheses in the Statement.

[F1]

Independent random elements have product joint law and Fubini's theorem for L^1 functions on a sigma-finite product allow coordinatewise integration and independent ghost coordinates on the finite product law.

[F2]

Jensen's inequality for expectation gives Jensen's inequality for convex functions; Dominated convergence permits bounded limits under integration.

[F3]

Markov's inequality for random variables turns exponential-moment bounds into tail bounds. Logarithm and exponential obey their usual derivative rules (Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm, The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t, The exponential function is smooth and $(\exp)^{'} = \exp$ ).

Proof

Given: The objects and hypotheses in the Statement. First take a finite class and $B > 0$ ; the case $B = 0$ is immediate.

1.1F1F2F3algebra

For positive bounded $U$ bounded away from zero, define $Ent (U) = E [U \log U] - E U \log E U$ . The function $Φ (u, a) = u \log (u / a) - u + a$ is jointly convex: its Hessian quadratic form is $(d u - (u / a) d a)^{2} / u \geq 0$ . Direct differentiation in $a$ gives $Ent (U) = \inf_{a > 0} E Φ (U, a)$ , attained at $a = E U$ . If $E_{i}$ integrates coordinate $i$ , the product identity $Ent (U) = E_{- i} {Ent}_{i} (U) + {Ent}_{- i} (E_{i} U)$ is obtained by adding and subtracting $E [(E_{i} U) \log (E_{i} U)]$ . Joint convexity gives ${Ent}_{j} (E_{i} U) \leq E_{i} {Ent}_{j} (U)$ for $j \neq i$ : apply Jensen to $Φ (E_{i} U, E_{i} E_{j} U)$ and integrate coordinate $j$ . Induction in the product identity proves tensorization $Ent (U) \leq E \sum_{i} {Ent}_{i} (U)$ . All integrations here are on finite product laws.

2.1F1F2step 1.1algebra

Let $Z_{i}^{'}$ replace $X_{i}$ by an independent copy and put $V_{+} = \sum_{i} E_{i}^{'} (Z - Z_{i}^{'})_{+}^{2}$ . Jensen for the logarithm gives ${Ent}_{i} (e^{t Z}) \leq {Cov}_{i} (e^{t Z}, t Z)$ for $t > 0$ . A fresh-copy expansion expresses this covariance as $\frac{t}{2} E_{i, i^{'}} [(e^{t Z} - e^{t Z_{i}^{'}}) (Z - Z_{i}^{'})]$ . Swap the two copies to restrict to $Z > Z_{i}^{'}$ and use $1 - e^{- t a} \leq t a$ for $a \geq 0$ . Tensorization from step 1.1 then yields $Ent (e^{t Z}) \leq t^{2} E [e^{t Z} V_{+}]$ . Choose the first maximizing function $f_{*}$ for $Z$ in a fixed finite ordering. Since $Z - Z_{i}^{'} \leq f_{*} (X_{i}) - f_{*} (X_{i}^{'})$ , the bound $(a - b)^{2} \leq 2 a^{2} + 2 b^{2}$ gives $V_{+} \leq 2 W + 2 n s^{2}$ .

2.2F2F3step 1.1algebra

Write $c = B^{2}$ and $W_{i} = \sup_{f} \sum_{j \neq i} f (X_{j})^{2}$ . Choosing a common maximizer for $W$ shows $0 \leq Δ_{i} = W - W_{i} \leq c$ and $\sum_{i} Δ_{i} \leq W$ . Use the conditional variational formula of step 1.1 with comparator $e^{a W_{i}}$ , which is independent of coordinate $i$ . With $ψ (u) = e^{u} - u - 1$ , it gives ${Ent}_{i} (e^{a W}) \leq E_{i} [e^{a W} ψ (- a Δ_{i})]$ . Convexity and $ψ (0) = 0$ imply $ψ (- a Δ_{i}) \leq (Δ_{i} / c) ψ (- a c)$ . Tensorization therefore implies, for $L (a) = \log E e^{a W}$ , $a L^{'} (a) - L (a) \leq ψ (- a c) L^{'} (a) / c$ , or $(1 - e^{- a c}) L^{'} (a) \leq c L (a)$ . If $m = 0$ , $W = 0$ almost surely and the following bound is immediate. Otherwise differentiating $L (a) / (e^{a c} - 1)$ shows it is nonincreasing; its limit at zero is $m / c$ . Thus $L (a) \leq (m / c) (e^{a c} - 1) \leq 2 a m$ whenever $0 \leq a c \leq 1 / 2$ , where the last scalar inequality follows by integrating $e^{u} \leq 2$ on $[0, 1 / 2]$ .

3.1F2F3step 2.1step 2.2algebra

Put $H (t) = \log E e^{t Z}$ and $D = t H^{'} (t) - H (t)$ , and let $E_{t}$ denote integration against density $e^{t Z - H (t)}$ . Step 2.1 gives $D \leq 2 t^{2} E_{t} W + 2 t^{2} n s^{2}$ . Jensen under this tilted law applied to $e^{a W} / e^{t Z - H (t)}$ gives $a E_{t} W \leq L (a) + D$ ; indeed its expectation under the tilt is $E e^{a W}$ , while the expectation of its logarithm is $a E_{t} W - D$ . Taking $a = 4 t^{2}$ and using step 2.2 yields $D \leq (8 m + 4 n s^{2}) t^{2}$ for $0 < t \leq 1 / (\sqrt{8} B)$ . Integrating $(H (t) / t)^{'} = D / t^{2}$ from zero proves $\log E e^{t (Z - E Z)} \leq A t^{2}$ , where $A = 8 m + 4 n s^{2}$ .

4.1F2F3step 3.1algebra∎

Put $b = \sqrt{8} B$ . If $A > 0$ , choose $t = \sqrt{x} / (\sqrt{A} + b \sqrt{x}) < 1 / b$ . Markov's inequality and step 3.1 show that a deviation of size $A t + x / t$ has probability at most $e^{- x}$ . Since $A t + x / t \leq 2 \sqrt{A x} + b x$ , the stated tail bound follows. The case $A = 0$ follows by taking $t ↑ 1 / b$ in the same exponential bound. Finally enumerate a countable class with zero first and increase its finite initial subclasses. Their $Z, W$ increase to the displayed suprema and are bounded by $2 n B, n B^{2}$ ; bounded convergence passes the exponential bounds and their expectations to the limit. The same Chernoff argument proves the assertion for the countable class.

AlgorithmAlgorithm: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Geometric median of block means

Definition

Let $H$ be a separable real Hilbert space, let $n \geq 1$ , and let $1 \leq k \leq n$ be an integer. Given $(x_{1}, \dots, x_{n}) \in H^{n}$ , put $q = ⌊ n / k ⌋$ and $r = n - k q$ . Form consecutive blocks $B_{1}, \dots, B_{k}$ in index order, with $∣ B_{j} ∣ = q + 1$ for $j \leq r$ and $∣ B_{j} ∣ = q$ for $j > r$ . Compute the block means $m_{j} = ∣ B_{j} ∣^{- 1} \sum_{i \in B_{j}} x_{i}$ . Return the unique minimum-norm point of

\underset{z \in H}{argmin} \sum_{j = 1}^{k} ∥ z - m_{j} ∥ .

The objective minimizers are called geometric medians of the block means. The minimum-norm rule makes the output single-valued. Existence, uniqueness of that selected point, and Borel measurability as a function of the input tuple are proved in Measurable minimum-norm geometric-median selection ↗.

AlgorithmAlgorithm: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Adaptive multivariate trimmed mean

Definition

Let $d, N \geq 1$ be integers, let $0 \leq η \leq 1 / 10$ , and let $0 < δ < 1$ satisfy $N \geq 2560 \log (2 / δ)$ . Given two observed halves ${\tilde{X}}_{1}, \dots, {\tilde{X}}_{N}$ and ${\tilde{Y}}_{1}, \dots, {\tilde{Y}}_{N}$ in $R^{d}$ , set

ε = \max {10 η, \frac{2560 \log (2 / δ)}{N}} \in (0, 1] .

For $v \in S^{d - 1}$ , sort $⟨ {\tilde{Y}}_{i}, v ⟩$ nondecreasingly and let $α_{v}$ and $β_{v}$ be its order statistics of ranks $⌈ ε N / 2 ⌉$ and $⌈ (1 - ε / 2) N ⌉$ . Write $ϕ_{a, b} (t) = \min {b, \max {a, t}}$ . For $Q > 0$ define $U_{Q} (v) = \frac{1}{N} \sum_{i = 1}^{N} ϕ_{α_{v} - Q, β_{v} + Q} (⟨ {\tilde{X}}_{i}, v ⟩), Γ (v, Q) = {z \in R^{d} : ∣ ⟨ z, v ⟩ - U_{Q} (v) ∣ \leq 2 ε Q} .$ and $Γ (Q) = ⋂_{v \in S^{d - 1}} Γ (v, Q)$ . For each $j \in Z$ , put

K_{j} = ⋂_{i \geq j} Γ (2^{i}), S = {j \in Z : K_{j} \neq \emptyset} .

Return the unique minimum-norm point of $K_{j}$ if $S$ has least element $j$ ; if $S = Z$ , return the unique minimum-norm point of $⋂_{i \in Z} Γ (2^{i})$ ; if $S = \emptyset$ , return the first-half sample mean $N^{- 1} \sum_{i = 1}^{N} {\tilde{X}}_{i}$ . This three-branch selector is total on the displayed input domain; its existence and Borel measurability are proved in Totality and measurability of the repaired multivariate trimmed-mean selector ↗.

AlgorithmAlgorithm: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Split-sample univariate winsorized trimmed mean

Definition

Let $N \geq 1$ be an integer, let $η \geq 0$ , $0 < δ < 1$ , and set

ε = 8 η + \frac{12 \log (4 / δ)}{N} .

The procedure is admissible when $0 < ε \leq 1 / 4$ . Its input is two observed real samples ${\tilde{X}}_{1}, \dots, {\tilde{X}}_{N}$ and ${\tilde{Y}}_{1}, \dots, {\tilde{Y}}_{N}$ . Sort the second sample nondecreasingly as ${\tilde{Y}}_{(1)}^{*} \leq \dots \leq {\tilde{Y}}_{(N)}^{*}$ and define $r (u) = ⌈ u N ⌉$ for $0 < u \leq 1$ . Set

α = {\tilde{Y}}_{(r (ε))}^{*}, β = {\tilde{Y}}_{(r (1 - ε))}^{*},

and, for $α \leq β$ , let $ϕ_{α, β} (x) = \min {β, \max {α, x}}$ . Return

\hat{μ} = \frac{1}{N} \sum_{i = 1}^{N} ϕ_{α, β} ({\tilde{X}}_{i}) .

The operation is defined for every admissible input, including tied observations.

Remarks

The probability guarantee is stated separately under the absolutely continuous clean-sample and sample-replacement hypotheses of Univariate trimmed-mean bound under sample replacement.

LemmaStatement: AI-adaptedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

An absolutely continuous upper quantile has its specified tail mass

Statement

Let $Z$ be a real random variable whose law is absolutely continuous with respect to Lebesgue measure on $R$ . For $0 < u < 1$ , define

Q_{u} (Z) = \sup {t \in R : P (Z \geq t) \geq 1 - u} .

Then $Q_{u} (Z)$ is finite and

P (Z \geq Q_{u} (Z)) = P (Z > Q_{u} (Z)) = 1 - u .

Facts & Assumptions

Given: A real random variable $Z$ with an absolutely continuous law and $0 < u < 1$ .

[A1]

Countable Choice is used by the published singleton-null result, which is the only reason for an axiom assumption here (The Axiom of Countable Choice ( ${A C}_{ω}$ ), Every at most countable subset of $R^{n}$ is Lebesgue null; in particular $λ_{1} (Q) = 0$ ).

[F1]

Absolute continuity means every Lebesgue-null Borel set has probability zero (Absolute continuity of a signed or complex measure with respect to a positive measure).

[F2]

Every singleton in $R$ is Lebesgue null under Countable Choice (Every at most countable subset of $R^{n}$ is Lebesgue null; in particular $λ_{1} (Q) = 0$ ).

[F3]

A probability measure has total mass one and is continuous from below and from above; the latter applies because the first term has mass at most one (Probability measures and probability spaces, Continuity from below for measures, Continuity from above when one set has finite measure).

[F4]

Every nonempty subset of $R$ that is bounded above has a finite least upper bound (The Cauchy-sequence reals have the least-upper-bound property).

Proof

technique · direct

Given: Countable Choice, a real random variable $Z$ with an absolutely continuous law, and $0 < u < 1$ .

1.1A1F1F2F3givenalgebra

For each $t \in R$ , the event ${Z = t}$ is measurable and its singleton is Lebesgue null by [F2]. Absolute continuity [F1] gives $P (Z = t) = 0$ . Therefore, if $t_{n} ↑ t$ , the events ${Z \geq t_{n}}$ decrease to ${Z \geq t}$ and [F3] gives $P (Z \geq t_{n}) ↓ P (Z \geq t)$ . If $t_{n} ↓ t$ with $t_{n} > t$ , these events increase to ${Z > t}$ , so [F3] gives convergence to $P (Z > t) = P (Z \geq t)$ . Thus the nonincreasing tail function $S (t) = P (Z \geq t)$ is continuous at every $t$ .

1.2F3F4givenalgebra

As $n \to \infty$ , the events ${Z \geq n}$ decrease to the empty set and ${Z \geq - n}$ increase to the whole sample space. By [F3], $S (n) \to 0$ and $S (- n) \to 1$ . Since $1 - u \in (0, 1)$ , the set $A = {t : S (t) \geq 1 - u}$ is nonempty and bounded above; [F4] gives its finite supremum. Continuity of $S$ makes $A$ closed, so that supremum $Q_{u} (Z)$ belongs to $A$ .

2.1step 1.1step 1.2algebra∎

If $S (Q_{u} (Z)) > 1 - u$ , continuity at $Q_{u} (Z)$ would give some $t > Q_{u} (Z)$ with $S (t) > 1 - u$ , contradicting that $Q_{u} (Z)$ is an upper bound for $A$ . Hence $S (Q_{u} (Z)) = 1 - u$ . Step 1.1 gives $P (Z = Q_{u} (Z)) = 0$ , so $P (Z > Q_{u} (Z)) = P (Z \geq Q_{u} (Z)) = 1 - u$ .

LemmaStatement: AI-adaptedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

Basic finite covariance matrix identities for robust mean bounds

Statement

Let $d \geq 1$ and let $X$ be a Borel random vector in $R^{d}$ with $E ∥ X ∥_{2}^{2} < \infty$ . Define $μ = E X$ coordinatewise, $Y = X - μ$ , and the finite matrix $Σ$ by $Σ_{r s} = E [Y_{r} Y_{s}]$ for $1 \leq r, s \leq d$ . Then $Σ$ is symmetric positive semidefinite,

tr Σ = E ∥ X - μ ∥_{2}^{2},

and $0 \leq λ_{\max} (Σ) \leq tr Σ$ . If $tr Σ = 0$ , then $X = μ$ almost surely.

Facts & Assumptions

Given: A Borel random vector $X$ in $R^{d}$ , $d \geq 1$ , with finite second moment.

[F1]

The Borel random-vector hypothesis means inverse images of Borel sets are measurable; composing with the continuous coordinate and norm-square maps preserves this property because inverse images of open sets under continuous maps are open. Expectation is integration against the probability measure and variance is the second centered moment (Random elements and real random variables, Expectation of a nonnegative or integrable random variable, Moments, variance, and covariance on a probability space).

[F2]

Expectation is linear for integrable variables (Linearity, monotonicity, and the modulus bound for expectation). The pointwise inequalities $∣ x ∣ \leq 1 + x^{2}$ and $2 ∣ x y ∣ \leq x^{2} + y^{2}$ give the integrability bounds used below.

[F3]

The Euclidean inner product is $⟨ x, y ⟩ = \sum_{r = 1}^{d} x_{r} y_{r}$ and $∥ x ∥_{2}^{2} = ⟨ x, x ⟩$ (The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ ).

[F4]

A nonnegative measurable function with integral zero vanishes almost everywhere (A nonnegative measurable function has integral $0$ exactly when it vanishes almost everywhere).

[F5]

Cauchy–Schwarz holds in the Euclidean inner product, and a symmetric matrix in the standard orthonormal basis represents a self-adjoint endomorphism whose largest eigenvalue is the maximum of its Rayleigh quotient $R_{Σ} (v) = ⟨ Σ v, v ⟩ / ⟨ v, v ⟩$ over nonzero $v$ (Cauchy–Schwarz: $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥ ∥ y ∥$ , with equality exactly for dependent pairs, In an orthonormal basis, self-adjoint means conjugate-transpose symmetry and normal means commuting with the conjugate transpose, The Rayleigh quotient of a nonzero vector for a self-adjoint endomorphism, The smallest and largest eigenvalues of a self-adjoint endomorphism are the minimum and maximum Rayleigh quotients).

Proof

technique · direct

Given: A Borel random vector $X$ in $R^{d}$ , $d \geq 1$ , with $E ∥ X ∥_{2}^{2} < \infty$ .

1.1F1F3givenalgebra

Each coordinate $X_{r}$ is square-integrable because $∣ X_{r} ∣ \leq ∥ X ∥_{2}$ , and is integrable since $∣ X_{r} ∣ \leq 1 + X_{r}^{2}$ . Hence each $μ_{r}$ is finite. Also $E [Y_{r}^{2}] \leq 2 E [X_{r}^{2}] + 2 μ_{r}^{2} < \infty$ . For every $r, s$ , the pointwise inequality $2 ∣ Y_{r} Y_{s} ∣ \leq Y_{r}^{2} + Y_{s}^{2}$ gives $E ∣ Y_{r} Y_{s} ∣ < \infty$ , so every entry of $Σ$ exists. Since $Y_{r} Y_{s} = Y_{s} Y_{r}$ , $Σ$ is symmetric.

2.1F2F3step 1.1algebra

For $v \in R^{d}$ , linearity of expectation [F2] and the finite-sum definition [F3] give $v^{T} Σ v = E [⟨ v, Y ⟩^{2}] \geq 0$ , so $Σ$ is positive semidefinite. Summing its diagonal entries and using linearity again yields $tr Σ = E [\sum_{r = 1}^{d} Y_{r}^{2}] = E ∥ Y ∥_{2}^{2}$ .

3.1F3F5step 2.1algebra

For nonzero $v$ , [F5] identifies $λ_{\max} (Σ)$ with the maximum Rayleigh quotient; pointwise Euclidean Cauchy–Schwarz gives $R_{Σ} (v) = E [⟨ v, Y ⟩^{2}] / ∥ v ∥_{2}^{2} \leq E ∥ Y ∥_{2}^{2} = tr Σ$ . Positive semidefiniteness from step 2.1 also gives $R_{Σ} (v) \geq 0$ , so maximizing proves $0 \leq λ_{\max} (Σ) \leq tr Σ$ .

4.1F1F4step 2.1∎

If $tr Σ = 0$ , step 2.1 gives $E ∥ Y ∥_{2}^{2} = 0$ . By [F1], the continuous polynomial $x \mapsto ∥ x - μ ∥_{2}^{2}$ composed with the Borel map $X$ is measurable, so [F4] applies and gives $∥ Y ∥_{2}^{2} = 0$ almost surely. The Euclidean norm is positive definite, hence $Y = 0$ almost surely and $X = μ$ almost surely.

LemmaStatement: AI-adaptedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

Every positive real lies below a dyadic scale less than twice as large

Statement

For every real $a > 0$ , there is an integer $i$ such that $a \leq 2^{i} < 2 a$ .

Facts & Assumptions

Given: A positive real number $a$ .

[F1]

The reals are Archimedean: a natural number can be chosen larger than any fixed positive real (Every complete ordered field is Archimedean).

[F2]

Induction gives $2^{n} \geq n + 1$ for $n \geq 0$ , and integer powers obey $2^{- n} = 1 / 2^{n}$ and $2^{i} = 2 \cdot 2^{i - 1}$ (The principle of mathematical induction, Integer powers $a^{m}$ , Laws of integer exponents).

Proof

technique · direct

Given: A real $a > 0$ .

1.1F1F2givenalgebra

By [F1], choose an integer $n \geq 1$ with $n + 1 > \max {a, 1 / a}$ . By induction from [F2], $2^{n} \geq n + 1 > a$ , while $2^{- n} = 1 / 2^{n} \leq 1 / (n + 1) < a$ .

2.1F2step 1.1algebrachoose∎

In the finite ordered list of integers $- n, - n + 1, \dots, n$ , take the least $i$ with $2^{i} \geq a$ ; it exists because exponent $n$ qualifies and exponent $- n$ does not. Thus $i > - n$ , so $i - 1$ is in the list and fails the defining inequality: $2^{i - 1} < a \leq 2^{i}$ . The power law in [F2] gives $2^{i} = 2 \cdot 2^{i - 1} < 2 a$ .

CounterexampleConstruction: AI-generatedVerification: AI-adaptedjudge pass (gpt-6-luna)Open item page →

The four-Q0 trimming slab radius is false

Statement refuted

The claim that every point of the correct-scale tail intersection $K_{i_{0}}$ in Adaptive multivariate trimmed mean lies within $4 ε Q_{0}$ of the clean mean is false, even for an absolutely continuous univariate clean law and no actual replacements.

Facts & Assumptions

Given: $X$ uniform on $[- 1, 1]$ , $N = 4096$ , $η = 1 / 10$ , $δ = 1 / 2$ , and no replacements.

[F1]

Adaptive multivariate trimmed mean defines quantiles, slabs of radius $2 ε Q$ and their dyadic tail intersections.

[F2]

Basic finite covariance matrix identities for robust mean bounds supplies the covariance and trace convention; here direct integration gives $μ = 0$ and $Σ = 1 / 3$ .

Counterexample

Given: The stated uniform clean law and parameters.

1.1F1F2givenalgebra

Here $N \geq 2560 \log 4$ because $\log 4 < 3 / 2$ , and $ε = \max {1, 2560 \log 4 / 4096} = 1$ . The proposed scale is $Q_{0} = \max {256 \sqrt{1 / (3 N)}, 16 / \sqrt{3}} = 16 / \sqrt{3}$ . The unique dyadic scale in $[2 Q_{0}, 4 Q_{0})$ is $Q = 32$ , so $i_{0} = 5$ . All parameters belong to the asserted domain, and zero actual replacements is allowed when the known upper fraction is $1 / 10$ .

2.1F1step 1.1algebra∎

Every observed point and directional cutoff lies in $[- 1, 1]$ . For every dyadic $R \geq 32$ , the expanded clipping interval contains $[- 1, 1]$ in each of the two unit directions. Thus $U_{R} (1) = \overset{ˉ}{X}$ , $U_{R} (- 1) = - \overset{ˉ}{X}$ , and $Γ (R) = [\overset{ˉ}{X} - 2 R, \overset{ˉ}{X} + 2 R]$ . These intervals are nested, so $K_{5} = [\overset{ˉ}{X} - 64, \overset{ˉ}{X} + 64]$ . Since $∣ \overset{ˉ}{X} ∣ \leq 1$ , $50 \in K_{5}$ for every realization, but $50 > 64 / \sqrt{3} = 4 ε Q_{0}$ . The proposed high-probability event therefore has probability zero, disproving the radius constant.

CounterexampleConstruction: AI-generatedVerification: AI-adaptedjudge pass (gpt-6-luna)Open item page →

The excess-tail functional cannot upper-bound the trimmed mean

Statement refuted

Replacing the raw centered-tail functional in the univariate trimmed-mean bound by $E_{e x c} (u) = \max {E [∣ Z - Q_{u / 2} (Z) ∣ 1_{{Z \leq Q_{u / 2} (Z)}}], E [∣ Z - Q_{1 - u / 2} (Z) ∣ 1_{{Z \geq Q_{1 - u / 2} (Z)}}]}$ would falsely assert $P (∣ \hat{μ} - μ ∣ \leq 3 E_{e x c} (4 ε) + 2 σ \sqrt{\log (4 / δ) / N}) \geq 1 - δ$ for Split-sample univariate winsorized trimmed mean. This fails for a bounded absolutely continuous law.

Facts & Assumptions

Given: $N = 10^{6}$ , $η = 1 / 100$ , $δ = 1 / 10$ , $w = 1 / 1000$ , and $X = S + U$ , where $S$ is a uniform sign and $U$ is independent uniform on $[- w, w]$ ; clean coordinates are iid copies. Assume Countable Choice as in the quantile supplier.

[F1]

Split-sample univariate winsorized trimmed mean sorts the second half at levels $ε$ and $1 - ε$ and averages the clipped first half.

[F2]

An absolutely continuous upper quantile has its specified tail mass uses exact continuous quantiles, with its Countable Choice hypothesis (The Axiom of Countable Choice ( ${A C}_{ω}$ )).

[F3]

Chebyshev's inequality for random variables bounds a centered random variable's tail by its variance divided by the squared threshold.

Counterexample

Given: The displayed parameters and symmetric two-interval clean law. Replace the first $20000$ negative first-half observations by $+ 1$ , or all negatives if fewer; do not change the second half.

1.1F1F2givenalgebra

This law is absolutely continuous with density $1 / (4 w)$ on each interval $[- 1 - w, - 1 + w]$ and $[1 - w, 1 + w]$ , has mean zero and variance $σ^{2} = 1 + w^{2} / 3$ . The replacement rule is a measurable finite-coordinate rule and makes at most $20000 = 2 η N$ changes. Put $ε = .08 + 12 \log 40 / 10^{6}$ , so $.08 < ε < .081 < 1 / 4$ , and $δ \geq e^{- N / 4}$ . At lower tail mass $2 ε$ the quantile is $- 1 - w + 8 w ε$ . Integration over the lower interval gives $E [(Q_{2 ε} - X) 1_{{X \leq Q_{2 ε}}}] = (8 w ε)^{2} / (8 w) = 8 w ε^{2}$ ; symmetry gives the same upper-tail excess. Hence $3 E_{e x c} (4 ε) + 2 σ \sqrt{\log 40 / 10^{6}} < .0042$ , using $\log 40 < 4$ , $ε < .081$ and $σ^{2} < 1.000001$ .

2.1F1F3step 1.1algebra∎

Let $A$ be the event that the clean first-half sign average has absolute value at most $.01$ , and let $B$ be the event that the second-half negative-sign count lies between $N / 4$ and $3 N / 4$ . The sign average has variance $1 / N$ , so [F3] gives $P (A^{c}) \leq .01$ . The second-half count has variance $N / 4$ , so $P (B^{c}) \leq 4 / N$ . On $A$ there are at least $.495 N$ negative first-half signs, so the replacement changes exactly $20000$ of them. The resulting sign average is at least $- .01 + .04 = .03$ . On $B$ , the ranks in [F1] put $α$ in the negative interval and $β$ in the positive interval, since $ε < .081 < 1 / 4$ . Every clipped value is at least its altered sign minus $w$ : a negative value is at least $- 1 - w$ , and a positive value, including a replacement $+ 1$ , clips to at least $1 - w$ . Therefore $\hat{μ} \geq .03 - w = .029$ on $A \cap B$ , whose probability is at least $.989996$ . This exceeds the proposed threshold $.0042$ with probability greater than $δ = .1$ , disproving the asserted coverage.

CounterexampleConstruction: Literature-sourcedVerification: AI-adaptedjudge pass (gpt-6-luna)Open item page →

The claimed univariate clean-quantile count exponent is too strong

Statement refuted

The auxiliary bound used in the source proof,

P ⁣ (B_{N} > \frac{3}{4} ε N) \leq e^{- ε N / 12}, B_{N} \sim Bin (N, ε / 2),

is false for admissible theorem parameters: with $η = 0$ , $ε = 1 / 10$ , $N$ sufficiently large and divisible by $40$ , and $δ = 4 e^{- N / 120}$ , one has

P ⁣ (B_{N} > \frac{3 N}{40}) > e^{- N / 120} = e^{- ε N / 12} .

For absolutely continuous clean data, An absolutely continuous upper quantile has its specified tail mass makes this binomial variable exactly the source's upper-quantile count. This refutes that proof step, not the univariate estimator theorem.

Facts & Assumptions

Given: An absolutely continuous real law, iid copies $Z_{1}, \dots, Z_{N}$ , and $N$ a sufficiently large multiple of $40$ .

[A1]

Countable Choice enters only through the published singleton-null result used by the exact-tail lemma (The Axiom of Countable Choice ( ${A C}_{ω}$ ), An absolutely continuous upper quantile has its specified tail mass).

[F1]

For $0 < u < 1$ , the upper quantile has exact tail mass $P (Z_{i} > Q_{u} (Z)) = 1 - u$ (An absolutely continuous upper quantile has its specified tail mass).

[F2]

The iid indicators of a common event are independent Bernoulli variables, and their sum has the binomial law (Identical distribution and IID families, Bernoulli random variables and binomial random variables as sums of independent Bernoulli trials).

[F3]

For $x > 0$ , $\log x = \int_{1}^{x} d t / t$ (The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t).

[F4]

The logarithm is continuous and satisfies its product and quotient laws, and it is inverse to the exponential (Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm, The natural logarithm as the inverse of the exponential function).

[F5]

For $w > 0$ , the exponential power series has nonnegative terms and $e^{w} \geq 1 + w + w^{2} / 2$ (The real exponential function and the number $e$ by a power series).

Counterexample

technique · direct

Given: The absolutely continuous law, iid copies, and the stated $N$ .

1.1F4F5givenalgebra

Put $η = 0$ and $δ = 4 e^{- N / 120}$ . For sufficiently large $N$ , $0 < δ < 1$ and $δ \geq e^{- N / 4}$ because $4 e^{29 N / 120} > 1$ . The theorem's definition then gives $ε = 8 η + 12 \log (4 / δ) / N = 1 / 10$ . Hence $p = ε / 2 = 1 / 20$ , $q = 3 ε / 4 = 3 / 40$ , and the asserted failure exponent is $ε / 12 = 1 / 120$ .

2.1A1F1F2step 1.1algebra

By [F1], each indicator $1 {Z_{i} > Q_{19 / 20} (Z)}$ has success probability $1 / 20$ ; iid sampling and [F2] give $B_{N} \sim Bin (N, p)$ with $p = 1 / 20$ . At $q = 3 / 40$ , its relative-entropy rate is $D (q ∥ p) = q \log (q / p) + (1 - q) \log ((1 - q) / (1 - p)) = \frac{3}{40} \log \frac{3}{2} + \frac{37}{40} \log \frac{37}{38}$ .

3.1F3step 2.1algebra

To bound this rate rigorously, put $x = 1 / 5$ and $y = 1 / 38$ . From [F3] and $s = (t - 1) / (t + 1)$ , $\log (3 / 2) = 2 \int_{0}^{x} (1 - s^{2})^{- 1} d s$ . On $[0, x]$ , $(1 - s^{2})^{- 1} = 1 + s^{2} + s^{4} + s^{6} + s^{8} / (1 - s^{2})$ and $s^{8} / (1 - s^{2}) \leq (25 / 24) s^{8}$ , so $\log (3 / 2) < 23947783 / 59062500 < 405466 / 10^{6}$ . Also $\log (37 / 38) = - \int_{0}^{y} (1 - s)^{- 1} d s \leq - y - y^{2} / 2 - y^{3} / 3 = - 2195 / 82308 < - 26668 / 10^{6}$ , since $(1 - s)^{- 1} \geq 1 + s + s^{2}$ . Therefore $D (q ∥ p) < (3 \cdot 405466 - 37 \cdot 26668) / (40 \cdot 10^{6}) = 229682 / 40000000 < 23 / 4000 < 1 / 120$ .

4.1F2F4F5step 1.1step 2.1step 3.1algebra∎

Let $m = q N + 1$ , an integer because $40 ∣ N$ . For $p_{m} = m / N$ , the binomial point-mass ratio $P_{p_{m}} (B_{N} = j + 1) / P_{p_{m}} (B_{N} = j) = ((N - j) / (j + 1)) (p_{m} / (1 - p_{m}))$ is greater than $1$ at $j = m - 1$ and less than $1$ at $j = m$ , and decreases with $j$ . Thus $m$ is a mode of $Bin (N, p_{m})$ , whose $N + 1$ masses sum to one; consequently $P_{p_{m}} (B_{N} = m) \geq 1 / (N + 1)$ . The binomial formula and [F4] give $P_{p} (B_{N} = m) = P_{p_{m}} (B_{N} = m) e^{- N D (p_{m} ∥ p)} \geq e^{- N D (p_{m} ∥ p)} / (N + 1)$ . By continuity of $D (r ∥ p)$ in $r$ , [F4] and step 3.1 give $D (p_{m} ∥ p) \to D (q ∥ p) < 1 / 120$ . Choose $c > 0$ with $D (q ∥ p) + c < 1 / 120$ . For all sufficiently large such $N$ , $D (p_{m} ∥ p) < 1 / 120 - c$ and [F5] gives $e^{c N} \geq 1 + c N + (c N)^{2} / 2 > N + 1$ . Therefore $P_{p} (B_{N} = m) > e^{- N / 120}$ . Since $m > 3 N / 40$ , this mass lies in ${B_{N} > 3 N / 40}$ , disproving the displayed source bound at the admissible parameters from step 1.1.

LemmaStatement: Literature-sourcedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

A geometric median is close when a strict majority is close

Statement

Let $H$ be a real Hilbert space, let $k \geq 1$ be an integer, let $m_{1}, \dots, m_{k} \in H$ , and let $m$ minimize $F (z) = \sum_{j = 1}^{k} ∥ z - m_{j} ∥$ . For $0 < a < 1 / 2$ and $r > 0$ , put

C_{a} = \frac{1 - a}{\sqrt{1 - 2 a}} .

If $z \in H$ satisfies $∥ m - z ∥ > C_{a} r$ , then more than $a k$ of the points $m_{j}$ satisfy $∥ m_{j} - z ∥ > r$ .

Facts & Assumptions

Given: A real Hilbert space $H$ , an integer $k \geq 1$ , points $m_{1}, \dots, m_{k}$ , a minimizer $m$ of their geometric-median objective, $0 < a < 1 / 2$ , $r > 0$ , and $z \in H$ .

[F1]

A geometric median minimizes $F (w) = \sum_{j} ∥ w - m_{j} ∥$ (Geometric median of block means).

[F2]

The norm is induced by a real inner product; orthogonal decompositions satisfy Pythagoras. Cauchy–Schwarz follows by minimizing $∥ u - t v ∥^{2} \geq 0$ over real $t$ when $v \neq 0$ (Hilbert space).

Proof

technique · direct

Given: A real Hilbert space $H$ , an integer $k \geq 1$ , points $m_{1}, \dots, m_{k}$ , a geometric median $m$ , $0 < a < 1 / 2$ , $r > 0$ , and $z \in H$ .

1.1F2algebra

Suppose at most $a k$ points satisfy $∥ m_{j} - z ∥ > r$ . Since $C_{a}^{2} = 1 + a^{2} / (1 - 2 a) > 1$ , write $D = ∥ z - m ∥ > C_{a} r > r$ and $d = (z - m) / D$ . For each of the at least $(1 - a) k$ remaining points, $u_{j} = (m_{j} - m) / ∥ m_{j} - m ∥$ is defined and $⟨ u_{j}, d ⟩ \geq (D - ∥ m_{j} - z ∥) / ∥ m_{j} - m ∥ > 0$ . Put $\cos θ_{j} = ⟨ u_{j}, d ⟩$ . By [F2], $0 < \cos θ_{j} \leq 1$ ; writing $d = \cos θ_{j} u_{j} + w_{j}$ with $w_{j} ⊥ u_{j}$ , Pythagoras gives $∥ w_{j} ∥ = \sin θ_{j}$ . The distance from $z = m + D d$ to the line through $m$ and $m_{j}$ is $D ∥ w_{j} ∥ = D \sin θ_{j}$ , and is at most $∥ z - m_{j} ∥ \leq r$ . Therefore $\cos θ_{j} \geq \sqrt{1 - (r / D)^{2}} > \sqrt{1 - C_{a}^{- 2}} = a / (1 - a)$ .

2.1F1F2step 1.1algebra∎

For $m_{j} \neq m$ , rationalizing the difference quotient gives $\lim_{t ↓ 0} (∥ m + t d - m_{j} ∥ - ∥ m - m_{j} ∥) / t = ⟨ m - m_{j}, d ⟩ / ∥ m - m_{j} ∥ = - \cos θ_{j}$ ; if $m_{j} = m$ , the quotient is $∥ t d ∥ / t = 1$ . Thus the right directional derivative of $F (m + t d)$ is $- \sum_{m_{j} \neq m} \cos θ_{j} + # {j : m_{j} = m}$ . Each good point from step 1.1 contributes less than $- a / (1 - a)$ , and each other point contributes at most $1$ by [F2]. Since at least $(1 - a) k$ points are good, the derivative is strictly less than $k - (1 - a) k (1 + a / (1 - a)) = 0$ . At a minimizer every right difference quotient is nonnegative, so this negative derivative is impossible. Thus more than $a k$ points lie outside the radius- $r$ ball about $z$ .

Remarks

The nonempty-center condition $k \geq 1$ is necessary. If $H = R$ , $k = 0$ , $z = 0$ , $r = 1$ , $a = 1 / 4$ , and $m = 4$ , the empty objective is zero at every point, so $m$ is a minimizer. Here $C_{a} = 3 / (2 \sqrt{2}) < 4$ , but there are zero outliers, not more than $a k = 0$ . All conclusions above retain their stated constants for every positive center count.

LemmaStatement: AI-adaptedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

Measurable minimum-norm geometric-median selection

Statement

Fix a separable real Hilbert space $H$ and an integer $k \geq 1$ . The rule in Geometric median of block means defines a single-valued Borel map $H^{k} \to H$ : for every tuple $(m_{1}, \dots, m_{k})$ the function $F_{m} (z) = \sum_{j = 1}^{k} ∥ z - m_{j} ∥$ has a nonempty closed convex minimizer set, and that set has a unique point of minimum norm. The choice-free Borel construction below does not use weak compactness or reflexivity. Countable Choice is used only for the published Hilbert projection supplier that identifies the minimum-norm point.

Facts & Assumptions

Given: A separable real Hilbert space $H$ , an integer $k \geq 1$ , and a tuple $m = (m_{1}, \dots, m_{k}) \in H^{k}$ .

[F1]

The geometric-median objective is $F_{m} (z) = \sum_{j = 1}^{k} ∥ z - m_{j} ∥$ ; the algorithm selects the minimum-norm point among its minimizers (Geometric median of block means).

[F2]

In a Hilbert space, a nonempty closed convex set has a unique nearest point to $0$ under Countable Choice (Projection onto a nonempty closed convex set, The Axiom of Countable Choice ( ${A C}_{ω}$ )).

[F3]

A closed bounded subset of $R^{d}$ is compact for finite $d \geq 1$ (Heine-Borel in $R^{n}$ : with the Euclidean metric a subset of $R^{n}$ is compact if and only if it is closed and bounded, and the proof by bisection uses no choice principle; the same holds on the real line).

[F4]

Cauchy–Schwarz implies $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥ ∥ y ∥$ in a Hilbert space (Cauchy–Schwarz: $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥ ∥ y ∥$ , with equality exactly for dependent pairs).

[F5]

A continuous real-valued function on a nonempty compact metric space attains a minimum and maximum (A continuous real-valued function on a nonempty compact metric space is bounded and attains a greatest and a least value).

[F6]

In a compact metric space, every family of closed sets with the finite-intersection property has nonempty intersection (A metric space is compact if and only if every family of closed subsets with the finite intersection property has nonempty intersection).

[F7]

Borel sets form a sigma-algebra, a map is Borel when inverse images of Borel sets are Borel, countable infima of Borel real maps are Borel, and pointwise limits of Borel real maps are Borel (The Borel sigma-algebra of a topological space, A measurable function between measurable spaces, Sequential suprema, infima, limsup, liminf, and pointwise limits of measurable functions are measurable).

[F8]

Separability means there is an at-most-countable dense subset; since $H$ is nonempty, A nonempty set is at most countable iff it is a surjective image of $N$ enumerates it by a sequence (Separability: the existence of an at most countable dense subset).

Proof

technique · direct

Given: A separable real Hilbert space $H$ , an integer $k \geq 1$ , and a tuple $m = (m_{1}, \dots, m_{k}) \in H^{k}$ .

1.1F1F3F4F5algebra

Let $V = span {m_{1}, \dots, m_{k}}$ . In the given center order, Gram–Schmidt replaces $m_{j}$ by $r_{j} = m_{j} - \sum_{ℓ < j} ⟨ m_{j}, e_{ℓ} ⟩ e_{ℓ}$ using the previously retained orthonormal vectors; if $r_{j} = 0$ it is skipped, and otherwise $e = r_{j} / ∥ r_{j} ∥$ is appended. Induction on the finite list shows the retained vectors are orthonormal and span $V$ . For $d = \dim V > 0$ , if $v_{n} = \sum_{ℓ = 1}^{d} a_{n ℓ} e_{ℓ} \in V$ converges in $H$ to $v$ , then [F4] gives $a_{n ℓ} = ⟨ v_{n}, e_{ℓ} ⟩ \to ⟨ v, e_{ℓ} ⟩$ for each $ℓ$ ; the finite sums converge to $\sum_{ℓ} ⟨ v, e_{ℓ} ⟩ e_{ℓ} = v$ , so $V$ is closed. If $d = 0$ , all centers are zero and $F_{m} (z) = k ∥ z ∥$ has the unique minimizer $0$ . For $d > 0$ , set $P_{V} z = \sum_{ℓ} ⟨ z, e_{ℓ} ⟩ e_{ℓ}$ ; its residual is orthogonal to $V$ . Pythagoras gives $∥ z - m_{j} ∥^{2} = ∥ P_{V} z - m_{j} ∥^{2} + ∥ z - P_{V} z ∥^{2}$ , so $F_{m} (P_{V} z) < F_{m} (z)$ whenever $z \notin V$ . Thus every minimizer lies in $V$ . The function $F_{m}$ is continuous and coercive because $F_{m} (z) \geq k ∥ z ∥ - \sum_{j} ∥ m_{j} ∥$ ; its sublevel set ${z \in V : F_{m} (z) \leq F_{m} (0)}$ is nonempty, closed and bounded in the finite-dimensional coordinate space $R^{d}$ , hence compact by [F3]. By [F5], $F_{m}$ attains a minimum there; the full minimizer set $C_{m}$ is nonempty, closed, bounded and compact, and it is convex because $F_{m}$ is convex.

1.2F1F2F3F4F5F7F8construct

By [F2], $C_{m}$ has a unique point $z_{*} (m)$ nearest to $0$ , its unique minimum-norm point. If $H = {0}$ , the selection is the constant zero map; otherwise fix a unit vector $e$ and a countable dense sequence $(d_{a})_{a \geq 1}$ in $H$ , whose existence is given by [F8]. The countable set $D = {⟨ d_{a}, e ⟩ : a \geq 1}$ is dense in $R$ : for each $t \in R$ , density gives $d_{a_{j}} \to t e$ , and [F4] gives $⟨ d_{a_{j}}, e ⟩ \to t$ . For $λ > 0$ , $G_{λ, m} (z) = F_{m} (z) + λ ∥ z ∥^{2}$ is continuous, coercive and strictly convex. Projection to $V$ cannot increase $F_{m}$ and strictly decreases the squared norm off $V$ , so every minimizer lies in $V$ ; if $d = 0$ the single candidate is $0$ . For $d > 0$ , a closed bounded sublevel set in $V$ is compact by [F3], so [F5] gives a unique minimizer $z_{λ} (m)$ . By continuity and density, $h_{λ} (m) = \inf_{a} G_{λ, m} (d_{a}) = G_{λ, m} (z_{λ} (m))$ . Each map $m \mapsto G_{λ, m} (d_{a})$ is continuous, so [F7] makes their countable infimum $h_{λ}$ Borel. For $s \geq 1$ , set $A_{a, s} = {m : G_{λ, m} (d_{a}) < h_{λ} (m) + 1 / s}$ . The countable dense set $D$ gives $A_{a, s} = ⋃_{q \in D} {m : G_{λ, m} (d_{a}) < q} \cap {m : h_{λ} (m) > q - 1 / s}$ so $A_{a, s}$ is Borel; density ensures at least one such $a$ for each $m$ . The least such $a$ is a Borel, countably-valued map because its level set at $a$ is $A_{a, s} ∖ ⋃_{b < a} A_{b, s}$ , and the selected point map is Borel since each open-set preimage is the union of its Borel level sets whose values lie in that open set. The selected point is within $(λ s)^{- 1 / 2}$ of $z_{λ} (m)$ : convexity of $F_{m}$ and $∥ (1 - t) z + t y ∥^{2} = (1 - t) ∥ z ∥^{2} + t ∥ y ∥^{2} - t (1 - t) ∥ y - z ∥^{2}$ , applied at the minimizer and followed by $t ↓ 0$ , give $G_{λ, m} (y) - G_{λ, m} (z_{λ}) \geq λ ∥ y - z_{λ} ∥^{2}$ . Hence the selected maps converge pointwise to $z_{λ}$ . Since they are countably valued with Borel level sets, their distances to each $d_{a}$ are Borel and converge to $∥ z_{λ} - d_{a} ∥$ ; [F7] makes these limits Borel. Balls with centers $d_{a}$ and positive rational radii form a countable basis of the separable metric space $H$ : every open neighborhood of a point contains such a ball around a sufficiently close dense center. Thus inverse images of open sets are countable unions of Borel inverse images of these balls, proving $m \mapsto z_{λ} (m)$ is Borel.

2.1F3F6F7step 1.2algebra

For every $s \geq 1$ , comparison with $z_{*} (m)$ in the minimization of $F_{m} + s^{- 1} ∥ \cdot ∥^{2}$ gives $∥ z_{1 / s} ∥ \leq ∥ z_{*} ∥$ and $F_{m} (z_{1 / s}) \leq F_{m} (z_{*}) + s^{- 1} ∥ z_{*} ∥^{2}$ . If $d = 0$ then both points are $0$ . Otherwise all $z_{1 / s}$ lie in the compact ball $B_{V} (0, ∥ z_{*} ∥)$ by [F3]. The closed tail sets $C_{n} = \overline{{z_{1 / s} : s \geq n}}$ inside this ball are nonempty, nested and have the finite-intersection property, so [F6] gives $c \in ⋂_{n} C_{n}$ . For every $n$ , continuity of $F_{m}$ and the tail bounds imply $F_{m} (c) \leq F_{m} (z_{*}) + ∥ z_{*} ∥^{2} / n$ , while $∥ c ∥ \leq ∥ z_{*} ∥$ ; letting $n \to \infty$ shows $c \in C_{m}$ is a minimum-norm minimizer, hence $c = z_{*}$ . If the sequence did not converge to $z_{*}$ , some $ρ > 0$ would leave arbitrarily late terms at distance at least $ρ$ ; the closed tail closures of those terms are nonempty nested subsets of the same compact ball, so [F6] gives a point in their intersection. It lies in every $C_{n}$ , hence equals $z_{*}$ , but its distance from $z_{*}$ is at least $ρ$ , a contradiction. Thus $z_{1 / s} \to z_{*}$ . By [F7] and the separable-metric basis argument of step 1.2, the pointwise limit of the Borel maps $z_{1 / s}$ is Borel.

3.1F1F2step 1.1step 1.2step 2.1∎

The minimizer set is nonempty, closed and convex by step 1.1, its minimum-norm point is unique by step 1.2, and step 2.1 proves the selected map is Borel. The only choice principle used is Countable Choice in [F2]; the dense sequence is supplied by separability and all subsequent approximations use least-index rules.

LemmaStatement: AI-adaptedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

Totality and measurability of the repaired multivariate trimmed-mean selector

Statement

For each fixed admissible $d, N, ε$ and each observed data tuple in $(R^{d})^{2 N}$ , the procedure Adaptive multivariate trimmed mean returns a unique vector in $R^{d}$ . As a function of the observed data tuple it is Borel measurable. The fallback branch covers the case where no dyadic tail intersection is nonempty; the all-scale branch covers the case where every tail intersection is nonempty.

Facts & Assumptions

Given: Integers $d, N \geq 1$ , fixed $ε \in (0, 1]$ , and an arbitrary data tuple in $(R^{d})^{2 N}$ .

[F1]

The algorithm's directional order statistics, winsorized centers, slabs, tail intersections, and three output branches are as in Adaptive multivariate trimmed mean.

[F2]

The Euclidean unit sphere and closed unit ball are compact, and a closed bounded subset of $R^{d}$ is compact (Euclidean spheres and closed balls as subspaces of $R^{n}$ , Heine-Borel in $R^{n}$ : with the Euclidean metric a subset of $R^{n}$ is compact if and only if it is closed and bounded, and the proof by bisection uses no choice principle; the same holds on the real line).

[F3]

A continuous real-valued function on a nonempty compact space attains a minimum (A continuous image of a compact space is compact; a continuous real-valued map on a nonempty compact space attains a maximum and a minimum; and a continuous bijection from a compact space to a Hausdorff space is a homeomorphism).

[F4]

Cauchy–Schwarz holds for the Euclidean inner product; consequently $∥ z ∥_{2} = \sup_{v \in S^{d - 1}} ∣ ⟨ z, v ⟩ ∣$ (Cauchy–Schwarz: $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥ ∥ y ∥$ , with equality exactly for dependent pairs, The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ , Euclidean spheres and closed balls as subspaces of $R^{n}$ ).

[F5]

In a compact metric space, every family of closed sets with the finite intersection property has nonempty intersection (A metric space is compact if and only if every family of closed subsets with the finite intersection property has nonempty intersection).

[F6]

Rational $d$ -tuples are countable and dense, and a nonempty countable set has an enumeration by $N$ ( $Q^{n}$ is a countable dense subset of $R^{n}$ , and rational open boxes form a countable basis, A nonempty set is at most countable iff it is a surjective image of $N$ ).

[F7]

Borel sets form a sigma-algebra, a map is Borel when preimages of Borel sets are Borel, pointwise limits of measurable real functions are measurable, and rational open boxes form a countable basis of $R^{d}$ (The Borel sigma-algebra of a topological space, A measurable function between measurable spaces, Sequential suprema, infima, limsup, liminf, and pointwise limits of measurable functions are measurable, $Q^{n}$ is a countable dense subset of $R^{n}$ , and rational open boxes form a countable basis).

[F8]

A continuous map from a compact metric space to a metric space is uniformly continuous (Heine-Cantor: a continuous map from a compact metric space to any metric space is uniformly continuous).

Proof

technique · direct

Given: Integers $d, N \geq 1$ , fixed $ε \in (0, 1]$ , and an arbitrary data tuple in $(R^{d})^{2 N}$ .

1.1F1F2F4algebra

Fix the data tuple $x$ and put $M (x) = \max_{i} {∥ {\tilde{X}}_{i} ∥_{2}, ∥ {\tilde{Y}}_{i} ∥_{2}}$ . Every projected observation and each order-statistic endpoint lies in $[- M (x), M (x)]$ , so $∣ U_{Q} (v; x) ∣ \leq M (x) + Q$ . Hence $z \in Γ (Q)$ implies $∣ ⟨ z, v ⟩ ∣ \leq M (x) + (1 + 2 ε) Q$ for every unit $v$ and $∥ z ∥_{2} \leq M (x) + (1 + 2 ε) Q$ by [F4]. Each order statistic of a finite list $a_{1}, \dots, a_{N}$ equals $\min_{∣ J ∣ = k} \max_{j \in J} a_{j}$ at rank $k$ : every such maximum is at least the $k$ th smallest entry, and the first $k$ indices attain it. Thus the directional order statistics, clipping endpoints, and $U_{Q} (v; x)$ are continuous in $(x, v)$ for fixed $Q$ . Each $Γ (v, Q)$ is a closed convex slab; intersections preserve these properties. Therefore $Γ (Q)$ and every $K_{j}$ are closed and convex; a nonempty $K_{j}$ is bounded by the displayed radius at $Q = 2^{j}$ , hence compact by [F2].

2.1F1F2F3F5step 1.1choosealgebra

Since $K_{j} \subseteq K_{j + 1}$ , $S = {j : K_{j} \neq \emptyset}$ is upward closed. If $S$ is nonempty and proper, choose $j_{0} \in S$ and $j_{1} \notin S$ ; upward closure forces $j_{1} < j_{0}$ , and the least point of the nonempty finite set $S \cap {j_{1} + 1, \dots, j_{0}}$ is least in $S$ . If $S = Z$ , the nested nonempty compact sets $K_{0} \supseteq K_{- 1} \supseteq K_{- 2} \supseteq \dots$ have the finite-intersection property inside compact $K_{0}$ , so [F5] gives a nonempty compact intersection. This intersection is exactly $⋂_{i \in Z} Γ (2^{i})$ , since the constraints in $K_{- n}$ range over all $i \geq - n$ . Each nonempty branch set (a least-index $K_{j}$ or the all-scale intersection) is compact and convex, so its norm attains a minimum by [F3]. If distinct $z, w$ both minimize squared norm, then $∥ (z + w) / 2 ∥_{2}^{2} = (∥ z ∥_{2}^{2} + ∥ w ∥_{2}^{2}) / 2 - ∥ z - w ∥_{2}^{2} / 4$ is smaller, a contradiction; the minimum-norm point is unique. The empty- $S$ fallback is the defined first-half mean. Thus every branch is total and single-valued.

2.2F1F2F8step 1.1algebra

For fixed $Q > 0$ , define $g_{Q} (x, z) = \max_{v \in S^{d - 1}} {∣ ⟨ z, v ⟩ - U_{Q} (v; x) ∣ - 2 ε Q}$ . It is continuous: the maximand is jointly continuous by step 1.1, the sphere is compact by [F2], and on a compact neighborhood of any $(x, z)$ times the sphere [F8] gives uniform continuity, which bounds the change in the maximum by the supremum change of the maximand. Also, $Γ (Q) = {z : g_{Q} (x, z) \leq 0}$ , and $g_{Q}$ is convex in $z$ as a maximum of absolute affine functions minus constants. Put $g_{I} (x, z) = \sup_{i \in I} g_{2^{i}} (x, z)$ for $I = I_{j} = {i \in Z : i \geq j}$ or $I = Z$ . If $Q \geq 2 M (x)$ , no first-half projection is clipped, so $U_{Q} (v; x) = ⟨ \overset{ˉ}{X}, v ⟩$ and $g_{Q} (x, z) = ∥ z - \overset{ˉ}{X} ∥_{2} - 2 ε Q$ , where $\overset{ˉ}{X} = N^{- 1} \sum_{i} {\tilde{X}}_{i}$ . On any compact neighborhood of $(x, z)$ this identity makes the high-scale terms tend uniformly to $- \infty$ ; for $I_{j}$ they are eventually below $g_{2^{j}}$ , and for $I = Z$ eventually below $g_{1}$ . Thus the high-scale supremum is locally a finite maximum. For the all-integer index set, define $g_{0}$ using clipping to $[α_{v}, β_{v}]$ and no error allowance; the same compact-sphere maximum argument shows $g_{0}$ is continuous. Expanding both clipping endpoints by $Q$ changes each clipped observation by at most $Q$ , so $∣ g_{Q} - g_{0} ∣ \leq (1 + 2 ε) Q$ uniformly in $(x, z)$ . On a compact neighborhood, all scales $i < - m$ therefore have supremum between $g_{0}$ and $g_{0} + (1 + 2 ε) 2^{- m}$ , while for all sufficiently large $m$ the scales $i > m$ are below $g_{1}$ . Hence $g_{I}$ is a local uniform limit of the continuous finite maxima $\max {g_{0}, g_{2^{i}} : - m \leq i \leq m}$ and is continuous. Being a supremum of convex functions, $g_{I}$ is convex in $z$ .

3.1F2F3F8step 1.1step 2.2

For $I = I_{j}$ , every $z \in K_{j}$ satisfies $∥ z ∥_{2} \leq R_{j} (x) = M (x) + (1 + 2 ε) 2^{j}$ by step 1.1; for $I = Z$ , every feasible $z$ lies in $Γ (1)$ and has norm at most $R_{\infty} (x) = M (x) + 1 + 2 ε$ . These radii are positive and continuous. Since $K_{I} (x) = {z : g_{I} (x, z) \leq 0}$ , its nonemptiness is equivalent to $m_{I} (x) \leq 0$ , where $m_{I} (x) = \min_{∥ w ∥_{2} \leq 1} g_{I} (x, R_{I} (x) w)$ . The minimum exists by [F2], [F3]. It is continuous in $x$ : on a compact neighborhood of any $x$ , [F8] makes $(x, w) \mapsto g_{I} (x, R_{I} (x) w)$ uniformly continuous in $x$ uniformly over the compact unit ball, and the difference of two minima is bounded by the supremum of the corresponding function differences. Thus each event ${x : K_{I} (x) \neq \emptyset} = {x : m_{I} (x) \leq 0}$ is Borel.

4.1F2F3F6F7step 2.2step 3.1

Fix one such branch index set $I$ and write $R = R_{I} (x)$ . By [F6], enumerate a countable dense rational subset $(r_{a})$ of $Q^{d}$ and set $d_{a} = r_{a} / \max {1, ∥ r_{a} ∥_{2}}$ . The radial map is continuous and is the identity on the unit ball, so $(d_{a})$ is dense in that ball. Let $h_{I} (x, w) = g_{I} (x, R w)$ and, for each integer $λ \geq 1$ , minimize $J_{λ, I} (x, w) = R^{2} ∥ w ∥_{2}^{2} + λ \max {h_{I} (x, w), 0}$ over $∥ w ∥_{2} \leq 1$ . The function is jointly continuous and strictly convex in $w$ : $h_{I}$ is convex by step 2.2, its positive part is convex, and $R > 0$ makes the quadratic strictly convex. Compactness and [F3] give a unique minimizer $w_{λ, I} (x)$ . The value $b_{λ, I} (x) = \inf_{a} J_{λ, I} (x, d_{a})$ is Borel as a countable infimum of continuous functions and equals the minimum by density and continuity. For each integer $s \geq 1$ , put $A_{a, s} = {x : J_{λ, I} (x, d_{a}) < b_{λ, I} (x) + 1 / s}$ . The rational points in [F6] give $A_{a, s} = ⋃_{q \in Q} {x : J_{λ, I} (x, d_{a}) < q} \cap {x : b_{λ, I} (x) > q - 1 / s}$ , so $A_{a, s}$ is Borel. Such indices exist by density; the least one's level set is $A_{a, s} ∖ ⋃_{b < a} A_{b, s}$ , and $x \mapsto d_{a (x, s)}$ is Borel because each open-set preimage is the union of the Borel level sets whose values lie in that open set. Strong convexity gives $J_{λ, I} (x, y) - J_{λ, I} (x, w_{λ, I}) \geq R^{2} ∥ y - w_{λ, I} ∥_{2}^{2}$ : apply the quadratic identity $∥ (1 - t) w + t y ∥_{2}^{2} = (1 - t) ∥ w ∥_{2}^{2} + t ∥ y ∥_{2}^{2} - t (1 - t) ∥ y - w ∥_{2}^{2}$ , convexity of the penalty, minimality, and let $t ↓ 0$ . Hence $∥ d_{a (x, s)} - w_{λ, I} (x) ∥_{2} < 1 / (R \sqrt{s})$ , so these Borel maps converge pointwise to $w_{λ, I}$ . Each selected map is countably valued with Borel level sets, so its coordinate functions are Borel; [F7] makes their pointwise limits measurable. Rational open boxes form a countable basis by [F6], so $w_{λ, I}$ is Borel. For each coordinate $j$ , the pair $(R_{I} (x), w_{λ, I, j} (x))$ is Borel because inverse images of rational rectangles are intersections of coordinate preimages and those rectangles form a countable basis of $R^{2}$ . Multiplication is continuous, so its composition with this pair map is Borel by the inverse-image definition; hence $z_{λ, I} (x) = R_{I} (x) w_{λ, I} (x)$ is Borel.

5.1F2F7step 2.1step 2.2step 3.1step 4.1

On the Borel event $E_{I} = {x : K_{I} (x) \neq \emptyset}$ , let $z_{*} (x)$ be its unique minimum-norm point from step 2.1 and put $w_{*} = z_{*} / R$ . Comparing the penalized minimum with the feasible $w_{*}$ gives $∥ z_{λ, I} (x) ∥_{2} \leq ∥ z_{*} (x) ∥_{2}$ and $\max {g_{I} (x, z_{λ, I} (x)), 0} \leq ∥ z_{*} (x) ∥_{2}^{2} / λ$ . The sequence $z_{λ, I} (x)$ lies in the compact closed ball of radius $R (x)$ by [F2]. Every sequence in a compact metric space has a convergent subsequence: if no point had infinitely many terms in every neighborhood, neighborhoods containing only finitely many term indices would cover the ball, contradicting a finite subcover; if one point did have infinitely many terms in every neighborhood, choosing the least successive indices in shrinking balls would give a convergent subsequence. Thus every subsequence has a convergent subsubsequence. By continuity of $g_{I}$ , each cluster point is feasible; the norm bound makes its norm no greater than $∥ z_{*} (x) ∥_{2}$ , so uniqueness in step 2.1 forces every cluster point to equal $z_{*} (x)$ . The full sequence therefore converges to $z_{*} (x)$ : otherwise a subsequence staying a fixed positive distance away would have a different cluster point. The maps equal to $z_{λ, I}$ on $E_{I}$ and $0$ off it are Borel: for an open set their inverse image is the branch-event intersection with the Borel inverse image under $z_{λ, I}$ , with $E_{I}^{c}$ added exactly when $0$ belongs to the open set. They converge everywhere, to $z_{*}$ on $E_{I}$ and to $0$ off it; their pointwise limit is Borel by [F7].

6.1F1F7step 2.1step 3.1step 5.1∎

The events $S = \emptyset$ , $S = Z$ , and $\min S = j$ are respectively countable intersections or combinations of the Borel nonemptiness events in step 3.1, so they are Borel by [F7]. On each such event the algorithm uses the corresponding Borel branch selector from step 5.1 or the continuous first-half mean. For every open target set, its inverse image under the piecewise map is the countable union of each branch event intersected with that branch map's Borel inverse image; it is Borel. Step 2.1 proves all branches defined and single-valued, so the complete output map is total and Borel.

LemmaStatement: AI-adaptedProof: AI-adaptedOpen item page →

The split-sample univariate trimmed mean is total and Borel measurable

Statement

Fix an integer $N \geq 1$ , $0 < ε \leq 1 / 4$ , and the split-sample rule in Split-sample univariate winsorized trimmed mean. It defines a total continuous, hence Borel measurable, map $R^{2 N} \to R$ for every admissible pair of observed samples, including tied values.

Facts & Assumptions

Given: $N \geq 1$ , $0 < ε \leq 1 / 4$ , and two real samples of length $N$ .

[F1]

The algorithm uses ranks $r (u) = ⌈ u N ⌉$ , sets its cutoffs to the second-half order statistics at ranks $r (ε)$ and $r (1 - ε)$ , clips first-half observations with $ϕ_{α, β} (x) = \min {β, \max {α, x}}$ , and returns their finite average (Split-sample univariate winsorized trimmed mean).

[F2]

A map between measurable spaces is Borel when preimages of Borel sets are Borel; open sets belong to the Borel sigma-algebra (A measurable function between measurable spaces, The Borel sigma-algebra of a topological space).

Proof

technique · direct

Given: $N \geq 1$ , $0 < ε \leq 1 / 4$ , and two real samples of length $N$ .

1.1F1givenalgebra

Since $0 < ε \leq 1 / 4$ , both $ε$ and $1 - ε$ lie in $(0, 1]$ . Thus $1 \leq r (ε), r (1 - ε) \leq N$ , and monotonicity of the ceiling gives $r (ε) \leq r (1 - ε)$ . The corresponding sorted values therefore satisfy $α \leq β$ , so every clipped value in [F1] is a finite real and the output is defined for every input, including ties.

1.2F1givenalgebra

For a scalar list $y_{1}, \dots, y_{N}$ , its $k$ th order statistic equals $\min_{J \subseteq {1, \dots, N}, ∣ J ∣ = k} \max_{j \in J} y_{j}$ : every $k$ -subset has a maximum at least the $k$ th smallest value, while the indices of the first $k$ sorted values attain it. This is a finite minimum of finite maxima of coordinate functions, hence is continuous in the list. The two cutoff maps in [F1] are therefore continuous; $ϕ_{α, β} (x)$ is continuous in $(α, β, x)$ because it is a composition of minimum and maximum, and the final finite average is continuous. Hence the estimator is a continuous map on $R^{2 N}$ .

2.1F2step 1.1step 1.2∎

For any Borel target set, its preimage under a continuous map is Borel: preimages of open sets are open, and the sets whose preimages are Borel form a sigma-algebra containing all open sets. By [F2] this is exactly Borel measurability, so the total estimator from step 1.1 is Borel.

LemmaStatement: AI-adaptedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

The multivariate trimmed-mean rate follows from a correct-scale slab event

Statement

Let $Σ$ be a finite covariance matrix in $R^{d}$ , $d \geq 1$ , with $tr Σ > 0$ , mean $μ$ , and $0 \leq λ_{\max} (Σ) \leq tr Σ$ as in Basic finite covariance matrix identities for robust mean bounds. Let $0 \leq η \leq 1 / 10$ , $0 < δ < 1$ , $N \geq 2560 \log (2 / δ)$ , and $ε = \max {10 η, 2560 \log (2 / δ) / N}$ . Define

Q_{0} = \max {\frac{256}{ε} \sqrt{\frac{tr Σ}{N}}, 16 \sqrt{\frac{λ_{\max} (Σ)}{ε}}} .

Fix $b > 0$ and any integer $i_{0}$ with $2^{i_{0}} \in [2 Q_{0}, 4 Q_{0})$ and any observed input tuple to Adaptive multivariate trimmed mean. If $K_{i_{0}}$ is nonempty and every $z \in K_{i_{0}}$ satisfies $∥ z - μ ∥_{2} \leq b ε Q_{0}$ , then the algorithm's output satisfies

∥ \hat{μ} - μ ∥_{2} \leq c_{b} [\sqrt{\frac{tr Σ}{N}} + \sqrt{\frac{λ_{\max} (Σ) \log (1 / δ)}{N}} + \sqrt{λ_{\max} (Σ) η}],

where

c_{b} = b \max {256 + 16 \sqrt{2560 \log 2}, 16 \sqrt{2560}, 16 \sqrt{10}} .

In particular, $b = 4$ recovers the original constant and $b = 16$ applies to the corrected slab proposition. This is a deterministic implication from the slab event; it does not assert that the event has high probability.

Facts & Assumptions

Given: The parameters, covariance matrix, mean, dyadic index, arbitrary observed data tuple, and the stated nonempty correct-scale slab condition.

[F1]

The selector returns a point of $K_{j}$ when $S = {j : K_{j} \neq \emptyset}$ has least element $j$ ; if $S = Z$ , it returns a point in the all-scale intersection; the sets $K_{j}$ are nested (Adaptive multivariate trimmed mean, Totality and measurability of the repaired multivariate trimmed-mean selector).

[F2]

The covariance matrix is positive semidefinite and $0 \leq λ_{\max} (Σ) \leq tr Σ$ (Basic finite covariance matrix identities for robust mean bounds).

[F3]

The logarithm is increasing and satisfies $\log (2 / δ) = \log 2 + \log (1 / δ)$ for $0 < δ < 1$ (The natural logarithm as the inverse of the exponential function, Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm).

Proof

technique · direct

Given: The positive-trace covariance, parameters, dyadic index, arbitrary observed input tuple, and correct-scale slab condition in the Statement.

1.1F1givenalgebra

Since $K_{i_{0}} \neq \emptyset$ , $i_{0} \in S$ . If $S = Z$ , [F1] puts the algorithm output in $⋂_{i \in Z} Γ (2^{i}) \subseteq K_{i_{0}}$ . If $S$ is nonempty and proper, its least element $j_{*}$ satisfies $j_{*} \leq i_{0}$ , so nesting in [F1] gives $K_{j_{*}} \subseteq K_{i_{0}}$ and the output again belongs to $K_{i_{0}}$ . Thus the event condition implies $∥ \hat{μ} - μ ∥_{2} \leq b ε Q_{0}$ .

2.1F2F3step 1.1algebra∎

The definition of $Q_{0}$ gives $b ε Q_{0} \leq 256 b \sqrt{tr Σ / N} + 16 b \sqrt{λ_{\max} (Σ) ε}$ . Since $ε \leq 10 η + 2560 \log (2 / δ) / N$ , square-root subadditivity and [F3] bound the second term by $16 b \sqrt{10 λ_{\max} (Σ) η} + 16 b \sqrt{2560 λ_{\max} (Σ) \log (1 / δ) / N} + 16 b \sqrt{2560 λ_{\max} (Σ) \log 2 / N}$ . By [F2] the final term is at most $16 b \sqrt{2560 \log 2} \sqrt{tr Σ / N}$ . These three coefficients are bounded by $c_{b}$ , giving the stated implication. At $b = 4$ this is exactly the previous constant.

LemmaStatement: AI-adaptedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

Exact recovery by the multivariate trimmed mean at zero covariance

Statement

Let $X$ be a Borel random vector in $R^{d}$ , $d \geq 1$ , with finite second moment, mean $μ$ , and covariance matrix $Σ$ as defined in Basic finite covariance matrix identities for robust mean bounds. Let two halves of size $N$ be iid clean copies, and let the observed vector be a sample-replacement version with at most $⌊ 2 η N ⌋$ changed coordinates in total. Assume $0 \leq η \leq 1 / 10$ , $0 < δ < 1$ , and $N \geq 2560 \log (2 / δ)$ . With $ε = \max {10 η, 2560 \log (2 / δ) / N}$ , if $tr Σ = 0$ , then Adaptive multivariate trimmed mean returns $μ$ almost surely.

Facts & Assumptions

Given: The clean iid halves, their zero-trace covariance, the sample-replacement budget, and the displayed parameter domain.

[F1]

For a finite-second-moment vector, zero covariance trace implies that the clean law is concentrated at its mean (Basic finite covariance matrix identities for robust mean bounds).

[F2]

The replacement model allows at most $⌊ 2 η N ⌋$ changed entries among the full vector of length $2 N$ ; the clean entries are iid and the observed entries may depend on all clean data (Adversarial sample replacement, Identical distribution and IID families).

[F3]

The algorithm uses the second-half directional order statistics at ranks $⌈ ε N / 2 ⌉$ and $⌈ (1 - ε / 2) N ⌉$ , clips first-half projections to the interval expanded by $Q$ , and returns the minimum-norm point of the all-scale intersection when every $K_{j}$ is nonempty (Adaptive multivariate trimmed mean).

[F4]

On the stated domain, $0 < ε \leq 1$ and $ε \geq 10 η$ (Adaptive multivariate trimmed mean).

[F5]

The all-scale minimum-norm selector is single-valued whenever its intersection is nonempty (Totality and measurability of the repaired multivariate trimmed-mean selector).

Proof

technique · direct

Given: The zero-trace covariance, iid clean halves of size $N$ , the sample-replacement budget, and the displayed $η, δ, N$ domain.

1.1F1F2F3F4givenalgebra

By [F1] and iid sampling in [F2], with probability one every clean coordinate in both halves equals $μ$ . Fix any such clean realization and any admissible replacement output. Each observed half has at most $m \leq ⌊ 2 η N ⌋ \leq 2 η N \leq ε N / 5$ changed coordinates. Put $q = ε N / 2$ , so $m < q \leq N / 2$ . The two ranks in [F3] are $r_{-} = ⌈ q ⌉$ and $r_{+} = ⌈ N - q ⌉ = N - ⌊ q ⌋$ . They satisfy $m < r_{-}, r_{+}$ and $r_{-}, r_{+} \leq N - m$ : indeed $r_{-} \leq ⌈ N / 2 ⌉ \leq N - m$ , while $r_{+} \geq ⌈ N / 2 ⌉ > m$ and $r_{+} = N - ⌊ q ⌋ \leq N - m$ . Thus for every unit $v$ , both order statistics of the second half equal $⟨ μ, v ⟩$ , since the unaltered projections occupy all ranks from $m + 1$ through $N - m$ .

2.1F3F4step 1.1algebra

For any $Q > 0$ and unit $v$ , the unaltered first-half projections equal $⟨ μ, v ⟩$ , while each changed projection after clipping to $[⟨ μ, v ⟩ - Q, ⟨ μ, v ⟩ + Q]$ differs from it by at most $Q$ . By step 1.1 these are the clipping endpoints used by [F3], so $∣ U_{Q} (v) - ⟨ μ, v ⟩ ∣ \leq m Q / N \leq 2 η Q \leq ε Q / 5 < 2 ε Q$ . Hence $μ \in Γ (Q)$ for every dyadic $Q = 2^{i}$ , and $μ \in K_{j}$ for every integer $j$ . Therefore $S = Z$ in [F3].

3.1F3F5step 1.1step 2.1algebra∎

Let $z$ belong to the algorithm's all-scale intersection. For each fixed unit $v$ and every integer $i$ , its slab constraint and step 2.1 imply $∣ ⟨ z - μ, v ⟩ ∣ \leq ∣ ⟨ z, v ⟩ - U_{2^{i}} (v) ∣ + ∣ U_{2^{i}} (v) - ⟨ μ, v ⟩ ∣ \leq 2 ε 2^{i} + 2 η 2^{i}$ . Letting $i \to - \infty$ gives $⟨ z - μ, v ⟩ = 0$ for every unit $v$ . If $z \neq μ$ , choosing $v = (z - μ) / ∥ z - μ ∥_{2}$ contradicts that equality; thus the all-scale intersection is exactly ${μ}$ . Since $S = Z$ , [F3] and [F5] make the algorithm return its unique point $μ$ . The argument holds on the probability-one event from step 1.1, proving the claim.

PropositionStatement: Literature-sourcedProof: AI-adaptedOpen item page →

Correct-scale slab bound for multivariate trimming

Statement

Let $X$ be an absolutely continuous random vector in $R^{d}$ with mean $μ$ and finite covariance matrix $Σ$ as defined in Basic finite covariance matrix identities for robust mean bounds. Let $X_{1}, \dots, X_{N}, Y_{1}, \dots, Y_{N}$ be $2 N$ iid clean copies and let their observed replacement sample have at most $⌊ 2 η N ⌋$ changed coordinates in total. Assume $0 \leq η \leq 1 / 10$ , $0 < δ < 1$ , $N \geq 2560 \log (2 / δ)$ , and $ε = \max {10 η, 2560 \log (2 / δ) / N} \leq 1$ . If $tr Σ > 0$ , put

Q_{0} = \max {\frac{256}{ε} \sqrt{\frac{tr Σ}{N}}, 16 \sqrt{\frac{λ_{\max} (Σ)}{ε}}} .

For the slabs and tail intersections in Adaptive multivariate trimmed mean, Every positive real lies below a dyadic scale less than twice as large supplies an integer $i_{0}$ with $2^{i_{0}} \in [2 Q_{0}, 4 Q_{0})$ . Then, with probability at least $1 - δ$ , $K_{i_{0}} = ⋂_{i \geq i_{0}} Γ (2^{i})$ is nonempty and every $z \in K_{i_{0}}$ satisfies $∥ z - μ ∥ \leq 16 ε Q_{0}$ . The positive-trace condition is required to make $Q_{0} > 0$ .

Facts & Assumptions

Given: The clean iid halves, replacement budget and parameter domain in the Statement, with positive covariance trace.

[F1]

A variance-sensitive bound for bounded empirical suprema: for bounded $∣ f ∣ \leq B$ with $P f^{2} \leq s^{2}$ , the centered supremum $Z$ satisfies $Z \leq E Z + 2 \sqrt{(8 E W + 4 N s^{2}) x} + \sqrt{8} B x$ outside probability $e^{- x}$ , where $W = \sup_{f} \sum_{i} f (X_{i})^{2}$ .

[F2]

Independent-process symmetrization for convex moments and One-sided coordinate Rademacher contraction supply ghost-sample symmetrization and coordinate contraction. In the proof below their one-sided forms are derived directly to keep the constants explicit.

[F3]

Basic finite covariance matrix identities for robust mean bounds gives $E ∥ X - μ ∥^{2} = tr Σ$ and $E ⟨ X - μ, v ⟩^{2} \leq λ_{\max} (Σ)$ for unit $v$ . Cauchy–Schwarz: $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥ ∥ y ∥$ , with equality exactly for dependent pairs and Markov's inequality for random variables give the norm and tail bounds used below.

[F4]

Adaptive multivariate trimmed mean defines the directional quantiles, clipped centers and slabs; Adversarial sample replacement permits at most $2 η N$ changes in either half, including sample-dependent choices.

[F5]

Dominated convergence passes bounded pointwise limits under integration. The iid finite product law is Independent random elements have product joint law; Every positive real lies below a dyadic scale less than twice as large gives the stated dyadic index.

[F6]

Since $tr Σ > 0$ , $d \geq 1$ , and $Q^{d}$ is countable and dense in $R^{d}$ ( $Q^{n}$ is a countable dense subset of $R^{n}$ , and rational open boxes form a countable basis); normalizing its nonzero elements gives a countable dense subset of $S^{d - 1}$ because normalization is continuous away from zero and every unit vector is nonzero.

Proof

Given: The objects in the Statement. Write $r = \sqrt{tr Σ / N}$ , $λ = λ_{\max} (Σ)$ and $x = ε N / 1280$ .

1.1F2F3F5F6algebra

Put $D = {q / ∥ q ∥_{2} : q \in Q^{d} ∖ {0}}$ and include the zero vector. By [F6], $D$ is countable and dense in $S^{d - 1}$ : rational vectors approximate every unit vector, and normalization is continuous at nonzero vectors. For each bounded continuous scalar map used below, the sample sums and their population expectations are continuous in direction, the latter by [F5]. Thus their suprema over $D \cup {0}$ equal the full directional suprema and are measurable. For any such class $g_{v}$ , use the independent clean half $Y_{1}, \dots, Y_{N}$ as the ghost copy of $X_{1}, \dots, X_{N}$ ; its product law and independence follow from [F5] and the iid hypothesis. When the same argument is applied to the $Y$ half, swap the roles of the two clean halves. Jensen gives $E \sup_{v} \sum_{i} (g_{v} (X_{i}) - P g_{v}) \leq E \sup_{v} \sum_{i} (g_{v} (X_{i}) - g_{v} (Y_{i}))$ . Pair swapping inserts independent signs; separating the two halves gives at most $2 E \sup_{v} \sum_{i} σ_{i} g_{v} (X_{i})$ . For an $L$ -Lipschitz scalar map $ψ$ , averaging one sign with arbitrary remaining offsets $A_{v}$ gives $\frac{1}{2} \sup_{v, w} (A_{v} + A_{w} + ψ (t_{v}) - ψ (t_{w})) \leq \frac{1}{2} \sup_{v, w} (A_{v} + A_{w} + L ∣ t_{v} - t_{w} ∣)$ . Swapping $v, w$ shows that the final supremum equals the one with $L (t_{v} - t_{w})$ ; successive coordinate replacements prove one-sided contraction with factor $L$ . Countable limits follow by monotone convergence after subtracting one fixed candidate, or bounded convergence on the finite sign space for a fixed sample. Finally set $S = \sum_{i} σ_{i} (X_{i} - μ)$ . Independence of the signs gives $E ∥ S ∥^{2} = N tr Σ$ . Since $u \leq 1 + u^{2}$ for $u \geq 0$ , $E ∥ S ∥ < \infty$ ; then $0 \leq E (∥ S ∥ - E ∥ S ∥)^{2} = E ∥ S ∥^{2} - (E ∥ S ∥)^{2}$ gives $E ∥ N^{- 1} S ∥ \leq r$ .

2.1F1F3step 1.1algebra

Put $h (t) = \min {1, (2 ∣ t ∣ / Q_{0} - 1)_{+}}$ . It is $2 / Q_{0}$ -Lipschitz, vanishes at zero and majorizes $1_{{∣ t ∣ \geq Q_{0}}}$ . By [F3], $P h (⟨ X - μ, v ⟩) \leq 4 λ / Q_{0}^{2} \leq ε / 64$ . For its centered supremum, step 1.1 gives $E Z / N \leq 4 r / Q_{0} \leq ε / 64$ . Since $h^{2} \leq h$ , $E W / N \leq ε / 32$ , and its second moment is at most $ε / 64$ . Apply [F1] separately to each clean half with $B = 1$ . Except on probability $e^{- x}$ for each half, its maximal empirical $h$ average is at most $ε / 32 + 2 \sqrt{5 ε x / (16 N)} + \sqrt{8} x / N = ε / 16 + \sqrt{8} ε / 1280 < ε / 8$ . Thus each clean half has fewer than $ε N / 8$ projections of centered absolute value at least $Q_{0}$ , uniformly in direction.

2.2F1F3step 1.1algebra

Fix $Q = 2^{i_{0}} \in [2 Q_{0}, 4 Q_{0})$ . Put $g_{v} (z) = ϕ_{- Q, Q} (⟨ z - μ, v ⟩)$ and $W_{Q} (v) = N^{- 1} \sum_{i} g_{v} (X_{i})$ . Antipodal directions and odd clipping make the absolute centered supremum equal its one-sided counterpart. Step 1.1 gives $E Z / N \leq 2 r$ . The square of clipping is $2 Q$ -Lipschitz and vanishes at zero, so the same symmetrization/contraction argument yields $E W / N \leq λ + 4 Q r$ for the squared-class supremum. Here $∣ g_{v} ∣ \leq Q$ and $P g_{v}^{2} \leq λ$ . Since $r \leq ε Q / 512$ and $λ \leq ε Q^{2} / 1024$ , [F1] bounds $\sup_{v} ∣ W_{Q} (v) - P W_{Q} (v) ∣$ outside probability $e^{- x}$ by $2 r + 2 \sqrt{19 ε Q^{2} x / (256 N)} + \sqrt{8} Q x / N < ε Q / 32$ . Also $∣ P g_{v} ∣ \leq E [∣ ⟨ X - μ, v ⟩ ∣ 1_{{∣ ⟨ X - μ, v ⟩ ∣ > Q}}] \leq λ / Q \leq ε Q / 1024$ , since the unclipped projection is centered.

3.1F4step 2.1algebra

Each observed half has at most $2 η N \leq ε N / 5$ changes. On both events of step 2.1, fewer than $13 ε N / 40 < ε N / 2$ projections in either observed half are outside $[⟨ μ, v ⟩ - Q_{0}, ⟨ μ, v ⟩ + Q_{0}]$ . Both directional quantile ranks $k = ⌈ ε N / 2 ⌉$ and $k = ⌈ (1 - ε / 2) N ⌉$ satisfy $k \geq ε N / 2$ and $N - k + 1 \geq ε N / 2$ ; in the potentially integral boundary the strict count inequality suffices. Hence both quantiles lie in that interval, including at $ε = 1$ . Write $a_{v} = α_{v} - ⟨ μ, v ⟩$ and $b_{v} = β_{v} - ⟨ μ, v ⟩$ , so $- Q_{0} \leq a_{v} \leq b_{v} \leq Q_{0}$ .

4.1F4step 2.1step 3.1step 2.2algebra

For any clean centered projection $t$ , the data-dependent clipping $ϕ_{a_{v} - Q, b_{v} + Q} (t)$ differs from $ϕ_{- Q, Q} (t)$ by at most $Q_{0}$ and agrees with it when $∣ t ∣ < Q - Q_{0}$ . Since $Q - Q_{0} \geq Q_{0}$ , step 2.1 bounds the average difference by $ε Q_{0} / 8 \leq ε Q / 16$ . The data-dependent clipping interval has length at most $2 Q + 2 Q_{0} \leq 3 Q$ , so first-half replacements change its average by at most $6 η Q \leq 3 ε Q / 5$ . Combining these bounds with step 2.2 gives $\sup_{v} ∣ U_{Q} (v) - ⟨ μ, v ⟩ ∣ \leq (3 / 5 + 1 / 16 + 1 / 32 + 1 / 1024) ε Q = 3557 ε Q / 5120 < ε Q$ . Thus $μ \in Γ (Q)$ and every $z \in Γ (Q)$ has $∥ z - μ ∥ \leq 3 ε Q < 12 ε Q_{0} \leq 16 ε Q_{0}$ .

5.1F4step 2.1step 2.2step 3.1step 4.1algebra∎

On the same events, for every $R \geq Q$ the clips at expanded intervals $[a_{v} - R, b_{v} + R]$ and $[a_{v} - 2 R, b_{v} + 2 R]$ differ by at most $R$ . They differ only on observed centered projections with absolute value at least $R - Q_{0} \geq Q_{0}$ . Their observed number is less than $13 ε N / 40$ by step 3.1, so $∣ U_{2 R} (v) - U_{R} (v) ∣ \leq 13 ε R / 40 < 2 ε R$ . Consequently $Γ (R) \subseteq Γ (2 R)$ , and $K_{i_{0}} = Γ (Q)$ is nonempty with the required radius. The three exceptional events in steps 2.1 and 2.2 have total probability at most $3 e^{- x} \leq 3 (δ / 2)^{2} \leq δ$ , because $ε N \geq 2560 \log (2 / δ)$ and $0 < δ < 1$ . This proves the proposition simultaneously for every admissible replacement of the clean samples.

Remarks

The constant $4 ε Q_{0}$ in the former statement and source Proposition 1 is false because the slab width scales with the chosen dyadic $Q$ , not $Q_{0}$ . The four-Q0 trimming slab radius is false gives an explicit continuous counterexample. The corrected bound preserves the main theorem's universal-constant rate. The zero-trace branch is Exact recovery by the multivariate trimmed mean at zero covariance.

TheoremStatement: Literature-sourcedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

Finite-variance Hilbert mean bound for geometric medians of means

Statement

Assume Countable Choice. Let $H$ be a separable real Hilbert space and let $X_{1}, \dots, X_{n}$ be iid Borel $H$ -valued random elements with $E ∥ X_{1} ∥^{2} < \infty$ . Let $μ = E_{B} X_{1}$ be their Bochner mean, define $x \otimes y : h \mapsto ⟨ h, y ⟩ x$ , and let

Σ = E_{B} [(X_{1} - μ) \otimes (X_{1} - μ)] \in S_{1} (H), V = tr Σ = E ∥ X_{1} - μ ∥^{2},

where $E_{B}$ denotes Bochner expectation, $S_{1} (H)$ is the Banach space of trace-class operators on $H$ , and $x \otimes y$ is the rank-one operator $h \mapsto ⟨ h, y ⟩ x$ . For $0 < p < a < 1 / 2$ , put $ψ (a; p) = a \log (a / p) + (1 - a) \log ((1 - a) / (1 - p))$ and $C_{a} = (1 - a) / \sqrt{1 - 2 a}$ . Set $a = 7 / 18$ , $p = 1 / 10$ , and

k = ⌊ \frac{\log (1 / δ)}{ψ (a; p)} ⌋ + 1.

If $0 < δ < 1$ and $k \leq n / 2$ , apply Geometric median of block means to $X_{1}, \dots, X_{n}$ using $k$ blocks and call the output $\hat{μ}$ . Then

P ⁣ (∥ \hat{μ} - μ ∥ > 11 \sqrt{\frac{V \log (1.4 / δ)}{n}}) \leq δ .

If $V > 0$ , the same bound holds with $\geq$ in place of $>$ in the displayed event. If $V = 0$ , then $\hat{μ} = μ$ almost surely. The finite-variance assumption is on the clean iid sample; no sample-replacement or Huber-contamination guarantee is asserted here.

Facts & Assumptions

Given: Countable Choice, a separable real Hilbert space $H$ , iid Borel random elements $X_{1}, \dots, X_{n}$ with finite second moment, $0 < δ < 1$ , and the displayed $k \leq n / 2$ condition.

[A1]

Countable Choice is used by Projection onto a nonempty closed convex set in the geometric-median selector and by the trace-class supplier chain; the Bochner integrability criterion itself is choice-free (The Axiom of Countable Choice ( ${A C}_{ω}$ ), Measurable minimum-norm geometric-median selection, Trace class operator).

[F1]

A Borel map into separable $H$ is strongly measurable by finite-valued approximations from a fixed dense sequence; strong measurability and integrability of the norm imply Bochner integrability (Strongly measurable Banach-valued function, Bochner-integrable function, Bochner integrability criterion).

[F2]

Trace-class operators form a Banach space under trace norm, and the trace is a bounded linear functional whose value on a nuclear representation $T h = ⟨ h, u ⟩ v$ is $⟨ v, u ⟩$ (Trace class operator, Trace class is a two sided Banach operator ideal, Trace is absolutely convergent and basis independent).

[F3]

The Bochner norm inequality and commutation with bounded linear maps give $∥ E_{B} Z ∥ \leq E ∥ Z ∥$ and $T (E_{B} Z) = E_{B} (T Z)$ for bounded linear $T$ (Bochner integral norm inequality, Bounded linear maps commute with Bochner integration).

[F4]

Independent random elements have product joint law; disjoint subfamilies of an independent family remain independent (Independent random elements have product joint law, Disjoint groups of an independent sigma-algebra family remain independent).

[F5]

For a nonnegative random variable $W$ and $t > 0$ , $P (W \geq t) \leq E W / t$ (Markov's inequality for random variables).

[F6]

Fubini applies to the integrable scalar cross-term $⟨ Y_{i}, Y_{l} ⟩$ under the product law of independent random elements (Fubini's theorem for L^1 functions on a sigma-finite product, Independent random elements have product joint law).

[F7]

The natural logarithm and exponential satisfy their usual inverse and algebraic identities (The natural logarithm as the inverse of the exponential function, The real exponential function and the number $e$ by a power series).

[F8]

For $0 < a < 1$ and $0 < p < 1$ , write $ψ (a; p) = a \log (a / p) + (1 - a) \log ((1 - a) / (1 - p))$ ; this is the Bernoulli relative-entropy expression used in the Chernoff calculation below.

[F9]

If a geometric median is farther than $C_{a} r$ from a point, more than $a k$ block centers are farther than $r$ from that point (A geometric median is close when a strict majority is close).

[F10]

Cauchy–Schwarz holds for the Hilbert inner product (Cauchy–Schwarz: $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥ ∥ y ∥$ , with equality exactly for dependent pairs).

[F11]

A nonnegative measurable function with integral zero vanishes almost everywhere (A nonnegative measurable function has integral $0$ exactly when it vanishes almost everywhere).

[F12]

The minimum-norm geometric-median selector is Borel, and the block means are continuous functions of the input sample (Geometric median of block means, Measurable minimum-norm geometric-median selection).

[F13]

Separability means that a nonempty space has an at-most-countable dense subset; A nonempty set is at most countable iff it is a surjective image of $N$ enumerates that subset by a sequence (Separability: the existence of an at most countable dense subset).

[L1]

If $t = (x - 1) / (x + 1)$ and $∣ t ∣ < 1$ , then $\log x = 2 \sum_{j = 0}^{\infty} t^{2 j + 1} / (2 j + 1)$ ; truncating after $j = M$ leaves absolute remainder at most $2 ∣ t ∣^{2 M + 3} / ((2 M + 3) (1 - t^{2}))$ . This follows by integrating the geometric series for $2 / (1 - t^{2})$ .

Proof

technique · direct

Given: Countable Choice, a separable real Hilbert space, the iid sample with finite second moment, the confidence parameter $δ$ , and the stated $k \leq n / 2$ condition.

1.1F1F13givenalgebra

The map $X_{1}$ is strongly measurable: by [F13], fix a countable dense sequence $(h_{j})$ in $H$ and approximate each $x \in H$ by the nearest of $h_{1}, \dots, h_{m}$ , breaking finite ties by the least index. The cells defining these finite-valued simple Borel maps are Borel because they are finite intersections of strict or weak comparisons of continuous distance functions, and the maps converge pointwise to $x$ . Since $∥ X_{1} ∥ \leq 1 + ∥ X_{1} ∥^{2}$ , $E ∥ X_{1} ∥ < \infty$ , so [F1] defines $μ = E_{B} X_{1}$ .

1.2F4F5F7F8F9algebra

If the geometric median is farther than $C_{a} r_{0}$ from $μ$ , [F9] forces more than $a k$ bad block means. For $W$ the number of bad blocks, independence and $P (bad block j) \leq p$ give $E e^{λ W} \leq (1 - p + p e^{λ})^{k}$ for $λ > 0$ . Markov's inequality with $λ = \log (a (1 - p) / (p (1 - a))) > 0$ gives $P (W \geq a k) \leq e^{- k ψ (a; p)} < δ$ , after substituting this $λ$ and simplifying.

2.1A1F2F3F10F11F12givenstep 1.1

For the rank-one operator $x \otimes y$ , [F10] gives $∥ x \otimes y ∥ \leq ∥ x ∥ ∥ y ∥$ , with equality by testing $y / ∥ y ∥$ when $y \neq 0$ ; its only possible nonzero singular value is this operator norm, so $∥ x \otimes y ∥_{1} = ∥ x ∥ ∥ y ∥$ . Apply the rank-one map to the finite-valued simple approximants from step 1.1: the resulting $S_{1} (H)$ -valued functions are simple and converge pointwise in trace norm, because $∥ u \otimes u - v \otimes v ∥_{1} \leq (∥ u ∥ + ∥ v ∥) ∥ u - v ∥$ . Hence $(X_{1} - μ) \otimes (X_{1} - μ)$ is strongly measurable; its trace norm is $∥ X_{1} - μ ∥^{2}$ , which is integrable since $E ∥ X_{1} - μ ∥^{2} \leq 2 E ∥ X_{1} ∥^{2} + 2 ∥ μ ∥^{2}$ . The Bochner integrability criterion gives its Bochner expectation $Σ$ in $S_{1} (H)$ . The bounded trace functional commutes with this integral by [F3], and [F2] gives $tr Σ = E ∥ X_{1} - μ ∥^{2} = V$ . For $h, g \in H$ , bounded evaluation maps commute with the integral and give $⟨ Σ h, g ⟩ = E [⟨ h, X_{1} - μ ⟩ ⟨ X_{1} - μ, g ⟩]$ ; this is symmetric in $h, g$ and is nonnegative when $h = g$ . If $V = 0$ , [F11] gives $X_{1} = μ$ almost surely. Identical distribution and a finite union of null events imply that all $X_{i} = μ$ simultaneously almost surely; hence every block mean is $μ$ . The objective in [F12] is then $k ∥ z - μ ∥$ , uniquely minimized at $μ$ , so $\hat{μ} = μ$ almost surely. Thus the strict-tail event in the Statement is empty when its threshold is zero. Assume $V > 0$ below.

3.1F3F4F6F10step 2.1algebra

Let $m_{j}^{\circ}$ be a block size. For centered $Y_{i} = X_{i} - μ$ , expand $E ∥ \sum_{i \in B_{j}} Y_{i} ∥^{2}$ into diagonal and cross terms. Each diagonal term is $V$ ; for $i \neq l$ , product-law independence [F4] and scalar Fubini [F6] give $E ⟨ Y_{i}, Y_{l} ⟩ = \int ⁣ \int ⟨ x, y ⟩ d P_{Y} (x) d P_{Y} (y) = 0$ . The integrand is integrable because [F10] gives $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥ ∥ y ∥$ and $E ∥ Y_{i} ∥ < \infty$ ; the inner integral is zero by [F3] and $E_{B} Y_{l} = 0$ . Dividing by $(m_{j}^{\circ})^{2}$ yields $E ∥ m_{j} - μ ∥^{2} = V / m_{j}^{\circ}$ .

4.1F4F5F12step 3.1givenalgebra

Since $k \leq n / 2$ , every block has size at least $⌊ n / k ⌋ \geq n / (2 k)$ . Put $r_{0} = \sqrt{2 k V / (p n)}$ . By [F5] and step 3.1, $P (∥ m_{j} - μ ∥ > r_{0}) \leq p$ for each block. The block means are independent by [F4], and [F12] makes their geometric-median aggregate a Borel random element.

5.1F9step 4.1step 1.2algebra

The same Chernoff calculation as step 1.2 applies to every $q < a$ . For each sufficiently large integer $s$ , use radius $(1 - 1 / s) r_{0}$ in step 4.1, so the bad-block probability is at most $p_{s} = p / (1 - 1 / s)^{2} < a$ . The event ${∥ \hat{μ} - μ ∥ \geq C_{a} r_{0}}$ is contained in the corresponding strict-radius event, whose probability is at most $e^{- k ψ (a; p_{s})}$ . Let $s \to \infty$ ; continuity gives $e^{- k ψ (a; p)} < δ$ .

6.1F7L1step 2.1step 4.1step 5.1algebra∎

For $a = 7 / 18$ and $p = 1 / 10$ , $C_{a} = (1 - a) / \sqrt{1 - 2 a}$ ; applying [L1] with $M = 50$ and $t = - 13 / 68, 13 / 22, 1 / 6$ gives $2915 / 10000 < ψ (a; p) < 2916 / 10000$ and $3364 / 10000 < \log (7 / 5)$ . Hence $5 / 18 < ψ (a; p) < \log (7 / 5)$ and $C_{a} \sqrt{2 / (p ψ (a; p))} \leq 11$ . From $k = ⌊ \log (1 / δ) / ψ (a; p) ⌋ + 1$ we have $k ψ (a; p) \leq \log (1 / δ) + ψ (a; p) < \log (7 / (5 δ))$ . Step 4.1 therefore gives the asserted nonstrict-tail bound for $V > 0$ after replacing $r_{0}$ by its expression; the strict-tail event is a subset, so its bound follows as well. When $V = 0$ , exact recovery in step 2.1 gives the strict-tail bound. No nonstrict-tail assertion at zero threshold is made.

TheoremStatement: Literature-sourcedProof: AI-adaptedOpen item page →

Univariate trimmed-mean bound under sample replacement

Statement

Assume Countable Choice. Let $X$ be an absolutely continuous real random variable with mean $μ$ and finite positive variance $σ^{2} = E [(X - μ)^{2}]$ (Moments, variance, and covariance on a probability space). Let $X_{1}, \dots, X_{N}, Y_{1}, \dots, Y_{N}$ be $2 N$ iid clean copies of $X$ , and let $({\tilde{X}}_{1}, \dots, {\tilde{X}}_{N}, {\tilde{Y}}_{1}, \dots, {\tilde{Y}}_{N})$ be a sample-replacement version with at most $⌊ 2 η N ⌋$ changed coordinates in total (Adversarial sample replacement). Let $0 \leq η$ , $0 < δ < 1$ , $δ \geq e^{- N / 4}$ , and

ε = 8 η + \frac{12 \log (4 / δ)}{N} \in (0, 1 / 4] .

Apply Split-sample univariate winsorized trimmed mean with these parameters. For the centered variable $Z = X - μ$ , define, for $0 < u < 1$ ,

Q_{u} (Z) = \sup {t \in R : P (Z \geq t) \geq 1 - u},

and, for $0 < u \leq 1$ , define

E (u, X) = \max {E [∣ Z ∣ 1_{{Z \leq Q_{u / 2} (Z)}}], E [∣ Z ∣ 1_{{Z \geq Q_{1 - u / 2} (Z)}}]} .

Here $E$ is the raw centered-tail functional, distinct from the excess-tail lower-bound functional. The claims are

P ⁣ (∣ \hat{μ} - μ ∣ \leq 3 E (4 ε, X) + 2 σ \sqrt{\frac{\log (4 / δ)}{N}}) \geq 1 - δ

and

P ⁣ (∣ \hat{μ} - μ ∣ \leq 10 \sqrt{ε} σ) \geq 1 - 4 e^{- ε N / 12} .

Facts & Assumptions

Given: Countable Choice, the absolutely continuous centered clean variable $Z = X - μ$ , the iid halves and replacement budget, and the displayed parameter domain.

[F1]

Apply An absolutely continuous upper quantile has its specified tail mass to the absolutely continuous variable $X$ . The threshold set defining $Q_{p} (Z)$ is the translate by $- μ$ of the one defining $Q_{p} (X)$ , so $q_{p} = Q_{p} (Z) = Q_{p} (X) - μ$ and $P (Z \leq q_{p}) = p$ , $P (Z \geq q_{p}) = 1 - p$ for $0 < p < 1$ . Countable Choice is retained from that supplier (The Axiom of Countable Choice ( ${A C}_{ω}$ )).

[F2]

Adversarial sample replacement allows at most $M = ⌊ 2 η N ⌋$ changes in either half. Split-sample univariate winsorized trimmed mean uses nearest-rank quantiles and clipping; The split-sample univariate trimmed mean is total and Borel measurable makes the output measurable and total.

[F3]

The proof of Bernstein inequality for bounded independent sums, step 2.1, establishes the one-sided bound $P (\sum_{i} V_{i} \geq u) \leq \exp [- u^{2} / (2 (v + b u / 3))]$ for centered independent summands with $∣ V_{i} ∣ \leq b$ and total variance $v$ . In particular, a centered average of variance at most $σ^{2} / N$ has upper or lower deviation at most $\sqrt{2 σ^{2} a / N} + 2 b a / (3 N)$ outside probability $e^{- a}$ , by substituting this threshold into the displayed bound. The zero-variance case is deterministic.

[F4]

Iid event indicators have the binomial distribution (Identical distribution and IID families, Bernoulli random variables and binomial random variables as sums of independent Bernoulli trials); Markov's inequality is Markov's inequality for random variables. Expectations and variances have their usual integral definitions (Expectation of a nonnegative or integrable random variable, Moments, variance, and covariance on a probability space).

Proof

Given: The objects in the Statement. Write $Z = X - μ$ , $ℓ = \log (4 / δ)$ , $t = ℓ / N$ , and $T (u) = E (u, X)$ ; step 1.1 verifies that centering the data shifts the estimator output by $- μ$ .

1.1F1F4givenalgebra

Shifting every clean and observed coordinate by $- μ$ shifts both order-statistic cutoffs, every clipped value, and the output by $- μ$ , so it suffices to analyze the centered data $Z$ . By [F1], for each $p \in (0, 1)$ the quantile $q_{p} = Q_{p} (Z)$ has $P (Z \leq q_{p}) = p$ and $P (Z \geq q_{p}) = 1 - p$ . Thus $∣ q_{p} ∣ \leq σ / \sqrt{\min (p, 1 - p)}$ : if $q_{p} \geq 0$ , use $σ^{2} \geq q_{p}^{2} P (Z \geq q_{p})$ ; if $q_{p} < 0$ , use $σ^{2} \geq q_{p}^{2} P (Z \leq q_{p})$ . For any event $A$ , $E [∣ Z ∣ 1_{A}] \leq σ \sqrt{P (A)}$ : when $P (A) > 0$ , this follows by expanding $0 \leq E [(∣ Z ∣ / σ - 1_{A} / \sqrt{P (A)})^{2}]$ , and the zero-probability case is immediate. Also $T$ is nondecreasing, since its tail sets expand with $u$ , and $T (4 ε) \leq σ \sqrt{2 ε}$ by [F1] and this inequality. For a lower clipping endpoint $a = q_{p}$ with $p \leq 1 / 2$ , put $L = E [∣ Z ∣ 1_{{Z \leq a}}]$ . If $a \leq 0$ , $E [(a - Z) 1_{{Z \leq a}}] \leq L$ . If $a > 0$ , centering implies $a (1 - p) \leq E [Z 1_{{Z > a}}] = - E [Z 1_{{Z \leq a}}] \leq L$ ; hence $a p \leq L$ and the clipping excess is at most $2 L$ . The symmetric upper-endpoint argument is identical. For a deterministic clip $W = ϕ_{a, b} (Z)$ , $E [(W - c)^{2}] = Var W + (E W - c)^{2}$ with $c = ϕ_{a, b} (0)$ , and $∣ W - c ∣ \leq ∣ Z ∣$ because clipping is 1-Lipschitz. Thus $Var W \leq σ^{2}$ ; also $∣ W - E W ∣ \leq b - a$ since both values lie in $[a, b]$ .

1.2F1F2F3F4algebra

First use inner endpoints $q_{2 ε}, q_{1 - 2 ε}$ and outer endpoints $q_{ε / 2}, q_{1 - ε / 2}$ . Require each of the two inner clean $Y$ tail counts to exceed $N (ε + 2 η)$ and each outer count to be less than $N (ε - 2 η)$ . Put $a = η / t \geq 0$ . Since $ε = (8 a + 12) t$ , [F3] for the binomial counts bounds each inner failure by $\exp [- 36 (a + 2)^{2} ℓ / (36 a + 56)] \leq e^{- 18 ℓ / 7}$ , and each outer failure by $\exp [- (2 a + 6)^{2} ℓ / ((28 / 3) a + 16)] \leq e^{- 9 ℓ / 4}$ . The two rational functions are increasing for $a \geq 0$ , as direct differentiation shows, so their minima are their values at zero. Thus all four count conditions hold outside probability $4 e^{- 9 ℓ / 4} \leq δ / 2$ , since $ℓ > \log 4$ . After $M \leq 2 η N$ changes the inner counts are still strictly greater than $ε N$ and outer counts strictly less than $ε N$ . Integer counts and the ranks $r_{-} = ⌈ ε N ⌉$ , $r_{+} = N - ⌊ ε N ⌋$ therefore give $q_{ε / 2} \leq α - μ \leq q_{2 ε}$ and $q_{1 - 2 ε} \leq β - μ \leq q_{1 - ε / 2}$ . For example fewer than $ε N$ values below an outer lower endpoint means at most $r_{-} - 1$ such values, while more than $ε N$ values above an inner upper endpoint means at least $⌊ ε N ⌋ + 1$ such values. These strict inequalities cover noninteger ranks and the integral boundary without a rounding loss.

2.1F2F3step 1.1step 1.2algebra

On the count event, monotonicity of clipping endpoints bounds the clean first-half clipped average above by the average of $W^{+} = ϕ_{q_{2 ε}, q_{1 - ε / 2}} (Z)$ and below by the average of $W^{-} = ϕ_{q_{ε / 2}, q_{1 - 2 ε}} (Z)$ . Step 1.1 bounds $E W^{+} \leq 2 T (4 ε)$ and $E W^{-} \geq - 2 T (4 ε)$ , their variances by $σ^{2}$ , and their interval widths by $2 \sqrt{2} σ / \sqrt{ε}$ . These comparison variables have fixed endpoints, so their deviation events are functions of the clean $X$ half and do not rely on the corrupted cutoffs being independent of it. Apply [F3] at $a = ℓ$ separately to the two comparisons. As $t / ε \leq 1 / 12$ , each deviation is at most $σ \sqrt{t} [\sqrt{2} + (4 \sqrt{2} / 3) \sqrt{t / ε}] \leq 2 σ \sqrt{t}$ . Their total exceptional probability is $2 e^{- ℓ} = δ / 2$ .

3.1F1F2step 1.1step 1.2step 2.1algebra

Write $A = q_{ε / 2}$ , $B = q_{1 - ε / 2}$ . Replacing at most $M$ first-half points changes the clipped average by at most $2 η (B - A) \leq (ε / 4) (B - A)$ . If $A \leq 0 \leq B$ , $(ε / 4) (B - A) \leq \max {(ε / 2) ∣ A ∣, (ε / 2) ∣ B ∣} \leq T (ε)$ . If both endpoints are positive, use $B - A \leq B$ and the same upper-tail bound; if both are negative, use $B - A \leq ∣ A ∣$ and its lower-tail bound. By monotonicity $T (ε) \leq T (4 ε)$ . Combining this with step 2.1 and the two exceptional probabilities proves the first displayed bound with its exact constants $3$ and $2$ , uniformly over every admissible sample-dependent replacement.

4.1F1F2F3step 1.1step 1.2step 2.1step 3.1algebra∎

For the second bound put $s = ε N / 12 \geq ℓ > \log 4$ and keep the same inner quantiles but use wider outer endpoints $q_{ε / 4}, q_{1 - ε / 4}$ . Use the same count thresholds $N (ε \pm 2 η)$ . Since $2 η \leq ε / 4$ , the inner downward gap is at least $3 ε / 4$ from mean $2 ε$ , and the outer upward gap is at least $ε / 2$ from mean $ε / 4$ . The function $u^{2} / (2 (p + u / 3))$ increases for $u > 0$ , so [F3] bounds each inner failure by $e^{- ε N / 8} = e^{- 3 s / 2}$ and each outer failure by $e^{- 3 ε N / 10} = e^{- 18 s / 5}$ . The same strict rank argument of step 1.2 brackets the corrupted cutoffs. For the fixed comparison clips, step 1.1 gives directional bias at most $2 T (4 ε) \leq 2 \sqrt{2} σ \sqrt{ε}$ , variance at most $σ^{2}$ and width at most $4 σ / \sqrt{ε}$ . Bernstein at $a = s$ therefore bounds each directional clean-average noise by $(1 / \sqrt{6} + 2 / 9) σ \sqrt{ε}$ . The replacement shift is at most $2 η \cdot 4 σ / \sqrt{ε} \leq σ \sqrt{ε}$ . The total error is consequently at most $(2 \sqrt{2} + 1 / \sqrt{6} + 2 / 9 + 1) σ \sqrt{ε} < 10 σ \sqrt{ε}$ . Its exceptional probability is at most $2 e^{- 3 s / 2} + 2 e^{- 18 s / 5} + 2 e^{- s} \leq 4 e^{- s}$ , because the first two terms sum to at most $4 e^{- 3 s / 2} \leq 2 e^{- s}$ . This proves the second assertion.

Remarks

The source distinguishes an excess-tail lower-bound functional from the raw-tail upper-bound functional used here. The former transcription into this theorem was false; The excess-tail functional cannot upper-bound the trimmed mean gives a continuous counterexample. The claimed univariate clean-quantile count exponent is too strong refutes a different source proof step. The exact-count and wider-outer-quantile arguments above avoid that step while preserving both estimator constants, confidence levels and the procedure. No atomic-law extension is claimed.

TheoremStatement: Literature-sourcedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

Multivariate trimmed-mean bound under sample replacement

Statement

Let $X$ be an absolutely continuous random vector in $R^{d}$ with mean $μ$ and finite covariance matrix $Σ$ as defined in Basic finite covariance matrix identities for robust mean bounds. Let $X_{1}, \dots, X_{N}, Y_{1}, \dots, Y_{N}$ be $2 N$ iid clean copies and let their observed replacement sample have at most $⌊ 2 η N ⌋$ changed coordinates in total. Assume $0 \leq η \leq 1 / 10$ , $0 < δ < 1$ , and $N \geq 2560 \log (2 / δ)$ . Set $ε = \max {10 η, 2560 \log (2 / δ) / N}$ and let $\hat{μ}$ be the repaired, total selector in Adaptive multivariate trimmed mean. Then there is a universal constant $c > 0$ such that

P ⁣ (∥ \hat{μ} - μ ∥ \leq c [\sqrt{\frac{tr Σ}{N}} + \sqrt{\frac{λ_{\max} (Σ) \log (1 / δ)}{N}} + \sqrt{λ_{\max} (Σ) η}]) \geq 1 - δ .

The claim is restricted to the displayed domain, which ensures $ε \leq 1$ . No guarantee is asserted for $1 / 10 < η < 1 / 2$ , for $η \geq 1 / 2$ , or for atomic laws.

Facts & Assumptions

Given: The iid clean law, replacement coupling and parameters in the Statement.

[F1]

Correct-scale slab bound for multivariate trimming gives a nonempty dyadic tail intersection with radius $16 ε Q_{0}$ outside probability $δ$ when the covariance trace is positive.

[F2]

The multivariate trimmed-mean rate follows from a correct-scale slab event turns a radius $b ε Q_{0}$ into the displayed rate with an explicit universal constant $c_{b}$ ; it applies at $b = 16$ .

[F3]

Exact recovery by the multivariate trimmed mean at zero covariance gives exact recovery when the covariance trace is zero. Basic finite covariance matrix identities for robust mean bounds gives nonnegative covariance trace.

[F4]

Adaptive multivariate trimmed mean and Totality and measurability of the repaired multivariate trimmed-mean selector supply the total Borel selector on every admissible observed input.

Proof

Given: The objects and hypotheses in the Statement.

1.1F1F2F4given

If $tr Σ > 0$ , [F1] supplies, with probability at least $1 - δ$ , the nonempty correct-scale tail intersection of radius $16 ε Q_{0}$ . On that event [F2] at $b = 16$ bounds the output of [F4] by exactly the displayed three-term rate, with universal constant $c_{16}$ . The selector's measurability in [F4] makes the error event measurable.

2.1F3step 1.1algebra∎

If $tr Σ = 0$ , [F3] gives exact recovery almost surely, so the error bound holds with probability one. These are the only cases by [F3], and the same positive constant $c_{16}$ works in both. Thus the claimed probability is at least $1 - δ$ throughout the stated domain.

5 · Examples, counterexamples and false statements

None yet.