Operational ReciprocalTest conditional oracle, fair-bit, and uniform probabilities
ProvedCountingLLL.ReciprocalTest.operational_phase_probabilitiesalgorithmsprobability
Under the original entropy law with , at any exact operational state: an oracle query returns zero with probability ; a Coin fair-bit query returns one with probability ; and a finite-uniform check selects its distinguished zero value with probability . Each probability is stated as a joint state-and-outcome factorization, so no positive-probability conditioning assumption is needed.
Preamble
import Definitions.Def_CountingLLL_ReciprocalEncodedLaw open MeasureTheory ProbabilityTheory CountingLLL.ReciprocalTest open scoped ENNReal
Formal statement
theorem CountingLLL.ReciprocalTest.operational_phase_probabilities (B : ℝ≥0∞) (hB : B ≤ 1) (n : ℕ) :
(∀ (s : State) (k : Context), s.phase = .coinOracle k →
entropyLaw B {ω | run ω n = s ∧ ω.1 s.oracleUsed = false} =
entropyLaw B {ω | run ω n = s} * B) ∧
(∀ (s : State) (k : Context), s.phase = .coinFair k →
entropyLaw B {ω | run ω n = s ∧ ω.2.1 s.fairUsed = true} =
entropyLaw B {ω | run ω n = s} * (1/2)) ∧
(∀ (s : State), s.phase = .uniformCheck →
entropyLaw B {ω | run ω n = s ∧ (ω.2.2 (s.j-1,s.uniformUsed)).val = 0} =
entropyLaw B {ω | run ω n = s} * (1/(((s.j-1)+1 : ℕ) : ℝ≥0∞))) := by sorrySource
Liu, Wang, Yin, Zhang and Zhou, A Counting and Sampling Lovász Local Lemma, STOC #442, Algorithm 6, pp. 27–28, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/442.pdf