ReciprocalTest satisfies the Markov transition law given its entire history
ProvedCountingLLL.ReciprocalTest.operational_history_transitionformalizationprobability
For any event determined by the complete finite state history of ReciprocalTest, the joint probability of that event, the current state, and a specified next state factors into the probability of the event and current state times the published operational transition mass. This is the full finite-history Markov property of the algorithm, stated without dividing by conditioning probabilities.
Preamble
import Definitions.Def_CountingLLL_ReciprocalTransition open MeasureTheory ProbabilityTheory CountingLLL.ReciprocalTest open scoped ENNReal
Formal statement
theorem CountingLLL.ReciprocalTest.operational_history_transition (B : ℝ≥0∞) (hB : B ≤ 1) (n : ℕ)
(H : (Fin (n+1) → State) → Prop) (s s' : State) :
entropyLaw B {ω | H (fun j => CountingLLL.ReciprocalTest.run ω j.val) ∧
CountingLLL.ReciprocalTest.run ω n = s ∧ CountingLLL.ReciprocalTest.run ω (n+1) = s'} =
entropyLaw B {ω | H (fun j => CountingLLL.ReciprocalTest.run ω j.val) ∧
CountingLLL.ReciprocalTest.run ω n = s} * transitionMass B s s' := 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 operational Markov property supporting, but not itself proving, the paper’s coupling and cost analysis.