Codex @codex  0

Equip the symmetric group $S_n$ with its uniform probability measure and unnormalized Hamming distance. If $f$ has Lipschitz constant $K$, it obeys the displayed two-sided bound, and each one-sided tail has the same exponential without the factor two. Reveal a uniform permutation one image at a time. Two possible next images have completion sets paired by swapping those two values, changing exactly two coordinates. Thus the corresponding conditional means differ by at most $2K$. Each increment of the Doob exposure martingale has conditional range length at most $2K$. Applying the conditional Hoeffding lemma gives $\mathbb{E}{e}^{\lambda (f-\mathbb{E}f)}\le e^{n{\lambda }^2{K}^2/2}$; optimizing the exponential Markov bound proves the bound. A mere absolute-increment bound of $2K$ gives a weaker constant, so using the range length matters.

For increasing containment indicators, attach independent Bernoulli selectors of parameter $t$. Janson inequality applied to the selected events gives $\mathbb{E}(1-t{)}^X\le \exp (-t\mu +t^2\Delta /2)$. Set $t=1-e^{-s}$ and apply the exponential Markov bound. The estimates $s-s^2/2\le 1-e^{-s}\le s$ give exponent at most $-sa+s^2(\mu +\Delta )/2$. Optimizing at $s=a/(\mu +\Delta )$ proves the displayed lower-tail bound, with the dependency sum ordered and excluding the diagonal.

For a nonnegative random variable $Y$ and threshold $a>0$, Markov's inequality givesThe useful case has finite expected value; an infinite right side gives no finite information. The bound also holds if $Y$ is nonnegative almost surely. Combining it with the elementary bound one gives $\mathbb{P}(Y\ge a)\le \min \{1,\mathbb{E}Y/a\}$. Nonnegativity is essential: negative values could otherwise cancel the contribution of large positive values to the expected value.

The idea is an average budget. Every outcome where $Y\ge a$ contributes at least $a$ times its probability to $\mathbb{E}Y$, and the other outcomes contribute nonnegative amounts. Formally, the indicator function gives $Y\ge a{1}_{\{Y\ge a\}}$; taking the expected value proves the bound. ^[ref].

For example, let $Y$ take $0$, $1$, $2$, $5$ with respective probabilities $0.5$, $0.2$, $0.2$, $0.1$. Its expected value is $1.1$. At $a=2$, the tail probability is $0.3$, while the bound is $1.1/2=0.55$. At $a=5$, the tail probability is $0.1$, while the bound is $0.22$. A different probability distribution with the same expected value, putting masses $0.78$ and $0.22$ at $0$ and $5$, attains the bound $0.22$ exactly at $a=5$.

Markov's inequality is useful when a moment is easy to compute but a full probability distribution is difficult to determine. A nonnegative count with expected value less than one must have some positive probability of being zero, giving the first moment method. Applying the same bound to a squared centered random variable gives Chebyshev's inequality. Applying it to an exponential function of a random variable gives an exponential Markov bound, which can exploit more than a single moment.

On an independent Bernoulli product measure, the Harris-Kleitman inequality states that increasing events $E,F$ obeyThe same holds for two decreasing events; an increasing and a decreasing event have the reversed inequality.

Prove the stronger function version by induction on the number of coordinates. For increasing bounded functions $f,g$, condition on the last coordinate $Z$, with $\mathrm{Pr}(Z=1)=p$. The law of total covariance givesThe first term is nonnegative by induction, and the other factors are nonnegative by monotonicity. The one-coordinate case is the same formula without the first term. Event indicators prove the assertion. Two decreasing functions follow by replacing both by their negatives; replacing only one gives negative correlation of increasing and decreasing events.

Here is a precise Janson inequality and its lower-tail concentration form. Let $I_i$ indicate containment of a specified set of independent Bernoulli coordinates, set $X={\sum }_i{I}_i$, $\mu =\mathbb{E}X$, and letThis Janson dependency sum is ordered and excludes the diagonal. ThenA zero denominator means the trivial case $X=0$ almost surely.

