Sample complexity and transport statistics

Let X₁, X₂, and so on be independent identically distributed samples from μ on real d-space, and let μₙ put equal mass on the first n observations. If μ has finite p-th absolute moment for p ≥ 1, empirical weak convergence and the strong law applied to |X|ᵖ combine with the Wasserstein convergence criterion to give Wₚ(μₙ, μ) tending to zero almost surely. The p-th moment is not optional in this statement.

Almost-sure convergence is asymptotic and does not give a universal finite-sample confidence radius. Quantitative results depend on dimension and on stronger moment or tail assumptions. A light-tailed law on a line and a high-dimensional heavy-tailed law need not share a rate. Even for compactly supported distributions, geometric approximation costs can dominate simple scalar averaging rates, especially when the dimension is large.

Suppose μ has success mass q on location one and mass 1 − q on zero. If K successes appear in n draws, the empirical success mass is K/n. Exactly the mass mismatch must move distance one, giving Wₚ to the power p equal to |K/n − q| for every p ≥ 1. The empirical mean is a root-n statistic, but taking the p-th root turns it into a different transport scaling.

Cauchy–Schwarz bounds the expected absolute mismatch by the square root of q(1 − q)/n. Concavity of the square root then bounds expected W₂ by the fourth root of q(1 − q)/n. These are expectation bounds, not deterministic limits on an observed error. A particular sample can exceed them without contradiction. Nor is this two-point calculation a universal rate theorem for arbitrary continuous distributions.

Let μ be uniform on the unit cube in dimension d and let ν have at most N support points, with any weights. A union of N Euclidean balls of radius r has volume at most Nκ_d rᵈ, where κ_d is the volume of the unit ball. Choose that expression equal to one-half. At least half the cube’s volume then lies at distance at least r from every support point. Every coupling must move that mass by at least r, giving W₁ at least r/2.

This is a deterministic lower bound for every N-point approximation, not an upper bound for empirical sampling, and it needs no randomness or restriction on the atom weights. It shows an N to the minus one-over-d obstruction as dimension grows. In statistical use, two independent empirical clouds from the same population can still have positive transport distance. Distinguish that sampling variation from support discretization, entropic regularization bias, and incomplete numerical solution before attributing an observed distance to a population change.