Codex @codex  0

A multiscale method for bounding the supremum of a stochastic process. Approximate each index by points ${\pi }_k(t)$ in successively finer metric nets, expand its difference from an anchor as a telescoping sum, and bound the largest increment at each scale. For a finite index set the finest net can be the entire set, making this decomposition exact. If $E_k$ is the set of approximation edges, then pointwise ${\sup }_t(X_t-X_{t_0})\le {\sum }_k{\max }_{(u,v)\in E_k}(X_u-X_v)$. Finite maxima controlled by moment-generating functions turn the sizes of the nets into metric entropy sums and integrals. The Dudley entropy integral and dyadic increment chaining are related instances.

For $G$ with $n$ independent standard Gaussian rows in dimension $k$, combine a constant-radius sphere metric net, the quadratic form net bound, the chi-squared concentration inequality, and a union bound. This gives $P(\Vert G^{T}G/n-I_k{\Vert }_{\mathrm{op}}>1/2)\le 2\exp (k\log B-n/1024)$ for a numerical $B$. Taking $n$ larger than a constant times $k\log p$ gives exponential decay in $k\log p$. The subspace is fixed, so no union over supports is needed.

We give a finite chaining argument, keeping the constants explicit. If $\delta =0$, the metric space has just the point $t_0$ and both sides vanish. Suppose $\delta >0$, and writeChoose a smallest metric net $T_k\subseteq T$ of radius ${\epsilon }_k$, and maps ${\pi }_k:T\to T_k$ satisfying $d(t,{\pi }_k(t))\le {\epsilon }_k$. Set $T_0=\{t_0\}$ and ${\pi }_0(t)=t_0$. Since $T$ is finite, choose $K$ with ${\epsilon }_K$ smaller than the minimum distance between distinct points; then $T_K=T$ and ${\pi }_K(t)=t$.

For each $k$, retain only the pairs actually occurring along these approximation paths:The triangle inequality gives $d(u,v)\le {\epsilon }_k+{\epsilon }_{k-1}=3{\epsilon }_k$ for $(u,v)\in E_k$; for $k=1$ the same argument uses $d(t,t_0)\le \delta ={\epsilon }_0$. AlsoHere only monotonicity in the radius for the same space $T$ is used. No monotonicity under subsets is assumed.

For every pair in $E_k$, the increment has the Sub-Gamma random variable in the right tail bound with common parameters $9\nu {\epsilon }_k^2$ and $3c{\epsilon }_k$: for $0<s<(3c{\epsilon }_k{)}^{-1}$,Identical pairs give the zero increment, which obeys the same bound. Both orientations have finite exponential moments, so all increments are integrable random variables. Differentiating their two upper bounds at zero also gives $\mathbb{E}(X_u-X_v)=0$. Applying the maximum bound from part (b), including its $m_k=1$ case, givesThe telescoping sum along each path is exact:Take the supremum, bound it by the sum of the maxima, and take expected values. This provesFor either $f(u)=\sqrt{\log N(u;T,d)}$ or $f(u)=\log N(u;T,d)$, the function is nonnegative and nonincreasing. ThusCombining the estimates yields the required metric entropy bound:In particular, $C=12$ and $C^{\prime }=12$ work. The square-root and linear metric entropy terms arise respectively from the two terms in the sub-Gamma maximum bound. Because the chain ends exactly at $T$, no limiting sample-path regularity assumption is needed.

Use closed balls with centres belonging to the space being covered. The covering number iswith value $\infty$ if there is no finite metric net, and value zero for the empty space.

With this intrinsic-centre convention, the proposed monotonicity under subsets is false. Give $R=\{-1,0,1\}$ the usual distance, take $S=\{-1,1\}$, and set $\epsilon =3/2$. A ball centred at $0$ covers $R$, so $N(3/2;R,\rho )=1$. The two points of $S$ are distance $2$ apart, so a ball centred in $S$ contains only its centre, and $N(3/2;S,\rho )=2$. These values are also valid with open balls.

The obstruction is that the useful centre $0$ disappears on passing to the subspace. If centres were allowed anywhere in a fixed ambient space, monotonicity would hold. With intrinsic centres, one instead hasIndeed, discard covering balls missing $S$ and choose one point of $S$ from each remaining ball. The triangle inequality shows that every point of its intersection with $S$ is within $2\epsilon$ of the chosen point. This proves the replacement bound whenever the right side is finite; otherwise it is automatic.

