Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 208 (Concentration Inequalities)

If $X$ is sub-Gaussian with variance parameter $\nu$, thenfor every $\lambda \in \mathbb{R}$. Restricting this inequality to $|\lambda |<1/\alpha$ proves that $X$ is sub-exponential with parameters $(\nu ,\alpha )$ for every $\alpha >0$.

Now let $X=Z^2-1$ for a standard normal distribution variable $Z$. Its moment-generating function isand is infinite for $\lambda \ge 1/2$. A sub-Gaussian moment-generating function must be finite for every real $\lambda$, so $X$ cannot be sub-Gaussian with any finite parameter. For $|\lambda |<1/4$, the stated inequality givesThus $X$ is sub-exponential with parameters $(4,4)$.

For every $0<\lambda <1/\alpha$, the Chernoff bound and the sub-exponential moment-generating bound giveIf $0<t\le \nu /\alpha$, choose $\lambda =t/\nu$; at the endpoint, take a limit from below. This yieldsIf $t>\nu /\alpha$, let $\lambda \uparrow 1/\alpha$. Since $\nu /(2{\alpha }^2)<t/(2\alpha )$,and hence $\mathbb{P}(X\ge t)\le e^{-t/(2\alpha )}$.

Because the variables are independent, the moment-generating function of the sum factors. Whenever $|\lambda |<1/{\max }_i{\alpha }_i$,Therefore ${\sum }_i{X}_i$ is sub-exponential with parameters

Because $\mathbb{E}X=0$, the moment-generating function series and the Bernstein moment condition imply, for $|\lambda |b<1$,For $|\lambda |<1/(2b)$, the denominator satisfies $1-|\lambda |b>1/2$, soThus $X$ is sub-exponential with parameters $(2\nu ,2b)$.

Write $X=\mu +\sigma Z$ with $Z$ standard normal and set $g(z)=f(\mu +\sigma z)$. The Gaussian Poincaré inequality and the chain rule giveHence $N(\mu ,{\sigma }^2)$ satisfies a $\sigma$-Poincaré inequality in the question's convention, where the constant is squared on the right-hand side.

Let $X_1,\dots ,X_N$ be independent with laws $p_1,\dots ,p_N$. We prove the claim by induction. Split the law of total variance at the last coordinate:The first term is at most $c_N^2\mathbb{E}|{\partial }_{N}f(X){|}^2$. Apply the induction hypothesis to $g(x_1,\dots ,x_{N-1})={\mathbb{E}}_{X_N}f(x_1,\dots ,x_{N-1},X_N)$. Differentiation under the expectation and Jensen inequality giveWriting $c={\max }_i{c}_i$ and combining the terms yieldsThis is the Tensorization of a Poincaré inequality.

Let $g:\mathbb{R}\to \mathbb{R}$ be continuously differentiable. Applying the Poincaré inequality for $p$ to $g\circ \varphi$ and using the chain rule givesThus the Pushforward of a Poincaré inequality by a Lipschitz function gives a $cL$-Poincaré inequality for $q$.

The sharp Poincaré inequality for the uniform distribution on an interval isTensorizing these $n$ identical one-dimensional inequalities givesfor the uniform distribution on $[0,1{]}^n$. Therefore one may take $c=1/\pi$; this value is sharp, as functions depending only on one coordinate attain the one-dimensional constant.

Let $X_1,\dots ,X_n$ be independent random variables, let $f=f(X_1,\dots ,X_n)$, and let each $f_i$ depend on every coordinate except $X_i$. The modified logarithmic Sobolev inequality states that, for every real $\lambda$ for which the expectations exist,

To prove it, first apply tensorization of entropy:Condition on all coordinates except $X_i$ and use the stated variational formula with the admissible constant $u=e^{\lambda f_i}$. The $i$th conditional entropy is at mostSumming and taking the remaining expectations proves the inequality.

Put $Z_i=f_i(X^{(i)})$ and ${\Delta }_i=Z-Z_i$. The weakly self-bounding function assumptions give ${\Delta }_i\ge 0$ and ${\sum }_i{\Delta }_i^2\le Z$. For $0\le \lambda <2$, the bound $\varphi (-x)\le x^2/2$ and the modified logarithmic Sobolev inequality implyLet $H(\lambda )=\log \mathbb{E}{e}^{\lambda Z}$. Dividing by $\mathbb{E}{e}^{\lambda Z}$ turns this intoand thereforeSince $H(\lambda )\sim \lambda \mathbb{E}Z$ as $\lambda \downarrow 0$, integration givesSubtracting $\lambda \mathbb{E}Z$ from both sides yieldsas required. This is a Herbst argument with a variance proxy controlled by $Z$ itself.

Fix every coordinate except $X_i$. As $X_i$ varies, the longest increasing subsequence length can change by at most one: deleting the changed term leaves a common subsequence of length at least the larger value minus one. The conditional range therefore has length at most one, so the Popoviciu inequality on variances givesThe coordinatewise conditional-variance form of the Efron–Stein inequality now yields

Replacing one input coordinate changes the longest increasing subsequence length by at most one, so $Z=L(X)$ has the bounded differences property with $c_i=1$. The two-sided McDiarmid inequality gives, for $t\ge 0$,

Let $Z_i$ be the longest increasing subsequence length after deleting coordinate $i$. Then $0\le Z-Z_i\le 1$. Choose one longest increasing subsequence $I$ of length $Z$. If deleting $i$ reduces the optimum, then $i$ must belong to $I$; consequently at most $Z$ coordinates can satisfy $Z-Z_i=1$. Henceso $Z$ is a weakly self-bounding function. The variance bound for a weakly self-bounding function gives

The coordinate-deletion functions from part c show that $Z$ is weakly self-bounding. Its negative centered moment-generating function therefore satisfies the lower-tail concentration for a weakly self-bounding function estimateApplying the Chernoff bound, for every $\lambda \ge 0$,The exponent is minimized at $\lambda =t/\mathbb{E}Z$, giving