Editing Concentration of measure (section)

==The general setting==

Let <math>(X, d)</math> be a [[metric space]] with a [[Measure (mathematics)|measure]] <math>\mu</math> on the [[Borel set|Borel sets]] with <math>\mu(X) = 1</math>.
Let 
:<math>\alpha(\epsilon) = \sup \left\{\mu( X \setminus A_\epsilon) \, | A \mbox{ is a Borel set and} \, \mu(A) \geq 1/2 \right\},</math>
where 
:<math>A_\epsilon = \left\{ x \, | \, d(x, A) < \epsilon \right\} </math>
is the <math>\epsilon</math>-''extension'' (also called <math>\epsilon</math>-fattening in the context of [[Hausdorff_distance#Definition|the Hausdorff distance]]) of a set <math>A</math>.

The function <math>\alpha(\cdot)</math> is called the ''concentration rate'' of the space <math>X</math>. The following equivalent definition has many applications:
:<math>\alpha(\epsilon) = \sup \left\{ \mu( \{ F \geq \mathop{M} + \epsilon \}) \right\},</math>
where the supremum is over all 1-Lipschitz functions <math>F: X \to \mathbb{R}</math>, and 
the median (or Levy mean) <math> M = \mathop{\mathrm{Med}} F </math> is defined by the inequalities
:<math>\mu \{ F \geq M \} \geq 1/2, \, \mu \{ F \leq M \} \geq 1/2.</math>

Informally, the space <math>X</math> exhibits a concentration phenomenon if
<math>\alpha(\epsilon)</math> decays very fast as <math>\epsilon</math> grows. More formally,
a family of metric measure spaces <math>(X_n, d_n, \mu_n)</math> is called a ''Lévy family'' if
the corresponding concentration rates <math>\alpha_n</math> satisfy
:<math>\forall \epsilon > 0 \,\, \alpha_n(\epsilon) \to 0 {\rm \;as\; } n\to \infty,</math>
and a ''normal Lévy family'' if
:<math>\forall \epsilon > 0 \,\, \alpha_n(\epsilon) \leq C \exp(-c n \epsilon^2)</math>
for some constants <math>c,C>0</math>. For examples see below.