Projection moments, positive cap domination, and Riesz estimates on the sphere

Proof. Rotation invariance reduces the projection to the first k coordinates. Let G\in\R^k and H\in\R^{D-k} be independent standard Gaussian vectors. Then (G,H)/\sqrt{\norm G^2+\norm H^2} is uniform on the sphere. The random variables \norm G^2/2 and \norm H^2/2 are independent unit-scale gamma variables of shapes k/2 and (D-k)/2. Changing variables from these two positive numbers to their sum and their first fraction shows that the fraction has density

The direction of G is uniform and independent of these lengths. Polar coordinates in \R^k, with \vol(S^{k-1})=2\pi^{k/2}/\Gamma(k/2), now give (1). The surface-area identity itself follows by integrating e^{-\norm x^2} in polar coordinates. The direction of H is uniform and independent of both lengths and of G, which proves the conditional assertion. The event H=0 is null.□

Proof. On the ball of radius \sqrt k, the function e^{-\norm z^2/2} is at least e^{-k/2}. Comparing its integral there with the full Gaussian integral gives

which is the claimed bound.□

Proof. For r\le1, rotate c to the north pole. A sphere point in B(c,r) has last coordinate at least 1-r^2/2\ge1/2. Its surface element as a graph over c^\perp is at most twice Lebesgue measure, and its projection lies in the n-ball of radius r. The full sphere has area at least twice the volume of the unit n-ball, by projecting both hemispheres. This proves the upper bound for r\le1; total mass one proves it for r>1.

For the lower bound when r\le1, the angular radius 2\arcsin(r/2) is at least r. In polar angle the cap mass is the integral of \sin^{n-1}\theta over this interval divided by its integral over [0,\pi]. Use \sin\theta\ge2\theta/\pi for 0\le\theta\le r and bound the denominator by \pi. Since n\le2^{n-1}, the result is at least (r/\pi)^n. For 1\le r\le2, monotonicity therefore gives the lower bound with a=1/(2\pi).

If an ambient ball meets the sphere, choose c in the intersection. Its sphere portion is contained in B(c,2r), proving (4); an empty intersection is immediate. Finally, angular error at most \epsilon implies chordal error at most \epsilon, because 2\sin(\theta/2)\le\theta. Apply the sphere-centered upper bound to each fixed output and then integrate over any independent output randomization.□

Proof. First suppose the rule includes a fresh seed of law \kappa. Each completed-product measurable coordinate has a product-measurable version: approximate it by simple functions and replace the countably many level sets by product-measurable sets modulo null sets. Replace the resulting finite vector by a fixed point mass wherever it fails to be a probability vector. This repair occurs on a product-measurable null set. Integrating against \kappa now gives a Borel probability vector in the current pair, and Fubini shows agreement with the original integrated rule for \lambda-almost every pair. It therefore suffices to consider the coordinate probabilities in the first statement.

For each fixed state and index, combine the possible transitions and stops into a finite set of destinations, tagged as continuing or stopping. Choose Borel versions of their coordinate probabilities by the same simple-function construction. On the Borel null set where the versions fail to be nonnegative or to sum to one, replace the vector by a fixed point mass. Finitely many states and indices are involved, so all changes lie in one Borel \lambda-null set Z.

For every nonzero feature x, Lemma 2.1 gives a Lebesgue density for \inner{x}{S}. Since a Gaussian feature is nonzero almost surely, every pre-generated pair (X_t,\inner{X_t}{S}) has law absolutely continuous with respect to \lambda. Thus each pair avoids Z almost surely. Even if the current state depends on previous observations, the probability of being in a particular state and seeing a pair in Z is bounded by the marginal probability of seeing that pair in Z, which is zero.

Almost surely none of the finitely many pre-generated pairs lies in Z. Couple the original and modified finite destination kernels by the same fresh uniform random numbers. Induction gives identical state paths and stopping decisions; couple their unchanged terminal output laws identically as well. This proves equality of the specified joint laws. Finally, finite composition and integration of the Borel kernels against independent future features and coins defines a measurable continuation from every specified state and index, including unreachable states.□

