discrete_wasserstein_dist
The discrete Wasserstein-1 distance between two probability distributions on a pseudo metric space X with finite index sets I and J, probability weights p and q, and support points x : I → X and y : J → X, defined as the infimum of ∑_{i, j} γ(i, j) d(x_i, y_j) over all transport plans γ ≥ 0 with row sums p and column sums q.
Statement
noncomputable def discrete_wasserstein_dist {X : Type*} [PseudoMetricSpace X] {I J : Type*} [Fintype I] [Fintype J] (p : I → ℝ) (x : I → X) (q : J → ℝ) (y : J → X) : ℝ
- Defined in
- arXiv:2611.04275, Section 2.2, eq. (2.2)
- Verified
- 07 Nov 2026
- Axioms
- none listed
- Used by 2
- empirical_expected_transport_costThe expected Wasserstein-1 distance f_t between the empirical distribution of t independent uniform samples from a sequence of n servers s…
- subset_expected_transport_costThe expected Wasserstein-1 distance g_k between the uniform distribution over a uniformly random k-element subset A ⊆ Fin n of servers s :…
Read back from the Lean
Given a pseudometric space X, finite types I and J, weight vectors p : I → ℝ and q : J → ℝ, and point maps x : I → X and y : J → X, discrete_wasserstein_dist is defined as the real infimum (sInf) of the set of all c : ℝ for which there exists a transport plan γ : I → J → ℝ such that:
1. γ i j ≥ 0 for all i : I and j : J,
2. ∑ j, γ i j = p i for all i : I,
3. ∑ i, γ i j = q j for all j : J, and
4. c = ∑ i, ∑ j, γ i j * dist (x i) (y j).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- Wasserstein-1 distance between two finitely indexed discrete distributions on a pseudo metric space. -/ noncomputable def discrete_wasserstein_dist {X : Type*} [PseudoMetricSpace X] {I J : Type*} [Fintype I] [Fintype J] (p : I → ℝ) (x : I → X) (q : J → ℝ) (y : J → X) : ℝ := sInf {c : ℝ | ∃ γ : I → J → ℝ, (∀ i j, 0 ≤ γ i j) ∧ (∀ i, ∑ j, γ i j = p i) ∧ (∀ j, ∑ i, γ i j = q j) ∧ c = ∑ i, ∑ j, γ i j * dist (x i) (y j)}