Expected weighted upward changes factor by the upward probability
ProvedCountingLLL.ContractedWalk.weighted_increases_eqalgorithmsprobability
In the abstract contracted walk with upward probability , the expected sum of reciprocal-counter weights over upward changes is times the expected sum over all active changes. In particular, when the initial level is three and the initial counter is two, the latter is the source quantity .
Preamble
import Definitions.Def_CountingLLL_ContractedCost open MeasureTheory ProbabilityTheory CountingLLL.ContractedWalk open scoped ENNReal
Formal statement
theorem CountingLLL.ContractedWalk.weighted_increases_eq (p : ℝ≥0∞) (hp : p ≤ 1) (i j : ℕ) :
expectedWeightedIncreases p i j = expectedWeightedChanges p i j * p := by sorrySource
Liu, Wang, Yin, Zhang and Zhou, A Counting and Sampling Lovász Local Lemma, STOC #442, proof of Lemma 6.5, calls to O, p. 28, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/442.pdf