[proofplan] The proof converts the median condition into a Gaussian lower bound for the sublevel set $A=\{x:f(x)\leq m\}$. The Lipschitz condition implies that the Euclidean enlargement of $A$ by radius $t/L$ is contained in the sublevel set $\{x:f(x)\leq m+t\}$. Borell's [Gaussian isoperimetric inequality](/theorems/6759) then gives a lower bound on this enlarged set, which becomes the desired upper-tail estimate by taking complements. The lower-tail estimate follows by applying the same argument to $-f$, and the exponential estimate follows from an elementary Gaussian tail bound. [/proofplan] [step:Handle the degenerate Lipschitz constant] Assume first that $L=0$. For all $x,y \in \mathbb{R}^n$, \begin{align*} |f(x)-f(y)| \leq 0|x-y|=0. \end{align*} Thus $f(x)=f(y)$ for all $x,y \in \mathbb{R}^n$, so there is a constant $c \in \mathbb{R}$ such that $f(x)=c$ for every $x \in \mathbb{R}^n$. Hence $f(G)=c$ almost surely. A real number $m$ is a median of $f(G)$ only when $m=c$, and therefore, for every $t \geq 0$, \begin{align*} \mathbb{P}(f(G)>m+t)=0 \end{align*} and \begin{align*} \mathbb{P}(f(G)<m-t)=0. \end{align*} It remains to prove the theorem when $L>0$. [/step] [step:Enlarge the median sublevel set inside a higher sublevel set] Assume $L>0$. Define the Borel set $A \subset \mathbb{R}^n$ by \begin{align*} A=\{x \in \mathbb{R}^n : f(x)\leq m\}. \end{align*} Since $f$ is Lipschitz, it is continuous, hence $A$ is closed and Borel. Because $G$ has law $\gamma_n$ and $m$ is a median of $f(G)$, \begin{align*} \gamma_n(A)=\mathbb{P}(G \in A)=\mathbb{P}(f(G)\leq m)\geq \frac{1}{2}. \end{align*} For $r \geq 0$, define the closed Euclidean $r$-enlargement of $A$ by \begin{align*} A_r=\{x \in \mathbb{R}^n : \operatorname{dist}(x,A)\leq r\}, \end{align*} where $\operatorname{dist}(x,A)=\inf\{|x-y|:y \in A\}$. We claim that, for every $t \geq 0$, \begin{align*} A_{t/L}\subset \{x \in \mathbb{R}^n:f(x)\leq m+t\}. \end{align*} Indeed, let $x \in A_{t/L}$. By the definition of distance to a set, for every $\varepsilon>0$ there exists $y_\varepsilon \in A$ such that \begin{align*} |x-y_\varepsilon|\leq \frac{t}{L}+\varepsilon. \end{align*} Since $y_\varepsilon \in A$, we have $f(y_\varepsilon)\leq m$. The $L$-Lipschitz property gives \begin{align*} f(x)\leq f(y_\varepsilon)+L|x-y_\varepsilon|\leq m+L\left(\frac{t}{L}+\varepsilon\right)=m+t+L\varepsilon. \end{align*} Letting $\varepsilon \downarrow 0$ yields $f(x)\leq m+t$, proving the inclusion. [guided] We want to compare the event $\{f(G)>m+t\}$ with a geometric statement about subsets of $\mathbb{R}^n$, because Gaussian isoperimetry controls enlargements of sets. The natural set to start with is the median sublevel set \begin{align*} A=\{x \in \mathbb{R}^n : f(x)\leq m\}. \end{align*} The function $f$ is $L$-Lipschitz, so it is continuous, and therefore $A$ is a closed Borel subset of $\mathbb{R}^n$. Since $G$ has law $\gamma_n$, membership of $G$ in $A$ is exactly the event $f(G)\leq m$: \begin{align*} \gamma_n(A)=\mathbb{P}(G \in A)=\mathbb{P}(f(G)\leq m)\geq \frac{1}{2}. \end{align*} For $r \geq 0$, define the closed $r$-neighbourhood of $A$ by \begin{align*} A_r=\{x \in \mathbb{R}^n : \operatorname{dist}(x,A)\leq r\}, \end{align*} where \begin{align*} \operatorname{dist}(x,A)=\inf\{|x-y|:y \in A\}. \end{align*} The key point is that moving a distance at most $t/L$ away from $A$ can increase the value of $f$ by at most $t$. Let $x \in A_{t/L}$. The infimum in the definition of $\operatorname{dist}(x,A)$ need not be attained if one does not use closedness, so we use an approximation argument: for every $\varepsilon>0$ there exists $y_\varepsilon \in A$ with \begin{align*} |x-y_\varepsilon|\leq \frac{t}{L}+\varepsilon. \end{align*} Because $y_\varepsilon \in A$, we know $f(y_\varepsilon)\leq m$. Applying the Lipschitz inequality to the pair $x,y_\varepsilon \in \mathbb{R}^n$ gives \begin{align*} f(x)\leq f(y_\varepsilon)+|f(x)-f(y_\varepsilon)|\leq f(y_\varepsilon)+L|x-y_\varepsilon|. \end{align*} Combining these two estimates, \begin{align*} f(x)\leq m+L\left(\frac{t}{L}+\varepsilon\right)=m+t+L\varepsilon. \end{align*} Since this holds for every $\varepsilon>0$, letting $\varepsilon \downarrow 0$ gives $f(x)\leq m+t$. Thus every point in $A_{t/L}$ belongs to the sublevel set $\{x:f(x)\leq m+t\}$: \begin{align*} A_{t/L}\subset \{x \in \mathbb{R}^n:f(x)\leq m+t\}. \end{align*} This is the bridge from Lipschitz regularity to Gaussian geometry. [/guided] [/step] [step:Apply Gaussian isoperimetry to bound the upper tail] We use [Borell's Gaussian isoperimetric inequality](https://doi.org/10.1007/BF02366073) as an external input: if $B \subset \mathbb{R}^n$ is Borel and $\gamma_n(B)\geq 1/2$, then for every $r \geq 0$, \begin{align*} \gamma_n(B_r)\geq \Phi(r). \end{align*} The hypotheses apply to $B=A$, since $A$ is Borel and $\gamma_n(A)\geq 1/2$. Therefore, for every $t \geq 0$, \begin{align*} \gamma_n(A_{t/L})\geq \Phi\left(\frac{t}{L}\right). \end{align*} [guided] [Borell's Gaussian isoperimetric inequality](https://doi.org/10.1007/BF02366073) is the only external geometric input in the proof. In the form needed here, it says that whenever $B \subset \mathbb{R}^n$ is Borel and has Gaussian measure at least one half, its closed Euclidean $r$-enlargement satisfies \begin{align*} \gamma_n(B_r)\geq \Phi(r) \end{align*} for every $r \geq 0$. We apply this theorem with $B=A$. The required hypotheses have already been verified: $A$ is Borel because it is the closed sublevel set of the [continuous function](/page/Continuous%20Function) $f$, and \begin{align*} \gamma_n(A)=\mathbb{P}(f(G)\leq m)\geq \frac{1}{2} \end{align*} because $m$ is a median of $f(G)$. Hence, for every $t \geq 0$, choosing the enlargement radius $r=t/L$ gives \begin{align*} \gamma_n(A_{t/L})\geq \Phi\left(\frac{t}{L}\right). \end{align*} This is exactly the point at which the median information is converted into a quantitative Gaussian lower bound for the enlarged sublevel set. [/guided] By the inclusion proved above, \begin{align*} \{x \in \mathbb{R}^n:f(x)>m+t\}\subset \mathbb{R}^n \setminus A_{t/L}. \end{align*} Using again that $G$ has law $\gamma_n$, \begin{align*} \mathbb{P}(f(G)>m+t)=\gamma_n(\{x \in \mathbb{R}^n:f(x)>m+t\})\leq 1-\gamma_n(A_{t/L})\leq 1-\Phi\left(\frac{t}{L}\right). \end{align*} [/step] [step:Apply the upper-tail argument to the reflected function] Define the reflected function $g: \mathbb{R}^n \to \mathbb{R}$ by \begin{align*} g(x)=-f(x). \end{align*} For all $x,y \in \mathbb{R}^n$, \begin{align*} |g(x)-g(y)|=|f(x)-f(y)|\leq L|x-y|, \end{align*} so $g$ is also $L$-Lipschitz. Since $m$ is a median of $f(G)$, \begin{align*} \mathbb{P}(g(G)\leq -m)=\mathbb{P}(f(G)\geq m)\geq \frac{1}{2} \end{align*} and \begin{align*} \mathbb{P}(g(G)\geq -m)=\mathbb{P}(f(G)\leq m)\geq \frac{1}{2}. \end{align*} Thus $-m$ is a median of $g(G)$. Applying the already proved upper-tail estimate to $g$ gives, for every $t \geq 0$, \begin{align*} \mathbb{P}(g(G)>-m+t)\leq 1-\Phi\left(\frac{t}{L}\right). \end{align*} The event $\{g(G)>-m+t\}$ is exactly $\{f(G)<m-t\}$, hence \begin{align*} \mathbb{P}(f(G)<m-t)\leq 1-\Phi\left(\frac{t}{L}\right). \end{align*} [/step] [step:Convert the Gaussian tail bound into the exponential estimate] Let $\mathcal{L}^1$ denote one-dimensional [Lebesgue measure](/page/Lebesgue%20Measure) on $\mathbb{R}$. Let $\varphi: \mathbb{R} \to (0,\infty)$ denote the standard Gaussian density \begin{align*} \varphi(u)=\frac{1}{\sqrt{2\pi}}e^{-u^2/2}. \end{align*} For $s \geq 0$, define the tail function $T: [0,\infty) \to [0,\infty)$ by \begin{align*} T(s)=1-\Phi(s)=\int_{(s,\infty)} \varphi(u)\,d\mathcal{L}^1(u). \end{align*} Define $H: [0,\infty) \to [0,\infty)$ by \begin{align*} H(s)=e^{s^2/2}T(s). \end{align*} For $s>0$, differentiating under the one-dimensional integral with moving lower endpoint gives \begin{align*} H'(s)=s e^{s^2/2}T(s)-e^{s^2/2}\varphi(s). \end{align*} Since $u \geq s$ on $(s,\infty)$, \begin{align*} sT(s)=\frac{1}{\sqrt{2\pi}}\int_{(s,\infty)}s e^{-u^2/2}\,d\mathcal{L}^1(u)\leq \frac{1}{\sqrt{2\pi}}\int_{(s,\infty)}u e^{-u^2/2}\,d\mathcal{L}^1(u)=\varphi(s). \end{align*} Therefore $H'(s)\leq 0$ for every $s>0$, so $H(s)\leq H(0)=1/2$. Hence, for every $s \geq 0$, \begin{align*} 1-\Phi(s)=T(s)\leq \frac{1}{2}e^{-s^2/2}\leq e^{-s^2/2}. \end{align*} Substituting $s=t/L$ in the two one-sided bounds gives, for every $t \geq 0$, \begin{align*} \mathbb{P}(f(G)>m+t)\leq e^{-t^2/(2L^2)} \end{align*} and \begin{align*} \mathbb{P}(f(G)<m-t)\leq e^{-t^2/(2L^2)}. \end{align*} This completes the proof. [/step]