Proof. Let F be the row span of the pre-generated feature matrix and put u=P_FS. Its dimension is T almost surely, with the evident interpretation for T=0. The labels determine u. For T=0, the residual is the original uniform signal. For T>0, Lemma 2.1, applied after fixing the feature matrix, shows that conditional on all the data the residual is \sqrt{1-\norm u^2}\,\omega, with \omega uniform on the unit sphere of F^\perp. Before conditioning on the labels, isotropy gives \E\norm u^2=T/d. Consequently \Prob\{\norm u^2\ge1/2\}\le2T/d.

When \norm u^2<1/2, opposite residual directions give two signals at distance 2\sqrt{1-\norm u^2}>\sqrt2>2\epsilon. They have the same conditional law, and at most one can be within chordal distance \epsilon of a fixed output. Angular success implies this chordal condition, so conditional success is at most 1/2, also after averaging independent estimator randomness. Total success is at most

Giving the estimator all pre-generated data also covers a learner that stops at a prefix, with its independent shared and fresh randomness.□

Proof. Right rotational invariance allows us to replace the fixed columns of E by an independent uniform orthonormal frame. Conditional on P, its projection has the same law as the first k coordinates of that frame. Sample the full columns successively and let Z_j be the matrix of the first k coordinates of its first j columns. Set

Given the preceding full columns, the next column is uniform on the unit sphere in their d-j-dimensional orthogonal complement. The coordinate map from that complement to the first k coordinates has row Gram matrix S_j. When S_j>0, multiplication by S_j^{-1/2} makes its rows orthonormal. Lemma 2.1 and a linear change of variables therefore give the next projected column z conditional density

on z^{\mathsf T}S_j^{-1}z<1. This expression depends only on Z_j, so it is also the conditional density given those projected columns. The strict inequality implies S_{j+1}=S_j-zz^{\mathsf T}>0 almost surely. The determinant identity

shows that multiplication of the m conditional densities cancels every intermediate determinant. The remaining factor is \det S_m^{(d-k-m-1)/2}, proving (5). Its exponent is nonnegative and 0<\det S_m\le1.

The normalizing constants have the stated scale. For a unit-scale gamma variable G of shape a=(d-j-k)/2>0, Cauchy–Schwarz and the gamma recurrence give

Together with the factor \pi^{-k/2}, this bounds each c(d-j,k) by (C\sqrt d)^k.

For the last assertion, Gram–Schmidt writes [x_2-x_1,\ldots,x_{m+1}-x_1]=ER, where E has orthonormal columns and R is triangular with \abs{\det R}=\prod_{i=2}^{m+1}\delta_i. Right multiplication by R on k-by-m matrices has Jacobian \abs{\det R}^k, one factor for each row. Applying this change of variables to the preceding density proves (6).□

Proof. For 0<t\le R, the projection of B(z,R) onto F is contained in a j-ball of radius R. A maximal t-separated subset is a t-net with at most (3R/t)^j points, by packing disjoint j-balls of radius t/2. For j=0, one point suffices. The corresponding ambient balls of radius 2t cover the points of B(z,R) within distance t of F. Thus

Because \beta-j>0, continuity from above as t\downarrow0 gives \nu(F)=0. Distances greater than R contribute at most R^{-k}\nu(B(z,R))\le KR^{\beta-k}. On the shell 2^{-h-1}R<\dist(x,F)\le2^{-h}R, (9) gives a contribution at most

The sum over h\ge0 is at most twice its first term. Since \beta,j,k\le d, the resulting factor is bounded by C^d.□

Proof. When K=0, the measure is zero and the assertion is immediate. For K>0, let v_k be the unit-ball volume and define

These are jointly measurable nonnegative functions. Expanding their qth powers and using Tonelli’s theorem expresses the integrated moment through q points x_1,\ldots,x_q drawn from \nu. The intersection of the q label balls of radius \delta has volume at most v_k\delta^k; it is empty unless \norm{P(x_i-x_1)}\le2\delta for i\ge2.

Put \delta_i=\dist(x_i,\aff(x_1,\ldots,x_{i-1})). Lemma 3.2 shows that every affine plane encountered here has zero \nu-mass: its dimension is at most q-2, so the last condition in (10) applies. Consequently the tuple is affinely independent for \nu^{\otimes q}-almost every choice. For such a tuple, Lemma 3.1 applies with m=q-1; the condition k+q\le d is exactly its determinant condition. The probability of all q-1 inequalities is bounded by

