Exact finite path probabilities of ReciprocalTest
ProvedCountingLLL.ReciprocalTest.operational_path_probabilityformalizationprobability
For every finite prescribed sequence of states, the probability that the operational ReciprocalTest execution follows that sequence equals the indicator that the first prescribed state is the initial state, multiplied by the transition masses of all successive pairs. This is a complete finite-dimensional path law and is a tool for coupling the algorithm to the contracted walk.
Preamble
import Definitions.Def_CountingLLL_ReciprocalTransition open MeasureTheory ProbabilityTheory CountingLLL.ReciprocalTest open scoped ENNReal BigOperators open Classical
Formal statement
theorem CountingLLL.ReciprocalTest.operational_path_probability (B : ℝ≥0∞) (hB : B ≤ 1) (x : ℕ → State) (n : ℕ) :
entropyLaw B {ω | ∀ j ≤ n, run ω j = x j} =
(if x 0 = initial then 1 else 0) * ∏ j ∈ Finset.range n, transitionMass B (x j) (x (j+1)) := by sorrySource
Liu, Wang, Yin, Zhang, Zhou, A Counting and Sampling Lovász Local Lemma, STOC submission #442, §6.2, Lemma 6.5. This is an exact operational path-law ingredient for the source’s random-walk coupling.