[proofplan] We first prove the exponential moment estimate for bounded centered Lipschitz functions. The tilted probability measure converts the derivative of the logarithmic moment generating function into a difference of expectations, which is bounded by $W_1$ and then by the $T_1(C)$ inequality. This gives a differential inequality for the logarithmic moment generating function, hence a sub-Gaussian bound. Chernoff's bound gives the tail estimate for bounded functions, and truncation removes the boundedness assumption. [/proofplan]

[step:Derive the moment bound for bounded centered Lipschitz functions]Let $\mathcal{B}(E)$ denote the Borel $\sigma$-algebra generated by the metric topology on $E$. By the meaning of the hypothesis $T_1(C)$, $\mu$ is a probability measure on $(E,\mathcal{B}(E))$ with finite first moment and satisfies \begin{align*} W_1(\nu,\mu) \leq \sqrt{2C\,\operatorname{Ent}(\nu\mid\mu)} \end{align*} for every probability measure $\nu$ on $(E,\mathcal{B}(E))$ such that $\nu\ll\mu$ and $\operatorname{Ent}(\nu\mid\mu)<\infty$. Here $\operatorname{Ent}(\nu\mid\mu)$ denotes the relative entropy \begin{align*} \operatorname{Ent}(\nu\mid\mu):=\int_E \log\left(\frac{d\nu}{d\mu}(x)\right)\,d\nu(x), \end{align*} $\Pi(\nu,\mu)$ denotes the set of probability measures on $(E\times E,\mathcal{B}(E)\otimes\mathcal{B}(E))$ whose first marginal is $\nu$ and whose second marginal is $\mu$, and $W_1(\nu,\mu)$ denotes the first Wasserstein distance \begin{align*} W_1(\nu,\mu):=\inf_{\pi\in\Pi(\nu,\mu)}\int_{E\times E} d(x,y)\,d\pi(x,y). \end{align*} Let $G:E \to \mathbb{R}$ be a bounded Borel measurable $1$-Lipschitz function satisfying \begin{align*} \int_E G(x)\,d\mu(x) = 0. \end{align*} For $\lambda \geq 0$, define the logarithmic moment generating function $\Lambda:[0,\infty) \to \mathbb{R}$ by \begin{align*} \Lambda(\lambda) := \log\left(\int_E e^{\lambda G(x)}\,d\mu(x)\right). \end{align*} Since $G$ is bounded, $\Lambda$ is continuously differentiable and \begin{align*} \Lambda'(\lambda) = \frac{\int_E G(x)e^{\lambda G(x)}\,d\mu(x)}{\int_E e^{\lambda G(x)}\,d\mu(x)}. \end{align*} Let $\nu$ be a probability measure on $(E,\mathcal{B}(E))$ such that $\nu \ll \mu$, $\operatorname{Ent}(\nu\mid\mu)<\infty$, and $\nu$ has finite first moment. Because $G$ is bounded, the integrals $\int_E G(x)\,d\nu(x)$ and $\int_E G(y)\,d\mu(y)$ are finite. Because $\nu$ and $\mu$ have finite first moments, $W_1(\nu,\mu)$ is finite and the coupling costs below are meaningful. Since $G$ is centered and $1$-Lipschitz, every coupling $\pi \in \Pi(\nu,\mu)$ satisfies \begin{align*} \int_E G(x)\,d\nu(x) - \int_E G(y)\,d\mu(y) = \int_{E \times E} \bigl(G(x)-G(y)\bigr)\,d\pi(x,y) \leq \int_{E \times E} d(x,y)\,d\pi(x,y). \end{align*} Taking the infimum over $\pi \in \Pi(\nu,\mu)$ gives \begin{align*} \int_E G(x)\,d\nu(x) \leq W_1(\nu,\mu). \end{align*} The $T_1(C)$ hypothesis applies to such $\nu$, so \begin{align*} \int_E G(x)\,d\nu(x) \leq \sqrt{2C\,\operatorname{Ent}(\nu\mid\mu)}. \end{align*} We now prove the entropy variational step needed for the logarithmic moment bound. For $\lambda \geq 0$, define the tilted probability measure $\nu_\lambda$ on $(E,\mathcal{B}(E))$ by \begin{align*} \frac{d\nu_\lambda}{d\mu}(x) := \frac{e^{\lambda G(x)}}{\int_E e^{\lambda G(y)}\,d\mu(y)}. \end{align*} Since $G$ is bounded, $\nu_\lambda \ll \mu$, the density is bounded above and below by positive constants, and $\operatorname{Ent}(\nu_\lambda\mid\mu)<\infty$. To verify the finite-first-moment condition, fix a point $x_0\in E$ and let $M_\lambda:=\sup_{x\in E} d\nu_\lambda/d\mu(x)<\infty$. The finite-first-moment assumption on $\mu$ gives \begin{align*} \int_E d(x,x_0)\,d\nu_\lambda(x) \leq M_\lambda\int_E d(x,x_0)\,d\mu(x) < \infty. \end{align*} Thus $\nu_\lambda$ is admissible for the $T_1(C)$ hypothesis. Its entropy is \begin{align*} \operatorname{Ent}(\nu_\lambda\mid\mu) = \int_E \log\left(\frac{d\nu_\lambda}{d\mu}(x)\right)\,d\nu_\lambda(x) = \lambda\int_E G(x)\,d\nu_\lambda(x)-\Lambda(\lambda). \end{align*} Hence \begin{align*} \Lambda(\lambda)=\lambda\int_E G(x)\,d\nu_\lambda(x)-\operatorname{Ent}(\nu_\lambda\mid\mu). \end{align*} Applying the preceding transport-entropy estimate to $\nu_\lambda$ gives \begin{align*} \Lambda(\lambda) \leq \lambda\sqrt{2C\,\operatorname{Ent}(\nu_\lambda\mid\mu)}-\operatorname{Ent}(\nu_\lambda\mid\mu). \end{align*} For the scalar $r_\lambda:=\operatorname{Ent}(\nu_\lambda\mid\mu)\geq0$, completing the square gives \begin{align*} \lambda\sqrt{2Cr_\lambda}-r_\lambda = \frac{C\lambda^2}{2}-\left(\sqrt{r_\lambda}-\lambda\sqrt{\frac{C}{2}}\right)^2 \leq \frac{C\lambda^2}{2}. \end{align*} Therefore \begin{align*} \Lambda(\lambda) \leq \frac{C\lambda^2}{2}. \end{align*} Thus, for every $\lambda \geq 0$, \begin{align*} \int_E e^{\lambda G(x)}\,d\mu(x) \leq \exp\left(\frac{C\lambda^2}{2}\right). \end{align*}[/step]

