5
$\begingroup$

Let $(X_n)$ be a sequence of $\mathbb{R}^d$-valued random variables converging in distribution to some limiting random variable $X$ whose CDF is absolutely continuous with respect to the Lebesgue measure.

Does it follow that $X_n$ converges to $X$ in convex distance, i.e. that

$$\sup_{h} \lvert \operatorname{E}(h(X)) - \operatorname{E}(h(X_n)) \rvert \to 0,$$

where the supremum is taken over all indicator functions of measurable convex subsets of $\mathbb{R}^d$, if necessary assuming (absolute) continuity of the CDFs of the $X_n$ as well?

Remark 1: For $d=1$, the implication is true and can be proven by Polya's theorem (convergence in law of real valued random variables towards a limit with continuous CDF implies uniform convergence of the CDF). Is it still true for $d \geq 2$?

Remark 2: If absolute continuity is replaced by continuity the conclusion is false, see here

$\endgroup$

2 Answers 2

3
$\begingroup$

What is essential here is that the distribution of $X$ assigns little mass to sets which are essentially $(d-1)$-dimensional.


The standard approach to problems of this kind is to estimate $$ \operatorname{P}(X_n \in K) - \operatorname{P}(X \in K) $$ from above by $$ \operatorname{E}(g(X_n)) - \operatorname{E}(f(X)) , $$ and from below by $$ \operatorname{E}(f(X_n)) - \operatorname{E}(g(X)) , $$ where $0 \leqslant f \leqslant \mathbb{1}_K \leqslant g \leqslant 1$, and $f$ and $g$ are continuous. In $k$-th step we choose $f$ and $g$ in such a way that $\operatorname{E}(g(x) - f(x)) < \tfrac{1}{2 k}$. Convergence of $\operatorname{E}(f(X_n))$ to $\operatorname{E}(f(X))$ and convergence of $\operatorname{E}(g(X_n))$ to $\operatorname{E}(g(X))$ imply that $$ -\tfrac{1}{k} \leqslant \operatorname{P}(X_n \in K) - \operatorname{P}(X \in K) \leqslant \tfrac{1}{k} $$ for all $n$ large enough.

This works as expected, i.e. leads to convergence of $\operatorname{P}(X_n \in K)$ to $\operatorname{P}(X \in K)$, if (and only if) $\operatorname{P}(X \in \partial K) = 0$: then (and only then) it is possible to choose $f$ and $g$ with the desired property.


Now in order to get uniform convergence for a class of sets $K$ — here the class of convex subsets of $\mathbb{R}^d$ — in every step $k$ we should choose $f$ and $g$ from a fixed finite-dimensional set of functions (which, of course, can well depend on $k$). One solution for the class of convex $K$ is as follows.

By tightness, there is $R > 1$ such that $\operatorname{P}(|X_n| > R) < \tfrac{1}{4 k}$ uniformly in $n$. We will choose (small) $\delta \in (0, 1)$ at a later stage. We cover the ball $\overline{B}(0, R)$ using $d$-dimensional cubes $Q_j$ with edge length $\delta$ and vertices at lattice points $(\delta \mathbb{Z})^d$. To be specific, suppose that the cubes $Q_j$ are open sets. Let $h_j = \mathbb{1}_{Q_j}$ be the indicator of $Q_j$. Then $$h_1 + \ldots + h_J = 1 \quad \text{a.e. on $\overline{B}(0, R)$}$$ (more precisely: everywhere on $\overline{B}(0, R)$, except possibly on the faces of cubes $Q_j$). We add $h_0 = 1 - \sum_{j = 1}^J h_j$ to this collection. Observe that $h_0 = 0$ a.e. on the complement of $\overline{B}(0, R)$, and hence $\operatorname{E}(h_0(X)) \leqslant \operatorname{P}(|X_n| > R) < \tfrac{1}{4 k}$. Furthermore, by the first part of this answer, we already know that $\operatorname{E}(h_j(X_n)) = \operatorname{P}(X_n \in Q_j)$ converges to $\operatorname{E}(h_j(X)) = \operatorname{P}(X \in Q_j)$ as $n \to \infty$ for every $j = 0, 1, \ldots, J$ (because the distribution of $X$ does not charge the boundaries of $Q_j$).

