3
$\begingroup$

Let $\gamma_n$ be the standard Gaussian measure on $\mathbb R^n$, $A \subseteq \mathbb R^n$ be Borel and $c \in \mathbb R^n$. Define the translate $A_c := c + A := \{c+a \mid a \in A\} = \{x \in \mathbb R^n \mid x-c \in A\}$. Assume $A$ is not too "small", e.g $\gamma_n(A) \ge 1/2$.

Question

  • What are good lower (and perhaps upper) bounds for $\gamma_n(A_c)$ ?

Observations

For a half-space $H = \{x \in \mathbb R^n \mid u^Tx \le v\}$, one has $H_c = \{x \in \mathbb R^n \mid u^Tx \le v + u^Tc\}$, another half-space with Gaussian volume $\gamma_n(H_c) = \Phi\left(\frac{v + u^Tc}{\|u\|}\right) = \Phi\left(\Phi^{-1}(\gamma_n(H)+\frac{u^Tc}{\|u\|}\right)$, where $\Phi$ is the 1D Gaussian CDF.


Update

Let $H$ be a half-space with same Gaussian volume as $B$, i.e $\gamma_n(H)=\gamma_n(A)$.

Question: Under which minimal / reasonable conditions do we have $\gamma_n(A_c) \ge \gamma_n(H_c)$ ?

$\endgroup$
4
  • $\begingroup$ I have the strong feeling such questions can be answered using inequalities of Brunn-Minkowski type ams.org/journals/tran/2010-362-10/S0002-9947-2010-04891-3/…, but I don't have much experience with those tools. $\endgroup$
    – dohmatob
    Mar 21, 2019 at 13:46
  • $\begingroup$ One simple observation: If $A$ is a ball centered at the origin, then $\gamma_n(A_c)<\gamma_n(A)$ for all $c\neq 0$, while for a half-space one has the sign of $\gamma_n(H_c)-\gamma_n(H)$ depending on whether $c$ points out of $H$ or into $H$ (and is zero if $c$ is parallel to \partial H$. $\endgroup$
    – RBega2
    Mar 21, 2019 at 15:41
  • $\begingroup$ @RBega2 Good points. BTW, your second remark is a consequence of what I wrote down as "observations". $\endgroup$
    – dohmatob
    Mar 21, 2019 at 15:50
  • $\begingroup$ I've just posted an answer below, based on Neymann-Pearson theory (1933). $\endgroup$
    – dohmatob
    Mar 25, 2019 at 13:15

2 Answers 2

2
$\begingroup$

Let \begin{equation} g(t):=\gamma_n(tu+c+A)=P(Z\in tu+c+A)=\int_{c+A}(2\pi)^{-n/2}e^{-|z+tu|^2/2}\,dz, \end{equation} where $t\in\mathbb R$, $u$ is a unit vector in $\mathbb R^n$, $Z$ is a standard Gaussian random vector in $\mathbb R^n$, and $|\cdot|$ is the Euclidean norm. Then \begin{equation} g'(0)=-\int_{c+A}(2\pi)^{-n/2}z\cdot u\,e^{-|z|^2/2}\,dz =-p\,u\cdot E(Z|Z\in c+A), \end{equation} where $p:=P(Z\in c+A)=\gamma_n(c+A)$ and $z\cdot u$ is the dot product of $z$ and $u$.

That is, the rate of change of $\gamma_n(c+A)$ with respect to $c$ in the direction of a unit vector $u$ equals the following:

$\gamma_n(c+A)$ times the $u$-coordinate $u\cdot E(Z|Z\in c+A)$ of the center $E(Z|Z\in c+A)$ of the standard Gaussian mass over the set $c+A$.

$\endgroup$
8
  • $\begingroup$ Great answer, thanks. Possible simplification: Let $\mu_A \in \mathbb R^n$ be the Gaussian barycenter of $A$. Then $E(Z|Z \in c + A) = E(Z-c|Z \in A) = E(Z|Z \in A)-c = \mu_A-c$. $\endgroup$
    – dohmatob
    Mar 21, 2019 at 17:52
  • $\begingroup$ Thank you for your comment. However, in general the equality $E(Z|Z\in c+A)=E(Z-c|Z\in A)$ will not hold. E.g., let $n=1$ and $A=[-1,1]$. Then for large $c>0$ we have $E(Z|Z\in c+A)\sim c$ but $E(Z-c|Z\in A)=-c$. Even the equality $E(Z|Z\in c+A)=E(Z+c|Z\in A)$ will not hold here: for these $n$ and $A$, we have $E(Z|Z\in c+A)<c=E(Z+c|Z\in A)$ for all real $c>0$. $\endgroup$ Mar 21, 2019 at 20:06
  • $\begingroup$ Oops, indeed my computations don't work. Thanks $\endgroup$
    – dohmatob
    Mar 21, 2019 at 20:19
  • $\begingroup$ Can the integral / differential computations in your answer be used to provide bounds (of any sort) on $\gamma_n(c+A)$ as asked in the question, or does your answer say the question is intricately complicated ? Thanks in advance. $\endgroup$
    – dohmatob
    Mar 21, 2019 at 20:20
  • $\begingroup$ In view of this center-of-Gaussian-mass interpretation, much will likely depend on the choice of $A$ (and $c$, too). Even some of the considerations in my previous comment for the simplest case of $n=1$ and a convex $A$ are not quite trivial. So, I'd be greatly (and pleasantly) surprised if bounds for general $A$ are obtained. $\endgroup$ Mar 21, 2019 at 20:47
2
$\begingroup$

It turns out that Neyman-Pearson theory helps get a nontrivial inequality.

Notations. For a p.s.d matrix $M$ of size $p$, consider the inner product on $\mathbb R^p$ defined by $\langle x,z \rangle_M := x^TMz$. This induces a norm defined by $\|x\|_M:=\sqrt{\langle x,x \rangle_M}$.

Theorem (Neyman-Pearson for translated multivaritate Gaussians). Let $\beta \in \mathbb R$, $\delta\in \mathbb R^p$ and $A$ be a Borell subset of $\mathbb R^p$. Let $X \sim \mathcal N(0,\Sigma)$ and $Y:=X+\delta$. Consider the half-space \begin{eqnarray} H=\{z \in \mathbb R^p \mid \langle\delta,z\rangle_{\Sigma^{-1}} \le \beta\}. \end{eqnarray}

  • If $\mathbb P(X \in A) \ge \mathbb P(X \in H)$, then $\mathbb P(Y \in A) \ge \mathbb P(Y \in H)$.
  • If $\mathbb P(X \in A) \le \mathbb P(X \in H^c)$, then $\mathbb P(Y \in A) \le \mathbb P(Y \in H^c)$.

Proof. The log of the ratio of the densities of $Y$ and $X$ is given by \begin{eqnarray*} \begin{split} \log(f_Y(z))-\log(f_X(z)) &= -\frac{1}{2}(z-\delta)^T\Sigma^{-1}(z-\delta)-\frac{1}{2}z^T\Sigma^{-1}z\\ &= \langle \delta,z \rangle_{\Sigma^{-1}}-\frac{1}{2}\|\delta\|_{\Sigma^{-1}}^2. \end{split} \end{eqnarray*} Thus $f_Y(z) \le t f_X(z)$ iff $\langle \delta,z \rangle_{\Sigma^{-1}}-\frac{1}{2}\|\delta\|_{\Sigma^{-1}}^2 \le \log(t)$. Define $t := e^{\beta-\frac{1}{2}\|\delta\|_{\Sigma^{-1}}^2}$. Then $S_t=H$, and we can apply the Neyman-Pearson Lemma (see Appendix below) to get the claimed results. $\Box$


Appendix

The following Lemma is a modern formulation of the celebrated Neyman-Pearson Lemma.

Lemma (Neyman-Pearson 1933). Let $A$ be an event in a probability space $\mathcal Z$, and let $X$, $Y$ be random variables on $\mathcal Z$, with densities $f_X$ and $f_Y$ respectively. Finally, let $t > 0$ and define \begin{eqnarray} S_t:= \{z \in \mathcal Z \mid f_Y(z) \le tf_X(z)\}. \end{eqnarray} We have the following:

  • If $\mathbb P(X \in A) \ge \mathbb P(X \in S_t)$, then $\mathbb P(Y \in A) \ge \mathbb P(Y \in S_t)$.
  • If $\mathbb P(X \in A) \le \mathbb P(X \in S_t^c)$, then $\mathbb P(Y \in A) \le \mathbb P(Y \in S_t^c)$.

Proof. Suppose $\mathbb P(X \in A) \ge \mathbb P(X \in S_t)$, and let $A^c$ be the set complement of $A$ in $\mathcal Z$. One computes \begin{eqnarray*} \begin{split} &\mathbb P(Y \in A)-\mathbb P(Y \in S_t)=\int 1_A(z)f_Y(z)dz-\int_{S_t}f_Y(z)dz\\ &= \int_{S_t} 1_A(z)f_Y(z)dz+\int_{S_t^c} 1_A(z)f_Y(z)dz-\left(\int_{S_t} 1_A(z)f_Y(z)dz+\int_{S_t} 1_{A^c}(z)f_Y(z)dz \right)\\ &=\int_{S_t^c} 1_A(z)f_Y(z)dz-\int_{S_t} 1_{A^c}(z)f_Y(z)dz\\ &\ge t\left(\int_{S_t^c} 1_A(z)f_X(z)dz-\int_{S_t} 1_{A^c}(z)f_X(z)dz\right),\text{ by definition of }S_t\\ &= t(\mathbb P(X \in A)-\mathbb P(X \in S_t)) \ge 0,\text{ by assumption}. \end{split} \end{eqnarray*} Thus $\mathbb P(Y \in A) \ge \mathbb P(Y \in S_t)$. Similarly, one proves the second part of the claim with "$\ge$" replaced with "$\le$". $\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\Box$

$\endgroup$
3
  • $\begingroup$ Looks like a nice idea. $\endgroup$ Mar 25, 2019 at 14:21
  • 1
    $\begingroup$ I believe the statement is wrong -- specifically, both Theorem and Lemma should have a complement on the second item ($H^c$ and $S_t^c$ for the second bullet of each statement). $\endgroup$
    – Clement C.
    Oct 31, 2023 at 4:44
  • $\begingroup$ Yes, obviously. That's what happens when you prove one part of a result and state that "the proof of the second part is completely analogous to the first". Fixed. $\endgroup$
    – dohmatob
    Oct 31, 2023 at 12:17

Your Answer

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

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