To prove the avoidance bound, expose the avoidance events in order. For a fixed $i$, separate earlier indices into those whose supports are disjoint from $S_i$ and those overlapping it. Write $C$ for avoidance of the first group and $D$ for avoidance of the second. The event $C$ is independent of $I_i$, while $C$ is decreasing and $\{I_i=I_j=1\}$ is increasing. The correlation inequality therefore givesThe first inequality divides a nonnegative numerator by $\mathrm{Pr}(D\mid C)\le 1$; the second uses a union bound and negative correlation with $C$. Conditioning events of zero probability already make full avoidance impossible. Multiply the resulting conditional avoidance bounds to obtain the Janson sequential product lemma. Taking logarithms and using $\log (1-u)\le -u$ gives $-\mu +\Delta /2$, since each unordered dependency pair is counted once in the sequential sum.

For the Janson lower-tail bound by independent thinning, attach independent selectors of probability $t$ to the events. Their total expectation and dependency sum are $t\mu ,t^2\Delta$, so avoidance of the selected events givesSet $t=1-e^{-s}$ and apply the exponential Markov bound to $e^{-sX}$. Using $s-s^2/2\le 1-e^{-s}\le s$ yieldsChoosing $s=a/(\mu +\Delta )$ proves the concentration assertion. For avoidance alone, optimizing $-t\mu +t^2\Delta /2$ also gives $e^{-{\mu }^2/(2\Delta )}$ when $\Delta \ge \mu$, and the original bound gives $e^{-\mu /2}$ when $\Delta \le \mu$.

To outline the sharp chromatic application, view an independent set of $G(n,p)$ as a clique of its complement, whose edge probability is $q=1-p$. Fix $0<\epsilon <1$, let $m=\lceil n/(\log n{)}^2\rceil$ and $r=\lfloor (2-\epsilon ){\log }_{b}n\rfloor$. For a particular $m$-vertex set, let $X$ count independent $r$-sets. Then $\mu =\left(\genfrac{}{}{0ex}{}{m}{r}\right)q^{\left(\genfrac{}{}{0ex}{}{r}{2}\right)}$, and the overlap calculation givesOverlap of only one vertex shares no edge, hence is independent. For completeness, the summand is at most $(r^2/(m-r){)}^{\ell }{b}^{\left(\genfrac{}{}{0ex}{}{\ell }{2}\right)}/\ell !$. Since $r\le (2-\epsilon /2){\log }_{b}m$ eventually, large overlaps are bounded by $m^{-c_{\epsilon }\ell }$; finitely many smaller overlaps are dominated by $\ell =2$. Also $\log \mu ={\Omega }_{p,\epsilon }((\log m{)}^2)$, so the diagonal contribution $1/\mu$ is negligible. The concentration bound consequently givesA union bound over at most $2^n$ vertex sets still tends to zero. Thus independent sets in every large subset of a dense random graph are available uniformly, including adaptively obtained remainders. Repeatedly remove an independent $r$-set and give it a new colour, then colour the fewer than $m$ leftover vertices individually. This uses at most $n/r+m$ colours. Combining with the first-moment lower bound and letting fixed $\epsilon$ be arbitrarily small gives the accurate leading asymptoticThe uniform subset estimate, rather than merely the existence of one large independent set, is what makes the sharp upper bound possible.

Expose the independent coordinates in order and let $M_i=\mathbb{E}[f\mid X_1,\dots ,X_i]$, $M_0=\mathbb{E}f$. This is the Doob exposure martingale. For fixed earlier coordinates, write $h_i(x)=\mathbb{E}[f\mid X_i=x,\text{earlier coordinates}]$. The remaining coordinates have the same distribution for all $x$, and the coordinate-change hypothesis gives $|h_i(x)-h_i(y)|\le c_i$. Thus the conditional range of $M_i-M_{i-1}$ has length at most $c_i$, and its conditional mean is zero.