Given a convex set $K$, we define $f$ to be the sum of all $h_j$ corresponding to cubes $Q_j$ contained in $K$, and $g$ to be the sum of all $h_j$ corresponding to cubes $Q_j$ which intersect $K$. Clearly, $$0 \leqslant f \leqslant \mathbb{1}_K \leqslant g \leqslant 1 \qquad \text{a.e.}$$ As in the first part of the proof, $$ \operatorname{E}(f(X_n)) - \operatorname{E}(g(X)) \leqslant \operatorname{P}(X_n \in K) - \operatorname{P}(X \in K) \leqslant \operatorname{E}(g(X_n)) - \operatorname{E}(f(X)) . $$ For $n$ large enough we have $$ \sum_{j = 0}^J |\operatorname{E}(h_j(X_n)) - \operatorname{E}(h_j(X))| \leqslant \tfrac{1}{2 k} , $$ and so $$ |\operatorname{E}(f(X_n)) - \operatorname{E}(f(X))| \leqslant \tfrac{1}{2 k} , \qquad |\operatorname{E}(g(X_n)) - \operatorname{E}(g(X))| \leqslant \tfrac{1}{2 k} .$$ Thus, $$ -\tfrac{1}{2k} - \operatorname{E}(g(X) - f(X)) \leqslant \operatorname{P}(X_n \in K) - \operatorname{P}(X \in K) \leqslant \tfrac{1}{2k} + \operatorname{E}(g(X) - f(X)) $$ for $n$ large enough, uniformly with respect to $K$. It remains to choose $\delta > 0$ such that $\operatorname{E}(g(X) - f(X)) < \tfrac{1}{2k}$ uniformly with respect to $K$; once this is proved, we have $$ -\tfrac{1}{k} \leqslant \operatorname{P}(X_n \in K) - \operatorname{P}(X \in K) \leqslant \tfrac{1}{k} $$ for $n$ large enough, uniformly with respect to $K$, as desired.

By definition, $g - f$ is the sum of some number of functions $h_j$ with $j \geqslant 1$ — say, $m$ of them — and possibly $h_0$. Recall that $\operatorname{E}(h_0(X)) \leqslant \operatorname{P}(|X_n| > R) < \tfrac{1}{4 k}$. It follows that $$ \operatorname{E}(g(X) - f(X)) \leqslant \tfrac{1}{4 k} + \sup \{ \operatorname{P}(X \in A) : \text{$A$ is a sum of $m$ cubes $Q_j$} \} . \tag{$\heartsuit$} $$ We now estimate the size of $m$.

Lemma. For a convex $K$, the number $m$ defined above is bounded by a constant times $(R / \delta)^{d - 1}$.

Proof: Suppose that $Q_j$ intersects $K$, but it is not contained in $K$. Consider any point $z$ of $K \cap Q_j$, and the supporting hyperplane $$\pi = \{x : \langle x - z, \vec{u} \rangle = 0\}$$ of $K$ at that point. We choose $\vec{u}$ in such a way that $K$ is contained in $\pi^- = \{x : \langle x - z, \vec{u} \rangle \leqslant 0\}$. If the boundary of $K$ is smooth at $z$, then $\vec{u}$ is simply the outward normal vector to the boundary of $K$ at $z$.

To simplify notation, assume that $\vec{u}$ has all coordinates non-negative. Choose two opposite vertices $x_1, x_2$ of $Q_j$ in such a way that $\vec{v} = x_2 - x_1 = (\delta, \ldots, \delta)$. Then the coordinates of $x_2 - z$ are all positive. It follows that for every $n = 1, 2, \ldots$, all coordinates of $(x_1 + n \vec{v}) - z = (x_2 - z) + (n - 1) \vec{v}$ are non-negative, and therefore the translated cubes $Q_j + n \vec{v}$ all lie in $\pi^+ = \{x : \langle x - z, \vec{u} \rangle \geqslant 0\}$. In particular, all these cubes are disjoint with $K$.

