AFTD Auto-Formalizing Theoretical Domains

discrete_wasserstein_dist

def

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)}
See it in the graphDiscuss this resultChallenge it