Theorem 5.1 — verified search with correlated errors
OpenCorrelatedLocalSearch.Supplement.theorem_5_1local-searchp2o-gran-per-chapterp2o-plan-paperp2o-v1probabilitytheoretical-computer-scienceweak-random-sources
For any ordered predecessor tree, , , and primitive-error law satisfying (14), the exact Appendix F walk halts almost surely, returns the predecessor with error at most , and uses
The algorithm is chosen without the correct leaf depth or a tree-height bound; every move makes all primitive queries, including prescribed dummies.
Differences from the source:
- encoding: with division-by-zero convention → a cubic bound always and a linear-over-margin bound when ; reason: their conjunction is exactly the stated minimum with the second branch infinite at criticality
- encoding: an ordered predecessor tree and the Appendix F walk described in prose → explicit half-open child intervals and a block-by-block state recursion consuming all three majority blocks, including dummies; reason: this makes the source's exact algorithm binding without changing any run
- encoding: expectation of a possibly infinite query count → an
ENNReallower Lebesgue integral of an infinity-valued natural query count; reason: nonintegrability gives infinity rather than a default value
Preamble
import Mathlib import Definitions.Def_CorrelatedLocalSearch_Supplement_VerifiedSearch set_option autoImplicit false
Formal statement
namespace CorrelatedLocalSearch.Supplement
open MeasureTheory
open scoped ENNReal BigOperators
/-- Xu, arXiv:2607.17469 (sha256 17e00d69…), Theorem 5.1, p.14 (PDF p.16), with the
exact Appendix F schedule. For every ordered tree, the algorithm is chosen without the correct
depth or a height bound; it returns the predecessor with error at most `eta` and has the full
cubic-to-linear primitive-query expectation. -/
theorem theorem_5_1 (p : Real) (hp0 : 1 / 2 < p) (hp1 : p < 1) :
∃ C : Real, 0 < C ∧
∀ tree : OrderedSearchTree, ∀ D : Real, 1 ≤ D -> ∀ eta : Real, 0 < eta -> eta < 1 ->
IsOrderedPredecessorTree tree ->
∃ A : VerifiedSearchAlgorithm tree,
UsesAppendixFSchedule p D eta A ∧
∀ target correct h, (∃ u : tree.Node, tree.leafLabel u = some correct ∧
tree.depth u = h ∧ TargetInLeafInterval tree u target) ->
∀ s, searchThreshold p ≤ s -> s ≤ 1 ->
∀ nu : Measure (Nat -> Bool), nu ∈ SourceClass (errorPi p) s D ->
nu {omega | A.queries target omega = ⊤} = 0 ∧
nu {omega | A.answer target omega ≠ some correct} ≤ ENNReal.ofReal eta ∧
let K := (h : Real) + Real.log D + Real.log (1 / eta) + 1
(∫⁻ omega, ((A.queries target omega : ℕ∞) : ENNReal) ∂nu) ≤
ENNReal.ofReal (C * K ^ 3) ∧
(0 < s - searchThreshold p ->
(∫⁻ omega, ((A.queries target omega : ℕ∞) : ENNReal) ∂nu) ≤
ENNReal.ofReal (C * K / (s - searchThreshold p))) := by sorry
end CorrelatedLocalSearch.Supplement
Source
Xu, Local Search with Correlated Randomness, arXiv:2607.17469 (sha256 17e00d69…), Theorem 5.1, p.14 (PDF p.16), schedule App. F pp.40–41 (PDF pp.42–43)