In the general case, when the coordinates of $\vec{u}$ have arbitrary signs, we obtain a similar result, but with $\vec{v} = (\pm \delta, \ldots, \pm \delta)$ for some choice of signs. It follows that with each $Q_j$ intersecting $K$ but not contained in $K$ we can associate the directed line $x_2 + \mathbb{R} \vec{v}$, and this this line uniquely determines $Q_j$: it is the last cube $Q$ with two vertices on this line that intersects $K$ (with "last" referring to the direction of the line).

It remains to observe that the number of lines with the above property is bounded by $2^d$ (the number of possible vectors $\vec{v}$) times the number of points in the projection of $(\delta \mathbb{Z})^d \cap \overline{B}(0, R)$ onto the hyperplane perpendicular to $\vec{v}$. The latter is bounded by a constant times $(R / \delta)^{d - 1}$, and the proof is complete. $\square$

(The above proof includes simplification due to Iosif Pinelis.)

Since the Lebesgue measure of $Q_j$ is equal to $\delta^d$, the measure of $A$ in ($\heartsuit$) is bounded by $m \delta^d \leqslant C R^{d - 1} \delta$ for some constant $C$. Furthermore, since the distribution of $X$ is absolutely continuous, we can find $\delta > 0$ small enough, so that $\operatorname{P}(X \in A) < \tfrac{1}{4 k}$ for every set $A$ with measure at most $C R^{d - 1} \delta$ (recall that $R$ was chosen before we fixed $\delta$). By ($\heartsuit$), we find that $$ \operatorname{E}(g(X) - f(X)) \leqslant \tfrac{1}{4 k} + \sup \{ \operatorname{P}(X \in A) : |A| \le C R^{d - 1} \delta\} \leqslant \tfrac{1}{2 k} , $$ uniformly with respect to $K$.

$\endgroup$
14
  • $\begingroup$ To me, the main difficulty here was to prove something like your "$m$ is bounded by a constant times $(R / \delta)^{d-1}$", which of course seems intuitively obvious. Is there is a quick way to show this? Or a reference? $\endgroup$ Feb 3, 2020 at 22:48
  • $\begingroup$ @IosifPinelis: $K' := K \cap B(0, R)$ is convex. Pick $x_0$ in the interior of $K'$. Then $K' = \{x : |x - x_0| \le \phi((x - x_0)/|x - x_0|)$ for a Lipschitz function $\phi$ with some Lipschitz constant $L$. Cover the unit sphere with $C (L+1) (R/\delta)^{d-1}$ balls of radius $\delta/R$, centered at $u_j$. Then $B_j := B(x_0+\phi(u_j)u_j, \delta)$ cover $\partial K'$. Each $B_j$ intersects with at most a constant number of supports of $h_j$, and the desired bound follows. $\endgroup$ Feb 3, 2020 at 23:41
  • $\begingroup$ @IosifPinelis: I just realised that in the above comment, $m$ depends on the Lipshitz constant, which in turn depends on the radius of the largest ball $B(x_0, r)$ contained in $K'$. I guess there must be a smarter argument; I'll try to come back to this tomorrow. $\endgroup$ Feb 3, 2020 at 23:45
  • $\begingroup$ @IosifPinelis: I have just edited in a simpler argument into the answer. Also, I extended the argument to arbitrary absolutely continuous distributions, and fixed other errors. Thank you for your comment, and please let me know if you still find any issues. $\endgroup$ Feb 4, 2020 at 9:04
  • $\begingroup$ @MateuszKwaśnicki Thank you VERY much for this very nice and elegant answer! I can follow everything and think your arguments are correct. See my other comment below for some suggestion on how to improve readability of your answer. $\endgroup$ Feb 4, 2020 at 10:53
1
$\begingroup$