The label-ball volumes cancel those in the definition of g_\delta. Absorbing 2^{k(q-1)} in C, we obtain

The degenerate tuples form a null set and can be assigned an infinite upper bound in this nonnegative integral.

Integrate first in x_q, then in x_{q-1},\ldots,x_2. At each step Lemma 3.2 bounds the current factor by C^d K R^{\beta-k}. The remaining first-point mass is at most KR^\beta. Hence the last integral in (12) is at most

This proves the qth power of (11) uniformly in \delta.

Define g(P,u)=\liminf_{j\to\infty}g_{1/j}(P,u). The assumed absolute continuity and Lebesgue differentiation [15, Theorem 1.6.19, pp. 146–147] imply that, for almost every P, this is a density of P_\#\nu for almost every u. Fatou’s lemma on the product space [15, Corollary 1.4.47, p. 110] gives (11). If \norm{u-Pz}>R, sufficiently small label balls miss P(B(z,R)), since P is a contraction; the displayed version is then zero. This limiting calculation concerns the exact projected measure. It introduces no noise into an observation.□

Proof. Restriction preserves the stated all-ball bound. For every P, the projection of \sigma is absolutely continuous by Lemma 2.1, so the same holds for the restricted weighted measure. The exact margins are

Thus Theorem 3.3 applies. This also records the nonnegative frame-determinant exponent (d-k-q)/2=(d-2\lfloor d/4\rfloor)/2.□

Proof. Right rotational invariance of X makes P have law \vartheta_{d,k}; the independence assertion about P,H used later is proved below. The exact determinant and inverse-distance margins are

Apply Theorem 3.3 with q=p, \beta=\lambda, K=D^d, and R=1. If \ell(P,z) is its Lebesgue density, then g_X(z)=v_k\ell(P,z) is the required normalized density. Moreover

Use the unit-ball volume estimate (2). Since k\ge d/32 for sufficiently large d,

Theorem 3.3 now bounds the normalized L^p norm by \exp(C_Dd), proving (14). The density version and its support are inherited from that theorem. The mass-at-most-one and absolute-continuity hypotheses have been retained explicitly.□

Proof. Full row rank holds almost surely because the rank-deficient matrices are the zero set of nonzero minors and the Gaussian law has a density. Right multiplication of X by a fixed orthogonal matrix leaves its law unchanged, fixes H, and right-rotates P. Let O be an independent uniform orthogonal matrix. For bounded measurable \phi,\psi, invariance and averaging give

where \mu is uniform orthogonal probability. The inner integral is independent of P: the right action on \mathcal V_{d,k} is transitive, and \mu is invariant. Its value is \int\psi\,d\vartheta_{d,k}. This factorizes the expectation for all bounded measurable tests, which proves the stated law and independence.□

Proof. Write X=HP as in Lemma 3.6 and average the full radial dependence of the routing rule:

These are measurable nonnegative weights with \sum_w\tau_w\le1. Independence gives the exact identity

Fix E=B(z,R), and let g_w(P,u) be the exact density in Corollary 3.4 for \1_Ef_w\sigma. After integrating (16) over E, pushforward integration yields \int\!\int\sum_w\tau_w g_w\,du\,d\vartheta_{d,k}. Each g_w is supported in \norm{u-Pz}\le R. On this domain the measure with density \tau_w, relative to frame probability, label Lebesgue measure, and counting measure in w, has total mass at most v_kR^k. Hölder’s inequality therefore gives

Substitute (13). The radius powers add exactly to \beta. Also k\ge d/8, so (2) gives

This proves (15). The original Q_w could use all entries of H; only after that dependence was retained did we average it into \tau_w.□

Proof. Use the fixed-seed and Borel-kernel convention of Section 2, and set n=d-1 and \beta=n-q. For each terminal state and stopping index, let h(s) be the success probability of its signal-independent output law. The cap estimates of Lemma 2.3 give

The last inequality follows from R\le\epsilon or R\ge\epsilon, respectively. Thus the all-radii coefficient for every terminal function is at most K_0=C^d\epsilon^q.

Divide the horizon into b blocks of k rows, padding the last block with independent rows ignored by its rules. Starting at a specified state and boundary index, define its continuation by a fresh future execution. This definition does not condition on that state being reached. The continuation functions are Borel and take values in [0,1] by Lemma 2.6.

