Proof of Theorem 5, p. ec5 — T = Σ_i P(x ∈ R_i)T_i, so T/T(π*) → 1 whenever every T_i/T(π*) → 1
ProvedCarlssonPartition.Equitable.total_expectationheavy-trafficlaw-of-total-expectationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1region-partitioning
Let the instance satisfy the standing assumptions and let be a partition of . Let and be real functions of the arrival rate such that, for every ,
Then the overall expected delivery time given by the law of total expectation, with , satisfies
along the same heavy-traffic limit.
This is the final step of the proofs of Theorems 5 and 6: once each district is asymptotically as fast as , so is the region partitioning policy as a whole.
Formalization Note. The content is that the district probabilities sum to for a partition up to null sets, together with averaging of ratios under a probability vector.
Preamble
import Mathlib import Definitions.Def_CarlssonPartition_Equitable_Setting open Filter Topology MeasureTheory
Formal statement
namespace CarlssonPartition.Equitable
theorem total_expectation (I : Instance) (hI : I.Standing)
(Rs : Fin I.m → Set Plane) (hP : I.IsPartition Rs)
(Tstar : ℝ → ℝ) (T : Fin I.m → ℝ → ℝ)
(hT : ∀ i, Tendsto (fun lam => T i lam / Tstar lam) (I.heavy I.m I.R I.f) (𝓝 1)) :
Tendsto (fun lam => (∑ i, I.pr (Rs i) * T i lam) / Tstar lam) (I.heavy I.m I.R I.f) (𝓝 1) := by sorry
end CarlssonPartition.Equitable
Source
Carlsson, Liu, Salari and Yu, Provably Good Region Partitioning for On-Time Last-Mile Delivery, accepted manuscript (SSRN 3915544; published in Operations Research 72(1):91–109, 2024, doi:10.1287/opre.2021.0588), p. ec5, proof of Theorem 5, display after 'Therefore, the expected delivery time to the whole service region is'
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.