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.

| cite | improve this question | | | | |
$\endgroup$
  • $\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$ – Adrien Hardy Feb 7 '18 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$ – random_shape Feb 7 '18 at 16:48
5
$\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$.

| cite | improve this answer | | | | |
$\endgroup$

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.