General finite-alphabet tapes, prefix-bounded sources and prefix capacity
DefinitionCorrelatedLocalSearch_Supplement_GeneralSourcelocal-searchp2o-gran-per-chapterp2o-plan-paperp2o-v1probabilitytheoretical-computer-scienceweak-random-sources
Let be a finite alphabet, let be a full-support probability mass function on , and let . For a word , its cylinder has reference mass . The source class consists of probability laws on whole tapes satisfying for every finite word. For a closed event , is the infimum of over finite prefix-free cylinder covers of .
This general, nonuniform model is used by every non-SAT result in the supplement. It is a whole-prefix constraint, not a per-step conditional bound.
Formalization Note Tapes are functions with zero-based positions. Capacities and probabilities are in .
Definition code
import Mathlib
set_option autoImplicit false
namespace CorrelatedLocalSearch.Supplement
open MeasureTheory Filter Topology
open scoped ENNReal BigOperators
/-- A zero-based finite prefix of a tape over a general alphabet. -/
def tapePrefix {A : Type*} (omega : Nat -> A) (t : Nat) : List A :=
List.ofFn (fun i : Fin t => omega i)
/-- The cylinder generated by a finite word. -/
def cylinder {A : Type*} (w : List A) : Set (Nat -> A) :=
{omega | tapePrefix omega w.length = w}
/-- The reference product mass `P[w] = product_i pi(w_i)`. -/
noncomputable def wordMass {A : Type*} (pi : A -> Real) (w : List A) : Real :=
(w.map pi).prod
/-- The paper's whole-tape prefix-bounded source class over a finite full-support alphabet. -/
def SourceClass {A : Type*} [MeasurableSpace A] (pi : A -> Real) (s D : Real) :
Set (Measure (Nat -> A)) :=
{nu | IsProbabilityMeasure nu ∧
∀ w : List A,
nu (cylinder w) ≤ ENNReal.ofReal (D * wordMass pi w ^ s)}
/-- A finite prefix-free cylinder cover of an event. -/
def IsPrefixFreeCover {A : Type*} (E : Set (Nat -> A)) (B : Finset (List A)) : Prop :=
(E ⊆ ⋃ w ∈ (B : Set (List A)), cylinder w) ∧
∀ u ∈ B, ∀ v ∈ B, u ≠ v → ¬ (u <+: v) ∧ ¬ (v <+: u)
/-- The powered reference cost of a finite word family. -/
noncomputable def coverCost {A : Type*} (pi : A -> Real) (s : Real)
(B : Finset (List A)) : ENNReal :=
∑ w ∈ B, ENNReal.ofReal (wordMass pi w ^ s)
/-- The finite-prefix-cover capacity `C_s(E)` of (2). -/
noncomputable def prefixCapacity {A : Type*} (pi : A -> Real) (s : Real)
(E : Set (Nat -> A)) : ENNReal :=
⨅ B : Finset (List A), ⨅ (_h : IsPrefixFreeCover E B), coverCost pi s B
/-- An event is determined by its first `T` symbols. -/
def DependsOnFirst {A : Type*} (E : Set (Nat -> A)) (T : Nat) : Prop :=
∀ omega omega', tapePrefix omega T = tapePrefix omega' T → (omega ∈ E ↔ omega' ∈ E)
/-- The best cost among covers whose words all have one prescribed depth. -/
noncomputable def singleDepthCost {A : Type*} (pi : A -> Real) (s : Real)
(E : Set (Nat -> A)) (t : Nat) : ENNReal :=
⨅ B : Finset (List A),
⨅ (_h : IsPrefixFreeCover E B ∧ ∀ w ∈ B, w.length = t), coverCost pi s B
/-- The worst probability of an event over a prefix-bounded source class. -/
noncomputable def worstProbability {A : Type*} [MeasurableSpace A] (pi : A -> Real)
(s D : Real) (E : Set (Nat -> A)) : ENNReal :=
⨆ nu : {nu : Measure (Nat -> A) // nu ∈ SourceClass pi s D}, nu.1 E
/-- Main catalog declaration for the general finite-alphabet prefix source model. -/
abbrev GeneralSource {A : Type*} [MeasurableSpace A]
(pi : A -> Real) (s D : Real) := SourceClass pi s D
end CorrelatedLocalSearch.Supplement
Source
Xu, Local Search with Correlated Randomness, arXiv:2607.17469 (sha256 17e00d69…), §2, eqs. (1)–(2), pp.5–6 (PDF pp.7–8)