Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Observed return paths, the sign-agreement detector and test errors for feedback detection

Definition
AutomatedMarketStress557_Persistence_Supplement_FeedbackDetection

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

automated-marketshypothesis-testingp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1probability

Let (Ω,F,P)(\Omega,\mathcal F,P)(Ω,F,P) be a probability space carrying a real initial return r0r_0r0​ and news variables ξ1,ξ2,…\xi_1,\xi_2,\ldotsξ1​,ξ2​,…. The Gaussian experiment hypothesis says: the ξt\xi_tξt​ are independent standard normal variables, r0r_0r0​ is a random variable independent of the whole news sequence, r0≠0r_0\neq0r0​=0 almost surely, and the initial sign D0=sgn⁡(r0)D_0=\operatorname{sgn}(r_0)D0​=sgn(r0​) is uniform on {−1,+1}\{-1,+1\}{−1,+1}. Apart from this, the law of r0r_0r0​ is arbitrary. This is Assumption 1 of the paper with G=ΦG=\PhiG=Φ, expressed through the published feedback model applied to the initial sign D0D_0D0​.

For feedback β∈R\beta\in\mathbb Rβ∈R and scale sss, the observed returns are r0r_0r0​ itself at time 000 and, for t≥1t\ge1t≥1,

rt=βDt−1+sξt,Dt=sgn⁡(rt).r_t=\beta D_{t-1}+s\xi_t,\qquad D_t=\operatorname{sgn}(r_t).rt​=βDt−1​+sξt​,Dt​=sgn(rt​).

After nnn transitions the observation is the path (r0,…,rn)∈Rn+1(r_0,\ldots,r_n)\in\mathbb R^{n+1}(r0​,…,rn​)∈Rn+1, and PβP_\betaPβ​ denotes its law. The same r0r_0r0​ and news give the experiments PβP_\betaPβ​ and P−βP_{-\beta}P−β​, so the two experiments share their initial law.

For a path x=(x0,…,xn)x=(x_0,\ldots,x_n)x=(x0​,…,xn​) the sign-agreement statistic is

q^=1n∑t=1n1[sgn⁡xt=sgn⁡xt−1],\hat q=\frac1n\sum_{t=1}^n\mathbf 1[\operatorname{sgn}x_t=\operatorname{sgn}x_{t-1}],q^​=n1​t=1∑n​1[sgnxt​=sgnxt−1​],

and the detector outputs +1+1+1 ("herding", positive feedback) if q^>12\hat q>\tfrac12q^​>21​ and −1-1−1 (negative feedback) otherwise; ties at q^=12\hat q=\tfrac12q^​=21​ are decided negative.

A (possibly randomized) test of the full path is a measurable ψ:Rn+1→[0,1]\psi:\mathbb R^{n+1}\to[0,1]ψ:Rn+1→[0,1], read as the probability of answering "herding". Its error under feedback β\betaβ is ∫(1−ψ) dPβ\int(1-\psi)\,dP_\beta∫(1−ψ)dPβ​ when β>0\beta>0β>0 and ∫ψ dPβ\int\psi\,dP_\beta∫ψdPβ​ when β≤0\beta\le0β≤0. Deterministic tests are the indicator functions of measurable sets.

These objects are the setting of the paper's Theorem 4.5 on the sample complexity of detecting the sign of feedback.

Formalization Note The sign function maps 000 to +1+1+1; positive-time returns are nonzero almost surely, and r0≠0r_0\neq0r0​=0 almost surely by hypothesis. For n=0n=0n=0 the statistic is 000, so the detector answers negative. Path laws are pushforward measures on Fin (n+1) → ℝ.

Definition code
import Mathlib
import Definitions.Def_AutomatedMarketStress557_Persistence_Model

open MeasureTheory ProbabilityTheory
open scoped ENNReal
noncomputable section

namespace AutomatedMarketStress557.Persistence.Supplement

open AutomatedMarketStress557.Persistence

