A probability distribution can be represented by a finite cloud of particles. The most familiar construction is to draw independent samples. But if the distribution is known and the particles can be placed deliberately, randomness is an unnecessary source of error.
For a smooth, positive density on a bounded interval, the contrast is sharp. With \(n\) equally weighted particles, the smallest squared \(W_2\) error is of order \(n^{-2}\). Independent sampling gives expected squared error of order \(n^{-1}\). We can identify the optimal positions, compute the constants, and understand the difference using a single picture: approximate the quantile function by a staircase.
This is equal-weight quantization. General quantization allows the weights to vary too; its theory is developed by Graf and Luschgy [1]. The prescribed-weight problem on the line is studied systematically by Xu and Berger [2].
Transport on the line is an approximation problem
Let \(\mu\) be a probability measure on \(\mathbb R\) with finite second moment. Its cumulative distribution function and quantile are
\[ F_\mu(x)=\mu((-\infty,x]), \qquad Q(r)=\inf\{x:F_\mu(x)\ge r\},\quad 0<r<1. \]The one-dimensional transport formula says
\[ W_2(\mu,\nu)^2=\int_0^1|Q_\mu(r)-Q_\nu(r)|^2\,dr. \]It follows from monotone matching: crossing two ordered assignments increases their quadratic cost. Equivalently, using the same uniform random variable \(U\) to generate \(Q_\mu(U)\) and \(Q_\nu(U)\) gives an optimal coupling [4].
For ordered particle positions \(z_1\le\cdots\le z_n\), the quantile of \(\nu_z=n^{-1}\sum_i\delta_{z_i}\) is the constant \(z_i\) on the interval \(I_i=((i-1)/n,i/n)\). Consequently,
\[ W_2(\mu,\nu_z)^2 =\sum_{i=1}^n\int_{I_i}|Q(r)-z_i|^2\,dr. \]Choosing the best particles is exactly choosing the best constant on each fixed quantile bin.
Theorem 1 (the optimal particles are bin averages). For every \(\mu\in\mathcal P_2(\mathbb R)\), an optimal equal-weight \(n\)-particle approximation is
\[ \mu_n^*=\frac1n\sum_{i=1}^n\delta_{z_i^*}, \qquad z_i^*=n\int_{I_i}Q(r)\,dr. \]The ordered vector \(z^*\) is unique. Its entries may coincide if the original measure has atoms. More precisely, every ordered vector \(z\) satisfies the exact identity
\[ W_2(\mu,\nu_z)^2 =W_2(\mu,\mu_n^*)^2 +\frac1n\sum_{i=1}^n|z_i-z_i^*|^2. \]Proof: orthogonal projection onto a staircase
On \(I_i\), expand \(Q-z_i=(Q-z_i^*)+(z_i^*-z_i)\). The cross term vanishes because \(\int_{I_i}(Q-z_i^*)=0\). Integration gives
\[ \int_{I_i}|Q-z_i|^2 =\int_{I_i}|Q-z_i^*|^2+\frac1n|z_i-z_i^*|^2. \]Since \(Q\) is nondecreasing, its averages over consecutive bins are nondecreasing too. Thus the unconstrained binwise optimum already satisfies the ordering constraint. Summing proves both optimality and uniqueness of the ordered vector. \(\square\)
The familiar midpoint quantile \(Q((i-\tfrac12)/n)\) is generally only an approximation to the bin average. The exact optimizer uses an average in quantile space, or equivalently the mean of each equal-mass slice of the distribution. This is also a conditional expectation: replace \(Q(U)\) by its conditional mean given the bin containing \(U\).
The exact benchmark: a uniform distribution
For \(\mu=\operatorname{Unif}[0,1]\), \(Q(r)=r\). The optimal particles are the midpoints \(z_i^*=(i-\tfrac12)/n\), and
\[ W_2(\mu,\mu_n^*)^2 =n\int_{-1/(2n)}^{1/(2n)}s^2\,ds =\frac1{12n^2}. \]Now draw \(n\) independent uniform particles and sort them as \(U_{(1)}\le\cdots\le U_{(n)}\). For their empirical law \(\widehat\mu_n\), Theorem 1 gives an exact formula for each realization:
\[ W_2(\mu,\widehat\mu_n)^2 =\frac1{12n^2} +\frac1n\sum_{i=1}^n \left|U_{(i)}-\frac{i-\frac12}{n}\right|^2. \]The second term is the cost of the random deviations from the optimal staircase. Averaging it gives the following particularly clean identity.
Proposition 1 (uniform sampling error). For every integer \(n\ge1\),
\[ \mathbb E W_2(\operatorname{Unif}[0,1],\widehat\mu_n)^2 =\frac1{6n}. \]Proof: the first two moments of an order statistic
The density of \(U_{(i)}\) is the beta density with parameters \(i,n+1-i\). Its moments are
\[ \mathbb E U_{(i)}=\frac{i}{n+1}, \qquad \mathbb E U_{(i)}^2=\frac{i(i+1)}{(n+1)(n+2)}. \]Substitute into \(\sum_i\int_{I_i}\mathbb E(U_{(i)}-r)^2\,dr\). The sum of the second-moment terms is \(1/3\), the sum of \(\int_{I_i}r^2\,dr\) is \(1/3\), and the sum of the cross terms is \((4n-1)/(6n)\). Their difference is \(1/(6n)\). \(\square\)
On \([a,b]\), multiply both errors by \((b-a)^2\). The ratio of random expected squared error to deterministic optimal squared error is exactly \(2n\). For the distance itself, the deterministic error is of order \(n^{-1}\), whereas the root-mean-square random distance is of order \(n^{-1/2}\). The distinction between a squared error and its square root matters.
Numerical experimentation
The same powers for a smooth positive density
Uniformity is not the reason for the two different powers. What matters is regularity of the quantile. Assume \(\mu\) is supported on \([a,b]\), with a density \(\rho\in C^1([a,b])\) satisfying \(0<c\le\rho(x)\le C\). Then \(Q\in C^2([0,1])\), with
\[ Q'(r)=\frac1{\rho(Q(r))}. \]A small density stretches quantile space: a given mass interval occupies more physical space, making it harder to replace by one point.
Theorem 2 (the leading constants). Under these assumptions,
\[ \begin{aligned} n^2 W_2(\mu,\mu_n^*)^2 &\longrightarrow \frac1{12}\int_0^1 Q'(r)^2\,dr =\frac1{12}\int_a^b\frac{dx}{\rho(x)},\\ n\,\mathbb E W_2(\mu,\widehat\mu_n)^2 &\longrightarrow \int_0^1 r(1-r)Q'(r)^2\,dr. \end{aligned} \]The first constant measures local approximation error. The second contains the additional factor \(r(1-r)\), the variance profile of empirical mass fluctuations: these are strongest near the middle of the distribution. The full theory of random quantile errors is developed in [4] and [5]. In this regular setting, both limits have elementary proofs.
Proof: local slopes, then the fluctuations of order statistics
Deterministic placement. Set \(h=1/n\) and let \(c_i\) be the midpoint of \(I_i\). Taylor’s formula, uniformly on every bin, gives
\[ Q(r)=Q(c_i)+Q'(c_i)(r-c_i)+O(h^2). \]The bin average is \(Q(c_i)+O(h^2)\). After subtracting it, squaring and integrating,
\[ \int_{I_i}|Q(r)-z_i^*|^2\,dr =\frac{h^3}{12}Q'(c_i)^2+O(h^4). \]Sum the \(n\) bins and multiply by \(n^2\). The leading term is a Riemann sum; the remainder tends to zero. The substitution \(r=F_\mu(x)\), \(dr=\rho(x)\,dx\), gives the density expression.
Random placement. Write the sorted observations as \(Q(U_{(i)})\). For \(r\in I_i\), put \(\Delta=U_{(i)}-r\). Boundedness of \(Q'\) and \(Q''\) gives
\[ \mathbb E|Q(U_{(i)})-Q(r)|^2 =Q'(r)^2\,\mathbb E\Delta^2+O(\mathbb E|\Delta|^3), \]uniformly in \(i,r\). The elementary order-statistic estimates are
\[ \mathbb E\Delta^2=\frac{r(1-r)}n+O(n^{-2}), \qquad \mathbb E|\Delta|^3=O(n^{-3/2}). \]Why these moment estimates are uniform, including near the endpoints
Set \(s_i=i/(n+1)\). Since \(|s_i-r|\le1/n\), the beta mean and variance
\[ \mathbb E U_{(i)}=s_i,\qquad \operatorname{Var}(U_{(i)}) =\frac{s_i(1-s_i)}{n+2} \]give the first estimate. To bound the third absolute moment, use the fourth moment and Cauchy–Schwarz. For beta parameters \(A=i\), \(B=n+1-i\), \(N=A+B=n+1\), the fourth central moment is
\[ \mathbb E(U_{(i)}-s_i)^4 =\frac{3AB\{AB(N+2)+2(A-B)^2\}} {N^4(N+1)(N+2)(N+3)} \le\frac{C_0}{n^2}. \]This formula follows by expanding the centered fourth power and using \(\mathbb E U_{(i)}^k=\prod_{\ell=0}^{k-1}(i+\ell)/(n+1+\ell)\), for \(k\le4\). Adding the shift \(s_i-r\) gives \(\mathbb E\Delta^4=O(n^{-2})\). Therefore \(\mathbb E|\Delta|^3\le(\mathbb E\Delta^2\,\mathbb E\Delta^4)^{1/2}=O(n^{-3/2})\), with constants independent of the bin.
Integrating over all bins now yields
\[ \mathbb E W_2(\mu,\widehat\mu_n)^2 =\frac1n\int_0^1 r(1-r)Q'(r)^2\,dr+O(n^{-3/2}). \]Multiply by \(n\). This proves convergence of expectations directly, without needing to exchange a distributional limit and an expectation. \(\square\)
A small nonlinear example
Let the distribution be generated by the quantile \(Q(r)=r+\theta r^2\), with \(\theta>0\). Its density is smooth and bounded above and below on \([0,1+\theta]\). On a bin with midpoint \(c_i\),
\[ z_i^*=c_i+\theta c_i^2+\frac{\theta}{12n^2}, \qquad Q(c_i)=c_i+\theta c_i^2. \]The exact particles lie slightly to the right of the midpoint quantiles. Theorem 1 quantifies the price of using the latter: their squared error exceeds the optimum by exactly \(\theta^2/(144n^4)\). This is lower order than the \(n^{-2}\) leading term, explaining why midpoint quantiles are asymptotically correct although not exactly optimal.
The two leading constants can also be integrated explicitly:
\[ \begin{aligned} \frac1{12}\int_0^1Q'(r)^2\,dr &=\frac1{12}\left(1+2\theta+\frac43\theta^2\right),\\ \int_0^1r(1-r)Q'(r)^2\,dr &=\frac16+\frac{\theta}3+\frac{\theta^2}5. \end{aligned} \]What this comparison does and does not promise
The weights are fixed at \(1/n\). Allowing nonuniform weights changes the optimization problem: equal-length or nearest-neighbor cells need not carry equal mass. In higher dimensions there is no global ordering, so quantile bins no longer solve the problem; equal-weight constructions require different geometry [6].
The density assumptions also matter. If the density vanishes, or the support is unbounded, the integrals in Theorem 2 may diverge. In particular, one must not apply these finite constants unchanged to an untruncated Gaussian. The general empirical bounds in [7] and the one-dimensional analysis in [4] describe how tails and regularity affect sampling rates.
Atoms can change the sampling rate too. For \(\mu=(\delta_0+\delta_1)/2\), write \(K_n\) for the number of sampled ones. Only the excess mass at one endpoint must cross the unit interval, so
\[ W_2(\mu,\widehat\mu_n)^2 =\left|\frac{K_n}{n}-\frac12\right|, \qquad \mathbb E W_2(\mu,\widehat\mu_n)^2 \sim\frac1{\sqrt{2\pi n}}. \]The last equivalent follows from the binomial CLT and uniform integrability of the standardized absolute fluctuations. In contrast, for every even \(n\), deliberate equal-weight placement represents this law exactly by repeating each endpoint \(n/2\) times. The \(n^{-2}\) versus \(n^{-1}\) comparison is a theorem for the stated positive-density class, not a universal pair of rates for all measures. The same two-point fluctuation explains the general sampling bound in the post on Bernstein polynomials of measures.
Finally, optimal placement assumes access to the target quantile, or to a sufficiently accurate approximation of it. If the distribution itself must be learned from data, quantization does not erase that statistical uncertainty. It separates two questions: how well do we know the distribution, and how efficiently can we represent the distribution we know?
References
- Siegfried Graf and Harald Luschgy. Foundations of Quantization for Probability Distributions. Lecture Notes in Mathematics 1730, Springer, 2000.
- Chuang Xu and Arno Berger. Best finite constrained approximations of one-dimensional probabilities. Journal of Approximation Theory 244, 1–36, 2019.
- Gabriel Peyré. Optimal Transport for Machine Learners, 2025–2026. §6.4, Propositions 6.14–6.15.
- Sergey Bobkov and Michel Ledoux. One-Dimensional Empirical Measures, Order Statistics, and Kantorovich Transport Distances. Memoirs of the American Mathematical Society 261(1259), 2019. Author’s copy.
- Eustasio del Barrio, Evarist Giné, and Frederic Utzet. Asymptotics for L² functionals of the empirical quantile process, with applications to tests of fit based on weighted Wasserstein distances. Bernoulli 11(1), 131–189, 2005.
- Julien Chevallier. Uniform decomposition of probability measures: quantization, classification, rate of convergence. arXiv:1801.02871, 2018.
- Nicolas Fournier and Arnaud Guillin. On the rate of convergence in Wasserstein distance of the empirical measure. Probability Theory and Related Fields 162, 707–738, 2015.