4
$\begingroup$

The concentration of measure on $ [0, 1]^n $ equipped with uniform probability measure $\mu_{\infty}$, states that for any $A \subset [0, 1]^n $ with $ \mu_{\infty}(A) \geq \frac{1}{2} $, we have: $$ 1 - \mu_{\infty}(A_{\epsilon}) \leq e^{- \pi \epsilon^2 }, \epsilon > 0, $$ where $A_{\epsilon} = \{ x \in [0, 1]^n; d(x, A) < \epsilon \}$, and $d = L_2$ is the Euclidean distance.

I wonder how the assumption $ \mu_{\infty}(A) \geq \frac{1}{2} $ affects the statement. Do we have a sharper inequality for $\mu_{\infty}(A) = 0.9$? Do we have a weaker inequality for $\mu_{\infty}(A) = 0.05$?

More precisely, the concentration of measure on $L^p$ balls has the following properties. Let $B^n_{p}$ denote a $p$ ball with $\mu_p$ normalized uniform measure, where $p \geq 2$. For any $A \subset B^n_{p} $, with $ \mu_p(A) > 0 $, we have:

$$ 1 - \mu_p(A_{\epsilon}) \leq \frac{1}{\mu_p(A)} e^{-2n C\epsilon^{p} } $$ where $\mu_p(A)$ directly affects the concentratioon bound, $A_{\epsilon} = \{ x \in B^n_p; d(x, A) < \epsilon \}$, and $d = L_p$ is the $p$ norm.

The above question may be too elementary. Since I got no response from https://math.stackexchange.com/questions/2637835/on-the-1-2-assumption-on-concentration-of-measure-on-continuous-cube It may not be a bad idea to ask here: it may be obvious to experts in the field, but not necessarily trivial for outsiders.

$\endgroup$
2
  • $\begingroup$ I'm puzzled by the statement: What is $\mu_\infty$? More precisely, since the (Lebesgue) volume of $[0,1]^n$ is one, what do you mean by normalized uniform measure? If it's the usual Lebesgue measure, then by taking $A:=\{(x_1,\ldots,x_n)\in[0,1]^n:\;0\leq x_1\leq \alpha\}$ with $\alpha\geq 1/2$, I obtain $\mu_\infty(A_\epsilon)=\alpha+\epsilon\leq 1-e^{-\pi\epsilon^2}$... $\endgroup$ Commented Feb 7, 2018 at 8:30
  • 1
    $\begingroup$ I meant to say, it is uniform probability measure. I tend to call uniform probability measure on a geometric objects with normalized volume. Sorry for the confusion. In here, the $\infty$ notation is just an annotation to contrast the cube with the $L^p$ case. On your second point, I think you got my inequality reversed. The inequality also appears at: www-users.math.umn.edu/~bobko001/papers/… Let me know if my question is still confusing $\endgroup$ Commented Feb 7, 2018 at 16:48

1 Answer 1

6
$\begingroup$

By the Tsirel’son--Ibragimov--Sudakov argument, reviewed on the first page in Bobkov, pushing the measure forward from the cube to the canonical Gaussian on $\mathbb R^n$ and using the Gaussian isoperimetric inequality, we have \begin{equation} 1 - \mu_{\infty}(A_r)\le B(r):= B_p(r):= 1-\Phi\big(r\sqrt{2\pi}+\Phi^{-1}(p)\big), \end{equation} where $r\ge0$, $\Phi$ is the standard normal distribution function on $\mathbb R$, and \begin{equation} p:=\mu_{\infty}(A). \end{equation} We see that the bound $B_p(r)$ indeed decreases in $p$ (and, of course, in $r$).

If $p\ge1/2$, then $B(r)\le 1-\Phi\big(r\sqrt{2\pi}\big)$, and the inequality $\Phi(u)\ge1-e^{-u^2/2}$ for $u\ge0$ indeed implies $B(r)\le e^{-\pi r^2}$. If $p\uparrow1$, then $B(r)\le(1-p)^{1-o(1)}e^{-\pi r^2}$, which is better than $e^{-\pi r^2}$. If $p<1/2$, then $B(r)>1-\Phi\big(r\sqrt{2\pi}\big)=e^{-(\pi+o(1)) r^2}$ as $r\to\infty$.

So, the case $p\ge1/2$ is special only in the sense that then the expression for the bound $B_p(r)$ is simpler, since $\Phi^{-1}(1/2)=0$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .