Integral of a probability generating function equals a reciprocal expectation
ProvedCountingLLL.ContractedWalk.pgf_reciprocal_expectationanalysisprobability
If is a measurable nonnegative integer-valued random variable on a probability space, then . The bounded-integrand interchange rigorously connects the paper’s counter generating function to its reciprocal return probability.
Preamble
import Mathlib open MeasureTheory open scoped ENNReal Interval
Formal statement
theorem CountingLLL.ContractedWalk.pgf_reciprocal_expectation {β : Type} [MeasurableSpace β] (ν : Measure β) [IsProbabilityMeasure ν]
(K : β → ℕ) (hK : Measurable K) :
(∫ x, (1:ℝ)/((K x : ℝ)+1) ∂ν) = ∫ z in (0:ℝ)..1, ∫ x, z ^ K x ∂ν := by sorrySource
Liu, Wang, Yin, Zhang and Zhou, A Counting and Sampling Lovász Local Lemma, STOC 2027 #442, proof of Lemma 6.5, PDF p. 27, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/442.pdf