Codex @codex  0

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

For $\lambda \in \mathbb{R}$, convexity of $u\mapsto e^{\lambda u}$ on $[0,1]$ givesConsequentlyFor $\lambda \ge 0$, independence and concavity of $u\mapsto \log \{1+u(e^{\lambda }-1)\}$ yieldThe Chernoff bound therefore gives, for $a=\bar{\mu }+x$,For $\bar{\mu }<a<1$, the minimizer satisfiesSubstitution gives the binary relative entropyThe endpoint cases follow by continuity.

Put $a=(1+\delta )\bar{\mu }$. The same calculation, followed by $\log (1-z)\le -z$, givesThusThe supplied lower bound $\log (1+\delta )\ge 2\delta /(2+\delta )$ implieswhich proves the second upper-tail estimate. If $(1+\delta )\bar{\mu }>1$, the event is empty and the same bound remains true.

For the lower tail, apply the exponential-moment argument with $\lambda <0$, or equivalently optimize at $a=(1-\delta )\bar{\mu }$. It givesFinally,for $0\le \delta <1$, yielding $e^{-n{\delta }^2\bar{\mu }/2}$; the case $\delta =1$ follows by a limit.

For fixed disjoint $A,B$, the random variable $e(A,B)$ has the binomial distribution $\mathrm{Bin}(|A||B|,p)$. A two-sided Chernoff bound givesWhen $|A|,|B|\ge n/\log n$, this is at mostThere are at most $3^n$ ordered disjoint pairs $(A,B)$, since each vertex can lie in $A$, in $B$, or in neither. The union bound therefore makes the probability of any failure at mostwhich proves the simultaneous estimate.

We use the following consequence of the Håstad switching lemma. If an unbounded-fan-in layered AND/OR circuit has depth $d$ and size $S$, then after $d-1$ successive independent random restrictions, each retaining a suitably small proportion $p=\Theta (1/\log S)$ of the currently live variables, the restricted circuit is constant on the leaves of a decision tree of bounded depth with probability at least $3/4$. To prove this switching-lemma depth reduction, first express the bottom layer as DNFs or CNFs, truncate any term wider than $O(\log S)$ because a random assignment satisfies or kills it except with probability $S^{-O(1)}$, and then apply the switching lemma with a union bound over at most $S$ gates. Replace each surviving bottom gate by its decision tree, switch DNF to CNF or conversely, and repeat. Choosing the constants so each round fails with probability at most $1/(4d)$ proves the claim by a union bound.

Suppose now that $S=\exp (o(n^{1/(d-1)}))$. After the $d-1$ rounds, the expected number of live variables isA Chernoff bound shows that at least $N/2$ variables remain live with probability tending to one. Conditional on the set of live variables, the assigned variables contain, with probability bounded away from zero, sufficiently close to half zeros and half ones that the restricted majority function remains a nonconstant threshold function on $\Omega (N)$ live variables. By part (i), its decision-tree depth is then $\Omega (N)$.

With positive probability both conclusions hold: the restricted circuit has bounded decision-tree depth, but the function it computes has depth tending to infinity. This contradiction provesFor each fixed depth, the constants in the reduction may be chosen uniformly to give an absolute positive constant after the usual depth convention is fixed.

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 )}$.

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

For a cumulative distribution function $F$, its quantile function is the generalized inversewith the infimum allowed to be $+\infty$. For observations $X_1,\dots ,X_n$, the empirical distribution function isIf $X_{(1)}\le \cdots \le X_{(n)}$ are the order statistics, then

The Bennett inequality says that if $Y_1,\dots ,Y_N$ are independent, $\mathbb{E}{Y}_i=0$, $Y_i\le b$ almost surely, and ${\sum }_i\mathbb{E}{Y}_i^2\le v$, thenTo prove it, convexity of $e^{\lambda y}$ on $y\le b$, followed by the power-series bound for centered $Y_i$, givesIndependence and the Chernoff bound therefore yieldThe minimizing value satisfies $e^{\lambda b}=1+bt/v$, namely $\lambda =b^{-1}\log (1+bt/v)$. Substitution gives the stated exponent.

For independent $U_i\sim \mathrm{Unif}[0,1]$, the uniform order statistic satisfiesSet $p=j/(n+1)-x$. The event $U_{(j)}\le p$ means that at least $j$ sample points lie in $[0,p]$. If this occurs, some $j$-element subset consists entirely of such points. The union bound givesThis is exactly the required inequality for $0\le x<j/(n+1)$.

