# Lipschitz functions that saturate the Lipschitz inequality on the average (part 1)

Consider a 1-Lipschitz function $$f: \mathbb R^n \to \mathbb R$$ satisfying the inequality \begin{align*} |f(x) - f(y)| \le \|x-y\|_2, \;\forall x,y \in \mathbb R^n. \end{align*} For $$n \ge 2$$, can we find a 1-Lipschitz function that saturates the above inequality on the average?

To make the notion of "on the average" precise, let $$x$$ and $$y$$ be independent standard Gaussian vectors, i.e., $$x,y \sim N(0,I_n)$$. One can show that $$\mathbb E \big|\|x\|_2 - \|y\|_2\big| \asymp 1.$$ while $$\mathbb E\|x-y\|_2 \asymp \sqrt{n}.$$ Is there a 1-Lipschitz function $$f : \mathbb R^n \to \mathbb R$$ such that $$\mathbb E|f(x) - f(y)| \asymp \sqrt{n}?$$ Here $$\asymp$$ means inequalities go in both directions up to constants.

A related question is determining the order of $$\sup_{f \in \text{Lip}(1)}\mathbb E|f(x) - f(y)|$$ where $$\text{Lip}(1)$$ is the set of $$1$$-Lipschitz functions from $$\mathbb R^n$$ to $$\mathbb R$$.

• What do you mean by $\|x\|$ as opposed to $\|x\|_2$? – Anthony Quas Jan 24 at 0:47
• @AnthonyQuas, yes, the $\ell_2$ norm. – passerby51 Jan 24 at 2:22
• All the norms are the $\ell_2$ norm. I have edited the question. – passerby51 Jan 24 at 2:32

There is no $$1$$-Lipschitz function $$f\colon \mathbb R^n \to \mathbb R$$ such that $$\mathbb E|f(x) - f(y)| \asymp \sqrt{n}.$$
Indeed, for any such function, by the Gaussian concentration for Lipschitz functions (see e.g. Theorem 2.4, page 31), $$P(|f(x)-Ef(x)|\ge t)\le2e^{-t^2/2}$$ for all $$t\ge0$$. So,
$$E|f(x)-Ef(x)|=\int_0^\infty P(|f(x)-Ef(x)|\ge t)\,dt\le\sqrt{2\pi},$$ and hence also $$E|f(y)-Ef(x)|=E|f(y)-Ef(x)|\le\sqrt{2\pi}$$, so that $$E|f(x)-f(y)|\le E|f(x)-Ef(x)|+E|f(y)-Ef(x)|\le2\sqrt{2\pi}=o(\sqrt n).$$
It also follows that $$\sup_{f\in\text{Lip}(1)}E|f(x) - f(y)|\asymp1.$$