# Proof function mapping from standard normals to standard normal is lipschitz-1

Let $X_1,...,X_n$ be i.i.d $\mathcal{N}(0,1)$ and let $f: \mathbb{R}^n \rightarrow \mathbb{R}$ be a $L$-Lipschitz function. I'm trying to prove that if $f(X_1,...,X_n) \sim \mathcal{N}(0,1)$ then $f$ is 1-Lipschitz.

(Tsirelson-Ibragimov-Sudakov 1976) Let $X_1,...,X_n$ be i.i.d $\mathcal{N}(0,1)$ and let $f: \mathbb{R}^n \rightarrow \mathbb{R}$ be a $L$-Lipschitz function with respect to the Euclidean norm. Then $$\mathbb{P}\left[f(X_1,...,X_n) - \mathbb{E}\left[f(X_1,...,X_n)\right] \geq t\right] \leq e^{\frac{-t^2}{2L^2}}$$ If $f(X_1,...,X_n) \sim \mathcal{N}(0,1)$ then the expectation of $f=0$ and by the markov inequality we have \begin{align} \mathbb{P}\left[f(X_1,...,X_n) \geq t\right] &=\\ \inf_{\lambda>0} \mathbb{P}\left[\exp(\lambda f(X_1,...,X_n)) \geq e^{\lambda t}\right] &\leq\\ \inf_{\lambda>0} e^{-\lambda t}\mathbb{E}\left[\exp(\lambda f(X_1,...,X_n))\right] &=\\ \inf_{\lambda>0} e^{\frac{\lambda^2}{2} - \lambda t} = e^{\frac{-t^2}{2}} \end{align} after making the optimal choice $\lambda = t$. We now can rewrite our Lipschitz bound as: $$\mathbb{P}\left[f(X_1,...,X_n) \geq t\right] \leq e^{\frac{-t^2}{2}} \leq e^{\frac{-t^2}{2L^2}}$$ Therefore \begin{align} ||f||_L \geq 1 \\ \end{align}

This is as far as I got. Is there a way to upper bound the $||f||_L$?

• if $f(X_1, \dots, X_n) \sim \mathcal{N}(0, 1)$ doesn't it mean that $f(\cdot)$ is linear with proper normalization? – pointguard0 Aug 15 '18 at 21:31
• nevertheless, you've proved that $\mathbb{P}[f(X_1, \dots, X_n) \ge t] \le e^{-\frac {t^2} 2}$ [not equal] yielding $L=1$, by definition. – pointguard0 Aug 15 '18 at 21:38
• I'm not sure what you mean, it's possible to have a larger Lipschitz constant that fulfills the constraint. Could you please explain? – Armen Aghajanyan Aug 15 '18 at 22:02
• what metric are you using for Lipschitz continuity on $\mathbf{R}^n$? – pointguard0 Aug 16 '18 at 13:40
• I'm using euclidean norm induced metric. $d(x,y)=||x-y||$ – Armen Aghajanyan Aug 16 '18 at 16:28