3
$\begingroup$

A metric probability space $(X, \mu, \rho)$, i.e., a complete separable metric space with a probability measure on its Borel sets, is said to satisfy (Gaussian) concentration of measure property if there exists a positive constant $c > 0$, such that for every Lipschitz function $f \colon X \to \mathbb{R}$, $$ \tag{1}\label{1} \mu\left\{x \in X : f(x) - \mu f \ge t\right\} \le e^{-t^2/(2 c \lVert f \rVert_{\text{Lip}}^2)}, \quad \forall \; t > 0, $$ where $$\lVert f \rVert_{\text{Lip}}^2 = \sup_{\substack{x,y \in X \\ x \neq y}} \frac{\lvert f(x)-f(y)\rvert}{\rho(x,y)}.$$

This can equivalently be viewed geometrically.

Usually $X$ is taken to be some product space $X_1 \times \dotsb \times X_n$ and $f$ is viewed as a function of independent random variables, or in other words, $\mu$ is taken to be a product measure $\mu_1 \otimes \dotsb \otimes \mu_n$. There has been quite a lot of work done in the case of non-product measures also, where dependence is usually modeled using Markov kernels.

It seems to me that concentration of measure is the norm rather than the exception. Now, of course, concentration doesn't hold in the trivial case where the random variables are the same. What are some nontrivial examples where concentration fails to happen?

Specifically, a case where the dependence of $t$ in the exponent of Equation \eqref{1} is $o(t^2)$, and a case where even $o(t)$ is too much to expect.

$\endgroup$

1 Answer 1

3
$\begingroup$

$Y_i\sim^\text{iid} \text{Exp}(1)$ random variables, $f(Y)=\min_i Y_i$ has Exponential distribution with parameter $n$ with $f$ 1-Lipschitz. Then $E[f(Y)]=1/n$ but $$P(f(Y)-E[f(Y)]>t)=\exp(-n(t+1/n))$$ so you get $t$ and not $t^2$ inside the exponent. So even with independent components, you do not have the Lipschitz concentration inequality for random variables that have exponential tails instead of subgaussian ones.

$\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.