/-- The hypotheses of Theorem 4.5 (PDF pp. 3–4) on the randomness: Assumption 1
(PDF p. 3) with Gaussian news `G = Φ`, stated through the published `Model` with
initial sign `D₀ = sgn r₀`. The initial return `r₀` itself is a real random
variable, independent of the entire news sequence (Assumption 1), with
`r₀ ≠ 0` almost surely, which is what "D₀ uniform on {±1}" means for
`D₀ = sgn r₀`. Its law is otherwise arbitrary. Feedback and scale are not part
of the predicate; the same `r₀, ξ` serve the `+β` and `-β` experiments. -/
def GaussianExperiment {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω)
    (r₀ : Ω → ℝ) (ξ : ℕ → Ω → ℝ) : Prop :=
  Model P (gaussianReal 0 1) (fun ω => sign (r₀ ω)) ξ ∧ AEMeasurable r₀ P ∧
  IndepFun r₀ (fun ω n => ξ n ω) P ∧ (∀ᵐ ω ∂P, r₀ ω ≠ 0)

/-- The observed returns `r₀, r₁, …` of equation (3), PDF p. 2: time zero is the
actual real initial return, and every later return is the published recursion
started from the initial sign `sgn r₀`. -/
def observedReturn {Ω : Type*} (β s : ℝ) (r₀ : Ω → ℝ) (ξ : ℕ → Ω → ℝ) :
    ℕ → Ω → ℝ
  | 0 => r₀
  | t + 1 => returns β s (fun ω => sign (r₀ ω)) ξ (t + 1)

/-- The observation `(r₀, …, rₙ)` after `n` transitions. -/
def observedPath {Ω : Type*} (β s : ℝ) (r₀ : Ω → ℝ) (ξ : ℕ → Ω → ℝ) (n : ℕ)
    (ω : Ω) : Fin (n + 1) → ℝ :=
  fun i => observedReturn β s r₀ ξ i ω

/-- The law `P_β` of `(r₀, …, rₙ)` under feedback `β`. -/
def pathLaw {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) (β s : ℝ)
    (r₀ : Ω → ℝ) (ξ : ℕ → Ω → ℝ) (n : ℕ) : Measure (Fin (n + 1) → ℝ) :=
  P.map (observedPath β s r₀ ξ n)

/-- The number of sign agreements `D_t = D_{t-1}`, `t = 1, …, n`, of a path. -/
def agreementCount (n : ℕ) (x : Fin (n + 1) → ℝ) : ℕ :=
  (Finset.univ.filter fun t : Fin n => sign (x t.succ) = sign (x t.castSucc)).card

/-- The sign-agreement statistic `q̂ = (1/n) ∑_{t=1}^n 1[D_t = D_{t-1}]`. -/
def agreementFraction (n : ℕ) (x : Fin (n + 1) → ℝ) : ℝ :=
  (agreementCount n x : ℝ) / n

/-- The detector of Theorem 4.5: `+1` ("herding", positive feedback) iff
`q̂ > 1/2`, and `-1` (negative feedback) otherwise, ties included. -/
def agreementTest (n : ℕ) (x : Fin (n + 1) → ℝ) : ℝ :=
  if 1 / 2 < agreementFraction n x then 1 else -1

/-- Misclassification probability of a (possibly randomized) test of the full
path under feedback `β`: `ψ x ∈ [0,1]` is the probability that the test outputs
"herding" (positive feedback) on the observation `x`. For `β > 0` an error is
the output "negative"; otherwise an error is the output "herding". -/
def testError {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) (β s : ℝ)
    (r₀ : Ω → ℝ) (ξ : ℕ → Ω → ℝ) (n : ℕ) (ψ : (Fin (n + 1) → ℝ) → ℝ) : ℝ :=
  if 0 < β then ∫ x, (1 - ψ x) ∂(pathLaw P β s r₀ ξ n)
  else ∫ x, ψ x ∂(pathLaw P β s r₀ ξ n)

end AutomatedMarketStress557.Persistence.Supplement
Source
Irene Aldridge, STOC 2027 submission #557 (October 2026), Theorem 4.5 and its proof, PDF pp. 3–4; equation (3), PDF p. 2; Assumption 1, PDF p. 3; https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/557.pdf

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me