Concentration — Examples

Each $X_i$ is a real random variable by [F1], and their given independence is understood by [F2]. Their two-point laws make them integrable with mean $(1\mathrm{/}2)\cdot 1+(1\mathrm{/}2)\cdot (-1)=0$ by [F3], and they lie in $[-1,1]$ almost surely. Thus the Hoeffding width sum is ${\sum }_i(1-(-1){)}^2=4n$.

Apply [F4] with those endpoints. The exponent is $-2t^2\mathrm{/}(4n)=-t^2\mathrm{/}(2n)$, yielding the stated bound.

Write $\varphi (x)=e^{-x^2\mathrm{/}2}\mathrm{/}\sqrt{2\pi }$. By [F7] and composition, $u\mapsto e^{-u}$ is continuous and integrable on compact intervals by [F8]. The map $x\mapsto x^2\mathrm{/}2$ is differentiable with derivative $x$ by [F7]; the identity $x$ is continuous because $\mathrm{\mid }x-y\mathrm{\mid }<\eta$ whenever $\mathrm{\mid }x-y\mathrm{\mid }<\delta$ with $\delta =\eta$, so it is integrable on $[0,R]$ by [F8]. Thus [F4] applies. By [F7], $(-e^{-u}{)}^{\mathrm{\prime }}=e^{-u}$, so [F8] evaluates the resulting integral: ${\int }_0^{R}x\varphi (x)dx=(1-e^{-R^2\mathrm{/}2})\mathrm{/}\sqrt{2\pi }\le 1\mathrm{/}\sqrt{2\pi }$. The integrand $x\varphi (x)$ is continuous and bounded on every compact interval by [F7] and [F8], so [F13] identifies these Riemann integrals with Lebesgue integrals. Reflection $x=-y$ in [F4], followed by [F13], gives ${\int }_{-R}^0(-x)\varphi (x)dx={\int }_0^{R}x\varphi (x)dx$ since $\varphi$ is even. Letting integer $R$ increase to infinity, [F2], [F3] for nonnegative functions, and [F5] give $\mathbb{E}\mathrm{\mid }G\mathrm{\mid }=2{\int }_0^{\mathrm{\infty }}x\varphi (x)dx<\mathrm{\infty }$. Since $\varphi$ is even, the positive and negative parts of $x\varphi (x)$ have equal integrals, so [F3] for integrable functions gives $\mathbb{E}G=0$.

Put $a=\lambda \sigma$. The function $x\mapsto e^{ax}$ is continuous and Borel measurable by [F7] and [F9], so [F3] and completing the square, using [F6], give $\mathbb{E}{e}^{\lambda \sigma G}=\frac{1}{\sqrt{2\pi }}{\int }_{\mathbb{R}}{e}^{ax-x^2\mathrm{/}2}dx=e^{a^2\mathrm{/}2}\frac{1}{\sqrt{2\pi }}{\int }_{\mathbb{R}}{e}^{-(x-a{)}^2\mathrm{/}2}dx$.

For every positive integer $R$, [F4] with translation by $a$ gives ${\int }_{-R}^R{e}^{-(x-a{)}^2\mathrm{/}2}dx={\int }_{-R-a}^{R-a}{e}^{-y^2\mathrm{/}2}dy$. The two integrands are continuous and bounded on these compact intervals by [F7] and [F8]; [F13] therefore identifies both sides with their Lebesgue integrals. Both interval families increase to $\mathbb{R}$, so [F5] passes these equal integrals to the whole-line limit; [F2] identifies that limit as $\sqrt{2\pi }$. Step 1.2 then yields $\mathbb{E}{e}^{\lambda \sigma G}=e^{a^2\mathrm{/}2}=e^{{\lambda }^2{\sigma }^2\mathrm{/}2}$.

By [F12] and step 1.1, $\mathbb{E}{Z}_j=\sigma \mathbb{E}G=0$; step 2.1 gives its moment generating function. Thus each $Z_j$ is centered sub-Gaussian with proxy ${\sigma }^2$ by [F10]. Apply [F11] to the $m$ variables. They are all equal, but the bound requires no independence.

The choice $ϵ=1\mathrm{/}2$ is in $(0,1)$ and gives the finite-net factor $(1+2\mathrm{/}ϵ{)}^d=5^d$.

By [F1], $Z$ satisfies the centered projection condition required by [F2]. Apply [F2] with the value from step 1.1. Since $(1-1\mathrm{/}2{)}^2\mathrm{/}(2{\sigma }^2)=1\mathrm{/}(8{\sigma }^2)$, the stated positive-proxy bound follows; the zero-proxy clause of [F2] gives the boundary case.