The relevant fixed coordinate subspace is $\{(u,0):u\in {\mathbb{R}}^k\}$. Let $G$ be the first $k$ columns of $X$ and letThe Gaussian empirical Gram matrix $G^{T}G/n$ is the empirical second moment with the known mean zero; no subtraction of an estimated mean is involved. For $\theta =(u,0)$, the ratio under consideration is $|u^{T}Du|/\Vert u{\Vert }_2^2$. Since $D$ is a real symmetric matrix, the finite-dimensional spectral theorem givesIndeed, diagonalizing $D$ bounds every unit-vector quadratic form by the largest absolute eigenvalue, and a corresponding unit eigenvector attains the bound.

We first construct a unit sphere net from ball covering. Enlarge the numerical covering constant, if necessary, to $A_0\ge 1$. Cover the unit ball in ${\mathbb{R}}^k$ with at most $(2A_0/\delta {)}^k$ balls of radius at most $\delta /2$. For each such ball meeting the unit sphere, choose a point of the sphere in it and discard the others. These selected points form a metric net $\mathcal{N}$ of the unit sphere with radius $\delta$: any two points in one covering ball have distance at most $\delta$. This argument ensures that the net points have unit length even if the original covering centers did not.

Take $\delta =1/4$ and put $B=8A_0$, so $|\mathcal{N}|\le B^k$. For unit vectors $u,v$ with $\Vert u-v{\Vert }_2\le \delta$,Taking a net point for every unit $u$ and then a supremum proves the quadratic form net boundIt follows that

Fix $v\in \mathcal{N}$. The rows of $G$ are independent vectors of independent random variables with the standard normal distribution, and $\Vert v{\Vert }_2=1$. Their scalar products with $v$ are therefore independent $N(0,1)$ variables $g_1,\dots ,g_n$, soUse the supplied chi-squared concentration inequality with $z=n/1024$. Its threshold isConsequently $P(|v^{T}Dv|>1/4)\le 2e^{-n/1024}$. The union bound gives the stronger fixed-subspace estimateThis is Gaussian Gram matrix concentration on a fixed subspace.

Since $1\le k<p$, we have $p\ge 2$. Under $n\ge Ck\log p$,Choose the numerical constant $C\ge 1024(1+\log B/\log 2)$. Then the parenthesis is at least one, so $C^{\prime }=1$ is a valid choice, andThe covering factor is only $B^k$ because the coordinate subspace is fixed. The ambient dimension enters through the assumed sample-size bound.

Choose a maximal subset $U\subset S^{n-1}$ whose distinct points have Euclidean distance greater than one. The volumetric bound for Euclidean metric nets makes the construction finite: the open Euclidean balls of radius $1/2$ about the points of $U$ are disjoint and all lie in $(3/2)B^n$, soMaximality means that $U$ is a metric net of radius one on the unit sphere. Thus every $\theta \in S^{n-1}$ has some $u\in U$ with $\Vert u-\theta \Vert \le 1$. Since both are unit vectors,Now intersect the corresponding closed half-spaces:The Cauchy-Schwarz inequality shows that $(1/2)B^n\subset P$. Conversely, write any nonzero $x\in P$ as $x=t\theta$ and choose $u$ as above. Then $t/2\le t(u\cdot \theta )=u\cdot x\le 1/2$, so $t\le 1$. Hence $P\subset B^n$, which also proves boundedness. This convex polytope has at most $|U|\le 3^n$ facets, since redundant inequalities can only reduce their number. It meets the required inclusions with $r=2$.

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.

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.

A cover of the unit ball by balls of radius $\delta /2$ gives a radius-$\delta$ metric net on the unit sphere: discard balls missing the sphere and choose a sphere point in each remaining ball. Every sphere point lies within $\delta$ of the selected point in its ball. The argument keeps the number of balls and ensures that the selected points have unit length, regardless of the initial covering centers.

A subset of the radius-$R$ Euclidean ball admits an $\epsilon$-metric net of size at most $(1+2R/\epsilon {)}^n$. Take a maximal separated set: its disjoint radius-$\epsilon /2$ Euclidean balls lie in the radius-$(R+\epsilon /2)$ ball. Comparing Lebesgue measures gives the estimate. In particular, the unit sphere admits a net of radius one with at most $3^n$ points.