# Uniqueness of the limit sequence of discrete probability measures

Let $$N_n$$ be a sequence of natural numbers increasing to infinity, and suppose we have a sequence of finite sets of distinct points $$X_n = \{x_1^{n},x_2^{n},\ldots,x^{n}_{N_n}\} \subset[0,1] \subset \mathbb{R}$$. Consider the discrete probability measure $$\rho_n = \frac{1}{N_n}\sum_{i=1}^{N_n}\delta_{x^{n}_i},$$ a normalized sum of delta functions centered at the points $$x^{n}_i$$. Being bounded as a linear operator on $$C([0,1])$$, there exists a vaguely convergent subsequence of the $$\rho_n$$ i.e. there exists a probability measure $$\rho$$ on [0,1] such that $$\int_0^1fd\rho_{n_k} \to_{k\to \infty} \int_0^1 fd\rho$$ for all $$f \in C([0,1])$$. Let me further impose a spacing condition that if $$r_n := \inf_{i\neq j} |x^n_i - x^n_j|$$ is the minimum distance between distinct pairs of the $$x^n_i$$, then $$\inf_n N_n r_n > 0.$$ (in particular, this implies $$x^n_i$$ are distinct). This loosely can be interpreted as enforcing that the $$X_n$$ not accumulate too much on 0-dimensional sets (or perhaps I should say on sets of Hausdorff/Minkowski dimension < 1? I'm not sure and would be interested in answers to this as well, though it's not my main question).

As a simple example, if $$X_n$$ is regularly spaced on $$[0,1]$$, then $$d\rho = dx =$$ Lebesgue measure.

My question is: What further conditions can be imposed on the sets $$X_n$$ to guarantee that the original sequence $$\rho_n$$ converges (as opposed to a subsequence)?

Note that this is a rewrite of an earlier question of mine (my first ever), since closed (Uniqueness of the limit of a sequence of (discrete) probability measures). I understand if it gets closed again, because it's pretty specific yet open-ended at the same time. I imagine any nontrivial answer would be kind of creative, perhaps involving a rule or algorithm for how the points in the $$X_n$$ are distributed, and/or involving some nestedness property. Nestedness alone (i.e. $$X_n \subset X_{n+1}$$) does not guarantee uniqueness of the limit, as I have constructed counterexamples to demonstrate.

• At some point, you'll need to rule out the situation where $X_{2n}$ consists of $n$ points uniformly distributed in $[0;1/2]$ and $X_{2n+1}$ consists of $n$ points in $[1/2;1]$. More generally, if two sequences converge to two different limits and satisfy your assumptions, a mixture as described above will have two limit points and still satisfy your criteria. – Pierre PC Apr 20 '19 at 6:15
• If the inf equals $c>0$, then your condition says that any limit point $\rho$ is ac with respect to Lebesgue measure with density $\le 1/c$. Conversely, all such prob measures are possible as limit points. I don't think there will be a useful criterion how to read off convergence from the points that is not near tautological. – Christian Remling Apr 20 '19 at 16:32
• If the measure $\rho$ is the arcsine measure, then such conditions can be formulated. Let $\hat I_n=\prod_{x,y \in X_n, x \ne y}{|x-y|}^{\frac{1}{N_n(N_n-1)}}$. If $\lim_{n \to \infty} \hat I_n = e^{-1/4}$, then $\rho_n \to \rho$ vaguely. This is because $\rho$ is the (unique) measure with minimal logarithmic energy on $[0,1]$ (viewed as a subset of the complex plane) and $1/4$ is the value of this minimal energy. The numbers $I_n$ can be thought of as discrete energies". – Margaret Friedland Apr 20 '19 at 21:21
• @MargaretFriedland: Except that this has unbounded density, so can't be the limit when the points $x_n$ satisfy the OP's assumptions. – Christian Remling Apr 21 '19 at 0:20
• @ChristianRemling Excellent point re absolute continuity with respect to Lebesgue measure. I was aware of this, but I'm impressed you figured it out as fast as you did. – Ben Ciotti Apr 23 '19 at 1:20

For this answer the assumption that the points $$x_i^n$$ are distinct is not necessary. The restriction to $$[0,1]$$ is also not necessary. The answer applies to probability measures with finite support on any complete metric space.

On the set of Borel probability measures on $$[0,1]$$, the topology in question is given by the Kantorovich-Rubinshtein metric $$d_0$$. See V.I. Bogachev, "Measure theory", Chapter 8, or the Wikipedia article "Wasserstein metric". In this metric the set of probability measures is complete. So a sequence converges if and only if it is Cauchy.

The Kantorovich-Rubinshtein metric is the optimal transport metric. The distance $$d_0(\rho,\sigma)$$ is the least cost of moving some divisible matter from a state distributed according to $$\rho$$ to one distributed according to $$\sigma$$, when the cost of moving a unit amount from $$x\in[0,1]$$ to $$y\in[0,1]$$ is the distance $$|x-y|$$.

