Memoryless product integral of the capped seed rank charges
ProvedRGMISFast.conditional_rank_charge_laplaceprobabilityrandomized-greedy-mis
Let be the explicit exponential conditional rank law at time , let with , and let be any finite set. For every real , with ,
This isolates the memorylessness and independence calculation in the proof of Equation (29). If a vertex in is already revealed, its rank is below , so both sides vanish. Otherwise, conditional on , the coordinates in are independent variables. Factor the exponential of the rank sum and integrate the finite product to obtain . The empty-set case is included. This auxiliary statement generalizes the paper's choice and ; it has no graph or activity assumptions because it is purely a product-measure identity.
Preamble
import Mathlib import Definitions.Def_RGMISFast_Gamma import Definitions.Def_RGMISFast_gammaA import Definitions.Def_RGMISFast_condLaw set_option autoImplicit false open MeasureTheory ProbabilityTheory open scoped ENNReal open RGMISFast
Formal statement
theorem RGMISFast.conditional_rank_charge_laplace {V : Type*} [Fintype V] [LinearOrder V]
(r₀ : V → ℝ) (θ a L : ℝ) (ha : 0 < a) (hθa : θ < a) (A : Finset V) :
(∫⁻ r in {r | ∀ v ∈ A, a ≤ r v},
ENNReal.ofReal (Real.exp (-(2 * S r A a + L))) ∂(condLaw r₀ θ ∅ (fun _ => 0))) =
condLaw r₀ θ ∅ (fun _ => 0) {r | ∀ v ∈ A, a ≤ r v} *
ENNReal.ofReal (Real.exp (-L) * gammaA a ^ A.card) := by sorrySource
Dalirrooyfard, Makarychev, Mitrović, Ramachandran, Randomized Greedy MIS Is Fast at Every Node, §6.2, proof of Lemma 3.1, paragraph preceding Equation (29), printed p.25 (PDF p.27), manuscript sha256 e93cdfecc03618969d5f2ecf8171c6f84c528edcc473b2f864299e555f823664.