Lemma 2 — the probability that some item is still waiting
ProvedCorrelatedRounding.lemma_2correlated-roundinge-commerce-fulfillmentp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
For a draw of Algorithm 1 and every ,
The event says that some item has not yet seen any FC open at time . The integral of this bound against gives the constant of Theorem 1.
Differences from the source:
- encoding: the event min_k (y_k/u_ki) E_k ≥ t → t lies below every EReal clock of item i; reason: same event, written without a minimum of extended reals
- generalization: "Assume without loss that y_k > 0 for all k" (p.9) → an FC with y_k = 0 is allowed, and its entry of the draw is unconstrained; reason: such an FC has clock ∞ at every item; the page's instances, all y_k > 0, are a special case
- encoding: items i = 1,…,q and FCs k = 1,…,K → Fin q and Fin K, both 0-based; reason: Lean convention; same instances
Preamble
import Mathlib import Definitions.Def_CorrelatedRounding_IsInstance import Definitions.Def_CorrelatedRounding_y import Definitions.Def_CorrelatedRounding_clock import Definitions.Def_CorrelatedRounding_IsAlg1Output import Definitions.Def_CorrelatedRounding_IsAlg1Draw open MeasureTheory ProbabilityTheory
Formal statement
namespace CorrelatedRounding
/-- **Lemma 2.** W. Ma, *Order-optimal Correlated Rounding for Fulfilling Multi-item E-commerce Orders*, arXiv:2207.04774v4, p.10:
"Under Algorithm 1, Pr[⋃_{i=1}^q (min_k (y_k/u_ki) E_k ≥ t)] ≤ q e^{−t} for all t ≥ 0."
**Formalization Note.** The event `min_k (y_k/u_ki) E_k ≥ t` is written as `t` lying below every `EReal` clock
of item `i`. Items are `Fin q`. -/
theorem lemma_2 {q K : ℕ} {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω}
[IsProbabilityMeasure μ] {u : Fin K → Fin q → ℝ} (hu : IsInstance u) {E : Fin K → Ω → ℝ}
(hE : IsAlg1Draw u μ E) (t : ℝ) (ht : 0 ≤ t) :
μ (⋃ i, {ω | ∀ k, (t : EReal) ≤ clock u (fun k' => E k' ω) k i}) ≤
ENNReal.ofReal (q * Real.exp (-t)) := by sorry
end CorrelatedRounding
Source
Ma, Order-optimal Correlated Rounding for Fulfilling Multi-item E-commerce Orders, arXiv:2207.04774v4, Lemma 2, p.10
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.