[guided]The goal of this step is to prove a Gaussian-type bound for the exponential moment of a bounded centered Lipschitz function. Let $G:E \to \mathbb{R}$ be bounded, Borel measurable, $1$-Lipschitz, and centered: \begin{align*} \int_E G(x)\,d\mu(x) = 0. \end{align*} For $\lambda \geq 0$, define \begin{align*} \Lambda(\lambda) := \log\left(\int_E e^{\lambda G(x)}\,d\mu(x)\right). \end{align*} Because $G$ is bounded, differentiation under the integral sign is justified, and \begin{align*} \Lambda'(\lambda) = \frac{\int_E G(x)e^{\lambda G(x)}\,d\mu(x)}{\int_E e^{\lambda G(x)}\,d\mu(x)}. \end{align*} We next turn the transport-entropy assumption into an exponential moment bound. Let $\nu$ be a probability measure on $(E,\mathcal{B}(E))$ such that $\nu \ll \mu$, $\operatorname{Ent}(\nu\mid\mu)<\infty$, and $\nu$ has finite first moment. Since $G$ is bounded, the integrals against $\nu$ and $\mu$ are finite. Since both measures have finite first moment, the Wasserstein distance $W_1(\nu,\mu)$ is finite. Because $G$ is centered, \begin{align*} \int_E G(x)\,d\nu(x)=\int_E G(x)\,d\nu(x)-\int_E G(y)\,d\mu(y). \end{align*} Let $\pi \in \Pi(\nu,\mu)$ be any coupling. The $1$-Lipschitz property gives $G(x)-G(y)\leq d(x,y)$ for all $x,y\in E$, so \begin{align*} \int_E G(x)\,d\nu(x)-\int_E G(y)\,d\mu(y) = \int_{E\times E}\bigl(G(x)-G(y)\bigr)\,d\pi(x,y) \leq \int_{E\times E} d(x,y)\,d\pi(x,y). \end{align*} Taking the infimum over all couplings yields \begin{align*} \int_E G(x)\,d\nu(x) \leq W_1(\nu,\mu). \end{align*} Because $\nu$ is one of the measures to which the $T_1(C)$ hypothesis applies, we obtain \begin{align*} \int_E G(x)\,d\nu(x) \leq \sqrt{2C\,\operatorname{Ent}(\nu\mid\mu)}. \end{align*} Now choose the particular measure that is adapted to the exponential moment. For $\lambda\geq0$, define the tilted probability measure $\nu_\lambda$ by \begin{align*} \frac{d\nu_\lambda}{d\mu}(x) := \frac{e^{\lambda G(x)}}{\int_E e^{\lambda G(y)}\,d\mu(y)}. \end{align*} The boundedness of $G$ makes this density bounded above and below by positive constants. Hence $\nu_\lambda\ll\mu$ and its entropy is finite. We also must verify the finite-first-moment hypothesis before applying $T_1(C)$. Fix $x_0\in E$ and set $M_\lambda:=\sup_{x\in E} d\nu_\lambda/d\mu(x)$. Since $M_\lambda<\infty$ and $\mu$ has finite first moment, \begin{align*} \int_E d(x,x_0)\,d\nu_\lambda(x) \leq M_\lambda\int_E d(x,x_0)\,d\mu(x) < \infty. \end{align*} Thus $\nu_\lambda$ is admissible for the $T_1(C)$ assumption. Computing the entropy from the density gives \begin{align*} \operatorname{Ent}(\nu_\lambda\mid\mu) = \int_E \log\left(\frac{d\nu_\lambda}{d\mu}(x)\right)\,d\nu_\lambda(x) = \lambda\int_E G(x)\,d\nu_\lambda(x)-\Lambda(\lambda). \end{align*} Rearranging this identity gives the entropy variational identity for this tilt: \begin{align*} \Lambda(\lambda) = \lambda\int_E G(x)\,d\nu_\lambda(x)-\operatorname{Ent}(\nu_\lambda\mid\mu). \end{align*} Applying the transport-entropy estimate to $\nu_\lambda$ therefore gives \begin{align*} \Lambda(\lambda) \leq \lambda\sqrt{2C\,\operatorname{Ent}(\nu_\lambda\mid\mu)}-\operatorname{Ent}(\nu_\lambda\mid\mu). \end{align*} Set \begin{align*} r_\lambda:=\operatorname{Ent}(\nu_\lambda\mid\mu). \end{align*} Since $r_\lambda\geq0$, completing the square in this scalar quantity gives \begin{align*} \lambda\sqrt{2Cr_\lambda}-r_\lambda = \frac{C\lambda^2}{2}-\left(\sqrt{r_\lambda}-\lambda\sqrt{\frac{C}{2}}\right)^2 \leq \frac{C\lambda^2}{2}. \end{align*} Thus \begin{align*} \Lambda(\lambda) \leq \frac{C\lambda^2}{2}. \end{align*} Equivalently, \begin{align*} \int_E e^{\lambda G(x)}\,d\mu(x) \leq \exp\left(\frac{C\lambda^2}{2}\right). \end{align*}[/guided]

