Background: On Pg. $44$ of these notes, it is stated that:
In the case of a sphere $\Omega = S^{n-1}$, we have the following pair of properties.
- If $A\subset\Omega$ with $\mu(A) = \frac12$, then $\mu(A_\epsilon) \ge 1 - e^{-n\epsilon^2/2}$.
- If $f:\Omega\to\mathbb R$ is $1$-Lipschitz there is a number $M$ for which $$\mu(|f-M| > \epsilon) \le 2e^{-n\epsilon^2/2}$$
We have seen how the second can be deduced from the first. The reverse implication also holds (apart from the precise constants involved). To see why, apply the second property to the function given by $f(x) = d(x,A)$.
Theme of this post: I need help deducing $(1)$ from $(2)$.
Notation:
- $S^{n-1}$ is the Euclidean sphere of unit radius in $\mathbb R^n$.
- $\mu$ refers to the rotation invariant probability measure on the sphere $S^{n-1}$. The measure of the entire sphere is $1$, that of a hemisphere is $\frac12$, etc.
- $d(x,A) = \inf\{\|x-y\|: y\in A\}$ where $A \subset\mathbb R^n$ is compact and $x \in \mathbb R^n$.
- A function $f: S^{n-1}\to\mathbb R$ is $1$-Lipschitz, if for any $x,y\in S^{n-1}$, $$\|f(x) - f(y)\| \le \|x-y\|$$
- $A_\epsilon$ is the $\epsilon$-thickening (or neighborhood) of $A$, that is $A_\epsilon = A + \epsilon B^n_2$ where $B^n_2 = \{x: \|x\| \le 1\}$.
My thoughts: The author suggests to put $f(x) = d(x,A)$ in $(2)$. First we would have to check that this function is $1$-Lipschitz. Consider $x,y\in S^{n-1}$, i.e. $\|x\|= \|y\| = 1$ and $A$, a compact subset of $S^{n-1}$. Thanks to @OliverDiaz's comment, I now see that $$|d(x,A) - d(y,A)| \le \|x- y\|$$ Consider $a\in A$, then $d(x,A)\le \|x-a\| \le \|x-y\| + \|y-a\|$. So, $d(x,A) - \|x-y\|\le \|y-a\|$. Taking $\inf_{a\in A}$, we have $d(x,A) - d(y,A) \le \|x-y\|$. Interchanging $x$ and $y$, we get $d(y,A) - d(x,A) \le \|x-y\|$ and hence the required inequality.
Since $f = d(\cdot, A)$ is Lipschitz, there is some $M$ for which $$\mu(|d(\cdot, A)-M| > \epsilon) \le 2e^{-n\epsilon^2/2}$$ i.e. $$\mu(|d(\cdot, A)-M| \le \epsilon) \ge 1 - 2e^{-n\epsilon^2/2}$$ It is easy to check that $A_\epsilon = \{x: d(x,A) \le \epsilon\}$. Due to the similarity in expression of what I have arrived at, and what I need to prove - I think I'm pretty close, but don't know what to do next.
Thank you!
I am continuing this answer from the thoughts you have added.
First of all, what is the median $M$ of the function $d(\cdot,A)$? We need to find $M$ that satisfies $$ \mu(d(\cdot,A) \geq M) \geq \frac{1}{2}\text{ and }\mu(d(\cdot,A) \leq M) \geq \frac{1}{2}. $$ It is quite easy to see that $M=0$ satisfies this since $\mu(A)=\frac{1}{2}$.
As @OliverDiaz has mentioned in the comments, $d(\cdot,A)$ is $1$-Lipschitz. Now, observe that since $d(\cdot,A) \geq 0$, the part of bound $(2)$ that bounds $\mu(M-f>\epsilon)$ is useless (it measures $\{f<-\epsilon\}$, which is trivially $0$ for our choice of $f$).
So, using only the relevant part of bound $(2)$, namely the second equation on page 44 of the notes, we have $$\mu(d(\cdot,A) > \epsilon) \leq e^{-n\epsilon^2/2}$$ and thus, $$\mu(A_\epsilon) \geq 1 - e^{-n\epsilon^2/2}.$$