# Unconditional lower bound for volume of blowup $\mu(B^\epsilon)$ for $\mu(B) \in (0, 1)$ and $\epsilon > 0$ not “too large”

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

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

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.
• My question requires $\mu(B) > 0$, which is not the case in the counterexample you're proposing. No ? – dohmatob Feb 1 '19 at 12:57
• I take back my last sentence. What about for $\epsilon \le \sqrt{2\log(1/\mu(B))}$ ? There is decrease. No ? – dohmatob Feb 2 '19 at 16:16