1
$\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$
  • $\begingroup$ What do you mean by "an unconditional upper bound [...] polynomial in ϵ"? $\endgroup$ – Iosif Pinelis Feb 1 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 at 12:58
  • $\begingroup$ Is $1$ an instance of $poly(\epsilon)$? $\endgroup$ – Iosif Pinelis Feb 1 at 14:08
0
$\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$
  • $\begingroup$ My question requires $\mu(B) > 0$, which is not the case in the counterexample you're proposing. No ? $\endgroup$ – dohmatob Feb 1 at 12:57
  • $\begingroup$ Oh ... I missed that condition. I have now updated the answer, in which that condition changes almost nothing. $\endgroup$ – Iosif Pinelis Feb 1 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 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 at 16:16
  • $\begingroup$ I have added a response to your latter comment. $\endgroup$ – Iosif Pinelis Feb 3 at 4:07

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.