Theorem 4.5 — Tight sample complexity of detecting the sign of feedback
OpenAutomatedMarketStress557.Persistence.Supplement.tight_sample_complexity_detecting_feedbackLet the returns follow , , for , where are independent standard normal variables (Gaussian news, ), the real initial return is independent of the news with almost surely and fair initial sign , and
Write for the law of the observed path ; the experiments and use the same initial return and the same news.
- Upper bound. Let , and let the test output "herding" () iff , and otherwise. For every and every with
the probability that the test's output differs from is at most .
- Lower bound. For every , every with
and every measurable, possibly randomized test of the full path , the error of under or its error under is larger than .
Logarithms are natural. The two thresholds agree up to a constant factor: the simplest serial statistic, which reads only the signs, detects the direction of feedback with essentially as few observations as any test that sees the full real returns. The theorem is a companion to the mission's goal (Theorem 4.2): marginal statistics cannot distinguish from , while this serial test can, at a quantified cost.
Formalization Note A test is a measurable giving the probability of answering "herding"; its error under is and under is . The lower bound is stated contrapositively: below the threshold, the larger of the two errors exceeds .
Differences from the source:
- encoding: D₀ uniform on {±1} for D₀ = sgn(r₀), r₀ independent of the news → r₀ a real random variable independent of the whole news sequence with r₀ ≠ 0 almost surely, and the published Model applied to the initial sign sgn(r₀) with ν the standard Gaussian; reason: the same set of initial laws; the Model's continuity, monotonicity and symmetry clauses hold for Φ and its sign-independence clause follows from the independence of r₀
- encoding: "unless n ≥ ½ (s/β)² log(1/(4δ))" → n < ½ (s/β)² log(1/(4δ)) implies the larger of the two errors exceeds δ; reason: the literal contrapositive
- generalization: every test that observes the full returns → every measurable ψ from paths to [0,1], the probability of answering herding, with errors defined by integrals; reason: randomized tests are included as well; a deterministic test is the indicator of a measurable set, so the Lean bound specializes to the source's
- encoding: the laws P± of (r₀, …, rₙ) under ±β, with the same law of r₀ → pushforwards of P under the observed-path map at β and at −β, for the same r₀ and news; reason: a path law depends only on the joint law of r₀ and the news, so this realizes every pair of experiments with a common initial law
- encoding: sgn with sgn(0) unspecified → a sign function with value +1 at 0; reason: every observed return is nonzero almost surely, so no instance changes
- encoding: δ with no stated lower bound → 0 < δ in both parts; reason: log(1/δ) and log(1/(4δ)) are defined only for δ > 0, so this excludes only undefined cases
import Mathlib import Definitions.Def_AutomatedMarketStress557_Persistence_Model import Definitions.Def_AutomatedMarketStress557_Persistence_Supplement_FeedbackDetection open MeasureTheory ProbabilityTheory open scoped ENNReal
namespace AutomatedMarketStress557.Persistence.Supplement
open AutomatedMarketStress557.Persistence
/-- Theorem 4.5 (Tight sample complexity of detecting feedback), Irene Aldridge,
STOC 2027 submission #557 (October 2026), PDF pp. 3–4. Gaussian news, `0 < |β| ≤ s`.
Upper bound: the sign-agreement test errs with probability at most `δ` once
`n ≥ 9 (s/β)² log(1/δ)`. Lower bound: for `δ < 1/4`, every measurable, possibly
randomized test of the full real path `(r₀, …, rₙ)` has error larger than `δ`
under `β` or under `-β` whenever `n < ½ (s/β)² log(1/(4δ))`. The `±β`
experiments share the initial return and the news. -/
theorem tight_sample_complexity_detecting_feedback {Ω : Type*} [MeasurableSpace Ω]
(P : Measure Ω) [IsProbabilityMeasure P] (r₀ : Ω → ℝ) (ξ : ℕ → Ω → ℝ)
(hE : GaussianExperiment P r₀ ξ) (β s : ℝ) (hβ : 0 < |β|) (hβs : |β| ≤ s) :
(∀ (n : ℕ) (δ : ℝ), 0 < δ →
9 * (s / β) ^ 2 * Real.log (1 / δ) ≤ n →
P.real {ω | agreementTest n (observedPath β s r₀ ξ n ω) ≠ sign β} ≤ δ) ∧
(∀ (n : ℕ) (δ : ℝ), 0 < δ → δ < 1 / 4 →
(n : ℝ) < 1 / 2 * (s / β) ^ 2 * Real.log (1 / (4 * δ)) →
∀ ψ : (Fin (n + 1) → ℝ) → ℝ, Measurable ψ → (∀ x, 0 ≤ ψ x ∧ ψ x ≤ 1) →
δ < max (testError P β s r₀ ξ n ψ) (testError P (-β) s r₀ ξ n ψ)) := by sorry
end AutomatedMarketStress557.Persistence.Supplement