Theorem 2.1 — exponential race:
ProvedKTaxi.Competitive.theorem_2_1exponential-distributionp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1probability
Let be independent real random variables on a probability space, with and . Then for every ,
Among independent exponential random variables, the probability that a given one is the smallest is proportional to its rate. It gives the selection probabilities of Algorithm 1.
Formalization Note The variables are measurable maps ζ : Fin m → Ω → ℝ with iIndepFun ζ P and P.map (ζ i) = expMeasure (rate i). The event is , and the probability is compared in ℝ≥0∞.
Differences from the source:
- encoding: ζ_i = min_j ζ_j → ζ_i ≤ ζ_j for every j; reason: the same event
- encoding: indices 1, …, m → Fin m (0-based); reason: Lean convention; same instances
Preamble
import Mathlib open MeasureTheory ProbabilityTheory
Formal statement
namespace KTaxi.Competitive
/-- **Theorem 2.1** (exponential race; Coester–Huang–Poon, STOC 2027 #96, PDF p. 4).
Let `ζ₁, …, ζ_m` be independent real random variables on a probability space with
`ζ_i ∼ Exp(λ_i)` and `λ_i > 0`. Then for every `i`,
`P(ζ_i = min_j ζ_j) = λ_i / ∑_j λ_j`. -/
theorem theorem_2_1 {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
{m : ℕ} (ζ : Fin m → Ω → ℝ) (rate : Fin m → ℝ) (hrate : ∀ i, 0 < rate i)
(hmeas : ∀ i, Measurable (ζ i)) (hind : iIndepFun ζ P)
(hlaw : ∀ i, P.map (ζ i) = expMeasure (rate i)) (i : Fin m) :
P {ω | ∀ j, ζ i ω ≤ ζ j ω} = ENNReal.ofReal (rate i / ∑ j, rate j) := by sorry
end KTaxi.Competitive
Source
Christian Coester, Yichen Huang, Tze-Yang Poon, The k-Taxi Problem Is Competitive on All Metrics, STOC 2027 submission #96 (October 2026; PDF SHA-256 09242267e431f586117500ee75c63e6f203519f497d01ee4d90d6989341648ed), https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/96.pdf, Theorem 2.1, PDF p. 4 (printed p. 3)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.