subset_expected_transport_cost
The expected Wasserstein-1 distance g_k between the uniform distribution over a uniformly random k-element subset A ⊆ Fin n of servers s : Fin n → X in a pseudo metric space X and the uniform distribution on all n servers, for 1 ≤ k ≤ n, and 0 if k = 0 or n < k.
Statement
noncomputable def subset_expected_transport_cost {X : Type*} [PseudoMetricSpace X] (n : ℕ) (s : Fin n → X) (k : ℕ) : ℝ
- Defined in
- arXiv:2611.04275, Section 2.2, eq. (2.5)
- Verified
- 07 Nov 2026
- Axioms
- none listed
- Built on 1
- discrete_wasserstein_distThe discrete Wasserstein-1 distance between two probability distributions on a pseudo metric space X with finite index sets I and J,…
Read back from the Lean
Given a pseudometric space $X$, natural numbers $n, k \in \mathbb{N}$, and a map $s : \text{Fin } n \to X$, subset_expected_transport_cost n s k is defined as:
- $0$, if $k = 0$ or $n < k$;
- Otherwise, the average over all subsets $A \subseteq \text{Fin } n$ of cardinality $k$ (i.e., multiplied by $\binom{n}{k}^{-1}$) of the discrete Wasserstein distance between the uniform probability distribution on $s$ restricted to $A$ (with mass $1/k$ on each element of $A$) and the uniform probability distribution on the whole sequence $s$ (with mass $1/n$ on each element of $\text{Fin } n$).
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
/-- Expected Wasserstein-1 distance g_k between the uniform distribution on a random k-subset of servers and the full server distribution. -/ noncomputable def subset_expected_transport_cost {X : Type*} [PseudoMetricSpace X] (n : ℕ) (s : Fin n → X) (k : ℕ) : ℝ := if k = 0 ∨ n < k then 0 else ((Nat.choose n k : ℝ))⁻¹ * ∑ A ∈ Finset.powersetCard k (Finset.univ : Finset (Fin n)), discrete_wasserstein_dist (fun _ : A => 1 / (k : ℝ)) (fun (i : A) => s i.1) (fun _ : Fin n => 1 / (n : ℝ)) s