Pairing independent product streams
ProvedCountingLLL.ReciprocalTest.paired_streamsprobability
Let and be independent sequences of independent identically distributed Boolean variables, with respective laws and . Then the paired sequence is an independent identically distributed sequence with common law . This reindexes the oracle and fair-bit entropy of Algorithm 6 into the trial-pair model of Coin.
Preamble
import Mathlib open MeasureTheory ProbabilityTheory open scoped ENNReal
Formal statement
theorem CountingLLL.ReciprocalTest.paired_streams (μ ν : Measure Bool) [IsProbabilityMeasure μ] [IsProbabilityMeasure ν] :
let μs := Measure.infinitePi fun _ : ℕ => μ
let νs := Measure.infinitePi fun _ : ℕ => ν
(μs.prod νs).map (fun p n => (p.1 n, p.2 n)) =
Measure.infinitePi (fun _ : ℕ => μ.prod ν) := by sorrySource
Liu, Wang, Yin, Zhang and Zhou, A Counting and Sampling Lovász Local Lemma, STOC 2027 #442, Algorithm 6, PDF p. 27, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/442.pdf