Here is the Hoeffding lemma needed for the sharp constant. If a mean-zero random variable $Y$ lies in an interval of length $c$, set $\psi (s)=\log \mathbb{E}{e}^{sY}$. Its second derivative is the variance under the exponentially tilted law. Under any such law, variance is at most $c^2/4$, by comparison with squared distance from the interval midpoint. Since $\psi (0)={\psi }^{\prime }(0)=0$, integration gives $\psi (s)\le s^2{c}^2/8$ for all real $s$. Applying this conditionally and iterating the tower property yieldsThe exponential Markov bound now givesFor $C>0$ choose $s=4t/C$. Apply the same argument to $-f$ and add the two tails, proving the McDiarmid inequalityFor $C=0$, $f$ is constant almost surely, and every positive-deviation probability is zero.

For the neighbourhood application, the ambient points must be elements of $\mathcal{P}[n]$, equivalently binary strings; the printed $y\in [n]$ is a type error. An $n$-element ambient set could not generally satisfy the stated exponential-size lower bound. Use the uniform product probability space on the Boolean cube and set $F(y)=d(y,A)$. Flipping one coordinate changes this Hamming distance by at most one, so $C=n$. Put $\mu =\mathbb{E}F$. Since $\mathrm{Pr}(F=0)=|A|/2^n\ge \epsilon$, the proved two-sided inequality gives, for $\mu >0$,Consequently $\mu \le \sqrt{(n/2)\log (2/\epsilon )}=t/2$; the same bound is immediate if $\mu =0$. ThereforeThis proves the Boolean cube expansion from bounded differences:The meaningful range is $0<\epsilon \le 1$; real radii are interpreted by the inequality on the integer-valued Hamming distance. The converted TeX's final $2^{2n}$ is another corruption: the original PDF has $2^n$.

Let $S$ be the number of red vertices in $W$. It has a binomial distribution with parameters $r$ and $1/2$, so independence givesFor $t=1$, the strict inequality $\log \cosh (1/2)<1/8$ follows by integrating $\tanh u<u$ for $u>0$. Hence the exponential Markov bound yieldsThereforeThis supplies the tail estimate directly, including the strict constant in the requested bound.

Use the uniform probability measure on the symmetric group $S_n$ and the unnormalized Hamming distanceLet $f:S_n\to \mathbb{R}$ have Lipschitz constant $K>0$ for this distance. We will prove the one-sided concentration inequalitiesConsequently $\mathbb{P}(|f-\mathbb{E}f|\ge t)\le 2e^{-t^2/(2n{K}^2)}$ for $t>0$. A zero Lipschitz constant makes $f$ constant, so that case is immediate.

Let $\sigma$ be a uniform permutation, reveal $\sigma (1),\dots ,\sigma (k)$ successively, and define the Doob exposure martingaleFix the first $k-1$ images. For an available value $a$, let $h(a)$ be the conditional mean when $\sigma (k)=a$. Given two available values $a,b$, left-composition with the transposition exchanging $a,b$ is a bijection from completions with next image $a$ to completions with next image $b$. It fixes the previously exposed images and changes exactly two coordinates of each complete permutation. Since conditional completions are uniform, averaging the Lipschitz condition over this pairing gives $|h(a)-h(b)|\le 2K$.

Thus, conditionally on the first $k-1$ images, $M_k-M_{k-1}$ has mean zero and takes values in an interval of length at most $2K$. We need the range-length version of the Hoeffding lemma: if a real random variable $Z$ has mean zero and lies in an interval of length $\ell$, thenHere is a proof. For $\psi (\lambda )=\log \mathbb{E}{e}^{\lambda Z}$, differentiation gives ${\psi }^{\prime \prime }(\lambda )={\mathrm{Var}}_{\lambda }(Z)$ under the exponentially tilted probability distribution. Any distribution on an interval of length $\ell$ has variance at most ${\ell }^2/4$, because its squared distance from the interval midpoint is at most ${\ell }^2/4$. Since $\psi (0)={\psi }^{\prime }(0)=0$, integrating this second-derivative bound gives the lemma for both signs of $\lambda$. The same argument holds for every conditional distribution.

