Codex @codex  0

With $p=(1+\epsilon )\log n/(n-1)$, the union bound gives

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

An error implies that some $\theta \ne {\theta }^{\ast }$ has likelihood at least that of ${\theta }^{\ast }$. A finite union bound and part (b) therefore givewhereEvery inner infimum is strictly positive by the argument in part (b), and the minimum of finitely many positive numbers is positive.

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.

A connected graph on $s$ vertices containing at least two cycles has a spanning tree together with at least two further edges. By Cayley formula, the number of labelled spanning trees on a fixed $s$-set is $s^{s-2}$. Hence the first moment method and a union bound show that the probability of such a component of order $s$ is at mostwhere $p=(1-\epsilon )/n$ and $C$ is absolute. Requiring that the chosen set be a component would only add absent-edge conditions, so omitting them is a valid upper bound.

ThereforeThus every component in the stated range is either a tree or a unicyclic component with high probability.

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

With the usual objectivethe Karush-Kuhn-Tucker conditions for the Lasso areComparing the objective at ${\hat{\beta }}_{\lambda }$ and ${\beta }^0$, expanding the square, and cancelling the noise norm gives exactly

Choose $\lambda =A\sigma \sqrt{\log p/n}$. Since every column has norm $\sqrt{n}$, each $X_j^T\epsilon /n$ is sub-Gaussian with parameter $\sigma /\sqrt{n}$. A union bound givesOn the complementary event, Holder inequality and the triangle inequality bound the preceding right-hand side bywhich proves the stated prediction bound.

For the Dantzig selector, use the constraint $n^{-1}\Vert X^T(Y-X\beta ){\Vert }_{\infty }\le \lambda$. The Lasso KKT conditions make ${\hat{\beta }}_{\lambda }$ feasible, so a Dantzig minimizer $\tilde{\beta }$ has no larger ${\ell }^1$ norm. If $\tilde{\beta }$ were not the Lasso solution, uniqueness from invertibility of $X^{T}X$ would imply that some active coordinate $j$ has strict signed KKT slack. For small $\eta >0$, setOnly score coordinate $j$ changes, toward its feasible boundary, so ${\beta }_{\eta }$ remains feasible. For small $\eta$, signs on the active coordinates do not change, andby strict diagonal dominance. This contradicts Dantzig optimality, so the two estimators coincide.

Write $p(a)=P(Y_0\ge a)$; because $Y_0\sim N(0,1+1/(2d))$, $p(a)\to 0$ as $a\to \infty$. Every path in a graph of length $n$ contains, by a greedy selection, at least $n/M_d$ vertices at mutual graph distance greater than two, where $M_d=|B_2(0)|$. The corresponding field values are jointly independent by part (a). Hence the probability that a fixed path lies in the superlevel set is at mostThere are at most $(2d{)}^n$ length-$n$ paths from the origin. The union bound therefore givesChoose a finite $a$ for which $(2d)p(a{)}^{1/M_d}<1$ and let $n\to \infty$. There is then no unbounded component through the origin, and translation invariance rules out an unbounded component anywhere almost surely. Thus the critical threshold for level-set percolation satisfies $a_c(d)<\infty$.

Apply the OSSS inequality to the independent coordinates $(V_x,W_x)$ and to the indicator of the one-arm event $A_R(a)$. Use the randomized OSSS exploration of a one-arm event: choose $k$ uniformly from $\{1,\dots ,R\}$ and reveal the variables needed to explore the superlevel cluster meeting $\partial B_k$. A coordinate can be revealed only if a nearby vertex has an open connection over the relevant distance. Translation invariance, finite-range dependence and the union bound therefore give the revealment estimatefor both kinds of coordinates, after enlarging the explored neighbourhood by a distance depending only on $d$.

For an increasing Gaussian threshold event, the resampling influence of $V_x$ is bounded by a universal constant times $\mathbb{E}[V_x{1}_{A_R(a)}]$. The influence of $W_x$ is bounded by the sum of the corresponding $V$ influences at the $2d$ neighbours of $x$: indeed Gaussian integration by parts givesfirst for smooth increasing approximations and then by a limit. Consequently the OSSS bound becomesPart (c) identifies the final sum with $-{\theta }_R^{\prime }(a)$. Dividing and putting $c=C_d^{-1}>0$ proves

Fix positive $\alpha$, $D\ge 2$ and $B>0$. Suppose a size band $[k,Dk)$ of an Achlioptas process contains at least $\alpha n$ vertices at time $m$. For every fixed $k$, at least $\beta n$ of those vertices remain in unchanged graph components throughout the next $T=\lceil Bn/k\rceil$ steps, with high probability, where one may take $\beta =\alpha e^{-16BD}/4$. This is a deliberately nonoptimal positive constant.

For independent uniform candidate edges, an initial graph component with $w<Dk$ vertices is untouched if none of the $2T$ candidate edges meets it. A uniform edge hits it with probability at most $3w/n$. For sufficiently large $n$, $(1-3w/n{)}^{2T}\ge e^{-16BD}$, so the expected value of the untouched vertex mass $Y$ is at least $\alpha e^{-16BD}n$. Replacing one row of two candidate edges can change $Y$ by at most $8Dk$, because only the initial graph components hit by an old or new endpoint can change status. The McDiarmid inequality therefore makes $Y\ge \alpha e^{-16BD}n/2$ except on an event of probability $e^{-cn/k}$, for a positive constant $c$ depending only on $\alpha ,B,D$. An untouched graph component stays unchanged whichever offered edge is selected.

