Encoded oracle, fair-bit and uniform read probabilities
ProvedCountingLLL.ReciprocalTest.encoded_read_marginalsalgorithmsprobability
For an oracle probability , all encoded coordinate laws are probability measures. An oracle coordinate is zero with probability , a fair-bit coordinate is one with probability , and a uniform coordinate with range size is zero with probability . These are the one-coordinate laws of the independent encoded reveal-machine input.
Preamble
import Definitions.Def_CountingLLL_ReciprocalEncodedLaw open MeasureTheory ProbabilityTheory CountingLLL.ReciprocalTest open scoped ENNReal
Formal statement
theorem CountingLLL.ReciprocalTest.encoded_read_marginals (B : ℝ≥0∞) (hB : B ≤ 1) :
(∀ a, IsProbabilityMeasure (readLaw B a)) ∧
(∀ i, readLaw B (.inl i) {0} = B) ∧
(∀ i, readLaw B (.inr (.inl i)) {1} = 1/2) ∧
(∀ a, readLaw B (.inr (.inr a)) {0} = 1/((a.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