If the distributions $$\rho$$ and $$\sigma$$ have finite support, every transport plan for moving from $$\rho$$ to $$\sigma$$ has a simple description: There are an integer $$K>0$$, elements $$y_1,y_2,...,y_K$$ in the support of $$\rho$$ and $$z_1,z_2,...,z_K$$ in the support of $$\sigma$$, and numbers $$\alpha_1,\alpha_2,...,\alpha_K \in[0,1]$$ such that $$\rho = \sum_{i=1}^K \alpha_i \delta_{y_i}$$, $$\sigma = \sum_{i=1}^K \alpha_i \delta_{z_i}$$, and the plan moves amount $$\alpha_i$$ from $$y_i$$ to $$z_i$$ for $$i=1,2,...,K$$. The cost of such a plan is $$\sum_{i=1}^K \alpha_i |y_i - z_i |$$.

The sequence of $$\rho_n$$ converges if and only if it is Cauchy. So this is a necessary and sufficient condition for it to converge:

$$(1) \;\; \forall \varepsilon>0 \;\exists M \;\forall m,n > M \;\exists K=K(m,n) \;\exists y_1,y_2,...,y_K,z_1,z_2,...,z_K \in[0,1]$$
$$\exists \alpha_1,\alpha_2,...,\alpha_K\in[0,1] \;\;\rho_m = \sum_{i=1}^K \alpha_i \delta_{y_i} , \;\;\rho_n = \sum_{i=1}^K \alpha_i \delta_{z_i}, \;\; \sum_{i=1}^K \alpha_i |y_i - z_i | < \varepsilon$$.

From this one can derive various sufficient conditions, depending on what one desires. For example, in the following condition for $$n>m$$ the amount $$\frac{1}{N_m}$$ at each point of $$X_m$$ is split into $$\frac{N_n}{N_m}$$ equal parts and each of those parts is transported to one point of $$X_n$$. (Of course this is only possible if $$N_m$$ divides $$N_n$$.)

$$(2) \;\; \forall \varepsilon>0 \;\exists M \;\forall n>m > M \;\exists y_1,y_2,...,y_{N_n} \in[0,1]$$ $$\rho_m = \frac{1}{N_n}\sum_{i=1}^{N_n} \delta_{y_i}, \;\frac{1}{N_n}\sum_{i=1}^{N_n} |x_i^n - y_i | < \varepsilon$$.

A variation of condition (2) may be useful when the sets $$X_n$$ form the levels of a tree in which each point in $$X_{n+1}$$ has exactly one parent in $$X_n$$ (for example, a nearest point in $$X_n$$) and each point in $$X_n$$ has the same number of children in $$X_{n+1}$$. The transport plan then follows the edges of the tree. For $$n>m$$ and $$x\in X_n$$, denote by $$A_m(x)$$ the unique ancestor of $$x$$ in $$X_m$$ (reached through a chain of parents). The following sufficient condition for the convergence of $$\rho_n$$ is a special case of (2):

$$(3) \;\; \forall \varepsilon>0 \;\exists M \;\forall n>m > M \;\;\frac{1}{N_n}\sum_{i=1}^{N_n} |x_i^n - A_m(x_i^n) | < \varepsilon$$.

• why is the suggested "transport plan" from $\rho_m$ to $\rho_n$ the optimal one? There are many possible choices of $\alpha_i$, $y_i$ and $z_i$. – Skeeve Apr 21 '19 at 7:37
• @Skeeve Thank you. I have edited the wording. – user95282 Apr 21 '19 at 11:13
• OK, but then it is only sufficient, necessity not evident. Actually it would be nice if you add some details and write an explicit formula for the Kantorovich-Rubinstein metric between $\rho_n$ and $\rho_m$. Maybe sorting $y_i$ and $z_i$ would help. – Skeeve Apr 21 '19 at 11:37
• @Skeve The cost of the optimal transport plan is $<\varepsilon$ if and only if there exists a plan whose cost is $<\varepsilon$. – user95282 Apr 21 '19 at 12:27
• sorry, but if there exists a plan whose cost is $<\varepsilon$ then how do we know that this is exactly the plan which moves $y_i$ to $z_i$? – Skeeve Apr 21 '19 at 22:30

Let $$F_n$$ be the distribution function of $$\rho_n$$. Then $$F_n(0-) = 0$$ and $$F_n(1)$$. Let $$\rho$$ be any limit point (w.r.to the weak topology) of $$(\rho_n)_{n \in N}$$ with distribution function $$F$$. Then there is a subsequence $$(F_{n_k})_{k \in N}$$ s.t. $$F_{n_k}$$ converges weakly to $$F$$, i.e. $$\lim_{k \to \infty} F_{n_k}(t) = F(t)$$ for each continuity point $$t$$ of $$F$$. If in particular $$F$$ is continuous (as implied by the spacing conditions, Remark of Christian Remling), then this convergence is uniform, i.e. $$\begin{eqnarray} (*) \lim_{k \to \infty} \|F_{n_k} - F\|_\infty = 0. \end{eqnarray}$$ Thus if we know that any possible limit distribution $$\rho$$ has a continuous distribution function $$F$$, then this limit distribution function $$F$$ is uniquely defined if and only if $$\begin{eqnarray} (**) \lim_{m,n \to \infty} \|F_n - F_m\|_\infty = 0. \end{eqnarray}$$ Note that here $$F_n$$ may be discountinuous. Of course this condition can be translated into conditions for the origninal $$X_n$$. Note that $$N_n \cdot F_n(t)$$ is the number of points $$x_i^n$$ in $$[0,t]$$.