4
$\begingroup$

Consider two measurable spaces $X_1 = (\mathbb{R}^m,\mathcal{B}(\mathbb{R}^m),\mu_1)$ and $X_2 = (\mathbb{R}^m,\mathcal{B}(\mathbb{R}^m),\mu_2)$ and the product spaces $$X_1^{q} = (\times_{i=1}^q\mathbb{R}^m,\otimes_{i=1}^q\mathcal{B}(\mathbb{R}^{m}),\mu_1^{\otimes q})\ \ \ \text{ and }\ \ \ X_2^{q} = (\times_{i=1}^q\mathbb{R}^m,\otimes_{i=1}^q\mathcal{B}(\mathbb{R}^{m}),\mu_2^{\otimes q})$$ where $\mu_1^{\otimes q} = \underbrace{\mu_1\otimes \cdots \otimes\mu_1}_{q}$ and $\mu_2^{\otimes q} = \underbrace{\mu_2\otimes \cdots \otimes\mu_2}_{q}$, respectively.

Let $$ D(\mu,\nu) = \sup_{\substack{\text{all closed balls } B \text{ of }\mathbb{R}^m\\ \text{in the Euclidean norm} }} \left|\mu(B)-\nu(B)\right| $$ be the discrepancy metric between probability measures $\mu$ and $\nu$ (see e.g. this paper for more details on this metric).

My question. For probability measures $\mu_1$ and $\mu_2$, does there exist $k>0$ independent of $\mu_1$ and $\mu_2$ such that $$ D(\mu_1^{\otimes q},\mu_2^{\otimes q})\le k D(\mu_1,\mu_2)\ \ \ ? $$

Note. For other probability metrics the answer is in the affirmative (e.g., for the total variation metric, see Eq. (4.5) of this paper) but I couldn't find anything about the discrepancy metric above. I suspect that, if true, this should be a rather known result. Any suggestion or comment is very welcome.

$\endgroup$
7
  • 1
    $\begingroup$ So, you want $k$ to depend only on $q$, right? $\endgroup$ Aug 8, 2022 at 22:01
  • 1
    $\begingroup$ @IosifPinelis: Yes. $\endgroup$
    – Ludwig
    Aug 9, 2022 at 6:23
  • 1
    $\begingroup$ I’m guessing you want the Euclidean distance to define the closed balls in $\mathbb R^d$? If you are allowed to use $\ell_\infty$ distance instead, this seems as though it becomes fairly straightforward? $\endgroup$ Aug 10, 2022 at 6:54
  • 1
    $\begingroup$ @AnthonyQuas: Yes, the balls are in the Euclidean norm. I edited the question to clarify this. Thanks for your comment. $\endgroup$
    – Ludwig
    Aug 10, 2022 at 7:09
  • 1
    $\begingroup$ Something is not clear to me. The two sides of the inequality are not homogeneous. So the best constant for $2\mu_1$ and $2\mu_2$ is $2^{q-1}$ times the best constant for $\mu_1$ and $\mu_2$, so there exists no $k$ independent from $\mu_1$ and $\mu_2$. Maybe you are talking of probability measures? $\endgroup$ Aug 19, 2022 at 14:10

1 Answer 1

2
$\begingroup$

Analogous to the TV metric, the requested upper bound holds for the discrepancy metric with $k=q$. The result given below can also be easily extended to general product probability measures $\mu=\otimes_{i=1}^q \mu_{i}$ and $\nu=\otimes_{i=1}^q \nu_i$ to obtain $$ D(\mu,\nu)\le \sum_{i=1}^q D(\mu_i, \nu_i)\;. $$


Suppose that $\mu_1$ and $\mu_2$ are probability measures. Let $B = \{ (x_1, \dots, x_q) : \sum_i (x_i - c_i)^2 \le R^2 \}$ be a closed ball in $\mathbb{R}^q$ with radius $R>0$ centered at $(c_1, \dots, c_q) \in \mathbb{R}^q$. Let $\mathbf{1}_A$ denote the indicator function of the set $A$.

By telescoping, and invoking Tonelli’s theorem to write $(\mu_1^{\otimes q}-\mu_2^{\otimes q})(B)$ as an iterated integral, note that \begin{align*} & |(\mu_1^{\otimes q}-\mu_2^{\otimes q})(B)|= \left| \int_{\mathbb{R}^q} \mathbf{1}_B(x_1, \dots, x_q) \biggl( d\mu_1(x_1) \cdots d\mu_1(x_q) - d\mu_2(x_1) \cdots d\mu_2(x_q) \biggr) \right| \\ &= \left| \int_{\mathbb{R}^q} \mathbf{1}_B(x_1, \dots, x_q) \sum_{ i=1}^q d\mu_1(x_1) \cdots d\mu_1(x_{i-1}) \biggl(d\mu_1(x_{ i}) - d\mu_2(x_{ i})\biggr) d\mu_2(x_{i+1}) \dots d\mu_2(x_q) \right| \\ &= \left| \sum_{ i=1}^q \int_{\mathbb{R}^{q-1}} \left(\int_{\mathbb{R}} \mathbf{1}_B(x_1, \dots, x_q)\biggl(d\mu_1(x_{ i}) - d\mu_2(x_{ i})\biggr) \right) d\mu_1(x_1) \cdots d\mu_1(x_{i-1}) d\mu_2(x_{i+1}) \dots d\mu_2(x_q) \right| \\ &\le \sum_{ i=1}^q \int_{\mathbb{R}^{q-1}} \left| \int_{\mathbb{R}} \mathbf{1}_B(x_1, \dots, x_q)\biggl(d\mu_1(x_{ i}) - d\mu_2(x_{ i})\biggr) \right| d\mu_1(x_1) \cdots d\mu_1(x_{i-1}) d\mu_2(x_{i+1}) \dots d\mu_2(x_q) \\ &\le \sum_{i=1}^q \sup_{\gamma_i, \rho_i} \left| \int_{\mathbb{R}}\mathbf{1}_{(x_i-\gamma_i)^2 \le \rho_i^2} \biggl(d\mu_1(x_{ i}) - d\mu_2(x_{ i}) \biggr) \right| \\ & \qquad \int_{\mathbb{R}^{q-1}} d\mu_1(x_1) \cdots d\mu_1(x_{i-1}) d\mu_2(x_{i+1}) \cdots d\mu_2(x_q) \\ &\le q D(\mu_1, \mu_2) \;. \end{align*} Since $B$ is arbitrary, the conjectured upper bound holds with $k=q$.


Remark. One can do much better than this linear upper bound in some special cases. For instance, suppose that $\mu_1 = \mathcal{N}(0,1)$ and $\mu_2 = \mathcal{N}(0, \sigma^2)$. Then, by moving to hyperspherical coordinates, it's not too hard to show that $$ D(\mu_1^{\otimes q},\mu_2^{\otimes q}) = \left| \frac{\Gamma(\frac{q}{2}, \frac{q \log{\sigma}}{\sigma^2-1}) - \Gamma(\frac{q}{2}, \frac{q \sigma^2 \log(\sigma)}{\sigma^2-1})}{ \Gamma(\frac{q}{2}) } \right| \; $$ which converges to one with $q$ and $k(q):= D(\mu_1^{\otimes q},\mu_2^{\otimes q}) /D(\mu_1,\mu_2) $ grows sublinearly. This Gaussian case is rather exceptional because the corresponding product measure can be directly written in terms of the Euclidean distance.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.