Within a block, a destination is either a continuing state at the next boundary or a terminal state tagged by its local stopping index. The possible local stopping indices are 0,1,\ldots,k, including an immediate stop. There are at most (k+1)2^M terminal destinations and 2^M continuing destinations, hence at most N_* in total. The global stopping index is determined by the fixed block start and this local index, so the terminal output retains its full allowed dependence on time.

Finite composition of the transition kernels produces Borel routing probabilities Q_w(X,y) for these destinations, with \sum_wQ_w\le1. Their continuation functions f_w use only future independent rows and coins; terminal destinations use the functions h above. The incoming continuation therefore has precisely the form

from Proposition 3.7. The Gaussian block is fresh: conditional on the fixed shared seed, its rows are jointly independent of the signal and entering state, which depends only on initialization, past pairs, and past coins.

Backward induction through the blocks multiplies the all-radii coefficient by at most C^dN_*^{1/q} per block. This factor is at least one, so the coefficient also bounds any earlier terminal option. Integrate the initial continuation over B(0,1) and average over the conditional initial-state law, which is independent of the signal and rows. Conditional success is at most the right side of (17). The bound is uniform in the fixed rules, so the shared-seed convention gives the same bound for the original learner. When T=0, the terminal bound supplies the conclusion directly.□

Proof of Corollary 2.5 and first proof of Theorem 2.4. Put L=\log(1/\epsilon). Choose an absolute dimension threshold so that Proposition 3.8 applies and k=q\ge d/8. If success is at least 2/3, (17) implies

Since b\le8T/d+1 and \log(k+2)/q is bounded by an absolute constant, this gives an absolute C_1 such that

No bound on M was used. Lemma 2.7 forces T>d/8, and hence T+d<9T. Substitution into (18) proves Corollary 2.5 with an absolute constant.

Finally, if M(d)=o(d^2), then 1+M(d)/d^2\le2 for all sufficiently large d. The corollary proves Theorem 2.4, with an absolute lower-bound constant and a dimension threshold that may depend on the memory sequence. This proof is uniform over the accuracy sequence and uses only within-block stopping indices.□

Proof. We prove a bound for nonnegative tests and then convert it into a countable positive domination.