[step:Apply Chernoff optimization to obtain the bounded tail bound] Let $G:E\to\mathbb{R}$ be bounded, Borel measurable, $1$-Lipschitz, and centered. For $t\geq0$ and $\lambda>0$, Markov's inequality applied to the nonnegative [random variable](/page/Random%20Variable) $e^{\lambda G}$ gives \begin{align*} \mu(\{x\in E:G(x)\geq t\}) = \mu(\{x\in E:e^{\lambda G(x)}\geq e^{\lambda t}\}) \leq e^{-\lambda t}\int_E e^{\lambda G(x)}\,d\mu(x). \end{align*} Using the moment bound from the previous step, \begin{align*} \mu(\{x\in E:G(x)\geq t\}) \leq \exp\left(-\lambda t+\frac{C\lambda^2}{2}\right). \end{align*} The quadratic function $\lambda \mapsto -\lambda t+C\lambda^2/2$ on $(0,\infty)$ is minimized at $\lambda=t/C$ when $t>0$. Substituting this value gives \begin{align*} \mu(\{x\in E:G(x)\geq t\}) \leq \exp\left(-\frac{t^2}{2C}\right). \end{align*} For $t=0$, the same bound is $\mu(\{G\geq0\})\leq1$, which is immediate. [/step]

[step:Remove the boundedness assumption by Lipschitz truncation] Let $F:E\to\mathbb{R}$ be Borel measurable, $1$-Lipschitz, and integrable. Define \begin{align*} m := \int_E F\,d\mu \end{align*} and define the centered function $G:E\to\mathbb{R}$ by \begin{align*} G(x):=F(x)-m. \end{align*} Then $G$ is $1$-Lipschitz and belongs to $L^1(E,\mathcal{B}(E),\mu)$, with \begin{align*} \int_E G\,d\mu=0. \end{align*} For each $a>0$, define the truncation map $\tau_a:\mathbb{R}\to[-a,a]$ by \begin{align*} \tau_a(r):=\max\{-a,\min\{r,a\}\}. \end{align*} The map $\tau_a$ is $1$-Lipschitz. Hence the map $G_a:E\to\mathbb{R}$ defined by $G_a(x):=\tau_a(G(x))$ is bounded, Borel measurable, and $1$-Lipschitz. Let \begin{align*} m_a:=\int_E G_a\,d\mu. \end{align*} Then $G_a-m_a$ is bounded, centered, and $1$-Lipschitz. Applying the bounded moment estimate to $G_a-m_a$ gives, for every $\lambda\geq0$, \begin{align*} \int_E e^{\lambda(G_a(x)-m_a)}\,d\mu(x) \leq \exp\left(\frac{C\lambda^2}{2}\right). \end{align*} Because $|G_a|\leq |G|$ and $G_a(x)\to G(x)$ for every $x\in E$, dominated convergence gives \begin{align*} m_a\to \int_E G\,d\mu=0. \end{align*} For fixed $\lambda\geq0$, Fatou's lemma applied to the nonnegative functions $e^{\lambda(G_a-m_a)}$ gives \begin{align*} \int_E e^{\lambda G(x)}\,d\mu(x) \leq \liminf_{a\to\infty}\int_E e^{\lambda(G_a(x)-m_a)}\,d\mu(x) \leq \exp\left(\frac{C\lambda^2}{2}\right). \end{align*} Thus the same moment bound holds for the original centered function $G$. [/step]

[step:Conclude the stated concentration inequality] For $t\geq0$ and $\lambda>0$, Markov's inequality and the moment bound for $G=F-m$ give \begin{align*} \mu(\{x\in E:F(x)-m\geq t\}) \leq \exp\left(-\lambda t+\frac{C\lambda^2}{2}\right). \end{align*} Optimizing at $\lambda=t/C$ for $t>0$ yields \begin{align*} \mu\left(\left\{x\in E:F(x)-\int_E F\,d\mu\geq t\right\}\right) \leq \exp\left(-\frac{t^2}{2C}\right). \end{align*} For $t=0$, the estimate reduces to the bound by $1$, so it also holds. This proves the claimed one-sided concentration inequality. [/step]