Prefix-weighted probability of a fresh upward step
ProvedCountingLLL.ContractedWalk.weighted_fresh_bitprobability
For an independent Bernoulli tape with success probability , let be any nonnegative weight determined by the first bits. Then
The result includes arbitrary nonnegative, possibly unbounded weights and is suited to the weighted upward-change count in the source cost analysis.
Preamble
import Definitions.Def_CountingLLL_ContractedWalk open MeasureTheory ProbabilityTheory CountingLLL.ContractedWalk open scoped ENNReal
Formal statement
theorem CountingLLL.ContractedWalk.weighted_fresh_bit (p : ℝ≥0∞) (hp : p ≤ 1) (t : ℕ)
(F : ((Finset.range t) → Bool) → ℝ≥0∞) :
(∫⁻ ω : Tape, F (fun j => ω j) * (if ω t then 1 else 0) ∂tapeLaw p) =
(∫⁻ ω : Tape, F (fun j => ω j) ∂tapeLaw p) * 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