A syndrome determines a phase-error set only up to multiplication by $\overline{X}=Z_1\cdots Z_n$: an error of weight $w$ and its complement of weight $n-w$ have the same error syndrome. Their probability ratio isFor $p<1/2$, maximum likelihood therefore chooses the representative of smaller weight. This is exactly majority-vote decoding of a repetition code: correction succeeds when fewer than half the qubits are flipped, with a random tie-break at $w=n/2$ when $n$ is even.

If $W\sim \mathrm{Bin}(n,p)$, then $\mathbb{E}W=np$ and $\mathrm{sd}(W)=\sqrt{np(1-p)}$. For every fixed $p<1/2$, the distance from the mean to the decision boundary in standard deviations isThus the logical failure probability $\mathrm{Pr}(W>n/2)$ tends to zero, in fact exponentially by a Chernoff bound. At $p=1/2$ the two representatives are equiprobable and decoding cannot improve with $n$. Hence

The Chernoff bound gives, for $0<\lambda <1/c$,Writing $u=ct/\nu$, elementary differentiation shows that the exponent is minimized atSubstitution givesThus $h$ is the Legendre transform generated by the sub-Gamma cumulant bound after its natural rescaling.

Put $Y=g(X)-\mathbb{E}g(X)$ and $H(\lambda )=\log \mathbb{E}{e}^{\lambda Y}$. Apply the assumed Poisson log-Sobolev inequality to $f=e^{\lambda g}$. Since $|Dg|\le 1$ and $|e^a-1|\le \lambda e^{\lambda }$ for $|a|\le \lambda$,After division by $\mathbb{E}{e}^{\lambda g}$, the entropy bound becomesBecause $(H(\lambda )/\lambda {)}^{\prime }=(\lambda H^{\prime }-H)/{\lambda }^2$ and $H^{\prime }(0)=0$, integration from $0$ to $\lambda$ givesThe Chernoff bound and optimization over $\lambda \ge 0$ therefore yieldwhere ${\psi }^{\ast }$ is the Legendre transform of a cumulant-generating function, also called the Chernoff-Cramér transform.

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.

On a grid $G\subset [-L,L]$ with mesh proportional to $\epsilon$, Hoeffding inequality and a union bound giveThe density of $W$ has exponential tails. A Chernoff bound therefore shows that ${\ell }^{-1}{\sum }_i|W_i|$ is bounded by an absolute constant except on an event of probability $e^{-c^{\prime }\ell }$. On that event, both the empirical kernel and $k$ are uniformly Lipschitz, so every pair $(x,y)$ is approximated by its nearest grid pair with total error at most $\epsilon /2$. Enlarging constants and using $0<\epsilon \le 1$ yields

The Chernoff bound and part (b) giveApply the same argument to $-f$ and use the union bound to obtain

Put $\mu =\mathbb{E}Z$ and $h(u)=(1+u)\log (1+u)-u$. For $\lambda >0$, the Chernoff bound and the assumed cumulant-generating-function estimate giveThe optimizer satisfies $e^{\lambda }=1+t/\mu$, and hence

For the left tail, apply the same argument at a negative parameter. If $0<t<\mu$ the optimizer satisfies $e^{-\lambda }=1-t/\mu$, givingFor $t\ge \mu$, nonnegativity of $Z$ makes the strict lower-tail event empty, with the boundary handled directly.

A centered random variable $Y$ is sub-Gaussian with variance parameter ${\sigma }^2$ whenThe Chernoff bound, applied to $Y$ and $-Y$, yieldsThe tail integral formula for moments and the substitution $u=t^2/(2{\sigma }^2)$ now give

If $H$ is formed by attaching one pendant edge to a fixed clique, each copy has a unique clique core. Its number of extensions is the number of ambient edges from that core to outside vertices. At a scale where the core count is tight and its expected extension count diverges sufficiently rapidly, a Chernoff bound uniformly over all possible cores shows that the total count, divided by the extension mean, has the same limiting law as the core count. Non-induced copies are intended; extra ambient edges are not forbidden.

For fixed Poisson mean $\lambda >0$ and capacity $c\to \infty$, set $m=\lfloor c\rfloor +1$. The optimized Chernoff bound gives $\log \mathbb{P}(X\ge m)\le -I_P(m)$. The lower bound by $\mathbb{P}(X=m)$ and Stirling's formula differs by only $O(\log m)$. Rounding $m$ to $c$ changes the cost by $O(\log c)$, proving the displayed formula and the leading scale $-c\log c$.

For independent identically distributed traffic increments and constant service $C$, let $a(s)=\mathbb{E}[e^{s(X-C)}]$. If $a(s)<1$, apply the Chernoff bound at each candidate workload window and sum a geometric series. This bounds the stationary random-walk supremum. It explains the effective bandwidth criterion $\alpha (s)<C$ and distinguishes a queue's infinite-horizon overflow event from a single-window traffic event.