Let $S={\sum }_{k=1}^{\mathrm{\infty }}{k}^{-4}$. Its partial sums are increasing, and for $k\ge 2$, $k^{-4}\le k^{-2}\le 1\mathrm{/}[k(k-1)]=1\mathrm{/}(k-1)-1\mathrm{/}k$; hence $1\le S\le 2$ and $S$ is finite by [F4]. Set $c=(2S{)}^{-1}>0$.

Enumerate $\mathrm{\Omega }=\{(k,s):k\ge 1,s\in \{-1,1\}\}$ by ${\omega }_{2k-1}=(k,1)$, ${\omega }_{2k}=(k,-1)$, and assign each atom weight $w_{2k-1}=w_{2k}=c{k}^{-4}$. Define $\mathbb{P}(A)={\sum }_{j\ge 1}{w}_j{\mathbf{1}}_A({\omega }_j)$ for $A\subseteq \mathrm{\Omega }$. The weights are nonnegative and sum to $2cS=1$, so all subseries converge by [F4]. For pairwise disjoint $A_r$, put $a_{rj}=w_j{\mathbf{1}}_{A_r}({\omega }_j)$ and $q_j={\sum }_r{a}_{rj}$; at most one term in each $q_j$ is nonzero. For every finite atom prefix $J$, only finitely many $A_r$ meet that prefix, so finite regrouping gives ${\sum }_{j=1}^J{q}_j={\sum }_r{\sum }_{j=1}^J{a}_{rj}\le {\sum }_r\mathbb{P}(A_r)$. Taking the supremum over $J$ yields $\mathbb{P}({\bigcup }_r{A}_r)\le {\sum }_r\mathbb{P}(A_r)$. Conversely, for each finite event prefix $R$ and each $\delta >0$, convergence of the finitely many subseries lets us choose one atom prefix $J$ for which ${\sum }_{r=1}^R\mathbb{P}(A_r)-\delta \le {\sum }_{r=1}^R{\sum }_{j=1}^J{a}_{rj}\le {\sum }_{j=1}^J{q}_j\le \mathbb{P}({\bigcup }_r{A}_r)$. Letting $\delta \downarrow 0$ and then taking the supremum over $R$ proves the reverse inequality. Thus [F1] makes $\mathbb{P}$ a probability measure.

Define $X(k,s)=sk$ on $(\mathrm{\Omega },\mathcal{P}(\mathrm{\Omega }),\mathbb{P})$. It is a real random variable by [F2], since every preimage is a subset of the full-power-set sample space.

By [F5] applied to finite atom prefixes, $\mathbb{E}\mathrm{\mid }X\mathrm{\mid }=2c{\sum }_{k\ge 1}{k}^{-3}$ and $\mathbb{E}{X}^2=2c{\sum }_{k\ge 1}{k}^{-2}$. For $k\ge 2$, $k^{-3}\le k^{-2}\le 1\mathrm{/}[k(k-1)]$, whose partial sums telescope to at most $1$; hence both moments are finite, so $X$ is integrable and square-integrable. The two atoms at each $k$ have equal mass and opposite values; since $\mathbb{E}\mathrm{\mid }X\mathrm{\mid }<\mathrm{\infty }$, their absolutely convergent contributions cancel and $\mathbb{E}X=0$. By [F3], $X$ is centered with finite variance $\mathrm{Var}(X)=\mathbb{E}{X}^2$.

For every integer $n\ge 1$, the atoms $(n,1)$ and $(n,-1)$ give $\mathbb{P}(\mathrm{\mid }X\mathrm{\mid }\ge n)\ge 2c{n}^{-4}>0$.

Suppose for contradiction that $X$ has a finite sub-Gaussian proxy ${\sigma }^2$. If ${\sigma }^2=0$, [F6] contradicts the positive tail in step 2.1.

If ${\sigma }^2>0$, [F6] gives $2c{n}^{-4}\le \mathbb{P}(\mathrm{\mid }X\mathrm{\mid }\ge n)\le 2e^{-n^2\mathrm{/}(2{\sigma }^2)}$. By [F8], $n^4{e}^{-n^2\mathrm{/}(2{\sigma }^2)}=(n^2{)}^2\mathrm{/}{e}^{n^2\mathrm{/}(2{\sigma }^2)}$, which tends to $0$ by [F7] with $x=n^2$, $m=2$, and $a=1\mathrm{/}(2{\sigma }^2)$. It is eventually smaller than $c$, so the upper tail is eventually smaller than $2c{n}^{-4}$, contradicting step 2.1. Thus this centered finite-variance variable is not sub-Gaussian for any finite proxy.