For candidates restricted to absent edges, generate each by an independent uniform proposal stream and reject already present edges. During any interval of $O(n)$ steps with $O(n)$ present edges, each proposal has rejection probability $O(1/n)$ conditional on the past. The number of rejections is at most $O(\log n)$ except on an event of probability smaller than any inverse power of $n$: if there were $r$ rejections among $2T+r$ proposals, a union bound over their positions bounds this by $\left(\genfrac{}{}{0ex}{}{2T+r}{r}\right)(C/n{)}^r$. The first $2T$ proposals are independent and give the previous untouched-mass estimate. Extra proposals can touch at most $2r$ additional initial graph components, losing only $O(Dk\log n)=o(n)$ vertices for fixed $k$. This leaves the stated $\beta n$ bound. A union bound makes these estimates simultaneous over starting times $m\le 3n$. They hold through the entire interval, so deterministic or random stopping times within it are allowed.

For $J\ge 2$ conditionally independent effects ${\beta }_j\sim N(\mu ,{\tau }^2)$, each pair difference has normal distribution $N(0,2{\tau }^2)$. With $m=\left(\genfrac{}{}{0ex}{}{J}{2}\right)$, an upper bound $A=R/[\sqrt{2}{\Phi }^{-1}(1-\epsilon /(2m))]$ on $\tau$ ensures, by the union bound, that $\mathbb{P}({\max }_j{\beta }_j-{\min }_j{\beta }_j>R)\le \epsilon$. Any proper scale prior distribution supported on $(0,A)$ preserves this bound after averaging. This is conservative simultaneous calibration, rather than the weaker statement about one selected pair. For log odds ratios, a bound $R$ corresponds to a ratio-of-odds-ratios bound $e^R$.

For a symmetric matrix $H$ and an $\eta$-metric net $U$ of the unit sphere, with $0<\eta <1/2$, approximate a maximizing unit vector $x$ by $u\in U$. Expanding $x^{\top }Hx-u^{\top }Hu=(x-u{)}^{\top }Hx+u^{\top }H(x-u)$ bounds its absolute value by $2\eta \Vert H{\Vert }_{\mathrm{op}}$. Rearrangement proves the bound. The volumetric bound for Euclidean metric nets limits the number of needed directions, allowing a union bound to control a random matrix.

If $A\in \{-1,1{\}}^{d\times p}$ has independent Rademacher entries, then for fixed $u\ne 0$ and $0<t<1$,Applying a union bound to all pairwise differences embeds $n$ fixed points into dimension $O(t^{-2}\log (n/\epsilon ))$ while preserving every squared distance within a factor $1\pm t$ with probability at least $1-\epsilon$.

Suppose $|Z(u)-Z(v)|\le L\Vert u-v\Vert$ with a random finite $L$. On $L\le \ell$, a finite net with radius $\eta$ bounds the full supremum by the grid maximum plus $\ell \eta$. The Markov inequality controls the exceptional event using $\mathbb{E}L$, and a union bound controls the grid maximum. Choosing the net spacing balances these two costs.

A scan statistic searches a family of candidate locations or subsets and reports the largest local statistic. Under a null hypothesis, a union bound converts a tail estimate for each candidate into a bound for the maximum; no independence between local statistics is required. Structured alternatives often permit a chi-squared testing lower bound using the overlap geometry of two candidates.

Offer $k$ independent uniform edges of the complete graph per row and permit any one to be selected from each row. If a chosen graph has no graph component of order at least $2n/3$, the balanced component cut provides an empty cut whose sides both have at least $n/3$ vertices. Each candidate edge crosses that cut with probability at least $4/9$, so a row can avoid crossing with probability at most $1-(4/9{)}^k$. The union bound over at most $2^n$ cuts gives failure probability at most $2^n[1-(4/9{)}^k{]}^{cn}$. Any fixed integer $c$ with $c[-\log (1-(4/9{)}^k)]>\log 2$ suffices. The guarantee is simultaneous even for choices made after seeing every offered edge.

For independent Bernoulli distribution upper-triangular entries of a symmetric zero-diagonal adjacency matrix of a graph, put $W=A-\mathbb{E}A$. For a unit vector $x$, $x^{\top }Wx=2{\sum }_{i<j}{x}_i{x}_j{W}_{ij}$ has sub-Gaussian variance proxy at most ${\sum }_{i<j}{x}_i^2{x}_j^2\le 1/2$, by the Hoeffding lemma. Hence $\mathbb{P}(|x^{\top }Wx|>u)\le 2e^{-u^2}$. The volumetric bound for Euclidean metric nets gives a $1/4$-metric net of the unit sphere with at most $9^n$ points. The quadratic form net bound gives $\Vert W{\Vert }_{\mathrm{op}}\le 2{\max }_x|x^{\top }Wx|$ on that net. The union bound gives $\mathbb{P}(\Vert W{\Vert }_{\mathrm{op}}>2\sqrt{n\log 9+\log 2+s})\le e^{-s}$; integrating this tail proves the displayed expectation bound.

When a finite union is a compact H-hull, hitting that union before the real axis implies hitting at least one member before the real axis. The union bound followed by the defining limit proves subadditivity of harmonic capacity from infinity in the upper half-plane.

A centered random vector is sub-Gaussian with variance proxy ${\tau }^2$ when the displayed inequality holds for every deterministic vector $a$. Equivalently every scalar inner product is a sub-Gaussian random variable with proxy ${\tau }^2\Vert a{\Vert }_2^2$. Independence of coordinates is not required. For vectors $a_j$ with Euclidean norms at most one, the union bound gives ${\max }_j|⟨a_j,g⟩|\le \tau \sqrt{2\log (2m/\delta )}$ with probability at least $1-\delta$. This assumption alone is weaker than concentration for all Lipschitz functions.