Apply it conditionally to each martingale difference and use the tower property of conditional expectation repeatedly:The exponential Markov bound now gives, for $\lambda >0$,Choose $\lambda =t/(n{K}^2)$ to obtain the upper tail in the box, and apply the argument to $-f$ for the lower tail. This proves concentration of Lipschitz functions on the symmetric group. Using only the bound $|M_k-M_{k-1}|\le 2K$ in the absolute-increment Azuma-Hoeffding inequality would lose a factor four in the exponent; the conditional range length is what yields the constant needed in part (ii).

Apply Markov's inequality to the nonnegative random variable $e^{\lambda X}$, since $X>t$ implies $e^{\lambda X}>e^{\lambda t}$:This exponential Markov bound remains true, though uninformative, when the expected value is infinite. For a standard normal distribution, completion of the square gives its moment-generating functionMinimize ${\lambda }^2/2-\lambda t$ over positive $\lambda$; the choice $\lambda =t$ gives the Chernoff bound

Use the normalizationfor the Lasso. A centered sub-Gaussian random variable with parameter $\sigma$ satisfies $\mathbb{E}{e}^{tW}\le e^{{\sigma }^2{t}^2/2}$ for all $t\in \mathbb{R}$; for a noncentered variable apply this definition to $W-\mathbb{E}W$. With fixed $X$, independence of the errors givesThe exponential Markov bound, optimized over $t$ separately for the two signs, gives $\mathrm{Pr}(|X_j^T\epsilon |/n>u)\le 2e^{-n{u}^2/(2{\sigma }^2)}$. Take $u=\lambda /2=\sigma A\sqrt{\log p/n}$ and apply the union bound over columns:The specified positive tuning parameter requires $p\ge 2$; at $p=1$ its formula is zero. For small $A$ the probability lower bound can be negative and hence uninformative. Although centering makes the centered errors dependent, $X^{T}1=0$ means $X^T(\epsilon -\bar{\epsilon }1)=X^T\epsilon$, so the preceding proof uses the original independent errors, not independence after centering.

The Karush-Kuhn-Tucker conditions, using the subdifferential of the L1 norm, areConsequently, for nonempty $B\subseteq \hat{S}$, on $\Omega$,This establishes the required active-set inequality without any rank condition on $X$.

For $s>0$, a sufficient Compatibility condition for the Lasso isIndeed, for $\delta =\hat{\beta }-{\beta }^0$, comparison of the two Lasso objective values and the score bound on $\Omega$ give the Basic inequality for the LassoIt follows that $\delta$ satisfies the Lasso cone condition and $\Vert {\delta }_S{\Vert }_1\le \sqrt{s{P}_E}/\varphi$. Thus $P_E\le 3\lambda \sqrt{s{P}_E}/\varphi$, including the trivial $P_E=0$ case. This proves the slightly stronger $P_E\le 9{\lambda }^{2}s/{\varphi }^2$, and in particular the requested $16{\lambda }^{2}s/{\varphi }^2$. If $s=0$, the same basic inequality forces $\hat{\beta }=0$ on $\Omega$; no nonempty-support compatibility constant is needed.

For the support-size argument, use the stated prediction bound with constant $16$. Set $b=|B|$. By the Cauchy-Schwarz inequality and the definition of the sparse maximum eigenvalue,Combining with the lower bound and squaring gives $\boxed{b\le 64{\kappa }_b^{2}s/{\varphi }^2}$ for every nonempty $B\subseteq \hat{S}$. If $m_{\ast }<\infty$ and $\hat{s}\ge m_{\ast }$, choose $B$ of size $m_{\ast }$; this contradicts the strict inequality defining $m_{\ast }$. If $m_{\ast }=\infty$, $\hat{s}\le p<\infty$ proves the assertion directly. Hence $\boxed{\hat{s}<m_{\ast }}$ in both cases.

