Monge and Kantorovich: maps versus couplings

Let μ and ν be probability measures on source and target spaces, and let c(x, y) be a nonnegative measurable cost. A measurable map T is feasible when its pushforward T#μ equals ν: the target mass of every measurable set is the source mass of its preimage. The Monge objective integrates c(x, T(x)) against μ. A source point has one image, so an atomic source cannot divide its mass among several destinations.

The map constraint is nonlinear in the unknown map and may admit no candidate. For example a single source atom always pushes forward to a single target atom, regardless of how its location is chosen. It cannot produce a target containing two atoms with positive masses. This is a structural obstruction, not an optimizer’s failure to search hard enough. If the two distributions have unequal total mass, even the balanced coupling problem below is infeasible; unbalanced transport requires a different formulation.

A coupling π is a probability measure on the product space whose first marginal is μ and whose second marginal is ν. It records how much source mass is paired with each target region. The independent product μ ⊗ ν is always a coupling, so feasibility is automatic for two probability measures. A transport map induces the special coupling (id, T)#μ, supported on its graph; general couplings need not have this graph form.

In finite spaces, couplings are nonnegative matrices with prescribed row and column sums. The row sums supply source masses and the column sums supply target demands. The objective is linear in the matrix entries. Keeping the marginals fixed is essential: without those constraints, minimizing a nonnegative transport cost would permit sending no mass at all. A coupling’s randomness describes allocation conditional on the origin, not random movement added after solving an unrelated optimization.

Kantorovich transport minimizes over a convex set: averaging two couplings preserves their marginals. This convexity enables linear programming, dual certificates, and compactness arguments. It does not imply that every optimal coupling is deterministic. Conditions ensuring a map, such as Brenier’s theorem for quadratic cost with an absolutely continuous source, are additional results. An optimizer’s matrix should not be silently converted into a map by choosing the largest entry of each row, because that can destroy target masses.

The cost function supplies the geometry. Squared Euclidean distance discourages long moves more strongly than ordinary distance, and multiplying all costs by a positive constant changes the reported value without changing minimizers. Neither formulation by itself guarantees smooth paths between endpoints; it specifies only the origin–destination allocation. Later lessons will turn optimal couplings into interpolating distributions and distinguish their static cost from the kinetic action of a time-dependent motion.