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



Lipschitz functions that saturate the Lipschitz inequality on the average (part 1)
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](https://www.stat.berkeley.edu/~mjwain/stat210b/Chap2_TailBounds_Jan22_2015.pdf)), 
$$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.$$


