The cheapest way to move one pile of probability onto another. Between two discrete distributions the cost is the minimum over coupling plans whose rows sum to the source and columns to the target of ∑ plan × distance. On the line this collapses to a closed form: the sorted matching, the area between the inverse CDFs. Rendered, not quoted — the plan, its cost, and the 1‑D formula are computed live.
source Monge, Mémoire sur la théorie des déblais et des remblais (1781) · Kantorovich, On the translocation of masses (1942) · Villani, Optimal Transport: Old and New (Springer, 2009). amber no stable arXiv id — cited by author / title / year.
Two probability piles on the line. Source p = mass at positions with weights; target q likewise. A transport plan π is a nonnegative matrix: entry πij is mass shipped from p‑atom i to q‑atom j.
Feasible means row sums = p and column sums = q — you neither create nor destroy mass. The cost of π is ∑ij πij·|xi−yj|. The OT distance W1 is the minimum over all feasible π.
On the line, Monge's original guess is right: the optimum is the monotone coupling — ship in sorted order, low‑to‑low.
W1 is distance between distributions as physical mass movement — the earth‑mover's distance. It is the metric a WGAN descends and the geometry the‑diffusion‑model flows along when it carries noise onto data.
Neighbour sphere: the‑diffusion‑model — a diffusion is a transport map built one small optimal step at a time; here we hold still and measure the single cheapest jump.
Live re‑check of the reported plan: are its column sums actually the target marginal? A number alone cannot tell you — the witness re‑runs feasibility every time.
Press tamper (window 6) and watch this flip red: the reported cost is unchanged, but it is no longer the cost of a transport.
Two constructed distributions with known atoms — every quantity below is closed‑form.
Three independent computations of the same number: the primal monotone coupling, the closed form ∫|Fp−Fq| dx, and the Kantorovich dual over 1‑Lipschitz potentials.
Proven result: the OT distance W1(p,q) equals the sorted‑matching area, and primal = closed‑form = dual to machine precision.
The line is a mercy. The sorted‑matching closed form is only 1‑D. In d ≥ 2 there is no sorting; the plan is a genuine linear program and the map (Brenier) is the gradient of a convex potential you must actually solve for.
Cost matters. W1 uses |x−y|. Squared cost gives W2, a different geometry; the monotone map is optimal for any convex ground cost on the line, but not for non‑convex costs.
Curse of dimension. Empirical W1 from n samples converges like n−1/d — useless estimates in high d without entropic regularization or slicing.
"W1 = ∑|pi−qi| — just compare the weights."
→ No. That is total‑variation / L1 on weights and ignores geometry. OT charges for distance moved; TV charges 1 for any move. They disagree the moment atoms sit at different places.
"Any plan with the right cost is a transport."
→ No — see window 6. A plan is a transport only if both marginals match. A cheap infeasible matrix is a fraud, not a coupling.
"The Monge map always exists."
→ amber Monge's formulation can be infeasible (splitting an atom). Kantorovich's relaxation to plans always has a minimiser; that is why the LP form is the honest one.
The disclosed planted void: report a plan whose column sums do not match the target, yet quote its cost as the OT distance. The reported number looks fine; the plan is not a transport at all.
The witness (window 7) re‑runs marginal feasibility and catches it live. selfcheck() plants and clears this same void at boot.