$\newcommand{\R}{\mathbb{R}} \newcommand{\ep}{\varepsilon} \newcommand{\p}{\partial} \newcommand{\de}{\delta} \newcommand{\De}{\Delta}$ This is to try to provide a simplification and detalization of the answer by Mateusz Kwaśnicki.

Suppose that the distribution of $X$ is absolutely continuous (with respect to the Lebesgue measure) and $X_n\to X$ in distribution. We are going to show that then $X_n\to X$ in in convex distance, that is, $$\sup_K|\mu_n(K)-\mu(K)|\overset{\text{(?)}}\to0$$ (as $n\to\infty$), where $\mu_n$ and $\mu$ are the distributions of $X_n$ and $X$, respectively, and $\sup_K$ is taken over all measurable convex sets in $\R^d$.

Take any real $\ep>0$. Then there is some real $R>0$ such that $P(X\notin Q_R)\le\ep$, where $Q_R:=(-R/2,R/2]^d$, a left-open $d$-cube. Since $X_n\to X$ in distribution and $P(X\in\p Q_R)=0$, there is some natural $n_\ep$ such that for all natural $n\ge n_\ep$ we have $$P(X_n\notin Q_R)\le2\ep.$$ Take a natural $N$ and partition the left-open $d$-cube $Q_R$ naturally into $N^d$ left-open $d$-cubes $q_j$ each with edge length $\de:=R/N$, where $j\in J:=[N^d]:=\{1,\dots,N^d\}$.

Using again the conditions that $X_n\to X$ in distribution and $\mu$ is absolutely continuous (so that $\mu(\p q_j)=0$ for all $j\in J$), and increasing $n_\ep$ is needed, we may assume that for all natural $n\ge n_\ep$ $$\De:=\sum_{j\in J}|\mu_n(q_j)-\mu(q_j)|\le\ep.$$

Take now any measurable convex set $K$ in $\R^d$. Then $$|\mu_n(K)-\mu(K)|\le|\mu_n(K\cap Q_R)-\mu(K\cap Q_R)| \\ +|\mu_n(K\setminus Q_R)-\mu(K\setminus Q_R)| $$ and $$|\mu_n(K\setminus Q_R)-\mu(K\setminus Q_R)|\le P(X_n\notin Q_R)+P(X\notin Q_R)\le3\ep. $$

So, without loss of generality (wlog) $K\subseteq Q_R$. Let $$J_<:=J_{<,K}:=\{j\in J\colon q_j\subseteq K^\circ\},$$ $$J_\le:=J_{\le,K}:=\{j\in J\colon q_j\cap \bar K\ne\emptyset\},$$ $$J_=:=J_{=,K}:=\{j\in J\colon q_j\cap\p K\ne\emptyset\},$$ where $K^\circ$ is the interior of $K$ and $\bar K$ is the closure of $K$.

The key to the whole thing is

Lemma. $|\bigcup_{j\in J_=}q_j|\le2d(d+2)R^{d-1}\de$, where $|\cdot|$ is the Lebesgue measure.

This lemma will be proved at the end of this answer. Using the absolute continuity of the distribution of $X$, we can take $N$ so large that for any Borel subset $B$ of $\R^d$ we have the implication $$|B|\le2d(d+2)R^{d-1}\de\implies \mu(B)\le\ep.$$

Using now the lemma, for $n\ge n_\ep$ we have $$\mu_n(K)-\mu(K) \le\sum_{j\in J_\le}\mu_n(q_j)-\sum_{j\in J_<}\mu(q_j) \\ \le\sum_{j\in J_\le}|\mu_n(q_j)-\mu(q_j)| +\mu \Big(\bigcup_{j\in J_=}q_j\Big)\le\De+\ep\le2\ep. $$ Similarly, $$\mu(K)-\mu_n(K) \le\sum_{j\in J_\le}\mu(q_j)-\sum_{j\in J_<}\mu_n(q_j) \\ \le\sum_{j\in J<}|\mu(q_j)-\mu_n(q_j)| +\mu \Big(\bigcup_{j\in J_=}q_j\Big)\le\De+\ep\le2\ep. $$ So, $|\mu_n(K)-\mu(K)|\le2\ep$. That is, the desired result is proved modulo the lemma.


