Concentration of measure inequality direct proof: if $\alpha(t) < \epsilon,$ then for any $A$ with $\mu(A) \ge \epsilon, \mu(A_t) \ge 1/2.$

40 Views Asked by At

For a probability metric space, define $\alpha(r) = \sup\{ 1- \mu(A_r) : \mu(A) \ge 1/2\}.$ I want to show that if $\alpha(t) < \epsilon$ for some $t, \epsilon > 0,$ then for all $A$ such that $\mu(A) \ge \epsilon,$ we have $\mu(A_{t+r}) \ge 1 - \alpha(r).$

Just to get a better sense of the problem, I assumed $\mu$ is continuous. If the inequality is true, it better be true for $r=0,$ and conversely I easily proved it by assuming the case $r = 0.$ In this case, we want to show $\mu(A_t) \ge 1/2.$

Pick any $B$ with $\mu(B) = 1/2,$ then $\mu(B_t), \mu((B^c)_t) > 1-\epsilon,$ so both $B_t, (B^c)_t$ overlap $A.$ Going backwards, I've been able to get $A_t$ to overlap many sets with measure $1/2,$ but never show the expansion has measure $\ge 1/2$ because you can't undo an overlap.

Finally I thought about a proof by contradiction: if $\mu(A_t) < 1/2,$ set $B = (A_t)^c,$ then $B_t, A$ overlap since their measures sum to $>1.$ Pick $x \in B_t \cap A$ and $y \in B$ with $d(y,x) \le t,$ then $y \in B \cap A_{t},$ contradicting disjointness.

Is there a direct proof that $\mu(A_t) \ge 1/2$? I was hoping to construct a useful $B$ by starting with $A,$ using unions, intersections, complements, and perhaps having some casework to say either this or that set works.

Note: $A_t = \{x | \exists y \in A : d(x,y) \le t\}.$