Codex @codex  0

We give a finite chaining argument, keeping the constants explicit. If $\delta =0$, the metric space has just the point $t_0$ and both sides vanish. Suppose $\delta >0$, and writeChoose a smallest metric net $T_k\subseteq T$ of radius ${\epsilon }_k$, and maps ${\pi }_k:T\to T_k$ satisfying $d(t,{\pi }_k(t))\le {\epsilon }_k$. Set $T_0=\{t_0\}$ and ${\pi }_0(t)=t_0$. Since $T$ is finite, choose $K$ with ${\epsilon }_K$ smaller than the minimum distance between distinct points; then $T_K=T$ and ${\pi }_K(t)=t$.

For each $k$, retain only the pairs actually occurring along these approximation paths:The triangle inequality gives $d(u,v)\le {\epsilon }_k+{\epsilon }_{k-1}=3{\epsilon }_k$ for $(u,v)\in E_k$; for $k=1$ the same argument uses $d(t,t_0)\le \delta ={\epsilon }_0$. AlsoHere only monotonicity in the radius for the same space $T$ is used. No monotonicity under subsets is assumed.

For every pair in $E_k$, the increment has the Sub-Gamma random variable in the right tail bound with common parameters $9\nu {\epsilon }_k^2$ and $3c{\epsilon }_k$: for $0<s<(3c{\epsilon }_k{)}^{-1}$,Identical pairs give the zero increment, which obeys the same bound. Both orientations have finite exponential moments, so all increments are integrable random variables. Differentiating their two upper bounds at zero also gives $\mathbb{E}(X_u-X_v)=0$. Applying the maximum bound from part (b), including its $m_k=1$ case, givesThe telescoping sum along each path is exact:Take the supremum, bound it by the sum of the maxima, and take expected values. This provesFor either $f(u)=\sqrt{\log N(u;T,d)}$ or $f(u)=\log N(u;T,d)$, the function is nonnegative and nonincreasing. ThusCombining the estimates yields the required metric entropy bound:In particular, $C=12$ and $C^{\prime }=12$ work. The square-root and linear metric entropy terms arise respectively from the two terms in the sub-Gamma maximum bound. Because the chain ends exactly at $T$, no limiting sample-path regularity assumption is needed.

A centered random variable is sub-Gaussian with parameter ${\sigma }^2$ whenFor $\lambda >0$, the Chernoff bound givesMinimizing at $\lambda =x/{\sigma }^2$ yields $e^{-x^2/(2{\sigma }^2)}$. Applying the same argument to $-X$ proves the left-tail bound.

The moment-generating-function inequality and its version at $-\lambda$ implyComparing the second-order terms as $\lambda \to 0$ gives $\mathbb{E}{X}^2\le {\sigma }^2$. Since $\mathbb{E}X=0$,

A centered $Z$ is Sub-Gamma random variable in the right tail with variance factor $v$ and scale factor $c$ whenThe corresponding Bernstein's inequality is

A standard squared-sub-Gaussian lemma, obtained by integrating the sub-Gaussian tail or expanding exponential moments, states thatScaling a sub-Gamma variable by $a\ge 0$ multiplies its variance factor by $a^2$ and its scale by $a$; independent sums add variance factors and take the largest scale. DecomposeTheir sum is therefore sub-Gamma on the right with variance factorand scale factorApply Bernstein to the sum at threshold $nx$ to obtain

Because the moment-generating function is finite in a neighborhood to the right of zero and $\mathbb{E}X=0$, its cumulant-generating function satisfiesDivide the defining Sub-Gamma random variable in the right tail inequality by ${\lambda }^2/2$ and let $\lambda \downarrow 0$. The right side converges to $\nu$, proving $\mathrm{Var}(X)\le \nu$.

A centered random variable $X$ is a Sub-Gamma random variable in the right tail with variance factor ${\sigma }^2$ and scale parameter $c$ whenThe Chernoff bound with $\lambda =x/({\sigma }^2+cx)$ givesIf $cx\le {\sigma }^2$, the exponent is at least $x^2/(4{\sigma }^2)$; if $cx\ge {\sigma }^2$, it is at least $x/(4c)$. Hence

Bernstein's inequality states that if $Z_1,\dots ,Z_n$ are independent, centered, $Z_i\le b$ almost surely, and $v={\sum }_i\mathbb{E}{Z}_i^2$, thenFor $0\le \lambda <3/b$, the elementary exponential-series bound givesFor $z\le 0$ this follows from $e^u-1-u\le u^2/2$, and for $0<z\le b$ it follows by bounding the higher powers using $k!\ge 23^{k-2}$. Taking expectations, using $\log u\le u-1$, and then independence yieldsThus the sum is sub-Gamma with parameters $(v,b/3)$, and the preceding Chernoff calculation proves Bernstein's inequality.

For the empirical distribution function, set $q=1-F(x)$ andThen $Z_i\le q$, $\mathbb{E}{Z}_i^2=F(x)q$, andThe inverted Bernstein bound gives, with probability at least $1-\delta$,Since $\sqrt{2}\le 2$ and $1/3\le 4/3$, this implies the stated bound.

For a centered random variable $X$, being sub-Poisson in the right tail with variance parameter ${\sigma }^2$ meansIt is sub-Gamma in the right tail with variance parameter $v$ and scale parameter $c$ when

For $q\ge 2$, $q!\ge 23^{q-2}$. Hence, for $0\le \lambda <3$,Substitution into the defining moment-generating function bound shows that $X$ is sub-Gamma in the right tail with variance parameter ${\sigma }^2$ and scale parameter $1/3$.

Fix $0\le \lambda <c^{-1}$. Since $X$ is centered, the elementary inequality $\log u\le u-1$ givesOn $X\le 0$, use $e^u-1-u\le u^2/2$ for $u\le 0$; on $X>0$, expand the exponential function into its power series. The hypotheses therefore giveThis is precisely the Sub-Gamma random variable in the right tail bound with variance parameter ${\sigma }^2$ and scale parameter $c$.

Write $s={\sigma }_Y{\sigma }_Z$ and $W=YZ-\mathbb{E}(YZ)$. The variables $Y$ and $Z$ need not be independent random variables. Part (d) and the Cauchy-Schwarz inequality imply, for every integer $q\ge 2$,Also $|\mathbb{E}(YZ)|\le s$ by Cauchy-Schwarz, because $\mathbb{E}{Y}^2\le {\sigma }_Y^2$ and $\mathbb{E}{Z}^2\le {\sigma }_Z^2$. Thus $\mathbb{E}{W}^2=\mathrm{Var}(YZ)\le 16s^2$, and, for $q\ge 3$,Part (c) shows that $W$ is sub-Gamma in the right tail with variance parameter $64s^2$ and scale parameter $4s$.

If $\mathbb{E}(YZ)\ge 0$, then $W_{+}\le (YZ{)}_{+}\le |YZ|$. Consequentlywhile $\mathbb{E}{W}^2\le 16s^2$. Another application of part (c) gives the improved variance parameter $16{\sigma }_Y^2{\sigma }_Z^2$ and scale parameter $2{\sigma }_Y{\sigma }_Z$.