2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Pierre PC Apr 20 at 6:15
  • 2
    $\begingroup$ 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. $\endgroup$ – Christian Remling Apr 20 at 16:32
  • $\begingroup$ 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". $\endgroup$ – Margaret Friedland Apr 20 at 21:21
  • $\begingroup$ @MargaretFriedland: Except that this has unbounded density, so can't be the limit when the points $x_n$ satisfy the OP's assumptions. $\endgroup$ – Christian Remling Apr 21 at 0:20
  • $\begingroup$ @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. $\endgroup$ – Ben Ciotti Apr 23 at 1:20
4
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Skeeve Apr 21 at 7:37
  • $\begingroup$ @Skeeve Thank you. I have edited the wording. $\endgroup$ – user95282 Apr 21 at 11:13
  • $\begingroup$ 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. $\endgroup$ – Skeeve Apr 21 at 11:37
  • $\begingroup$ @Skeve The cost of the optimal transport plan is $<\varepsilon$ if and only if there exists a plan whose cost is $<\varepsilon$. $\endgroup$ – user95282 Apr 21 at 12:27
  • $\begingroup$ 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$? $\endgroup$ – Skeeve Apr 21 at 22:30
2
$\begingroup$

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]$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.