# Gaussian concentration of measure, equivalent definitions

Mathematics Asked by Monty on January 12, 2021

I need some help going between two equivalent definitions.

First some notation :

$$bullet$$ For $$Asubseteq mathcal{X}$$ and $$r>0$$ define what is called the r-blowup of $$A$$ as $$begin{equation} A_r = { x in mathcal{X} : d(x,A)

$$bullet$$ We have a metric probability space $$(mathcal{X},d,mu)$$, i.e $$(mathcal{X},d)$$ is a Polish space, and $$mu$$ a probability measure on its Borel sets.

Now I am going to give two definitions for $$mu$$ satisfying a Gaussian concentration of measure. Can anyone show how to go from one definition to the other (of course with a change of constants).

$$textbf{Def.1}$$
$$mu$$ is said to have Guassian concentration on $$(mathcal{X},d)$$ if there exists $$K,kappa >0$$ such that

$$begin{equation}label{Gauss concentration} textit{whenever}~~mu(A)geq frac{1}{2} ~~ textit{it implies} ~~ mu(A_r)geq 1-K e^{-kappa r^2} end{equation}$$

$$textbf{Def.2}$$
We say $$mu$$ has Gaussian concentration of measure if there exists $$K,kappa >0$$ and some $$r_0>0$$, such that
$$begin{equation} textit{whenever}~~mu(A)geq frac{1}{2} ~~ textit{it implies} ~~ mu(A_r) geq 1-Ke^{-kappa(r-r_0)^2} ~~ forall rgeq r_0 end{equation}$$

[1, Page 103] claims that we can go between the two with a change of constants, how? Note going from $$textbf{Def.1}$$ to
$$textbf{Def.2}$$ is fine just replace $$r$$ by $$r-r_0$$.

[1] Raginsky, Sason. Concentration of Measure Inequalities in Information Theory, Communications and Coding. 2014

As you mentioned, it is easy to go from Definition $$1$$ to Definition $$2$$.

Let $$K$$, $$kappa$$, and $$r_0$$ be the constants in Definition 2. We will now find constants $$K'$$ and $$kappa'$$ for Definition $$1$$. Set $$K' := max(K,1)e^{4 kappa' r_0^2}$$ and $$kappa':= kappa/4$$ to be the constants in Definition 1. We will show that these constants suffice by considering two cases:

Case 1: $$r in [0,2r_0]$$. We have that $$K' exp(- kappa'r^2) = max(K,1)exp(kappa'(4r^2_0 - r^2)) geq 1,$$ and thus the desired inequality $$mu(A_r)geq 1 - K' exp(- r^2)$$ holds trivially.

Case 2: $$r geq 2r_0$$. We have the following series of inequalities: begin{aligned}1 - mu(A_r) &leq K e^{- kappa (r - r_0)^2} \ &leq K e^{- kappa r^2/4}\ &leq K'e^{- kappa r^2/4} = K'e^{- kappa' r^2}, end{aligned} where we used that $$K leq K'$$ and $$|r - r_0| geq r/2$$ for $$r geq 2r_0$$.

Correct answer by Ankitp on January 12, 2021

## Related Questions

### For each of the following sets A, B prove or disprove whether A ⊆ B and B ⊆ A

1  Asked on February 7, 2021

### Proofing Metropolis Hastings

0  Asked on February 7, 2021 by nestroy

### How to solve this limit $lim_{nto infty}(frac{2^n}{n^k})$?

4  Asked on February 7, 2021

### Is a ring homomorphism surjective if the restriction to the group of units is surjective?

1  Asked on February 7, 2021 by barry-allen

### $Var(X_1 X_2)=Var(X_1) Var(X_2)$

2  Asked on February 7, 2021

### Principal component analysis for ‘signal extraction’

0  Asked on February 7, 2021 by mat-p

### Show that ${a log n }$ is not equidistributed for any $a$

1  Asked on February 7, 2021 by dark_knight

### Monotone Convergence Property $iff$ Order Completeness in an arbitrary ordered field.

1  Asked on February 6, 2021

### The product of the ages of someone’s children

2  Asked on February 6, 2021 by rathal

### A committee of m members is to be chosen from a population of n students. What is your probability of being chosen?

1  Asked on February 6, 2021 by joseph-bungabong

### Prove by induction floor and ceiling

1  Asked on February 6, 2021 by user836026

### $a,b,c,d$ are complex numbers corresponding to points $A,B,C,D$ lying on a circle with origin as center,and chord $AB⟂CD$. Find $ab+cd$

3  Asked on February 6, 2021 by maven

### Let, $N,K,N’,K’$ be groups and $Ncong N’,Kcong K’$. Does $Nrtimes Kcong N’rtimes K’$?

0  Asked on February 6, 2021 by deltaepsilon

### Integrate $2x(2x-3)^frac{1}{2} dx$.

5  Asked on February 5, 2021 by pretending-to-be-a-calculator

### Dimensionality theorem irreps finite dimensional algebra

1  Asked on February 5, 2021 by gert

### On approximating the distribution of the distance between two random points on an $n$-sphere

1  Asked on February 5, 2021 by let101

### Rule of inference. Is the argument valid?

2  Asked on February 5, 2021 by blue

### Relation between norm and variance of a random vector

1  Asked on February 4, 2021

### limit superior of union and intersection of sets.

1  Asked on February 4, 2021