Proof of the lemma. Since $K$ is convex, for any $x\in\p K$ there is some unit vector $\nu(x)$ such that $\nu(x)\cdot(y-x)\le0$ for all $y\in K$ (the support half-space thing), where $\cdot$ denotes the dot product. For each $j\in[d]$, let $$S_j^+:=\{x\in\p K\colon\nu(x)_j\ge1/\sqrt d\},\quad S_j^-:=\{x\in\p K\colon\nu(x)_j\le-1/\sqrt d\},$$ $$J_{=,j}^+:=\{j\in J\colon q_j\cap S_j^+\ne\emptyset\},\quad J_{=,j}^-:=\{j\in J\colon q_j\cap S_j^-\ne\emptyset\},$$ where $v_j$ is the $j$th coordinate of a vector $v\in\R^d$. Note that $\bigcup_{j\in[d]}(S_j^+\cup S_j^-)=\p K$ and hence $\bigcup_{j\in[d]}(J_{=,j}^+\cup J_{=,j}^-)=J_=$, so that $$\Big|\bigcup_{j\in J_=}q_j\Big| \le \sum_{j\in[d]}\Big(\Big|\bigcup_{j\in J_{=,j}^+}q_j\Big|+\Big|\bigcup_{j\in J_{=,j}^-}q_j\Big|\Big) \le\de^d \sum_{j\in[d]}(|J_{=,j}^+|+|J_{=,j}^-|),\tag{*} $$ where now $|J_{=,j}^\pm|$ denotes the cardinality of $J_{=,j}^\pm$.

Now comes the key step in the proof of the lemma: Take any $x$ and $y$ in $S_d^+$ such that $x_d\le y_d$. We have the support "inequality" $\nu(x)\cdot(y-x)\le0$, which implies $$\frac{y_d-x_d}{\sqrt d}\le\nu(x)_d(y_d-x_d)\le\sum_{j=1}^{d-1}\nu(x)_j(x_j-y_j) \le|P_{d-1}x-P_{d-1}y|, $$ where $P_{d-1}x:=(x_1,\dots,x_{d-1})$. So, we get the crucial Lipschitz condition $$|y_d-x_d|\le\sqrt d\,|P_{d-1}x-P_{d-1}y| \tag{**}$$ for all $x$ and $y$ in $S_d^+$.

Partition the left-open $(d-1)$-cube $P_{d-1}Q_R$ naturally into $N^{d-1}$ left-open $(d-1)$-cubes $c_i$ each with edge length $\de=R/N$, where $i\in I:=[N^{d-1}]$. For each $i\in I$, let $$ J_{=,d,i}^+:=\{j\in J_{=,d}^+\colon P_{d-1}q_j=c_i\},\quad s_i:=\bigcup_{j\in J_{=,d,i}}q_j, $$ so that $s_i$ is the "stack" of all the $d$-cubes $q_j$ with $j\in J_{=,d}^+$ that $P_{d-1}$ projects onto the same $(d-1)$-cube $c_i$. Let $r_i$ be the cardinality of the set $J_{=,d,i}$, that is, the number of the $d$-cubes $q_j$ in the stack $s_i$. Then for some two points $x$ and $y$ in $s_i\cap S_d^+$ we have $|y_d-x_d|\ge(r_i-2)\de$, whence, in view of (**), $$\sqrt d\,\sqrt{d-1}\,\de\ge\sqrt d\,|P_{d-1}x-P_{d-1}y|\ge|y_d-x_d|\ge(r_i-2)\de,$$ so that $r_i\le d+2$. So, $$|J_{=,d}^+|=\sum_{i\in I}r_i\le\sum_{i\in I}(d+2)=(d+2)N^{d-1}=(d+2)(R/\de)^{d-1}.$$ Similarly, $|J_{=,j}^\pm|\le(d+2)(R/\de)^{d-1}$ for all $j\in[d]$. Now the lemma follows from (*).

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