Cap tests and their local mass. Put \rho_j=r2^{-j} and choose a finite \rho_j/2-net N_j of the sphere for every j\ge0. Take as a dictionary the parent cap, indexed by *, together with all B(c',\rho_j), c'\in N_j. Repetitions may have separate indices. For this countable index set I, write B_i=B(c_i,\rho_i) and

Thus \phi_*\,d\sigma=\mu_{c,r}, every \phi_i is a probability density, b_*=1, and the weights at level j are 2^{\alpha j}. If h\in L^\infty(\sigma) is nonnegative and satisfies

then its integral against any positive dictionary sum is at most that sum’s weighted cost. We will bound \int h f_w\,d\mu_{c,r} for every such test.

Let \nu be the image of h\mu_{c,r} under s\mapsto(s-c)/r. It has unit-ball support and mass at most one by the parent constraint. We claim that, for an absolute D\ge1,

For 0<t\le1/4, suppose the ball meets the rescaled cap, and choose a point s_0\in B whose image lies in it. The corresponding sphere points are all within 2rt of s_0. Set

A center in N_j within \rho/2 of s_0 gives a dictionary cap containing those points, since 2rt+\rho/2\le\rho. Its constraint and the two-sided cap estimate imply

An empty intersection has zero mass. For t>1/4, use the mass bound and 1\le4^\lambda t^\lambda. These estimates prove (24).

The quantitative test estimate. All hypotheses of Theorem 3.5 now hold for \nu. Indeed, the test, parent cap, and measure are fixed before the fresh matrix X is drawn. For every orthonormal k-frame P, the coordinate density in Lemma 2.1 gives P_\#\sigma\ll dz. Because h\mu_{c,r}\ll\sigma, its projection is also absolutely continuous, and the affine rescaling

gives the same conclusion for P_\#\nu. The theorem therefore supplies a jointly measurable density satisfying, for almost every X,

The density is relative to dm_k=dz/v_k on the unit ball; D, and hence the new constant, is absolute. Since s=c+ru gives Xs=Xc+rHPu, Tonelli’s theorem and Hölder’s inequality on the product law of X and z yield

The last line uses 0\le K_w\le1. Thus every test satisfying (23) obeys (25).

Representation by positive cap sums. The geometric estimate is complete; the remaining step uses only the dictionary and its test bound. If q_w=0, the feasible test h=1 shows that f_w\mu_{c,r}=0, and the empty sum suffices. Otherwise set K=\exp(Cd)q_w^\theta>0, with the constant from (25), and define in real L^1(\sigma)

Each series converges in L^1, since b_i\ge1 and \norm{\phi_i}_{L^1}=1. This convex set is norm compact. To see this, take a sequence and choose a coefficient array for each term. A diagonal subsequence converges coefficientwise, since 0\le a_i\le K/b_i. The limiting array has cost at most K by Fatou’s lemma. There are finitely many indices through every level J, and uniformly over all admissible arrays,

The same estimate holds for the limiting array. Finite-level convergence followed by (26) gives convergence in L^1. This proves sequential compactness, and hence compactness in the metric space L^1(\sigma) [10, Section 1.3, Theorem 1.37, p. 29].

Its signed downward closure

is convex, contains every nonpositive L^1 function, and is norm closed. In fact, if u_m\to u and u_m\le v_m\in\mathcal C_K, compactness provides a subsequence v_m\to v\in\mathcal C_K; then

Put F=f_w\phi_*. If F\notin\mathcal D_K, strict separation of the closed convex set \mathcal D_K and the compact singleton \{F\} [10, Section 5.2, Theorem 5.20(b), pp. 98–99] gives a continuous real functional \ell with

A probability measure is localizable [5, Theorem 211L], so real L^1–L^\infty duality [6, Theorem 243G(b)] represents \ell(u)=\int hu\,d\sigma for a real h\in L^\infty(\sigma). The finite supremum forces h\ge0: if h\le-\delta on a set E of positive measure, the functions -t\1_E\in\mathcal D_K would make it infinite. Define

Then

The cost bound gives the upper inequality, and the single terms (K/b_i)\phi_i give the reverse inequality by taking the supremum over i. This does not require the supremum to be attained. If S_h=0, the parent term gives \int h\phi_*\,d\sigma=0, and 0\le f_w\le1 implies \ell(F)=0, contrary to strict separation. If S_h>0, the function h/S_h satisfies (23), so (25) again contradicts separation. Therefore F\in\mathcal D_K. An admissible series dominates its density almost everywhere; integrating gives the asserted measure inequality and cost bound. Its total mass is at most K.□

Proof. Multiplication by a nonnegative measurable function preserves a measure inequality, as follows first for simple functions and then by monotone convergence. Summing over incoming states and cap terms therefore gives

Apply Proposition 4.1 separately to every term. For a fixed incoming cap, write q_{v,i,w} for its reference probabilities. They depend on that cap as well as on the starting state, and satisfy \sum_wq_{v,i,w}\le1. Hölder’s inequality for the finite sum gives

If the outgoing terms for this parent have coefficients \beta_j and radii \rho_j, their contribution to the global cost is bounded by

Sum first over w and then over the countably many incoming terms to obtain (28). Tonelli’s theorem applies throughout because every summand is nonnegative.

At each of finitely many block boundaries there are only countably many state–cap terms. Choosing a dominating sum for each produces a deterministic proof representation, with another countable sum at the next boundary. There is no choice indexed by the random signal or by the fresh matrix. The state measures here remain unnormalized joint measures; the argument never divides them by their total masses.□

Proof. For a fixed unit output z, write \vartheta=\arccos\inner{z}{s}. Angular success implies \norm{s-z}=2\sin(\vartheta/2)\le\epsilon. If \epsilon<r, Lemma 2.3 bounds its probability under \mu_{c,r} by

If \epsilon\ge r, use probability at most one and (\epsilon/r)^\alpha\ge1. Integration over Q proves the result.□

Proof. Fix t>0 throughout the argument and split its first t indices into b=\lceil t/k\rceil consecutive blocks of length at most k. At a prefinal boundary retain only paths that have not stopped and are eligible to continue. In the final block retain exactly the paths stopping at t, with their terminal state. For a fixed starting state and a supplied block of pairs, integrating the internal randomness gives the probability of each retained ending state. These are Borel kernels with sum at most one, since all omitted paths are discarded. A shorter block is padded by independent unused Gaussian rows, which the kernels ignore. Its likelihood for a signal s is therefore f_{v,w}(s) of (21). Conditional on the fixed seed, the fresh Gaussian feature rows in the block are jointly independent of the signal and entering state, indeed of the signal, initialization, past rows, and past coins. Given the signal, the past affects this likelihood only through the starting state and the fixed index.

At any counted boundary, let \eta_v(E) be the probability that S\in E and the path is counted in state v. These are unnormalized joint measures and their outgoing laws have exactly the formula in Lemma 4.2. Initially, B(c,2)=S^{d-1} and \mu_{c,2}=\sigma. Write V_0 for the initial finite state. For the fixed shared seed \xi, joint initialization independence gives

Thus the initial total cost is one before any discarded paths are removed, and at most one afterward. After b applications of that lemma, the counted terminal measures admit positive cap dominations of total cost at most [\exp(Cd)2^{M/p}]^b.

At each fixed terminal state and index t, the output is drawn from a fixed law using fresh randomness. Apply Lemma 4.3 to each term of its dominating cap sum. A term of coefficient a and radius r contributes at most \exp(Cd)(\epsilon/2)^\alpha a(2/r)^\alpha. Summing proves the conditional version of (30). At t=0, use the initial domination and the same terminal estimate directly. The index has been fixed throughout, so only the at most 2^M states at each ending boundary were counted. No additional state is charged for the value of t.

The countable dominating sums are chosen only after fixing the shared seed. The bound is uniform in that seed, so the common convention of Section 2 allows us to average the original conditional success probabilities. No measurable choice of cap decompositions across shared seeds is required. Finally, for M(d)=o(d^2) we eventually have M(d)\le d^2. Since p\ge d/32, the logarithm of the extra factor 2^{M/p} is then at most 32(\log2)d. Absorbing it into the absolute exponential constant proves (31).□

Proof of Theorem 2.4 by positive cap domination. Put L=\log(1/\epsilon).

For the given sequence M(d)=o(d^2), use (31) in all sufficiently large dimensions. The stopping events are disjoint. Since k\ge d/32, \alpha\ge d/3, and \lceil t/k\rceil\le t/k+1, summing over 0\le t\le T yields

Here (\epsilon/2)^\alpha\le\exp(-dL/3), and C_1,C_2 are absolute. If success is at least 2/3, taking logarithms gives

since \log(T+1)\le T for every T\ge0. Lemma 2.7 also gives T>d/8, and therefore T\ge1. Consequently

This proves the claimed bound with an absolute constant, uniformly over the full accuracy range. Only the dimension at which the memory factor is absorbed may depend on the sequence M(d).□

Proof. The ambient estimate (35) follows from Lemma 2.3, with 2^{d-1} absorbed into C^d. For dyadic outer radii r_m=\epsilon2^{-m}, the shell r_m/2<\norm{s-z}\le r_m contributes at most (2/r_m)^\alpha C^d r_m^{d-1}. The point s=z has zero \sigma-measure, and \sum_{m\ge0}2^{-m(d-1-\alpha)}\le2. Summing proves (36). The same argument at radius 1/10, together with the kernel bound 10^\alpha outside that ball, proves V(h)<\infty uniformly over 0\le h\le1.□

Proof. For every ambient center c and radius r>0, definition (34) gives

Fix 0<r\le\rho. A maximal r-separated subset of F\cap B_\rho(z) has at most (1+2\rho/r)^\ell \le(3\rho/r)^\ell points, by comparing disjoint radius-r/2 balls in F with the radius-(\rho+r/2) ball. It is an r-net. The orthogonal projection onto F of any point in B_\rho(z) lies in F\cap B_\rho(z), since z\in F. Consequently the part of B_\rho(z) within distance r of F is covered by the corresponding ambient radius-2r balls. Equation (38) yields

This includes \ell=0, with a one-point net. Since \alpha-\ell>0, letting r decrease to zero shows that F\cap B_\rho(z) has zero mass.

Every point of B_\rho(z) is within distance \rho of F. Apply (39) on the shells with outer distance r_m=\rho2^{-m} and bound the inverse power there by (2/r_m)^k. Their sum is at most

Here \alpha-\ell-k\ge\alpha-(q-1)-k\ge2, so the series is at most 2. Since \ell\le d/8, \alpha=d/2, and k\le d/8, the remaining constant is at most C^d. This proves (37).□

Proof. Let \mu be the finite Borel measure given by \mu(E)=\int_E h\mathbf1_H\,d\sigma on Borel subsets of the sphere. For \eta>0, let B_\eta^k=\{u\in\R^k:\norm u\le\eta\} and let \operatorname{vol}_k denote k-dimensional Lebesgue measure. Define

The integrand is Borel in (X,y,t), so the parameter integral is Borel in (X,y). We first prove (40) with R_\eta in place of R, uniformly in \eta.

Expand its qth moment at Xz+b by Tonelli’s theorem, using t_1,\ldots,t_q from the q copies of \mu. For a fixed tuple, the columns X(t_j-z) form an array whose k rows are independent centered Gaussian vectors with covariance

If G is nonsingular, their joint density is bounded everywhere by (2\pi)^{-kq/2}(\det G)^{-k/2}. Therefore the probability that all columns belong to the radius-\eta ball about b is at most this bound times \operatorname{vol}_k(B_\eta^k)^q.

The singular tuples have zero \mu^q mass. Indeed, at the first linearly dependent vector t_j-z, the point t_j lies in z+\operatorname{span}(t_1-z,\ldots,t_{j-1}-z), an affine space through z of dimension at most q-1. Lemma 5.2 assigns zero \mu mass to it. The degeneracy set is measurable, and Fubini’s theorem applied at each j proves the claim. For a nonsingular tuple, Gram–Schmidt triangularizes the matrix with columns t_j-z with diagonal entries equal to the successive orthogonal distances. Taking the determinant of its Gram matrix gives

Integrate this product first in t_q, then in t_{q-1}, and so on. For every nonsingular prefix, Lemma 5.2 bounds the next integral by C^dV(h)\rho^{\alpha-k}. The exceptional prefixes have zero product measure by the same degeneracy argument. It follows that the integral of (43) is at most (C^dV(h)\rho^{\alpha-k})^q. The ball volumes cancel in the moment expansion, and the Gaussian prefactor is at most one. Thus

for every \eta>0 and every fixed b.

Now choose the function once and for all:

It is jointly Borel. To see that it is a density, fix a full-row-rank X. Set D=(XX^{\mathsf T})^{1/2} and P=D^{-1}X, so D is invertible, P has orthonormal rows, and X=DP. Lemma 2.1 makes P_\#\sigma absolutely continuous, and the invertible map D preserves absolute continuity. Since \mu\le\sigma, the pushforward X_\#\mu is also absolutely continuous. The Lebesgue differentiation theorem [15, Theorem 1.6.19], applied to its L^1 density, shows that (44) equals that density almost everywhere in y. A Gaussian X has full row rank almost surely, since each successive Gaussian row avoids the span of the preceding rows.

For each fixed b, the identity R(X,Xz+b)=\liminf_m R_{1/m}(X,Xz+b) holds by the definition of the single function R. Fatou’s lemma [15, Corollary 1.4.47] over X now gives (40). These are separate moment statements for each deterministic b; no simultaneous almost-sure bound in X over all offsets is asserted. Finally, if \norm{y-Xz}>\norm X_{\mathrm{op}}\rho, then every Xt with t\in H is at distance at least \norm{y-Xz}-\norm X_{\mathrm{op}}\rho>0 from y. The averages in (42) are eventually zero, proving (41).□

Proof. Lemma 2.3 gives \int h\,d\sigma\le\epsilon^{d-1}, also for a randomized output law. For any ambient center z, use h\le1 and (36) inside B_\epsilon(z). Outside that ball, bound the kernel by \epsilon^{-\alpha} and use the total mass bound. The sum is at most C^d\epsilon^{d-1-\alpha} uniformly in z, proving (47).□

Proof. For each successor w, use the particular density R_w(X,y) of Lemma 5.3 for the measure h_i(w,\cdot)\mathbf1_{H_\rho(z)}\,d\sigma. Tonelli’s theorem, (46), and pushforward integration give

The pushforward identity used in the first inequality holds for every full-row-rank X, hence almost surely. The second inequality uses the probability-vector property of K^{(i)} and (41).

We need a deterministic integration region after averaging over X. Choose a sufficiently large absolute D_0 and partition the matrices into

These bins obey

For completeness, take 1/4-nets on the unit spheres of \R^d and \R^k. A maximal separated set has at most 9^d and 9^k points, respectively, by the disjoint-ball volume argument. Approximating each unit vector by its net point incurs an error at most \norm X_{\mathrm{op}}/2 in a bilinear form. Hence \norm X_{\mathrm{op}} is at most twice the largest absolute bilinear form on the two nets. Each such form is standard Gaussian, so its elementary tail bound and a union bound give

Putting t=D_0(j-1)\sqrt d proves (50) after increasing D_0, since k\le d/8.

For every deterministic b\in\R^k, Hölder’s inequality and (40) give

No conditional version of the density lemma is being used: Hölder’s inequality pays for the bin event. For a fixed matrix in E_j, translate y=Xz+b in (49); the remaining region is \norm b\le D_0j\sqrt d\,\rho. Joint measurability permits Tonelli’s theorem to integrate (52) over this deterministic ball.

The volume of that ball is at most C^d j^k\rho^k. Indeed, the unit-ball bound (2) gives v_k\le(2\pi e/k)^{k/2}. Since d/k\le16, v_k(D_0j\sqrt d\,\rho)^k\le C^d j^k\rho^k. Also, by q\ge2 and (50),

For the last bound use k\log j\le(d/8)(j-1)^2 for j\ge2 and sum the resulting geometric upper bound. Combining the volume and bin estimates with (49) proves (48). The powers of the shell radius cancel exactly:

□

Proof of Proposition 5.4. Outside B_\epsilon(z) use the shells

For every ambient z, at most C(1+L) of these meet the sphere. If \norm z\le3, all distances are at most 4, giving at most \lceil\log_2(4/\epsilon)\rceil nonempty shells. If \norm z>3, the distances lie between \norm z-1 and \norm z+1, whose ratio is less than 2; only a bounded number of dyadic shells can then meet that interval.

Inside B_\epsilon(z) use h_{i-1}\le1 and (36). On each remaining shell use Lemma 5.6. Taking the supremum over z and the maximum over v gives

Choose C_0 large enough that the first term here and the terminal value V_N are at most B in (45), and that the second coefficient is at most J-1. With U_i=\max\{V_i,B\}, equation (53) gives U_{i-1}\le J U_i, while U_N=B. Hence V_0\le BJ^N, also when N=0.

At z=0 the kernel in (34) equals one on the unit sphere, so \int h_0(v,s)\,d\sigma(s)\le V_0 for each initial state. For almost every fixed shared seed, averaging over its conditional initial-state law preserves the bound, because that law is independent of the signal and rows. Averaging the original conditional success probabilities over the seed then preserves it again. This proves (45).□

Proof of Theorem 2.4 by the Riesz method. There is a useful bound that counts possible terminal tags. For fixed rules as above, write p_{\mathrm{succ},\mathrm{rule}} for the conditional success probability. For a tag a, let f_a(s) be the probability of reaching it given s, and let g_a(s) be its output law’s success probability. This output law depends only on the tag, and 0\le f_a\le1. Lemma 2.3 gives \int g_a\,d\sigma\le C^d\epsilon^{d-1}, including a randomized output law. Sum over at most W tags to obtain

The right side is independent of the chosen rules, so averaging also gives p_{\mathrm{succ}}\le W C^d\epsilon^{d-1}.

Write L=\log(1/\epsilon). If T\ge dL, the conclusion already holds. In the remaining case T<dL, assume p_{\mathrm{succ}}\ge2/3. Taking logarithms in the averaged form of (54) gives

For the given memory sequence, eventually M\le d^2. Since L\ge\log10 and T<dL, we also have

for large d. It follows that (d-2)L\le d^2\log2+d\log C+\log(2d)+\log(3/2). Consequently, only in this remaining case,

Thus the multiplier from Proposition 5.4 obeys

using q\ge d/16. In particular the shell-count term has been bounded rather than removed.

Now (45) and p_{\mathrm{succ}}\ge2/3 imply

because N=\lceil T/k\rceil\le16T/d+1. The common full-data bound, Lemma 2.7, gives T>d/8; hence the additive d on the right of (56) is at most 8T. For d\ge4 the left coefficient is at least d/4, so T\ge c\,dL for an absolute c>0. This combines with the case T\ge dL already separated.□