When $1<m_{\ast }\le p$, minimality and monotonicity of the sparse maximum eigenvalues giveWhen $m_{\ast }=1$, the first result gives $\hat{s}=0$, so the same final bound holds. Thus the finite-index conclusion is $\boxed{\hat{s}\le 64{\kappa }_{m_{\ast }}^{2}s/{\varphi }^2(m_{\ast }<\infty )}$.

There is a genuine domain omission in the printed last assertion: the definition of ${\kappa }_m$ only makes sense for $1\le m\le p$, so ${\kappa }_{m_{\ast }}$ is undefined when $m_{\ast }=\infty$. This case can occur: take centered orthogonal columns with $X^{T}X/n=I_p$, $n\ge p+1$, $s=p$, and ${\varphi }^2=1$. Then ${\kappa }_m^2=1$ for every available $m$ and none exceeds $64p$, so $m_{\ast }=\infty$. A universally defined replacement, from $B=\hat{S}$ and monotonicity, isAlternatively, explicitly extend the definition by ${\kappa }_m={\kappa }_p$ for $m>p$, including infinity. Under that added convention the printed final expression is meaningful and follows from this replacement bound. Neither convention nor finiteness should be silently assumed.

For any $t>0$, the exponential Markov bound and part (b) giveThe minimum occurs at $t=v$, so the Gaussian tail bound is

The Markov inequality states that for a nonnegative random variable $Y$ and $a>0$,For $t>0$, the event $X\ge x$ is the same as $e^{tX}\ge e^{tx}$. Applying Markov's inequality to the nonnegative variable $e^{tX}$ gives the exponential Markov bound

Explore the connected component of a graph containing a fixed vertex $v$ by breadth-first search. If the exploration discovers at least $m$ vertices, then before its $m$th discovery at least $m-1$ of at most $mn$ tested potential edges must be present. The tests are independent Bernoulli trials with parameter $p=(1-\epsilon )/n$, soThe binomial distribution on the right has mean $(1-\epsilon )m$. For $m\ge 2/\epsilon$, the exponential Markov bound givesfor an absolute constant $c>0$. The union bound over the $n$ choices of $v$ now givesTaking $m=C_{\epsilon }\log n$ with $C_{\epsilon }>2/(c{\epsilon }^2)$ makes this probability tend to zero. This proves the subcritical component bound for a binomial random graph.

We prove the locally dense graph thinning lemma. Fix an integer $m>8/\epsilon$ and then choose $\delta <1/(3m)$. Partition the vertex set equitably as $V_1\bigsqcup \cdots \bigsqcup V_m$. For sufficiently large $n$, every part has at least $\delta n$ vertices. Consequently every pair $V_i,V_j$ has densityDelete all edges within parts. For each edge of $G$ joining $V_i$ to $V_j$, retain it independently with probability $p/d_{ij}$.

For fixed disjoint $A,B$, writing $A_i=A\cap V_i$ and $B_i=B\cap V_i$ givesThe omitted diagonal contribution satisfiesThe retained-edge indicators are independent. The exponential Markov bound therefore gives, for each fixed $(A,B)$,There are at most $3^n$ ordered pairs of disjoint vertex sets. A union bound shows that, with positive probability, no pair violates this estimate. For that realization,simultaneously for all disjoint $A,B$. As usual for a dense asymptotic statement, $n$ is taken sufficiently large; a lower-order integrality error is unavoidable for bounded $n$.

For every $\theta \ge 0$, the exponential Markov bound and independence giveTaking the infimum over $\theta \ge 0$ yieldsFor $x\ge m$, convexity makes this supremum equal to ${\psi }^{\ast }(x)$, proving the upper bound in the stated tail form of Cramér theorem.