REACH variance is at most Monte Carlo variance
ProvedFormalizedScopeReach.reach_variance_le_monteCarloAssume a countable vocabulary, normalized original and outcome-avoiding laws, and almost surely unequal outcome and threshold times under the original law. For every positive common sample count, REACH under independent outcome-avoiding sampling and the Monte Carlo estimator under independent original sampling both have finite second moments. The variance of REACH is less than or equal to the variance of Monte Carlo. The actual threshold is retained, and no bound or finite expectation is imposed on the number of tokens.
import Definitions.Def_FormalizedScopeReach_Trials open scoped BigOperators ENNReal open MeasureTheory ProbabilityTheory
namespace FormalizedScopeReach
theorem reach_variance_le_monteCarlo {V : Type} [Countable V] (M : Model V)
[IsProbabilityMeasure (originalLaw M)] [IsProbabilityMeasure (avoidingLaw M)]
(hne : ∀ᵐ x ∂originalLaw M, T_O M x ≠ T_E M x) (n : ℕ) (hn : 0 < n) :
MemLp (ℛ M n) 2 (iidLaw (avoidingLaw M) n) ∧
MemLp (M₀ M n) 2 (iidLaw (originalLaw M) n) ∧
variance (ℛ M n) (iidLaw (avoidingLaw M) n) ≤
variance (M₀ M n) (iidLaw (originalLaw M) n) := by sorry
end FormalizedScopeReach
Read-back
What the Lean code literally says, in plain math · GPT-6 (Codex independent sub-agent)
Read-back: FormalizedScopeReach.reach_variance_le_monteCarlo
For every countable, possibly finite, type , every model consisting of a distinguished element , a probability mass function for each finite list of elements of (with ), and a predicate on finite lists satisfying , the following implication holds. A timeline is any finite list over , and every set of timelines is measurable. Write for its length, for its prefix of length , and for its element at zero-based index . Call terminal when holds and fails for every . Give each terminal list original weight and every other list weight zero, and let , where is unit point mass at . Define the avoiding transition weight by if and otherwise, with this subtraction and division taken in the extended nonnegative reals. Give a list avoiding weight if it is terminal and contains no , and weight zero otherwise, and let . Assume separately that both and have total mass one. For each list , let be one plus the zero-based index of its first occurrence of if an occurrence exists, and otherwise; let be the least natural number such that holds, and if there is no such . These times take values in . Assume for -almost every ; this assumption is under the original law, and permits a null set of ties. For every natural number with , consider the product probability measures and on indexed families of timelines. Put regarded as a real number, define the real score , and define the real functions and . Then all three assertions hold: is almost everywhere strongly measurable and has finite second moment under ; is almost everywhere strongly measurable and has finite second moment under ; and . Here the finite-second-moment assertions mean that the square root of the nonnegative extended integral of the squared absolute value is finite. Variance is the real conversion of the nonnegative extended integral of under the indicated measure ; the asserted square integrability makes this the usual finite variance. The inequality is non-strict and includes equality and zero variance. No bound on timeline length, monotonicity of , or separate positivity assumption on is required. Every lies in , so its real conversion is finite; if , every other token has probability zero and the corresponding avoiding fraction is in the extended nonnegative reals. The total-mass-one hypotheses still have to hold with those weights. Empty products are one, so ; the empty list has zero weight under both laws because is false. On every terminal list is finite, so the no-ties assumption excludes positive original probability of a first occurrence of at the final position. On arbitrary lists with neither an occurrence nor a stopping prefix both times equal , and the strict-order indicator is zero. The definitions of the averages also assign zero at by empty summation and real division by zero, but the theorem excludes that value of . An empty type admits no such model because the model includes , and models for which either specified law fails to have total mass one do not satisfy the hypotheses.
Confirmed by the mission captain (proposal self-audit).