2
$\begingroup$

For a Borel subset $B$ of a metric space $X = (X,d)$ and $\epsilon>0$, recall the defintion of the $\epsilon$-blowup of $B$, namely $B^\epsilon = \{x \in X | d(x,B) \le \epsilon\}$. Let $\mu$ be a probability measure on $X$, and suppose $0 < \mu(B) < 1$. Under certain conditions (on $\mu$), we know that $1-\mu(B^\epsilon)$ decreases exponentially with increasing $\epsilon \ge \epsilon_0$, where $\epsilon_0>0$ is some phase-transition point. This is the phenomenon of measure-concentration in metric spaces. For example, Corollary 1.1 of Otto-Villani (2000) shows such a result with $\epsilon_0 = \sqrt{2\log(1/\mu(B))}$ for measures satisfying the Talagrand transportation-cost inequality.

Question

Can one have an unconditional upper bound (maybe something not exponential, but polynomial in $\epsilon$) for $1-\mu(B^\epsilon)$ valid for "small" $\epsilon$, say for all $\epsilon \le \epsilon_0' < \epsilon_0$ ?

Clarifications

Unconditional, meaning not assuming any magical properties on $\mu$, like log-concavity, etc.

Polynomial, meaning something like $1-\mu(B^\epsilon) \le \epsilon poly(\epsilon)$.

$\endgroup$
3
  • $\begingroup$ What do you mean by "an unconditional upper bound [...] polynomial in ϵ"? $\endgroup$ Feb 1, 2019 at 12:26
  • $\begingroup$ Unconditional, meaning not assuming any magical properties on $\mu$, like log-concavity, etc. Polynomial, meaning something like $1-\mu(B^\epsilon) \le poly(\epsilon)$. $\endgroup$
    – dohmatob
    Feb 1, 2019 at 12:58
  • $\begingroup$ Is $1$ an instance of $poly(\epsilon)$? $\endgroup$ Feb 1, 2019 at 14:08

1 Answer 1

1
$\begingroup$

Unconditional? Certainly not. E.g., suppose that $\mu$ is the standard Gaussian measure on $\mathbb R^d$ and $B$ is the ball of radius $r>0$ centered at $0$. Then for any $\delta\in(0,1)$, by the law of large numbers, $$1-\mu(B^\epsilon)=P\Big(\frac1d\sum_1^d Z_i^2>\frac{(r+\epsilon)^2}d\Big)\to1$$ for $d\to\infty$ and $\epsilon\in(0,(1-\delta)\sqrt d-r\,]$, where $Z_1,Z_2,\dots$ are iid $N(0,1)$. So, asymptotically there is no decrease at all in $\epsilon\le(1-\delta)\sqrt d-r$. So, any bound of the form $1-\mu(B^\epsilon)\le\epsilon\,\text{poly}(\epsilon)$ will not hold in this example.

Added in response to the comment "What about for $\epsilon\le2\log(1/\mu(B))$?" by the OP: $\quad$ As above, let $\mu$ be the standard Gaussian measure on $\mathbb R^d$. As usual, let $\Phi$ denote the cdf of $N(0,1)$. Fix any real $a$ and let $B:=(-\infty,a)\times\mathbb R^{d-1}$. Then $\mu(B)=\Phi(a)$, $\epsilon_0:=2\log(1/\mu(B))=2\ln(1/\Phi(a))$, and $$g(\epsilon):=1-\mu(B^\epsilon)=1-\Phi(a+\epsilon)$$ decreases from the constant $g(0)=1-\Phi(a)$ to the constant $g(\epsilon_0)=1-\Phi(a+\epsilon_0)=1-\Phi(a+2\ln(1/\Phi(a)))>0$ as $\epsilon$ increases from $0$ to $\epsilon_0=2\ln(1/\Phi(a))$. So, $1-\mu(B^\epsilon)$ does not decrease polynomially in $\epsilon$ as $\epsilon$ increases from $0$ to $\epsilon_0=2\log(1/\mu(B))$.

In particular, taking here $a=0$, we see that $1-\Phi(a+\epsilon)$ decreases from $1-\Phi(0)=0.5$ only to $1-\Phi(2\ln2)\approx0.08$ as $\epsilon$ increases from $0$ to $2\log(1/\mu(B))$. Now taking $a=3$, we see that $1-\Phi(a+\epsilon)$ decreases from $\approx0.001350$ only to $\approx0.001338$ as $\epsilon$ increases from $0$ to $2\log(1/\mu(B))$ -- almost no decrease.

$\endgroup$
5
  • $\begingroup$ My question requires $\mu(B) > 0$, which is not the case in the counterexample you're proposing. No ? $\endgroup$
    – dohmatob
    Feb 1, 2019 at 12:57
  • $\begingroup$ Oh ... I missed that condition. I have now updated the answer, in which that condition changes almost nothing. $\endgroup$ Feb 1, 2019 at 14:06
  • $\begingroup$ OK, I definitely think my question is not very well stated, and doesn't convey what I'm getting at. I'll try to fix it asap. Thanks for the input! $\endgroup$
    – dohmatob
    Feb 1, 2019 at 14:18
  • $\begingroup$ I take back my last sentence. What about for $\epsilon \le \sqrt{2\log(1/\mu(B))}$ ? There is decrease. No ? $\endgroup$
    – dohmatob
    Feb 2, 2019 at 16:16
  • $\begingroup$ I have added a response to your latter comment. $\endgroup$ Feb 3, 2019 at 4:07

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.