Localization costs and information growth for exact Gaussian observations

Proof. At a fixed state and index, combine continuation and stopping choices into one finite set of tagged destinations. Choose Borel versions of their completed-measurable coordinate probabilities. Such versions exist: measurable simple approximations may have each of their countably many level sets replaced by a Borel set modulo a null set. Outside a Borel \lambda-null set the versions agree with the original coordinates and form a probability vector. On the exceptional set use a fixed point mass. This gives nonnegative Borel coordinates whose sum is one everywhere.

There are finitely many states and indices, so a single Borel \lambda-null set contains every modification. Pregenerate all sample pairs through the horizon, including pairs ignored after stopping. Each of their unconditional marginals avoids this null set by the hypothesis on P. A finite union over indices therefore shows that no modified pair occurs almost surely. This argument uses the unconditional pair law; it does not require a positive density after conditioning on a state selected from past samples.

Couple the old and new finite kernels by the same fresh uniforms. Induction gives identical state paths and stopping decisions almost surely. At an identical terminal state and index the output laws are unchanged and can be coupled identically. This proves the joint-law claim.□

Proof. For fixed x\ne0, rotational invariance makes \langle x,S\rangle/\|x\| the first coordinate of a uniform spherical point. Its density on (-1,1) is proportional to (1-t^2)^{(d-3)/2}; this also is integrable for d=2. For example the formula follows by writing the point as a normalized standard Gaussian and separating its first coordinate from the remaining squared length. Thus the conditional label law has a Lebesgue density for every nonzero x. Fubini, discarding x=0, proves the first assertion.

For a chart put f_x(z)=\langle x,\phi(z)\rangle. At every regular z, the set of x with \nabla f_x(z)=D\phi(z)^{\mathsf T}x=0 is a proper linear subspace and has Gaussian measure zero. Fubini shows that for Gaussian-almost every x, the critical set of f_x has Lebesgue measure zero in the cube. Around every other interior point, choose a coordinate in which a partial derivative is nonzero. The inverse function theorem makes f_x, together with the remaining coordinates, a C^1 local coordinate system. In each such neighborhood the preimage of a Lebesgue-null subset of \R has zero q-dimensional volume, by Fubini and change of variables. A countable cover of the regular set proves absolute continuity of the label pushforward. The critical set and cube boundary are null. Integrating over x proves the second assertion.□

Proof. For 0<r\le1, a chordal cap about u has angular radius \theta\le\pi/3, \sin\theta\le r, and \cos\theta\ge1/2. Its normalized area is

The numerator is at most 2r^n/n after substituting w=\sin v; the denominator is at least 2/n, since \int_0^{\pi/2}\sin^{n-1}v\,dv \ge\int_0^{\pi/2}\sin^{n-1}v\cos v\,dv=1/n. For r\ge1 the same bound is trivial. An ambient ball meeting the sphere is contained, on the sphere, in a radius-2r ball about any point of its intersection, proving the second bound.

The row span of X has dimension T almost surely. Its labels specify the row-space projection of S. Conditional on the rows and labels, the remaining component is uniform on its sphere in \ker X, with radius R=\|P_{\ker X}S\|. To see this, write S as a normalized standard Gaussian and separate its independent row-space and nullspace components; the direction of the latter is independent of both lengths and of the former component.

When R>r_0>\epsilon, the set of residual directions that place the signal within \epsilon of a fixed estimate cannot contain both members of any antipodal pair. Its conditional mass is at most 1/2, including after averaging the estimate’s independent randomness. Finally, \E\|P_{\operatorname{row}X}S\|^2=T/d by rotational invariance. Markov’s inequality applied to \|P_{\operatorname{row}X}S\|^2=1-R^2 proves (3).□

Proof. On Q_0, \|z\|\le1/2, so the gradient of \sqrt{1-\|z\|^2} has norm at most 1/\sqrt3. This proves the Lipschitz bound; the cell formulas follow from the side length and normalized cube volume. Angular error at most \epsilon implies chordal error at most \epsilon, so the first n coordinates lie in the radius-\epsilon ball about the projection of v. Its normalized cube volume is at most n^{n/2}v_n\epsilon^n. The Gaussian integral on the radius-\sqrt n ball gives v_n\le(2\pi e/n)^{n/2}, proving the claim.□

Proof. We first derive a tube bound from (6), then estimate a smoothed projection by expanding its mth moment. Finally we pass to the exact measure. The replica expansion and Gaussian orthogonalization have a close predecessor in [12, Section 7, Lemma 12]; the weighted multirow estimate and the exact-measure passage are proved here.

For every affine q-plane V\subset\R^d with q\le m-2, we claim

Projection onto the first n coordinates shows that every such z lies within \delta r of the projection of c_Q+rV. Only the part of that projected plane within 2r of the center of Q is needed. A maximal \delta r-separated subset of that part has at most (C/\delta)^q points, by volume comparison in the plane. Balls of radius 2\delta r about these points cover all relevant z.

Choose l\ge0 so that 2^{-l}\le\delta<2^{-l+1}. Each covering ball meets at most C^n level-(J+l) cells. Indeed those cells are disjoint, have side greater than \delta r/(2\sqrt n), and lie inside a ball of radius 3\delta r. If v_n is the volume of the unit ball in \R^n, the estimate v_n\le(2\pi e/n)^{n/2} gives the claimed count; the powers of \sqrt n cancel. Each such cell has mass at most B2^{-\alpha nl}\le B\delta^{\alpha n}, proving (8).

By Cauchy–Schwarz, \nu has mass at most one. For \eta>0 define

This is smoothing in the label variable only. Expanding its mth power introduces points z_1,\ldots,z_m. Put a_i=a(z_i), define D_i for 2\le i\le m, and set

The exponent in (8) is positive. Thus each affine span in this display has zero \mu-mass and zero \nu-mass. Almost every tuple is affinely independent, and Gram–Schmidt gives V_*=\prod_{i=2}^mD_i.

The intersection of the m smoothing boxes has volume at most (2\eta)^k and is empty unless \|X(a_i-a_1)\|_\infty\le2\eta for every i\ge2. For a fixed affinely independent tuple, one row of these differences is Gaussian with covariance \mathsf D^{\mathsf T}\mathsf D and maximum density (2\pi)^{-(m-1)/2}V_*^{-1}. The k rows are independent. Bounding the probability of the difference box by its volume times this maximum density, and using Tonelli’s theorem, yields

All powers of \eta have canceled. We now bound the right-hand side uniformly over the preceding points in each affine span.

Put \gamma=\alpha n-(m-2). Cauchy–Schwarz and (8) give, for each fixed preceding tuple,

The chosen k,m satisfy \gamma/2-k\ge n/8. Integrating the tail of D_i^{-k} therefore gives

Integrate z_m,z_{m-1},\ldots,z_2 in this order in (9); the remaining z_1 integral has mass at most one. Taking the mth root gives

To recover exact labels, let \psi be continuous and compactly supported in the variables (X,u). Averaging \psi over a shrinking box and applying bounded convergence shows

Hölder’s inequality bounds this limiting functional by C^dB^{1/2}\|\psi\|_{m/(m-1)}. Continuous compactly supported functions are dense in L^{m/(m-1)}(P_Xdu). Duality supplies an L^m density with that bound. Agreement on continuous compactly supported tests identifies the two locally finite Borel measures. This proves (7) for the exact joint law, so it can be tested against arbitrary measurable message rules.□

Proof. Keep the normalization X\phi(z)=Xc_Q+rXa(z) from Section 3.1. Let L=\{u\in\R^k:\|u\|\le4\sqrt k\}. Since \|a(z)\|\le2,

uniformly in z. For example, if G is standard Gaussian in \R^k, then \E e^{\|G\|^2/4}=2^{k/2}, and Markov’s inequality at \|G\|>2\sqrt k proves this with c=1-\tfrac12\log2. Also |L|=v_k(4\sqrt k)^k\le C^k.

Define the subprobabilities

For a reference experiment, keep X Gaussian and replace the normalized exact label Xa(z) by an independent uniform point in L. Its message probabilities are

They satisfy \sum_wb_w=1. This uses the probability-kernel identity at every label, including labels outside the support of the observation law. Test Lemma 3.3 with \pi_w(X,Xc_Q+ru)\ind_L(u). Because 0\le\pi_w\le1, Hölder’s inequality gives, for every \|h\|_2\le1,

Duality in L^2(\mu) consequently gives

We next turn this into information without assuming that the posterior is uniform. Adjoin the bit G=\ind_{\{Xa(Z)\in L\}} to W, which can only increase mutual information. Put P_w=\int p_w\,d\mu and P_g=\sum_wP_w. For P_w>0, Jensen’s inequality under the probability measure p_w\mu/P_w gives

Thus the contribution from G=1 to I(Z;W,G) is at most

If b_w=0, then (12) gives P_w=0, and the corresponding terms vanish. The log-sum inequality and the entropy bound for N outcomes give

The good contribution is therefore at most 2\log A+(2/m)\log N-2P_g\log P_g.

For G=0, let q_w(z) be the corresponding conditional subprobability and Q_w=\int q_w\,d\mu. Since q_w\le1,

where P_b=1-P_g\le e^{-ck} by (11). The functions -P_g\log P_g and -P_b\log P_b are bounded by absolute constants. Finally 2\log A\le Cd+\log B, proving (10).□

Proof. For every measurable set A, the posterior satisfies \lambda(A)\le\mu_0(A)/p. A heavy cell at relative depth j therefore satisfies

Since 1-\alpha>0, this bounds j. The parent cell is heavy, so each path has a deepest heavy cell. There are only finitely many cells at the relevant levels, and all selection events are measurable.

Fix a selected cell R at relative depth j, and let R' be a strict descendant at further depth l. If R' is heavy, the event \{U=R\}\cap R' is empty: any point of R' has a deeper heavy ancestor. If R' is not heavy, then \lambda(R')<2^{-\alpha n(j+l)}. In either case,

At depth zero the bound follows from B_R\ge1. Notice that this uses the probability p_R of selection; replacing p_R by \lambda(R) would condition on a different event.

At depth j, there are at most K_j=2^{\alpha nj} heavy cells, because their posterior masses sum to at most one. The entropy chain rule and the bound on the number of choices at each depth prove (13). Comparing the depth distribution with the geometric distribution 2^{-(j+1)}, nonnegativity of relative entropy gives (14).

For the remaining estimate, write \log^+x=\max\{0,\log x\} for x>0. Let P_j=\Prob(j(U)=j) and, on a level of positive mass, set \rho_R=p_R/P_j. There are at most K_j possible cells on that level. Consequently, for u\ge0,

Indeed every cell in this event has conditional mass less than e^{-u}/K_j, and there are at most K_j of them. Integrating the tail shows that this positive logarithm has conditional expectation at most one. Since

averaging over the levels proves (15).□

Proof of Theorem 3.2. Start with \Pi_0 empty, Q_0 as above, J_0=0, and B_0=1. After observing W_i, put \Pi_i^-=(\Pi_{i-1},W_i). Apply Lemma 3.5 to this history and the parent Q_{i-1}. Let Q_i be the selected cell, j_i its relative depth, and J_i=J_{i-1}+j_i. Set \Pi_i=(\Pi_i^-,Q_i), and let B_i be the constant supplied by that lemma.

Only positive-probability histories matter. Each history has a finite range by induction: the message range is finite, and each intermediate history permits finitely many selected cells by Lemma 3.5. Thus every entropy below is finite. Fresh rows remain independent of Z conditional on the past, because all past messages and revelations depend only on Z, past data, and independent past randomization. The rule for W_i, conditional on this enlarged history, is an admissible kernel for Lemma 3.4; the extra cells are analysis variables and do not change the original rule.

Let h_i=H(j_i\mid\Pi_i^-), including the average over intermediate histories. The alphabet hypothesis and Lemmas 3.4 and 3.5 give

The selection is deterministic from (Z,\Pi_i^-), so

Summing the information chain rule, using B_0=1 and \sum_i j_i=J_t, yields

The 2 in the depth coefficient accounts for the depth entropy at selection and for its use in the next block’s concentration factor.

For a fixed terminal history, its posterior \lambda is supported in its level-J_t cell Q_t. Writing \mu_0(\,\cdot\mid Q_t) for normalized restriction to this cell gives the exact identity

Nonnegativity and averaging imply

Combining (16) and (17), and using (1-\alpha)n-2\ge n/4 for large n, proves \E J_t\le Ct. Substitution into (16) proves (5).□

Proof of Corollary 3.6. First average the success guarantee over s=\phi(Z), Z\sim\mu_0. Fix the shared rule-selection randomness, if present, with cube-prior average success greater than 3/5; such a choice exists because the original average is at least 2/3. The chart has full-rank derivative because its first n coordinates are z, so Lemma 2.2 applies. Apply Lemma 2.1 to these fixed rules. Now expose all remaining independent randomness and fix a realization with prior-average success at least 3/5. Finite transition and stopping kernels can be sampled using independent uniforms indexed by state and sample index. Output laws can likewise be sampled in advance for each terminal state and stopping index. The resulting deterministic learner has the same state bound, and its output is a function of its terminal state and stopping index.

Divide its horizon into t=\lceil T/k\rceil blocks. Pregenerate all k rows in every block, including an unused final suffix. A block message records one of the following: the continuing state; a terminal state together with the local stopping offset; or a dummy value if the learner was already inactive. Allowing offsets at the block endpoints and immediate stopping, it suffices to use

The transcript determines the global stopping index from the block index and local offset. Conditional on its past, the starting state is known, and composing the transitions gives a measurable rule of the whole exact block. Thus Theorem 3.2 applies. Eventually M\le d^2, so (18) gives \log N\le Cd^2 and hence (4) with an absolute C_0.

We next lower-bound the information needed for accurate estimation. For a fixed unit vector v, angular error at most \epsilon implies \|\phi(Z)-v\|\le\epsilon, and hence \|Z-P_{\R^n}v\|\le\epsilon. The normalized cube volume of this event is at most

Let p\ge3/5 be the success probability for the fixed learner and the cube prior. Under the product of the marginal laws of (Z,\widehat s), the same success event has probability p_0\le(5\epsilon)^n. Relative-entropy data processing to its binary indicator gives

For \epsilon\le1/10,

Since the output is determined by the messages, data processing and Theorem 3.2 imply t\ge c\log(1/\epsilon) for large d.

It remains to remove the ceiling in t=\lceil T/k\rceil. Return to the original randomized learner and average its every-signal success over a uniform spherical signal. The T>d/8 instance of Lemma 2.3 applies to this same learner and prior; it grants the entire stream and therefore includes early stopping. This step does not infer cube-prior success from a sphere-average premise. Thus T/k\ge1, \lceil T/k\rceil\le2T/k, and k\ge c'd for large d. The block lower bound gives T\ge c''d\log(1/\epsilon), as required.□

Proof. The score at depth zero is one. Every score at depth j is at most

which tends to zero uniformly in z. Hence a maximum is attained among finitely many depths. The first such depth is measurable because each score is constant on Borel cells and there are countably many score comparisons. Comparing its score with one proves the stated bound on J.

Let E_{j,B}\subseteq B be the actual selection event, of \pi-mass p. Comparison with the depth-zero score gives \pi(B)\ge2^{-\beta j}. If a further subcell B'\subseteq B of relative depth m has positive posterior mass after selection, it meets E_{j,B}. The maximizing inequality at such a point implies \pi(B')\le2^{-\beta m}\pi(B). Its new posterior mass is therefore at most p^{-1}\pi(B')\le e^{a'}2^{-\beta m}; if it has zero selected mass, the same bound holds. Since p\le\pi(B), the slack is nonnegative.

For fixed j, let p_B be the probabilities of its cell outcomes and p_j=\sum_Bp_B. These B’s are disjoint at one grid level, so \sum_B\pi(B)\le1. The log-sum inequality then gives

Summing over j proves \mathbb E a'\le H(J). Comparison of the law of J with the probability vector (2^{-j-1})_{j\ge0}, by nonnegativity of relative entropy, gives H(J)\le(1+\mathbb EJ)\log2. These quantities are finite because J has the displayed finite bound. Finally

Averaging proves (22).□

Proof. Let z_c be the center of C and s_c=s(z_c). The radius of C is r/2, so its graph image lies in B(s_c,r). For 0<h\le r, choose j\ge0 with r2^{-j}\le h<2r2^{-j}. A depth-(i+j) cell meeting the first-coordinate projection of an ambient ball of radius h lies in the concentric n-ball of radius 3r2^{-j}. These cells have disjoint interiors and volume (r2^{-j}/\sqrt n)^n. The unit-ball volume estimate v_n\le(2\pi e/n)^{n/2} therefore bounds their number by C^n, for an absolute C, by the Gaussian-integral proof in Lemma 3.1. By (20),

After increasing C, this bound also holds trivially when h>r.

If P has dimension m\le\ell, the projection of B(s_c,r) onto P is contained in an m-ball of radius r. A maximal h-separated set in that ball has at most (1+2r/h)^m points: its disjoint radius-h/2 balls fit inside the concentric ball of radius r+h/2. Ambient balls of radius 2h about these centers cover points of B(s_c,r) at distance at most h from P. Applying the ball bound and absorbing the covering constants gives, for C_2 absolute,

The estimate also shows that P has zero \mu-mass.

Suppose f>0, and put \theta=k/(\beta-m). Since m\le\ell=k\le n/8, we have \theta\le1/3. For t\ge1, the \mu-mass within F where (r/\operatorname{dist}(s(z),P))^k>t is at most \min\{f,Kt^{-1/\theta}\}. Integrating this tail and splitting at t=(K/f)^\theta\ge1 gives

Here K\ge1, 0<f\le1, and \theta\le1/3 justify the last inequality. This proves (23).

Let \nu_A be the image of \mu|_F under z\mapsto As(z). If F is measurable only in the completion, replace it by a Borel representative modulo \mu, which leaves the restricted measure unchanged. For h>0, write v_k for the volume of the unit ball in \mathbb R^k and define its ball-average density

Expand the \ellth power using z_1,\ldots,z_\ell integrated against (\mu|_F)^{\otimes\ell}, and put s_j=s(z_j). The intersection of the balls B(As_j,h) has volume at most v_kh^k, and is empty unless \|A(s_j-s_1)\|\le2h for all 2\le j\le\ell. For a fixed tuple, condition successively on the preceding difference images. Orthogonal decomposition of each Gaussian row shows that the conditional image at step j has an independent centered residual with covariance \operatorname{dist}(s_j,P_j)^2I_k, where

The subspace bound makes all zero-distance tuples null. On every remaining tuple, the conditional probability of a radius-2h ball is at most

Multiplying these bounds, dividing by (v_kh^k)^\ell, and including the intersection volume cancels every h and v_k factor. Integrating z_\ell,\ldots,z_2 in this order and applying (23) at each step leaves the factor \mu(F)=f for z_1. Absorbing the numerical Gaussian and radius factors into C_3^k proves

uniformly for h>0.

For every continuous compactly supported test function on the matrix and label space, integrals against these ball averages converge as h\downarrow0 to its integral against the exact joint image measure. This follows by averaging translations of the test function over a shrinking ball and then using bounded convergence. Hölder’s inequality bounds the limiting functional on L^{\ell/(\ell-1)}(\gamma_{k,d}(dA)\,db) by the \ellth root of the last display. Continuous compactly supported tests are dense for this locally finite reference measure. Extension and L^p duality therefore give a jointly measurable representing density with (24); equality on these tests identifies it with the exact image measure and makes it nonnegative. Finally, testing the joint identity on a countable algebra of rational label boxes and arbitrary measurable matrix sets identifies the conditional density for almost every A. The averaging operation has only proved a statement about exact labels; it is absent from the observation rule.□

Proof. Write q_u(A,b) for the kernel probabilities, so that q_u\ge0 and \sum_uq_u=1. With the center s_c used above, define

For each fixed Z, the vector A(s(Z)-s_c) is Gaussian with covariance at most r^2I_k. Hence

by Markov’s inequality and \mathbb E\exp(\|G\|^2/4)=2^{k/2} for standard Gaussian G\in\mathbb R^k. Define comparison probabilities

These probabilities use an auxiliary label uniform on the displayed ball, independently conditional on A.

For a measurable F of mass f, apply Hölder to its exact joint density v_F and the function q_u(A,b)\mathbf1_{\{\|b-As_c\|\le3r\sqrt k\}}. Since 0\le q_u\le1, its conjugate norm is at most (V\lambda_u)^{1-1/\ell}. Lemma 4.2 therefore gives

The r powers cancel. The exact exponent of f is

Because f\le1, it may be weakened to 2/3. The exponent of K is (\ell-1)/(3\ell)\le1/3. Thus, for an absolute C_4\ge1,

Put p_u=\Pr(U=u,E). For p_u>0, let \nu_u=\mathcal L(Z\mid U=u,E) and f_u=d\nu_u/d\mu. Applying (28) with F=C shows that

in particular \lambda_u>0. Since \mu\{f_u>e^t\}\le e^{-t}, a second application to that set gives

Integrating this upper bound gives \tfrac32(\log D_u^*+1). Relative entropy is no greater than the expected positive part of the log density, so

This calculation is why the a/3 in L_0 becomes a/2.

Let p_E=\sum_up_u. The log-sum inequality and the entropy bound for at most W letters give

The identity

therefore bounds the weighted sum of these log ratios by 1+(\log W)/\ell. All zero terms are omitted. For the outcomes (U,E^c), their weighted divergences to \mu sum to at most

Indeed, conditioning first on E^c multiplies the density by at most 1/p_{E^c}, and revealing U afterwards adds at most its conditional entropy. This bound is zero when p_{E^c}=0.

The mutual information of the finite pair (U,\mathbf1_E) is the sum of these good and bad weighted divergences. Combining the last bounds with (29) gives

Here (\log W)/\ell=O(d) and e^{-k}\log W=O(1) in the stated width range. Absorbing the absolute terms proves (27).□

Proof. First fix a realization of a data-independent shared seed, if present. The graph derivative contains the identity in its first n rows, so Lemma 2.2 applies to the cube prior. For this fixed seed, Lemma 2.1 supplies everywhere-defined Borel rules with the same prior law. We do this separately for each seed value under consideration; no jointly chosen family of Borel versions is needed. Use the initial finite state as \mathcal H_0. By the joint independence of the shared seed and initial state from the signal and all rows in Section 2, conditional on the fixed seed this state has zero information about Z, and the future rows remain independent of both. At an active block end record the continuing state or the terminal state and its stopping position within the block, including immediate stopping. Given the preceding history there are at most (k+2)2^M such destinations. After a stop, later messages may be dummy messages because the earlier history already records the terminal state and index. Padding the last block by ignored Gaussian rows is harmless. This count depends only on the block length, not the total horizon.

Start at depth i_0=0 with slack a_0=0. At step t, apply Lemma 4.3 to its outgoing message U_t. Then apply Lemma 4.1 to the posterior given \mathcal H_t^-=(\mathcal H_{t-1},U_t), and append its selection (J_t,B_t) to form \mathcal H_t. The new depth is i_t=i_{t-1}+J_t, and its slack is a_t. The added labels use only Z and the history already observed. Future Gaussian rows remain independent of that joint collection. Given the starting state, the message is a kernel of the fresh block data, so the block lemma applies on every positive-probability history.

Every such history of probability P has posterior at most \tau/P. All entropies used below are finite. Indeed a block message has a finite alphabet, and the depth bound in Lemma 4.1 is integrable after averaging over the preceding history because it is bounded by a constant times \log(1/P). The label-charge inequality then preserves finite history entropy by induction.

The information chain rule, followed by (21) and (22), gives

for an absolute C_5. On the other hand the final posterior is supported on a depth-i_N cell, of prior mass 2^{-ni_N}. Relative entropy to \tau is therefore at least ni_N\log2, since the conditional divergence to the uniform law of that cell is nonnegative. Averaging yields

The ratio (\beta+3/2)/n=1/2+3/(2n) is bounded away from one for large n. Substituting the last bound into the preceding upper bound and moving that term to the left proves I(Z;\mathcal H_N)\le C_6dN.

The history records the terminal state and stopping index. Conditional on those data, the output uses only fresh randomness, so data processing gives I(Z;\widehat S)\le I(Z;\mathcal H_N). For each fixed seed, Lemma 2.1 preserved the original conditional prior law, so the output-information bound just proved holds for that original law. Integrating the original measurable conditional information values over a shared seed R, whose law is independent of Z, gives

When T=0, the same argument has no blocks and the output is independent of Z. This proves the stated zero upper bound as well.□

Proof. At an attempt, consider the current conditional law in its current cell. A strict descendant E of relative depth h\ge1 is heavy if its current mass m_E exceeds 2^{-\alpha nh}. Select the heavy descendants with no heavy strict ancestor of positive relative depth. Every heavy cell has such a first heavy ancestor, because its chain of ancestors back to the current cell is finite. The selected cells are a countable disjoint family.

If W is in one of these cells, reveal which cell, condition on it, replace the current cell by it, and begin another attempt. Otherwise reveal that W is in the complement, whose current probability is q, condition on that complement, and keep the current cell. Stop if q\ge1/2; if 0<q<1/2, begin another attempt. Zero-probability branches are omitted. These operations are Borel and the label records their finite sequence if the procedure stops.

At a stop, a descendant that was heavy immediately before the last complement decision lies in a selected cell, so it has zero posterior mass. Every other descendant of depth h had mass at most 2^{-\alpha nh}, and conditioning on a complement of probability at least 1/2 increases this by at most two. The resulting law is therefore regular.

It remains to prove that a stop occurs and that its cost satisfies (34). Let f be the density of the current law relative to the uniform probability on the current cell. On a heavy transition of depth h, its value at the sampled point changes to

Its logarithm therefore decreases by at least (1-\alpha)nh\log2. On a complement transition it increases by \log(1/q). These are exact density updates on every positive-probability branch, with all previous complement exclusions retained in the conditional law.

Truncate after N\ge1 attempts, freezing a path once it has stopped. Let H_N be accumulated heavy depth, J_N the sum of complement logarithmic increases, and A_N the number of attempts actually made. If f_N is the resulting conditional density, the pathwise updates give

For an active attempt the conditional expected complement increase, counted as zero on a heavy branch, is q\log(1/q)\le1/e. Thus

We justify taking expectations of the logarithms before using (35). For any density f relative to a probability measure \lambda,

because x\log(1/x)\le1/e for 0<x<1. This bounds the expected negative log part at the sampled point, conditionally on each positive-probability history. Finite K_0 then makes the positive part of \log f_0(W) integrable. The path inequality bounds the positive part of \log f_N(W) by (\log f_0(W))^++J_N. Consequently \mathbb E\log f_N(W) is well defined and is the expected conditional relative entropy, hence is nonnegative. Taking expectations in (35) first shows \mathbb EH_N<\infty.

An attempt after the first follows a heavy transition or a continuing complement. The number of heavy transitions is at most H_N, because each adds at least one unit of depth. At each active attempt, the conditional probability of a continuing complement is at most 1/2. Counting such predecessors and taking expectations gives

Substituting \mathbb EJ_N\le\mathbb EA_N/e into the expected path inequality now yields

For sufficiently large n, the coefficient is at least bn=(1-\alpha)n(\log2)/2. Hence the expectations of H_N and, by (36), A_N, are bounded uniformly in N.

Both sequences increase on every path. Monotone convergence gives finite expectations for their limits H,A_*, and preserves \mathbb EA_*\le2(1+\mathbb EH). A path that never stops has A_N\to\infty, so nontermination has probability zero. The possible terminating histories form a countable set of finite sequences.

The limiting complement sum J also satisfies, by monotone convergence,

At termination the positive log part of the final density is integrable by the path inequality, and its negative log part is integrable by the conditional bound above. We may therefore take expectations directly in the terminating path inequality. This gives

which implies (34). In particular, no passage of a signed logarithm through a limit is being used.□

Proof. The cell diameter is 2^{-j}; the 2-Lipschitz property gives the stated support radius. For r\le R/2, choose h\ge1 with r\le R2^{-h}<2r. The depth-(j+h) cells have side between r/(2\sqrt n) and r/\sqrt n, and diameter at most r. A ball test for the graph image restricts w to a ball of radius r in its first n coordinates. Every cell meeting that ball lies in the concentric ball of radius 2r. Comparing disjoint cell volumes and using the unit-ball estimate from Lemma 3.1 gives at most

such cells. Each has P-mass at most 2\,2^{-\alpha nh}. Since 2^{-h}<2r/R and \alpha n=(d-1)/2\ge d/3=\beta d, all factors are bounded by C_0^d(r/R)^{\beta d} for an absolute C_0. For R/2<r\le R, enlarge C_0 and use total mass one.□

Proof. Let F be an affine subspace of dimension m\le p-2. For 0<r\le R, a maximal r-separated set in the projection of B(z,R) onto F has at most (5R/r)^m points, by packing disjoint radius-r/2 balls. Ambient balls of radius 2r at these centers cover the part of B(z,R) at distance at most r from F. If 2r>R, the trivial mass bound can replace the local bound at that radius, whose right side would already be at least one. Since \beta d-m\ge\gamma d, absorbing the covering constants gives

In particular F has zero \nu-mass. Set r_0=R e^{-(a+C_1)/\gamma}. Layer-cake integration, using total mass at most one above the cutoff r_0, gives

The last inequality uses k\le\gamma d/2.

Choose a continuous nonnegative probability density \varphi_\eta supported in B(0,\eta)\subseteq\mathbb R^k, and define

For \nu^{\otimes p}-almost every tuple s_1,\ldots,s_p, the differences s_i-s_1, 2\le i\le p, are linearly independent: at the ith step, the preceding affine span has dimension at most i-2\le p-2, so it is null by (40). For such a tuple put D=[s_2-s_1,\ldots,s_p-s_1]. The joint Gaussian vector of its images under A has density at most

The determinant factorization is Gram–Schmidt.

Expand g_\eta^p, shift the label integration variable by As_1, and integrate over the Gaussian difference images. Bounding their density by the displayed supremum leaves a product of p probability kernels. Its integral over the p-1 difference variables and then the shifted label variable is one. Tonelli’s theorem and successive integration of s_p,\ldots,s_2, using (41), therefore give

the last variable contributes \nu(\mathbb R^d)\le1.

For a continuous compactly supported test function v(A,y), integration against g_\eta converges to \int v(A,As)\,d\rho(A)d\nu(s) as \eta\downarrow0. Shrinking support and bounded convergence prove this for the finite measure \nu. Hölder bounds the limiting functional on L^{p/(p-1)}(\rho(dA)\,dy) by B^{(p-1)/p}. Density of continuous compactly supported tests and L^p duality give a representing density with that norm. Equality on those tests identifies it with the exact image measure, so a nonnegative version may be used. This proves (39). The auxiliary kernels have been removed before any message is formed.□

Proof. For each positive-probability letter let p_u=\Pr(U=u) and \ell_u(w)=\Pr(U=u\mid W=w). Its posterior density relative to P is \ell_u/p_u. Set

Since this density integrates to one, P(B_u)\le\lambda. Outside W\in B_U, the log posterior density is at most d. We will show that \Pr(W\in B_U) is exponentially small in d, and then bound its contribution using the finite alphabet.

Use z,R from Lemma 5.3. The exact joint law of (A,Y) has a density D(A,y) by Lemma 5.4 with a=0. The graph image of \lambda^{-1}P|_{B_u} has mass at most one and satisfies the ball hypothesis with multiplier e^d, namely with a=1. Let g_u(A,y) be its exact projection density from Lemma 5.4. Under the original experiment,

almost surely. This is the Radon–Nikodym ratio of the restricted joint measure to the original one; points where D=0 have zero original probability.

To control this ratio, choose an absolute C_2>2\sqrt{2\pi e} and define

For every fixed s in the support, A(s-z) is centered Gaussian with covariance at most R^2I_k. Markov’s inequality with exponential parameter 1/4 gives

The label ball of radius 2\sqrt kR has volume at most (2\sqrt{2\pi e}R)^k. The probability of points inside it where D<(C_2R)^{-k}, after integrating over A, is at most (2\sqrt{2\pi e}/C_2)^k. Thus

for some absolute c_2>0.

Let p=\lfloor\beta d/2\rfloor. On G, the density denominator is bounded below, so

where

is valid because k\ge1. Choose the fixed c_*>0 so that

Then the projection lemma applies and the last moment is at most e^{-3dp/4} for all sufficiently large d.

Given (A,Y), the conditional independence assumption lets us average the choice of U separately from the event W\in B_u. Consequently

The pth power of the maximum is at most the sum of the pth powers. Since \log m_d\le dp/4 eventually, Hölder and (44) bound this probability by e^{-d/2}. Also k\ge c_*d/2 eventually, so (43) yields

after decreasing an absolute c_3>0 and increasing the dimension threshold.

For q_u=\Pr(U=u,W\in B_u)\le p_u, the contribution of the event W\in B_U to \mathbb E\log(\ell_U(W)/p_U) is at most

The last bound is the entropy bound for at most m_d letters after normalization by q_0; its value is zero if q_0=0. The exponential bound on q_0 and \log m_d=o(d^2) make this o(1). Outside the event, the log posterior density is at most d. Hence I(W;U)\le d+o(1)\le2d, as claimed.□

Proof. At a node cell C, use the original law \mu conditioned on C. Select all inclusion-maximal strict dyadic descendants D whose conditional mass exceeds 2^{-n\ell/2}, where \ell is depth relative to C. They are disjoint: two dyadic cells are disjoint or nested, and nesting would contradict maximality. A point in a selected cell moves to that cell. Every other point stops in the remainder of the current cell. Repeat at the selected cells. The label records the terminal node and its remainder.

Let K=\|d\mu/d\tau_A\|_\infty<\infty; necessarily K\ge1. Along a nontrivial path reaching relative depth j, the product of the selected conditional masses exceeds 2^{-nj/2}. No complement decision occurs before stopping, so reaching the path cell is exactly membership in it. The same product is its original \mu-mass, which is at most K2^{-nj}. Hence

This uniformly bounds every nontrivial path depth and leaves finitely many grid cells. At an individual node, its bounded conditional density likewise rules out heavy descendants at unbounded depth, so each selected inclusion-maximal descendant exists. The construction is therefore a finite tree and defines a finite partition.

Let q_i be the conditional probability of the terminal remainder at its node, omitting zero-probability remainders. A strict descendant that exceeded its threshold before the remainder decision is contained in a selected cell and has zero remainder mass. Every other descendant has its conditional mass increased by at most q_i^{-1}. This proves (50); the case \ell=0 is immediate. The product of masses on the path, multiplied by q_i, is p_i, so its lower bound proves -\log p_i\le\tfrac12n(\log2)j_i+Q_i.

For the expected remainder cost, a node reached with probability r and having remainder probability q contributes rq\log(1/q) to \mathbb E_iQ_i. This is at most r, since q\log(1/q)\le1, with value zero at q=0. Summing over the finite tree bounds \mathbb E_iQ_i by the expected number of visited nodes. Each move increases depth by at least one, so this number is at most 1+\mathbb E_i j_i.

On the part with label i, the density relative to \tau_{A_i} is the original density relative to \tau_A, multiplied by p_i^{-1}2^{-nj_i}. Taking its logarithm, integrating on that part, and averaging over i proves (52). All terms are finite because the partition is finite and each conditional density is bounded.□

Proof. We first use the dyadic mass bound to control inverse Gram determinants of independent centered signal vectors. These determinants bound the moment of a smoothed projection density. We then remove the smoothing and compare the exact density with the Gaussian reference.

For every y\in\mathbb R^d and 0<r\le1,

Indeed, choose \ell\ge0 with 2^{-\ell-1}<r\le2^{-\ell}. A relative-depth-\ell cell meeting the projection of this ball onto the first n coordinates lies in the concentric ball of radius 2\,2^{-\ell}R. Its side is 2^{-\ell}R/\sqrt n. The unit-ball volume estimate in Lemma 3.1 therefore bounds the number of such disjoint cells by C^n. Multiply by their mass bound e^{Q_*}2^{-n\ell/2} and use 2^{-\ell}<2r.

If U\subseteq\mathbb R^d is a linear subspace of dimension m\le n/8, a maximal rR-separated set in its radius-R ball has at most (1+2/r)^m points. Its radius-rR balls cover that ball, by maximality. Because \|s-s_0\|\le R, ambient balls of radius 2rR about the translated centers cover the event \operatorname{dist}(s-s_0,U)\le rR. Using (54), and the trivial mass bound for r>1/2, gives

For m\le p-1, put a=n/2-m\ge3n/8 and D_U=R^{-1}\operatorname{dist}(s-s_0,U). Then 0<D_U\le1 almost surely. Let \mathcal A=C^ne^{Q_*}\ge1. Since J\le a/2, layer-cake integration of \Pr(D_U<r)\le\min\{1,\mathcal A r^a\}, split at \mathcal A^{-1/a}, gives

For independent z_1,\ldots,z_p\sim\mu, put s_i=s(z_i) and let G be the Gram matrix of e_i=s_i-s_0. Conditional on its predecessors, each e_i has positive distance from their span almost surely by (55). Gram–Schmidt and successive conditioning in (56) yield

Add an independent uniform vector in [-t,t]^J, t>0, to the exact label b. Its joint density is

Expand its integer pth power using independent e_1,\ldots,e_p. For fixed b, Tonelli’s theorem and independence of the J rows give

For almost every tuple the inner-product vector for one row is Gaussian with nonsingular covariance G. Its density is bounded by (2\pi)^{-p/2}(\det G)^{-1/2}. Each box probability is at most (2t)^p times this supremum. The 2t powers cancel, and (57) gives, uniformly in t,b,

Integrating on \Omega therefore bounds the local pth power integral by |\Omega|(Ce^{CQ_*/n}/R)^{Jp}.

For a continuous compactly supported test function on the product of the matrix space and \Omega, its integral against the jittered law converges to its integral against the exact law as t\downarrow0. Extend the test by zero outside a compact subset of \Omega and use bounded convergence. Hölder bounds these limiting integrals by the local L^p bound times the test’s L^{p/(p-1)}(dP_{X'}\,db) norm. Density of such tests and L^p duality give a density for the exact law on this open region, with

Equality on the tests identifies the represented measure with the restricted exact law. This asserts a density on \Omega, which is the only region used below.

On \Omega, the Gaussian reference satisfies h_R(b)\ge(CR)^{-J}. Also the ball-volume estimate gives |\Omega|\le(CR)^J. In the integral of f^ph_R^{1-p}, the powers of R from (58) are

Taking the pth root gives (53). The auxiliary jitter has been removed before the exact observation rule is applied.□

Proof. Put R=2^{-h} and s_0=s(\operatorname{center}A). Write the kernel probabilities as g_u(X,Y)\in[0,1], with \sum_ug_u(X,Y)=1 for every matrix-label pair (X,Y). Define

and define a comparison probability vector by

In \mathbb E_\mu K_u(s)^2, use two independent block matrices at the same signal s. Their stack has J=2k rows. When both blocks satisfy \mathcal G, the stacked residual norm is at most 2\sqrt J R<3\sqrt J R, inside \Omega. Apply Lemma 6.2 and Hölder’s inequality to this exact joint law. Under the Gaussian reference, the two matrices and the two residual vectors are independent between blocks. The product of the two g_u’s lies in [0,1] and has reference expectation \rho_u^2. Dropping the good indicators in its conjugate norm gives

Thus \rho_u=0 implies K_u=0 almost surely.

For every fixed s, the probability of \mathcal G^c is at most

for an absolute c>0, by the Gaussian exponential moment at 1/4. Put g_0(s)=\sum_uK_u(s)\ge1-\delta and P_g=\mathbb E_\mu g_0(s). Including the good indicator with u can only increase information. The indicator costs at most \log2, and the weighted bad conditional information costs at most \delta\log W.

The weighted good conditional information is at most

Indeed, replacing the actual conditional marginal \Pr(u\mid\mathcal G) by \rho adds P_gD(\Pr(u\mid\mathcal G)\Vert\rho)\ge0. Zero states cause no issue by (60). The contribution of -\log g_0(s) is at most \log(1/(1-\delta)). For the remaining term, Jensen’s inequality under the probability measure with weights \mu(ds)K_u(s)/P_g gives

The last inequality uses (60) and \sum_u\rho_u^{1-2/p}\le W^{2/p}, by concavity for p\ge2. All sums are finite. Combining the terms gives

Since k,p are proportional to n and \log W\le n^2, the last two terms are O(n). This proves the lemma.□

Proof. Before each block, apply Lemma 6.1 to the law conditional on the analysis transcript, and record its label. Also record the outgoing boundary state after the block. Initially the cell is the whole cube and the law is \tau. Every positive-probability posterior has bounded density relative to its current cell’s uniform law: splitting preserves this property, and conditioning on a state multiplies the density by a likelihood in [0,1] and divides by a positive state probability. Every split is finite, so each stage has finitely many histories. Future Gaussian rows remain independent of the signal and these histories, which depend only on the signal and past blocks. The block from a known entering state is a measurable kernel of its exact data. Lemma 6.3 therefore applies in each selected component.

For a current cell of depth h and conditional law \mu, define

It is nonnegative. By (52), the expected change under a split is

Within component i, conditioning on its outgoing state keeps the cell fixed and increases the expected relative entropy by exactly I_{\mu_i}(z;u). This follows by multiplying the density by \Pr(u\mid z,i)/\Pr(u\mid i), taking logarithms, and averaging. The block lemma bounds this increase by Cn+CQ_i. Thus the combined conditional drift is at most

for large n, using \mathbb E_iQ_i\le1+\mathbb E_i j_i. Only this expected bound on Q_i is used.

The initial potential is zero, so after B blocks \mathbb E\Phi\le C'nB. For the final transcript \mathcal H, its posterior in a depth-h cell satisfies

Averaging over the finite history gives

□

Proof. Choose a shared-seed value with conditional cube-prior success greater than 3/5. The joint experiment in Section 2 makes this conditioning meaningful, and the conditional initial-state law remains independent of the signal and rows. The derivative of the chart has the identity in its first p rows, so Lemma 2.2 proves absolute continuity of its one-pair law. Lemma 2.1 therefore provides everywhere Borel finite kernels preserving this fixed-seed cube-prior joint law of the signal, path, stopping index, and output.

Use the finite-randomness reduction following that lemma. Sample the conditional initial state, independent uniforms for all finite choices indexed by state and index (including an input-free index-zero stopping choice), and one output from each terminal state/index law. These finitely many choices are independent of the inputs. Fixing a realization by averaging retains cube-prior success at least 3/5. The resulting state rules are Borel, and the state and horizon bounds are unchanged.□

Proof. For 0<u<R, choose an integer j\ge1 with R2^{-j}\le u<2R2^{-j}, and write \delta=R2^{-j}. Project B(x,u) onto the first p coordinates. Each relative-depth j cell meeting the projected ball has diameter \delta, so the union of those cells lies in a ball of radius u+\delta<3\delta. The cells have disjoint interiors and volume (\delta/\sqrt p)^p. The unit-ball estimate used in (70) bounds their number by

Using (72) for each cell gives P\{s(z)\in B(x,u)\}\le15^p2^d2^{-\lambda j}. Since 2^{-j}\le u/R, this proves (73) after choosing C_0 absolutely. For u\ge R the bound follows from P(C)=1.

Let s_0 be the lift of the center of C. The cell has Euclidean radius R/2 in parameter space, so the Lipschitz bound implies \|s(z)-s_0\|\le R\le2R for z\in C. Orthogonal projection onto H is nonexpansive. Thus the projections of all these lifted points lie in the radius-2R ball in H about the projection of s_0. Disjoint ball packing covers that ball by at most (1+4R/u)^k balls of radius u. A point at distance at most u from H whose projection lies in one of these balls is within 2u of its center. For u\le R, applying (73) to the cover gives

Here and below C denotes an absolute constant that may increase. The identity Q=(d-1)/2-\lfloor d/8\rfloor\ge d/3 for large d lets us absorb C^d into C_1^Q. For u>R, enlarge C_1 so that the right side is at least one. This proves (74). In particular every affine subspace of the stated dimension has P-mass zero, by letting u decrease to zero.

To prove (75), apply the layer-cake formula to (\operatorname{dist}(s(z),H)/R)^{-n}\mathbf 1_E. At height t>0 its tail has mass at most \min\{\rho,C_1^Qt^{-Q/n}\}. With t_0=C_1^n\rho^{-n/Q},

Because \alpha\le1/4 and n\le d, an absolute C_2 bounds the prefactor by C_2^d. Restoring R^{-n} proves the assertion.

We turn from affine distances to the projection moment. Tonelli’s theorem expands \int J_\eta^k\,d\beta over z_1,\ldots,z_k\in E. Write s_i=s(z_i). For fixed A and this tuple, integration of \prod_{i=1}^k\varphi_\eta(y-As_i) over the common label y is the density at zero of the k-1 differences from the first of the independently mollified labels As_i+\eta Z_i. After averaging over A, the differences are centered Gaussian, independently across rows, with per-row covariance

Their density at zero is

where the upper bound is interpreted as infinity when G is singular. For nonsingular G, the inequality follows by factoring G^{1/2} and observing that all eigenvalues of I+\eta^2G^{-1/2}(I+\mathbf1\mathbf1^{\mathsf T})G^{-1/2} are at least one. Gram–Schmidt gives

The affine spaces here have dimension at most k-2. The null-mass consequence of (74), applied successively, shows that degenerate tuples have product P-measure zero. Integrate the last display from z_k down to z_2 using (75), then integrate z_1 with mass \rho. The result is

which is (76).

Hölder’s inequality now bounds the mollified measure of B by

Since \rho\le1, this implies the weaker power of \rho in (77). For an open B, couple the mollified labels as As(z)+\eta Z using one independent standard Gaussian Z. As \eta decreases to zero, membership of (A,As(z)) in B implies eventual membership of the approximants. Fatou’s lemma therefore passes the same bound to the exact observation measure. The Gaussian–Lebesgue measure \beta is a locally finite regular Borel measure on the Euclidean joint space. Its outer regularity extends the bound from open sets to every Borel B of finite measure. In particular the exact measure vanishes on \beta-null sets, so the same bound extends to the completion of \beta as well. The mollifier was used only in this calculation; the observation in (77) is the exact label.□

Proof. The functions q_w are Borel by integration of the Borel routing indicators. For b_w>0 define E_w=\{z:q_w(z)>2^{ad}b_w\}. Markov’s inequality gives P(E_w)\le2^{-ad}. A state with b_w=0 is reached with probability zero and contributes nothing.

Retain the lift s_0 of the center of C used in the preceding proof. Conditional on z, the vector A(s(z)-s_0) is distributed as \|s(z)-s_0\|Z for a standard Gaussian Z\in\mathbb R^n. Because \|s(z)-s_0\|\le2R,

The last inequality uses \mathbb E e^{\|Z\|^2/4}=2^{n/2}. Since n\ge d/64 for large d, the right side is exponentially small in d.

Define the joint domain

and let B_w=\mathcal D\cap f^{-1}(\{w\}). These Borel sets are disjoint, and the volume bound gives

Apply (77) to E_w and B_w, and sum over w. Hölder’s inequality on the finite state set yields

for an absolute C_4\ge1. The powers of R cancel exactly. Since 1-\alpha\ge3/4 and N^{1/k}\le2^d, choose a so that 3a/4\ge\log_2 C_4+3. The last display is then at most 2^{-2d}. Adding (80) and reducing an absolute c_1>0 if necessary proves (79) for large d.□

Proof. Run the fresh next block, and let \mathcal E=\{q_W(z)>2^{ad}b_W\} be the event in (79). Write \delta=\mathbb P(\mathcal E)\le2^{-c_1d}. Discard \mathcal E. For b_w>0, let r_w=\mathbb P(\mathcal E^c\mid W=w), and also discard every state with r_w<1/2. The mass of these states is at most 2\delta:

The two deletions therefore cost at most 3\delta.

For a remaining state w, condition on W=w and \mathcal E^c. Its parameter law P' is given by

for Borel B. Since r_w\ge1/2,

For z\in C, let U_j(z) be the cell containing z at relative depth j. Select the least j\ge0 maximizing the score

The score at j=0 is one. Since \mu_C(U_j(z))=2^{-pj}, (84) gives

This upper bound tends to zero. Thus the maximum is attained, and every selected depth is at most J_t, since a selected score is at least one. The least-maximizer rule is unambiguous. It is Borel: there are finitely many possible depths, the cell at each depth is a Borel function of z, and each score is a fixed number on that cell.

For each possible selected cell U, define the actual selection event

These Borel events form a finite partition of C. Discard those for which P'(F_U)<2^{-d}P'(U). At a fixed depth the cells partition C, so their P'-masses sum to one. Summing over the at most \lfloor J_t\rfloor+1 depths bounds this deletion by the second term of (83). Events of zero mass need no conditional law.

Fix a remaining event F_U of positive mass, and let j be the relative depth of U. Put P''=P'(\,\cdot\mid F_U). If a descendant V of U at further depth i meets F_U, choose z\in V\cap F_U. Maximality on this parameter’s cell chain gives

Consequently

using P'(F_U)\ge2^{-d}P'(U). If V\cap F_U is empty, its P''-mass is zero. This proves regularity in U.

The selected score is at least one, so P'(U)\ge2^{-\lambda j} and P'(F_U)\ge2^{-d-\lambda j}. The cell reference measures satisfy \mu_C|_U=2^{-pj}\mu_U. Therefore

The last inequality uses (a+1)d+1\le(a+2)d=Dd for d\ge1. Substituting the value of K yields

which is (82) at the new time and total depth. The normalization throughout is by P'(F_U), including when F_U is a proper subset of U.□

Proof. Apply Lemma 7.6 at each surviving history and at each block. There are finitely many histories at every time. The conditional deletion bounds are uniform, so their unconditional sum is at most \Delta_m: at each time, the probabilities of the surviving histories sum to at most one. Also p-\lambda=(d-1)/2, and hence J_t=O(t+1) with an absolute constant depending only on the already fixed a. Thus

which tends to zero when m=o(d).

At a surviving terminal history, integrating (82) forces K\ge1. Hence (p-\lambda)l\le Ddm. Since \mu(C)=2^{-pl}, the bound relative to the original cube probability becomes

The last inequality uses \lambda=p-\lambda. The history fixes the final boundary state and therefore its output. Equation (70) bounds conditional success by 2^{2Ddm}(5\epsilon)^p. Average over surviving histories and add the deleted mass to obtain (88). For m=0, the same argument is the fixed-output bound at the root.□

Proof. Let S be uniform on S^{d-1}, independently of the T pregenerated Gaussian rows. The original jointly measurable experiment has prior success equal to the integral of its fixed-signal successes. For each admissible fixed shared seed, Lemmas 2.2 and 2.1 give Borel rules with the same uniform-prior law. The bound below is uniform over these rules, so it bounds the original conditional success before averaging over the seed. This returns to the original learner; it does not reuse the cube-selected program.

If T\le d/4, the span U of the rows has dimension T almost surely. Given the rows, the labels determine P_US, since the row map is injective on U. Conditional on the rows and P_US, the residual (I-P_U)S is uniform on the sphere in U^\perp of radius r=(1-\|P_US\|^2)^{1/2}. This follows, for example, by representing S as a normalized standard Gaussian and using rotational invariance of its component in U^\perp.

Spherical symmetry gives \mathbb E\|P_US\|^2=T/d, so Markov’s inequality yields

Suppose r\ge1/2 and condition on the rows and labels. Fix any possible output, and let w be its projection onto U^\perp. If w=0, its residual error is r>1/10. If w\ne0, write \Theta for the unit residual direction and e=w/\|w\|. When |\langle\Theta,e\rangle|<1/2, the component of r\Theta orthogonal to e has length greater than \sqrt3\,r/2>1/10, so the output cannot succeed. The second moment of \langle\Theta,e\rangle for the uniform direction in the (d-T)-dimensional space U^\perp is 1/(d-T). Markov’s inequality therefore bounds success for the fixed output by 4/(d-T). The learner’s conditional output law uses only the revealed data and independent randomness, so averaging over that law preserves the bound. Angular success implies the Euclidean error bound used here.

The uniform-prior success is consequently at most 1/3+4/(d-T), which is below 2/3 for large d when T\le d/4. The every-signal premise gives uniform-prior average at least 2/3, a contradiction.□

Proof of Theorem 7.1. Write L=\log_2(1/\epsilon) and keep the absolute constants a,c_1,D already fixed. Choose

Suppose for contradiction that there are infinitely many dimensions with successful learners satisfying

All asymptotic reductions below concern these dimensions only.

We first obtain the precision range forced by the finite set of terminal labels. For fixed shared rules, there are at most (T+1)2^M terminal state/index labels. Let \mathcal O_{t,u} be the output law at one such label. For each parameter, its success probability is at most the sum, over all terminal labels, of the success probabilities under their output laws: this drops the probability of reaching each label, which is at most one. Integrating over z and then over each \mathcal O_{t,u}, using (70), bounds cube-prior success by (T+1)2^M(5\epsilon)^p. This bound is uniform in the fixed shared rules, so it also bounds the original randomized learner. Its every-signal guarantee gives cube-prior average at least 2/3. Thus

Because L\ge\log_2 10, the absolute number c_0=1-\log_2 5/\log_2 10 is positive and L-\log_2 5\ge c_0L. Under (91) and c\le1,

For large d, absorb the last L into c_0pL on the left of (92). It follows that

The constants in this bound are absolute. In particular, for a fixed memory sequence it bounds every L arising in (91) by the same sequence o(d).

At each such dimension, Lemma 7.2 supplies a deterministic Borel learner with cube-prior success at least 3/5. Pad a halted path by retaining its terminal state and its terminal index. At any later layer, the continuing states together with all terminal tags have total width at most

Pad the last block with ignored rows and put m=\lceil T/n\rceil. By (93), \log_2 N=o(d^2) and m=o(d). Since k=\Theta(d), N^{1/k}\le2^d for all sufficiently large dimensions under consideration. Proposition 7.7 applies and gives

The o(1) is uniform over the short-run precisions for a fixed memory sequence, by the uniform bound on L just obtained.

If L\le L_0, then (91) and c\le1/(4L_0) give T<d/4. Apply Lemma 7.8 to the original learner and its uniform-sphere average, obtaining a contradiction for large d. This use of the original learner preserves the prior of that lemma.

It remains to consider L>L_0. For large d, n\ge d/64, so

The last inequality follows from c\le1/(2048D) and L\ge32D. Also p=d-1\ge d/2 and L\ge2\log_2 5, whence

Therefore the second term in (95) is at most 2^{-dL/8}. It tends to zero, as does \Delta_m, contradicting the fixed lower bound 3/5. No infinite subsequence (91) exists. This proves the asserted sample bound with the absolute c in (90).□

Proof. Fix (g,w) with probability P_{g,w}>0. Conditioning gives \mu\le\sigma/P_{g,w}. Outside one \mu-null set, all the cells Q_j(s) have positive \mu-mass: at each level there are only countably many cells, and a countable union over levels still has zero mass. We make arbitrary choices on that null set. On the remaining points, the score at level a is zero, whereas (98) bounds the score at level j by

This upper bound tends to -\infty uniformly in s. Hence a maximum is attained, and the least maximizing index is measurable because the scores are measurable and indexed by the integers. The nonnegative score at the maximizer also gives

Averaging proves \mathbb E b<\infty. Since \log\mu(Q_b(S))\le0, we have J\le q(b-a)\log2\le d(b-a), proving (99).

For a nonnegative integer variable V of finite mean, relative entropy to the probability masses 2^{-i-1} gives

Apply this conditionally to b-a and to N. The value of a is known from G, so H(b\mid G,W)=H(b-a\mid G,W); moreover \mathbb E N\le\mathbb E(b-a). This proves (101). Given b=j, the cell label has at most (C2^j)^d possibilities. Hence H(Q_b(S)\mid G,W,b)\le d\log C+d(\log2)\mathbb E b, and H(G,W,Z) is finite.

It remains to account for the selected cell label. Fix g,w and a value b=j of positive conditional probability. Compare the conditional distribution of Q_j(S) under this selection with the level-j cell probabilities of \mu. Nonnegative relative entropy gives

Averaging this inequality and using the defining formula for J gives (100). This argument conditions on the selected level; it uses no stopping-time property of that level.□

Proof. Here H(G,W)\le H(G)+m<\infty, so the refinement lemma applies. We first bound projection densities for each class, using a fresh Gaussian matrix. We then compare the actual matrix, selected through W, with that fresh law.

Fix g,w,n of positive probability. Put

A level-j cube of positive \mu_n-mass contains a class point with J<(n+1)d. Since the score at that level is at most J, and \mu_n\le\mu/\alpha, it follows that

For 0<t\le1, choose j\ge a with t\delta/2\le\delta_j\le t\delta. A ball of radius t\delta meets at most C^d such cubes: their union lies in a ball of radius 2t\delta, and the volume estimate used above cancels the factor d^{d/2} in the inverse cube volume. Thus (103) bounds the mass of this ball by C^de^{(n+1)d}\alpha^{-1}t^q.

Let V be any affine plane of dimension r\le p-1. The projection of the current level-a cube onto V lies in a plane-ball of radius \delta. A maximal separated set covers that ball by at most (1+2/t)^r balls of radius t\delta. Points of the current cube within distance t\delta of V then lie in the corresponding ambient balls of radius 2t\delta. For t\le1/2 apply the ball estimate; for t>1/2 enlarge C and use total mass one. We obtain

In particular every such plane has zero mass. The layer-cake formula, applied to (\delta/\operatorname{dist}(u,V))^k, gives

Indeed the integral after multiplication by \delta^k is at most 1+Kk/(q-r-k) with K=C^de^{(n+1)d}/\alpha, and q-r-k is a positive multiple of d.

Fix any s\in S^{d-1} and draw U_1,\ldots,U_p independently from \mu_n. Let \Gamma_s be the Gram matrix of the vectors U_i-s. Gram–Schmidt expresses its determinant as the product of the squared distances from U_i to s+\operatorname{span}\{U_h-s:h<i\}. These planes have dimension at most p-1, and (104) shows that the distances are positive almost surely. Successive integration using (105) yields

The center s is fixed in this estimate and need not have law \mu_n.

We turn this inverse-volume bound into a pth moment of the class projection density. That moment will control its average logarithm under the actual matrix law; the relative-entropy comparison will charge at most m/p for selection through W.

Let \phi_\eta be the N(0,\eta^2I_k) density and define

Write \gamma_k for standard Gaussian k-by-d matrix law. For a fresh \widetilde A\sim\gamma_k, expansion of the pth power gives

For each row, the vector of projected differences has covariance \Gamma_s; adding the p independent mollifying Gaussians adds \eta^2I_p. Evaluating its density at zero and multiplying across independent rows proves the identity. The right side is bounded by (106).

We next select one density version that is valid on the true-label diagonal as well as under the actual selected rows. The projection of uniform sphere measure onto k<d coordinates has density

For completeness, write a uniform sphere point as a normalized standard Gaussian. The squared length of its first k coordinates is the ratio X/(X+X') for independent chi-square variables of k and d-k degrees of freedom. Changing variables in their gamma densities gives the beta density with parameters k/2,(d-k)/2; its direction is uniform and independent. Polar coordinates give the displayed density. Rotations and an invertible range map prove absolute continuity for every rank-k linear map, and the property passes from \sigma to \mu_n\ll\sigma.

Consequently the law of (\widetilde A,\widetilde A U), with U\sim\mu_n independent of \widetilde A, has a density \rho_0 relative to \gamma_k(dA)\,dy. The functions \rho_\eta converge to \rho_0 in this joint L^1 space. To see this, for almost every A use continuity of translations in L^1(dy) for its conditional density and average the Gaussian translations; the error is at most two, so dominated convergence permits averaging over A. Choose a sequence \eta_j\downarrow0 along which convergence also holds almost everywhere, and define everywhere

This is a version of \rho_0. The sequence was chosen without a value of s. Since (107) was bounded for every fixed s, Fatou’s lemma now gives, for this same version and for each fixed s,

There are only countably many triples (g,w,n), so this construction can be made for every occurring triple. Conditional on such a triple, the actual matrix law is absolutely continuous with respect to \gamma_k. Also, for almost every such matrix, the conditional signal law is absolutely continuous with respect to \sigma: conditioning the pre-block law by the discrete events W=w,N=n only reweights it. Its image under a full-rank matrix therefore has a Lebesgue density. Thus the actual joint law of the matrix and its label is absolutely continuous with respect to \gamma_k(dA)\,dy. In particular the chosen version \rho is valid in expectations under that actual law.

We have obtained the fresh projection estimate. To convert it into information, set Y=AS. Fresh independence and the conditional Markov property S\longrightarrow Y\longrightarrow W given (A,G) imply

The first line follows by expanding I(S;A,W\mid G) in two orders. It also gives I(A;S\mid G,W)\le I(S;W\mid A,G)\le m.

All the differential entropies in this argument, including after conditioning on N, are finite. Here are the needed integrability details. Because d-k\ge2, the coordinate density displayed above is bounded by a finite constant depending on d,k. For a rank-k matrix the corresponding bound is multiplied by (\det AA^{\mathsf T})^{-1/2}. Gram–Schmidt on Gaussian rows writes this determinant as a product of squared residual lengths, each with a chi-square law; the absolute logarithm is integrable from its gamma density. Thus \mathbb E|\log\det AA^{\mathsf T}|<\infty. Given G=g, the signal density is bounded by 1/\mathbb P(G=g) relative to \sigma, whose expected logarithm is H(G). Conditioning further on (W,N) can multiply a conditional label density by at most 1/\mathbb P(W=w,N=n\mid A,G); its expected logarithm is H(W,N\mid A,G)\le H(W,N\mid G)<\infty. These facts control the positive parts of the log label densities. To control their negative parts, compare with a fixed standard Gaussian label density. For two densities f,g,

because t\log(1/t)\le1/e for 0\le t\le1. The remaining Gaussian logarithm is integrable since \mathbb E\|Y\|^2=k. This proves the claimed finiteness and justifies the entropy identity.

Let c_G be a specified corner of the current cube, so \|S-c_G\|\le\delta=2^{-a}. Comparing the conditional label density with N(Ac_G,\delta^2I_k), and using independence of A to obtain \mathbb E[\|A(S-c_G)\|^2\mid G]\le k\delta^2, gives

For the other two terms in (109), first condition on N. Differential entropy decreases under this conditioning, and, since N is determined by (S,G,W),

The latter conditional mutual information is the average divergence from \mathcal L(S\mid A,G,W,N) to its marginal \mu_N. Data processing under s\mapsto As, followed by the definition of relative entropy for the two label densities, gives

Together with the preceding conditioning and chain-rule inequalities, this proves

This comparison is between finite quantities: the conditional mutual information is at most m, and the true log density was shown integrable. The projected log density ratio has integrable negative part by the same 1/e bound and finite positive part by data processing.

If P\ll P_0 and f\ge0, relative entropy to the probability law with density proportional to f^p gives

Truncating \log f proves this form whenever the left side is defined and the right side is finite. In the present application the preceding paragraph gives integrability. Apply (112) conditionally on (s,g,w,n) to the actual matrix law, taking P_0=\gamma_k and f(A)=\rho_{g,w,n}(A,As). The value of n is already determined by (s,g,w), and before W the matrix is independent of (S,G). The average divergence in this comparison is therefore

The average of -\log\alpha is H(N\mid G,W). Using (108) in (112) and then averaging gives

Finally (N+1)d\le J+d. Substitute this bound and (110)–(111) into (109) to obtain (102).□

Proof. Start with G_0=Q_0(S) and depth a_0=0. Its entropy is at most Cd by the grid count. After every outgoing state W, append the pair Z=(b,Q_b(S)) from Lemma 8.1. The enlarged history contains the outgoing state and a cell containing S at depth b. Its entropy and expected depth remain finite. Since this refinement uses only S and completed blocks, the next Gaussian rows remain independent of (S,G).

For a current history of depth a, define

Because Z is a function of (S,G,W),

The block estimate, (100), and (101) give

Here the term q\log2 pays the selected cell mass, and the remaining 2\log2 per unit of depth pays both the depth and class entropies. Thus the entire label Z has been included in the balance.

For each history value g, its conditional signal law is supported on the specified level-a cube. Relative entropy to \sigma is at least the negative logarithm of the \sigma-mass of that cube: this follows by writing it as relative entropy to normalized \sigma on the cube minus the logarithm of the cube mass. By (98),

It follows that F(G)\ge(1-\bar q/(d-1))I(S;G), with a positive coefficient bounded away from zero for large d. Iterating the upper bound from F(G_0)\le Cd proves (113).□

Proof. Use the reductions following Lemma 2.2 under the uniform prior. First fix the shared rule randomness with success greater than 3/5, and apply Lemma 2.1. Then fix the independent initial state, the finite transition choices, and the outputs assigned to terminal state/index pairs by averaging. The resulting deterministic Borel learner has uniform-prior success at least 3/5 and the same state and horizon bounds.

Put L=\log(1/\epsilon), with 0<\epsilon\le1/10. The case T\ge dL already has the required order. In the other case the fixed learner has at most (T+1)2^M terminal outputs, counting every possible stopping index. Angular error at most \epsilon implies Euclidean error at most \epsilon, because 2\sin(\theta/2)\le\theta. Applying (97) to each output gives

For the second inequality, take logarithms in the first and use T<dL and \log(dL+1)\le\log(d+1)+L. Thus M=o(d^2) implies L=o(d) along these putative short runs, and eventually T\le d^2. This is a consequence of the short-run assumption, not an added restriction on the accuracy sequence.

Preserve a stopped state together with its terminal index, and use ignored fresh samples after stopping. At any later index there are at most 2^M active states and (T+1)2^M tagged terminal states. Padding the last block as well therefore uses width at most

Take B=\lceil T/k\rceil blocks, padding with fewer than k ignored samples if necessary. The final augmented history recovers the output. Under the product of the signal and output marginals, angular success has probability at most \epsilon^{d-1} by (97). For an event with probabilities u and v under two laws, data processing to the event gives relative entropy at least u\log(1/v)-\log2: expand binary relative entropy and use binary entropy at most \log2. Hence

Since m/p=o(d), (113) and (116) imply L\le C(1+B). With B\le T/k+1, this gives T\ge cdL whenever L exceeds a fixed absolute constant.

We finish the bounded range of L with the route’s linear sample bound. Grant the learner all T<d pre-generated rows and exact labels, including any it did not use. Their row space V has dimension T almost surely. The data determine P_VS, and conditional on the data the residual S-P_VS has uniform direction in V^\perp, with radius \sqrt{1-\|P_VS\|^2}. This follows by splitting a normalized standard Gaussian into its independent row-space and nullspace components. Its conditional mean is zero and its covariance is (1-\|P_VS\|^2)P_{V^\perp}/(d-T). For every unit estimate determined by the data, also after averaging independent output randomness,

On angular success the squared inner product is at least \cos^2(1/10). Since (3/5)\cos^2(1/10)>1/2, average success 3/5 excludes T\le d/2 for large d. This linear bound absorbs the bounded range of L and completes the proof.□

Proof. We first control the volume of the simplex spanned by independent points from \nu. The use of Gaussian replicas and Gram–Schmidt factors is related to the projection argument of Sharan, Sidford, and Valiant [12, Section 7, Lemma 12]. The geometric moment and the exact-message information estimate needed here are proved below.

Let V be an affine subspace of dimension m\le p-2, and let 0<u\le1. Points of B(c,R) within distance uR of V project into V\cap B(c,2R). A maximal separated set covers this set by at most (C/u)^m balls in V of radius uR; when m=0, one ball suffices. The corresponding points in the original tube lie in ambient balls of radius 2uR. Such a ball of positive \nu-mass contains a point where (120) holds, and it is contained, on the support of \nu, in a radius-4uR ball about that point. Hence

The parameters give \alpha-m-a\ge3d/32. Integrating the tail of (R/\operatorname{dist}(S,V))^a, and using (122) for values of this variable above one, gives

Indeed the tail integral is bounded by 1+KC^d a/(\alpha-m-a). The tube bound also proves that V has zero \nu-mass.

Draw (S_1,\ldots,S_p)\sim\nu^{\otimes p}. Let F be the matrix with columns S_i-S_1, 2\le i\le p, and set v=\sqrt{\det(F^{\mathsf T}F)}. Gram–Schmidt writes v as the product of the distances from S_i to \operatorname{aff}(S_1,\ldots,S_{i-1}). The preceding zero-mass statement shows successively that these distances are positive almost surely. Integrating the last point first and repeating (123) proves

We use this moment in a normalized comparison of posterior replicas. Temporarily add an independent N(0,\sigma^2I_k) vector \eta to the labels, where 0<\sigma\le R, and set b=AS+\eta. Apply the given message kernel to (A,b) and call its output Z_\sigma. Write P_A for the Gaussian matrix law. With \varphi_\sigma denoting the noise density, write

Sample (A,b,Z_\sigma) from this experiment. Conditional on these variables, sample p independent points from the posterior of S given (A,b); their conditional law does not depend further on Z_\sigma. Let P_\sigma be the resulting marginal on (S_1,\ldots,S_p,A,b) and Q_\sigma its point-tuple marginal. Each pair (S_i,Z_\sigma) has the experiment’s original marginal. Put D_Q=D(Q_\sigma\|\nu^{\otimes p}), initially allowing the value +\infty. Once D_Q is finite, relative entropy to a product bounds the sum of the marginal relative entropies: their difference is the relative entropy of the joint law to the product of its own marginals. Apply this after conditioning on the common message and use the matching single-point marginals. The conditional chain rule then gives

It therefore suffices to prove D_Q/p\le C(d+\log K), uniformly in \sigma. We will prove finiteness and this bound by comparing the posterior tuple law with a normalized reference whose tuple marginal is exactly \nu^{\otimes p}.

Relative to \nu^{\otimes p}\otimes P_A\otimes db, the density of P_\sigma is

For a fixed tuple, the integral of the numerator over (A,b) is

Here \mathbf1\in\mathbb R^q is the all-ones column. To verify this formula, take p independent noisy labels with the same matrix A. Integrating their product density over their common value b evaluates at zero the density of the q differences from the first label. In one row, the projected signal differences have covariance F^{\mathsf T}F, and the noise differences have covariance \sigma^2(I_q+\mathbf1\mathbf1^{\mathsf T}). The rows are independent, which proves (127). On full-rank tuples,

Define a reference probability law R_\sigma by the density

The denominator is exactly the integral for each fixed tuple. Thus the tuple marginal of this reference law is \nu^{\otimes p}, rather than an unnormalized multiple of that law.

All logarithms in this comparison are integrable at fixed \sigma>0. The tuple is supported in B(c,R)^p, and

Hence \log c_\sigma is bounded as the tuple varies. Also \log f_\sigma is at most -\frac{k}{2}\log(2\pi\sigma^2) and at least this value minus

The latter term is integrable under the noisy experiment. Data processing therefore proves D_Q<\infty and gives

To bound the second term, compare f_\sigma(\cdot\mid A) with the N(Ac,2R^2I_k) density. Since \mathbb E\|b-Ac\|^2\le kR^2+k\sigma^2\le2kR^2, nonnegative relative entropy yields

Together with (128), this gives, initially allowing the expectation on the right to be extended,

Here the needed expectation is in fact finite. Put X=a\log(R^q/v). Hadamard’s inequality gives v\le(2R)^q, so X\ge-aq\log2. For bounded X' the probability law proportional to e^{X'}\nu^{\otimes p} and nonnegative relative entropy give

Apply this to X'=\min(X,n) and let n\to\infty. Monotone convergence after adding the fixed lower bound, together with (124), proves both finiteness and

Because k/a\le1/4, substitution into (131) and absorption of (k/a)D_Q give

Combining (132) with (125) proves (121) for the noisy experiment, uniformly over 0<\sigma\le R.

It remains to pass this inequality to the given exact-label rule. This step uses the rule itself, rather than a comparison of the statistical difficulties of noisy and noiseless experiments. For every rank-k matrix with k<d, the image of \mu has a Lebesgue density. One direct proof uses a normalized standard Gaussian: the squared length of the first k coordinates is a beta variable with parameters k/2,(d-k)/2, obtained from the ratio of independent chi-square variables, and its direction is uniform. This gives a density on the unit k-ball. Orthogonal changes of coordinates and an invertible range map give the claim for any rank-k matrix. Absolute continuity \nu\ll\mu preserves it. Since a Gaussian matrix has full row rank almost surely and itself has a Lebesgue density, (A,AS) has a joint Lebesgue density.

Let g_z(A,b) be the output probability of message z. For any bounded measurable function g and a random vector X with a Lebesgue density,

To see this, restrict the input density to a bounded cube and to values below a fixed bound, losing arbitrarily little probability. For small h, cut g off on a larger cube. The remaining integral is bounded by a constant times the Lebesgue L^1 distance between this cutoff and its translate. That distance tends to zero, since continuous compactly supported functions are dense in L^1 and their translates converge uniformly on a common compact set. This proves (133). Apply it to shifts in the label coordinates, then to h=(0,\sigma G) with G standard Gaussian by bounded convergence. The finite alphabet gives

Couple the two message probability vectors at each (S,A,\eta) by their common masses, so that their disagreement probability \delta is half the expected sum in (134). This is a measurable coupling because the alphabet is finite. Write h_2(t)=-t\log t-(1-t)\log(1-t), with 0\log0=0, for binary entropy. The disagreement indicator bounds each of the marginal and conditional entropy differences by h_2(\delta)+\delta\log w: on disagreement there are at most w possible values, and binary entropy is concave when conditional disagreement probabilities are averaged. Consequently

For w=1 both messages are constant and the assertion is immediate. The uniform noisy bound therefore proves (121) for the exact labels AS.□

Proof. Since \nu is a probability, B\ge1. Put m_s(r)=\nu(B(s,r)) and R_j=2^{1-j} for integers j\ge0. Choose J(s) to be the least index maximizing 2^{\alpha j}m_s(R_j), and write J=J(S). The score at j=0 is one because R_0=2 covers the sphere. The second cap bound in (119) gives

The ball masses are measurable in s, by integrating the Borel indicator of \|s-u\|\le R_j. Thus the least maximizer is measurable and

The entropy bound follows from the displayed finite range. For R=R_{J(s)}, compare the maximum with the least dyadic radius at least r when r\le2, and with R_0=2 when r>2. This proves

At each scale choose a finite maximal R_j-separated set of centers on the sphere. Its R_j-balls cover the sphere. Enumerate the centers and assign a point to the first center within distance R_j; this is a measurable rule. Let U=(J,i) record the scale and assigned center. Its range is finite by (136) and the finiteness of each net. For each cell u=(j,i) of positive probability, write c_u for its center, b_u=\mathbb P(U=u), and m_u^+=\nu(B(c_u,2R_j)).

At one scale, a point lies in at most 5^d of the enlarged balls B(c_u,2R_j). Indeed the disjoint interiors of the radius-R_j/2 balls about those centers lie in a ball of radius 5R_j/2 about the point. Volume comparison proves the count, and integration gives \sum_{u=(j,i)}m_u^+\le5^d. Write p_j=\mathbb P(J=j). Concavity of the logarithm with weights b_u/p_j at each positive-mass scale yields

The conditional prior \nu_u is supported in B(c_u,R_j) and remains absolutely continuous with respect to \mu. If s is in that cell, then m_s(R_j)\le m_u^+. Dividing (137) by b_u gives, for \nu_u-almost every s and all r>0,

Here m_u^+\ge b_u, so the factor is at least one. The matrix A remains independent of (S,U), and the same message kernel is used. Apply Lemma 9.1 for each u, average, and use (138). We obtain

We have bounded the information inside each cell. We now pay for its label in the presence of the side data. For a known scale j, predict the center index from (W,y) by the normalized probabilities

Discard zero-probability cells. At an occurring scale the denominator is positive and the set of indices is finite. Nonnegative relative entropy between the conditional center distribution and these probabilities bounds H(i\mid D_*,J) by the expected negative logarithm of the true cell’s prediction.

Fix a true point s with J(s)=j and put R=R_j. For its center,

For any candidate center c, direct Gaussian integration gives

Centers within distance 2R of s have total cell probability at most m_s(3R), since their cells are within an additional distance R. Centers at distances in (2^tR,2^{t+1}R], t\ge1, have total cell probability at most m_s(2^{t+2}R) and expected kernel at most 2^{-t\ell} per unit cell probability. The expected denominator in (140), evaluated at y=Ws, is therefore at most

The first inequality uses (137); the series converges because \ell-\alpha\ge1 for large d.

Jensen’s inequality for the logarithm of this denominator, together with the true-center squared term, bounds the expected prediction loss at s by Cd+\log(m_s(R)/b_U). The logarithms are integrable: the denominator is at least the true term, and its negative logarithm is bounded by -\log b_U plus a Gaussian squared term. Averaging and using m_S(R_J)\le m_U^+ in (138) gives

Finally U is a function of S, and Z is conditionally independent of D_* given (S,U). Since Z is finite,

The chain rule then gives I(S;Z\mid D_*)\le H(U\mid D_*)+I(S;Z\mid U). Combining (136), (139), and (142) proves (135). The cell has been revealed only inside this calculation, with its full conditional entropy charged; no local regularity of the original state posterior was assumed.□

Proof of Corollary 8.4 using side data. Take S\sim\mu and use the reductions following Lemma 2.2. First fix the shared rule randomness with uniform-prior success greater than 3/5, apply Lemma 2.1, and then fix the independent initial state with success at least 3/5. Fresh transition and terminal output randomness may remain: the two lemmas permit finite message kernels, and the calculation below integrates the terminal output law.

Put L=\log(1/\epsilon) with 0<\epsilon\le1/10. If T=0, the fixed initial state and terminal rule give an output independent of S, whose success is at most \epsilon^{d-1}<3/5 by (119). Thus the successful runs considered below have T\ge1.

It suffices to consider T<dL. There are at most (T+1)2^M terminal pairs consisting of the stopping index and state. For a fixed pair h, the joint subprobability law \lambda_h of S and the event of reaching h satisfies \lambda_h\le\mu. The unit output conditional on h uses only its terminal law and fresh randomness, so is independent of S. Angular success implies Euclidean error at most \epsilon, and (119) applies since \epsilon\le1/10. Integrating the terminal output law and summing over pairs gives

Using T<dL and \log(dL+1)\le\log(d+1)+L yields (d-2)L\le M\log2+O(\log d). Along a sequence M=o(d^2) this implies L=o(d) in the present short-run case and eventually T\le d^2.

After an early stop, preserve its state together with its terminal index and ignore the remaining fresh samples. The active states and all terminal tags together give the global width bound

The output law at a terminal tag is the original terminal law. Split the T padded samples into N=\lceil T/k_*\rceil consecutive blocks of length at most k_*. Let \Pi_i record every state at the first i block ends, with \Pi_0 empty. This is the full state transcript, not just its final state.

Independently draw one matrix W with \ell Gaussian rows and retain the same D_*=(W,WS) for all blocks. For every positive-mass history h of \Pi_{i-1}, its conditional signal law satisfies

Given h, the next block matrix is still fresh Gaussian and independent of S, and W remains independent of both. The incoming state is known from h. The persistent-memory restriction makes the successor state a kernel of that state and the block’s complete exact data, with alphabet size at most w. It has no access to D_*. Lemma 9.2 therefore applies conditionally on each history.

The posterior-density cost is small after averaging. Since \Pi_{i-1} is a tuple of at most N states from an alphabet of size w,

Jensen’s inequality gives

Here N=O(d) follows from T\le d^2 and k_*\ge d/64 for large d; also (\log w)/p=o(d) by (144). Summing the conditional information bounds for successive states by the chain rule gives an absolute C_1 such that

The local cell U used in each application is not an uncharged part of \Pi_N: its revelation was paid by (142) inside that block’s conditional bound.

For a lower bound on the same information, condition on D_*. Almost surely W has rank \ell. Its labels specify P_WS, where P_W is the orthogonal projector onto its row space. The remaining component has uniform direction in the nullspace, of dimension d-\ell, and radius

This conditional law follows by writing S as a normalized standard Gaussian: the nullspace direction is independent of its length and of the row-space component. The event \mathcal G=\{\rho\ge1/2\} is determined by D_*, and Markov’s inequality gives

On \mathcal G, the mass of the conditional sphere within Euclidean distance \epsilon of any fixed estimate is at most (4\epsilon)^{d-\ell-1}. If the ball meets that sphere, choose a point of intersection. The rest of the intersection lies within 2\epsilon of it. After rescaling the residual sphere by \rho\ge1/2, the radius is at most 4\epsilon\le2/5<1/2, so the first bound in (119) applies in ambient dimension d-\ell.

The final output \widehat S is conditionally independent of S given (\Pi_N,D_*), because the transcript contains its terminal tag. For each value of D_*, compare the actual joint law of (S,\Pi_N,\widehat S) with the product of its conditional S marginal and conditional (\Pi_N,\widehat S) marginal. On \mathcal G the success probability under this product is at most (4\epsilon)^{d-\ell-1}. Binary relative entropy is at least the true event probability times the negative logarithm of its product-law probability, minus \log2. Integrating over \mathcal G, and using nonnegativity elsewhere, gives

for an absolute c_0>0 and sufficiently large d. The coefficient 3/5-4/9 accounts for the success mass outside the failed-radius event. For the last inequality, d-\ell-1 is a positive multiple of d and L-\log4\ge(1-\log4/\log10)L.

Combining (146) and (148), and using N=\lceil T/k_*\rceil\le T/k_*+1, gives the exact intermediate bound

We retain a separate linear endpoint to absorb its additive constant. If T<d/3, reveal all T pre-generated rows and exact labels, even after an early stop. The same normalized-Gaussian argument gives a uniform conditional sphere of ambient dimension d-T. Its radius is at least 1/2 except on an event of probability at most 4T/(3d)<4/9. The preceding conditional cap argument therefore bounds the success of even a full-data estimator by

for sufficiently large d, a contradiction. Thus T\ge d/3. When L\ge2C_1/c_0, (149) implies T\ge cdL; for smaller L, the linear bound gives the same conclusion after reducing the absolute constant. The case T\ge dL needed no reduction. Every learner observation throughout this argument is the exact inner product; the auxiliary noise appeared only in the proved passage to the exact-message inequality.□

Proof. The subset averaging below is the entropy-cover mechanism used in the Product Theorem of Chung, Graham, Frankl, and Shearer [2, Section V, Equation (22), pp. 33–34]. We give the conditional differential-entropy form required here. Let Q be an independent Haar orthogonal frame and set Z_i=\langle Q_i,S\rangle. Put N=d-1. For a k-subset E\subset\{1,\ldots,N\}, the entropy chain rule and conditioning give

Every index occurs in the same number of k-subsets. Averaging over the subsets and over Q, whose law is unchanged by column permutations, yields

This uses no rotation invariance of the conditional law given K. All projected entropies are finite: the uniform projection density has an integrable logarithm for every number of coordinates at most d-1, and finite-entropy conditioning preserves this as above.

Let h_j^0 be the entropy of j fixed orthogonal coordinates of a uniform sphere point. The Gaussian maximum-entropy bound and the covariance I_j/d give

For j=N, the two hemispherical graphs give

For the last inequality, use the sphere-area formula and Stirling’s bound, and write S=g/\|g\|; Jensen bounds \mathbb E\log\|g\| above by \tfrac12\log d, whereas \mathbb E\log|g_d| is a finite absolute constant. Data processing gives

Thus (156) bounds the information in k frame coordinates by \tfrac{k}{N}I(S;K)+Cd.

Given X_B, its label is an invertible linear transform of the orthogonal coordinates in its row space. That row space is uniform, independent of (S,K); extending an orthonormal row frame gives the Q experiment above. Hence the same information bound holds for I(Y_B;K\mid X_B). Without K, (156) gives h_k^0\ge(k/N)h_N^0. Passing from orthogonal coordinates to Y_B adds \tfrac12\mathbb E\log\det(X_BX_B^{\mathsf T}), which cancels the leading -\tfrac{k}{2}\log d term. This proves both inequalities in (154).

By the definition of P,

Freshness and Y_B=X_BS give the chain-rule identity

Since k/(d-1)\le1/4, the first inequality of (154) can be absorbed on the left. This proves the information estimate in (155). Finally h(Y_B\mid X_B,K)=h(Y_B\mid X_B)-I(Y_B;K\mid X_B); the two bounds just proved give the negative-entropy estimate.□

Proof. We describe a decision tree conditional on K,A. At a node let \nu be the signal law after the recorded prefix, supported in the current ball B(z_0,r_0). Enumerate once and for all a countable dense family of affine subspaces of dimensions at most \ell-2, for example those generated by rational points. If the first subspace E with

exists, record whether the signal belongs to this tube. On a negative answer, continue with the conditional law and the same ball. On a positive answer, cover the current ball by a fixed ordered maximal \eta r_0-separated net, choose the first center within \eta r_0 of S, record its index, and replace the ball by the radius-\eta r_0 ball about that center. Then continue.

The full ambient net has at most (1+2/\eta)^d points. Given the selected subspace, only \exp(b_0d+\ell a) indices can occur, where b_0 is independent of a\ge1. To see this, an eligible center lies within 3\eta r_0 of E. Its projection to E lies in a radius-r_0 ball, coverable by (1+2/\eta)^v radius-\eta r_0 balls when v=\dim E. Over each covering ball, the eligible centers lie in an ambient radius-4\eta r_0 ball. Their disjoint radius-\eta r_0/2 balls fit in its radius-9\eta r_0/2 enlargement, giving at most 9^d centers. Since v\le\ell-2, the claimed exponential bound follows after enlarging b_0.

If no selected subspace exists, every affine subspace of dimension at most \ell-2 has mass at most p_0 in its open \eta r_0-tube. Indeed its distance function on the bounded current ball can be approximated uniformly within \eta r_0 by that of a subspace from the countable family. Mass greater than p_0 in the smaller open tube would therefore trigger the larger tube test for a member of the family.

In this case, draw \ell-1 additional independent points from \nu, using S as the first point, and record whether

On failure continue at the same scale with the updated signal law; on success stop. Before the outcome, the tuple is i.i.d. from \nu. If the volume is smaller than (\eta r_0)^q, one of the q successive distances is smaller than \eta r_0. Conditionally on its predecessors, each such event has probability at most p_0. The pass probability is therefore at least 1-qp_0\ge1/2.

Record the decision type, its outcome, and any ambient net index, but not the extra test points. Given (K,A) and the prefix, the type and selected subspace are already determined. The first successful subspace is a measurable choice because the family is countable and its tube probabilities are kernel integrals of Borel indicators. Fixed scaled nets and ordered ties give measurable centers. Regular conditional laws at nodes, with arbitrary defaults at null nodes, complete a recursion by probability kernels on standard Borel spaces. Independent auxiliary draws make W independent of (S,C_*) given (K,A).

First truncate the tree after u decisions, and write C_u,N_u for its string and number of refinements. At every active node the progress outcome, meaning refinement or a successful test, has conditional probability p\ge p_0. Its binary entropy is at most

because -p\log p\le p\log(1/p_0) and -(1-p)\log(1-p)\le p. The expected number of progress outcomes is at most \mathbb E N_u+1. Summing the node entropies and the eligible index costs gives

The expected number of active decisions is at most p_0^{-1}(\mathbb E N_u+1). For an encoding that is decoded given K alone, use two bits for the type and outcome at each active node and a fixed-length full ambient net index at a refinement. The decoder knows the truncation depth u; the recorded type and outcome determine any earlier stop. The ambient index recovers the next center without knowing the selected subspace. This prefix encoding has expected length at most C_a d(1+\mathbb E N_u) nats, so

At finite depth all strings have finite entropy. The area bound and the conditional mutual-information identity give

For large d, n-\ell>d/2 and u_d=O(\log d). Choose a once and for all large enough that the coefficient in braces is at least \delta da with an absolute \delta>0. It follows that \sup_u\mathbb E N_u<\infty, and then that the expected number of active decisions is bounded uniformly in u. By monotone convergence the full number of decisions is integrable, so the tree terminates almost surely. Denote its string and refinement count by C_*,N.

The same prefix encoding at termination has finite expected length, so H(C_*\mid K)<\infty. The truncated prefixes increase to the full string and N_u\uparrow N. Conditional information in the prefixes increases to the information in the full countable string; this also follows from the chain rule and H(C_*\mid C_u,K,A)\to0, using its finite entropy. Passing to the limit in the preceding bounds proves (157)–(159). Thus the stopping argument did not presume entropy finiteness for an infinite procedure.

Finally condition on a terminal prefix just before its successful test, with signal law \nu. Let E_{\mathrm{pass}} be its symmetric volume event and set Q=\nu^{\otimes\ell}(\,\cdot\mid E_{\mathrm{pass}}). The symmetry makes all marginals equal, and the first marginal is exactly the signal law after recording the pass. Call it \mu_*. If p=\nu^{\otimes\ell}(E_{\mathrm{pass}})\ge1/2, then the product-reference decomposition gives

All terms are finite because dQ/d\nu^{\otimes\ell} =\mathbf1_{E_{\mathrm{pass}}}/p. The volume bound holds throughout the conditioned law. This proves (160).□

Proof. We first identify a common measure for the two singular laws. Let \mathcal R be the open region in the ambient tuple–matrix space where D_{\mathbf s} has rank q, X has rank k, and j_X(s_i)>0 for every i. On the incidence constraint XD_{\mathbf s}=0, let \gamma_{\mathbf s} be the Gaussian matrix law conditioned on that constraint. The ambient Gaussian density of XD_{\mathbf s} at zero is

Indeed each row has covariance D_{\mathbf s}^{\mathsf T}D_{\mathbf s}. Write p_X for ambient Gaussian matrix density. On the regular incidence set the locally finite measure

also has the integration description

To verify this equality, take a continuous test G(\mathbf s,X) compactly supported in \mathcal R. In its integral under \sigma^{\otimes\ell}(d\mathbf s)p_X(X)dX, insert the normalized indicator of a radius-\varepsilon ball in \mathbb R^{kq}, evaluated at XD_{\mathbf s}. Fixing the tuple first, the conditional law given XD_{\mathbf s}=Z is \gamma_{\mathbf s} translated by Z(D_{\mathbf s}^{\mathsf T}D_{\mathbf s})^{-1}D_{\mathbf s}^{\mathsf T}. This translation and the Gaussian image density vary continuously at Z=0. On the tuple projection of the compact support, the smallest singular value of D_{\mathbf s} is bounded away from zero, so the image densities are uniformly bounded. Dominated convergence gives (165).

In the other order, fix X,s_1 and apply the area identity (150) separately to s_2,\ldots,s_\ell, using labels X(s_i-s_1). The affine fibers near the zero label are continuous translations and scalings of unit spheres. On the compact regular support their radii and j_X(s_i) are bounded away from zero, so the fiber integrals of G are continuous at zero and uniformly bounded. Dominated convergence in the label vector gives (166). Equality on all continuous compactly supported tests identifies the locally finite Borel measures on the regular set. Thus it also holds for nonnegative measurable integration there. This is a regular-region identity; no global finite mass for the unweighted incidence measure has been assumed.

Both probability laws in the comparison give this region full mass. For the reference, the one-point law has a density relative to sphere area, so its independent tuple is affinely independent almost surely. Its constrained rows live in dimension d-q>k and have full row rank almost surely. On the constraint, all points have the same row-space projection. That projection has norm strictly less than one: if s_1 were in the row space, then \langle s_1,s_i-s_1\rangle=0 would give \langle s_1,s_i\rangle=1, forcing s_i=s_1 and contradicting full affine rank. For the actual law, the volume lower bound gives full affine rank, and the true (S_1,X_A) marginal gives full row rank and positive residual radius almost surely. The quantities j_X(s_i) agree on the constraint because their row-space projections agree.

Condition now on (K,C_*). Jointly measurable density versions can be obtained by taking Radon–Nikodym derivatives of the joint laws with their conditioning variables and then disintegrating; absolute continuity follows from the finite-entropy conditioning above and from the coupling bound. Let p_c be the full-sphere marginal density, p_{1,X} the density of the true (S_1,X_A) law relative to \sigma\otimes dX, and p_{\mathrm{sl}}(\,\cdot\mid A) the conditional slice density. Let t(\mathbf s\mid A) be the coupling density relative to the product of these slice marginals. The reference density relative to (165) is

The actual density relative to the same measure, using (166), is

Here A=(X,Xs_1) is determined by X,s_1. Each p_c(S_i) is finite and positive almost surely under the actual law, since each coordinate has that marginal after averaging A. These densities therefore establish absolute continuity of the actual law with respect to the reference, rather than transferring arbitrary null sets between the singular laws.

The first-coordinate contribution to the expected log ratio is

The last equality uses independence of X_A from (S,K) at block entry. Each of the other q coordinates contributes h_f-h_{\mathrm{mid}}+\mathbb E\log j_{X_A}(S). The term \log\phi_{\mathbf S} contributes -\tfrac{kq}{2}\log(2\pi)-k\mathbb E\log\mathsf V, and \log t contributes D_{\mathrm{coup}}. These are finite log integrals. The signal and slice log densities are integrable because H(K,C_*)<\infty; the first-coordinate divergence is at most H(C_*\mid K); the Jacobian has its original true marginal; and

with \mathbb E[-\log r_*]<\infty. The coupling log likelihood is integrable by its finite divergence and the usual 1/e negative-part bound. Taking the log ratio now proves (163).

Discard X_A by data processing. The divergence of the tuple from the product of its (K,C_*)-conditional marginals is at most \mathcal E. Adding W and using an independent (K,C_*)-conditional copy of W in that reference adds at most H(W\mid K,C_*)\le b. Decomposing the same finite divergence after conditioning on W gives

The equality of every signal–message marginal, established before the lemma, is what makes the first term \ell times the same information. The second term is nonnegative. This proves (164).□

Proof. By definition, P_+=P_{\mathrm{mid}}+h_{\mathrm{mid}}-h_+. Combine (159) and (168), and take \gamma=\delta/2. For sufficiently large d, the coefficient -\delta da+C_a+\gamma da of \mathbb E N is nonpositive. The term u_d=O(\log d) is absorbed in C_2d. Since P,\Lambda\ge0, the remaining C'(P+d\Lambda)/d is bounded by (C_1/d)(P+\gamma d\Lambda). This proves (169).

Every new transcript is countable with finite entropy, specifies the new containing ball, and has \Lambda_+<\infty. Fresh future matrices can therefore be generated and the construction repeated. Starting from P_0=O(d) and \Lambda_0=0, iteration through m\le d steps has multiplier (1+C_1/d)^m\le e^{C_1}, which proves the potential bound in (170). Lemma 10.1 then gives the information bound. No linear-growth claim for unrestricted numbers of blocks is made.□

Proof. Set L=\log(1/\epsilon). For almost every realization of shared rule randomness, Lemmas 2.1 and 2.2 give Borel rules with the same uniform-prior experiment. All bounds below are numerical bounds on that conditional success probability, with constants independent of the realization, so they may be averaged. No jointly selected family of Borel versions is needed. The joint independence of the shared randomness and initial state from the signal and rows ensures the required signal-independent initial transcript for almost every value of the shared randomness.

We first explain why the restriction m\le d suffices. An angular cap of radius \epsilon has uniform mass at most (2\epsilon)^{d-1}. For example, its polar-area numerator is at most \epsilon^{d-1}/(d-1), while its denominator is at least (\pi/3)(\sqrt3/2)^{d-2}; the displayed bound follows for large d. There are at most (T+1)2^M terminal time–state pairs. For each pair, integration over its fixed fresh output law contributes at most one cap mass, even before multiplying by its reach probability. Summing and averaging over shared randomness gives

At indices with T<dL, \log(T+1)\le\log(d+1)+L. Since M=o(d^2), (171) implies L=o(d) along those indices. Also

eventually, and after padding to a multiple of k,

eventually. Thus every potentially short run lies within the proved horizon.

At indices with T\ge dL, the claimed conclusion holds with constant one. At all remaining indices, the horizon and width bounds just established apply eventually. Pad an early-stopping program by retaining its terminal state and stopping index, then ignore later observations and any suffix added to complete the last block. At boundaries its state is a message with at most e^b values. The augmented transcript retains all earlier auxiliary strings, but the learner uses only its state. Future matrices remain fresh, so Proposition 10.4 applies with m=\lceil T/k\rceil\le d. For each shared seed, I(S;K_m)\le C_0d(m+1), with an absolute C_0.

Let \pi be the success probability for that seed. The output uses information contained in K_m and fresh randomness. Under the product of its marginal and the uniform signal law, success has probability at most (2\epsilon)^{d-1}. By data processing and (1),

Combining the two bounds gives a numerical inequality in \pi; averaging it over the shared seed replaces \pi by the original success probability, at least 2/3. Thus, for absolute L_0,c_0>0, whenever L\ge L_0,

so T\ge k(c_0L/C_0-2). Choose L_1=\max\{L_0,4C_0/c_0\}. Since k\ge d/32, this gives

For L<L_1, the local full-data endpoint in Lemma 2.3 gives T>d/4, hence T\ge dL/(4L_1). The minimum of these absolute constants and one works for every allowed accuracy sequence, including nonmonotone ones.□

Proof. Apply [8, Theorem 3.3] with row count r, difference count p-1, tuple size p, and base and reweighted measure both equal to \mu. Its dimension condition is exactly r+p-1\le d-2, and its determinant and constrained Gaussian law are J and \gamma_{r,B_{\mathbf s}} above.□

Proof. A new sphere point avoids the proper affine span of its predecessors almost surely, so J>0 for \mu^{\otimes p}-almost every tuple. Apply (173) separately with r=k+1. Its dimension condition is

which follows from the integer inequality k+p+1<d. We check directly that the total mass on the label side is finite. The exponent in (172) is (d-k-3)/2\ge0, and hence

Here c_{d,k+1} is the positive normalizing constant in (172). Gram–Schmidt on the Gaussian rows expresses \sqrt{\det(XX^{\mathsf T})} as the product of their successive perpendicular lengths. Conditional on the preceding rows, these lengths have chi laws in dimensions d,d-1,\ldots,d-k. A chi variable in dimension v has a finite inverse moment of order p-1 whenever v>p-1, as is seen by integrating its density c_v t^{v-1}e^{-t^2/2} at zero and infinity. The smallest dimension here is d-k>p-1, so iterated conditioning makes the displayed determinant bound integrable.

Set H=1 in the r=k+1 instance. Its right side is the positive constant (2\pi)^{-(k+1)(p-1)/2} times \int J^{-(k+1)}d\mu^{\otimes p}, because the constrained matrix law is a probability. The finite label-side mass proves the claim. This argument is separate from the later logarithmic estimates.□

Proof. For each such value of A, on the label side of (173) with r=k, insert the everywhere-defined nonnegative Borel multiplier

The identity applies first to bounded truncations and then to this multiplier by monotone convergence. The label-side measure becomes the actual label law \rho_A(X,y)\,dy followed by p normalized posterior draws. The other side is the right side of (175) relative to \lambda. This proves the likelihood formula. In particular, no bounded posterior theorem has been applied to f_A; the only geometric input was the identity for \mu. Values on invalid label fibers are handled by the multiplier itself, so no unproved transfer of a Lebesgue-null set to the singular reference is being used.

We justify logarithmic integrability before taking any entropy difference. Since s_i\mid A has density f_A,

Together with \mathcal D(A)<\infty, this gives averaged absolute integrability of \log f_A(s_i). Let g be standard Gaussian density on \mathbb R^k. For almost every (A,X),

Moreover \mathbb E\|Y\|^2=k, because X is fresh and \|S\|=1. Since -\log g(Y)=\tfrac{k}{2}\log(2\pi)+\tfrac12\|Y\|^2, the negative part of \log\rho_A(X,Y) is integrable.

Put c=(2\pi)^{-k(p-1)/2} and

The r=k input shows 0<Z<\infty. Let Q be the probability with density cJ^{-k}/Z relative to \lambda. The likelihood formula gives \pi_A\ll\lambda. Since 0<J<\infty \lambda-almost surely, the density of Q is finite and strictly positive there; thus Q and \lambda have the same null sets, and \pi_A\ll Q. We may therefore write

Its positive part satisfies

so it is integrable by the two bounds just proved, without using \log J. Its negative part has integral at most 1/e: if v=d\pi_A/dQ, then \int v(\log v)_-\,dQ\le1/e. Hence \mathbb E D(\pi_A\|Q)<\infty, and the log likelihood in (176) is absolutely integrable on average. Rearranging that identity now proves full integrability of \log\rho_A(X,Y). This step has not used \log J.

By Lemma 11.2,

For probabilities P,Q and nonnegative F, exponential tilting gives

first for bounded F, and then for nonnegative F by truncation. This is the bounded variational inequality of [5, Equations (1.1)–(1.2)], with the limiting step given here. Apply it to F=(\log J)_- conditionally on A and average. Its right side is finite. The positive part of \log J is at most (p-1)\log2 by Hadamard’s inequality, since every chord has length at most two. This completes the integrability proof.□

Proof. Taking logarithms in (175) is legitimate by Lemma 11.3. Discard X by data processing, then condition on w. The latter step adds the conditional mutual information of the tuple and w, at most \log W. The product-reference chain rule, in the finite form discussed in [1, Section 3.3, Equations (13)–(18)], therefore yields

The label entropy is bounded by its cross entropy with N(Xc_A,r_A^2I_k). Freshness and the containing ball give \mathbb E(\|Y-Xc_A\|^2/r_A^2\mid A)\le k, whence

All terms are finite by (174) and the preceding lemma. Substitute this estimate and \log J=\sum_{i=2}^p\log\delta_i into (178). Since \log(r_A/\delta_i)\le\Delta_i, the result is

This finite relative entropy also implies that, almost surely, each conditional coordinate law given its predecessors is absolutely continuous with respect to \mu. The product-reference chain rule and the uniform choice of I give the exact identity

Dividing the preceding bound by p and using (p-1)/p\le1 gives (177).□

Proof. If I=1, set j=0. For I\ge2, set

When j=0, keep the old ball. When j\ge1, the predecessor span has dimension v=I-2 almost surely. Use orthonormal coordinates in that affine span based at s_1. The projection of s_I-s_1 has norm at most 2r_A, because both points lie in the old ball.

For every integer pair (j,v), fix an ordered 2^{-j}-net of the radius-two ball in \mathbb R^v with at most (1+4\cdot2^j)^v points. A maximal 2^{-j}-separated set has this size by comparing the volumes of its disjoint radius-2^{-j-1} balls with the containing ball. In dimension zero use one point. Record the first net point within 2^{-j} of the projection coordinates divided by r_A. After scaling and translating back, let c' be that point of the predecessor span. The in-span error and perpendicular error are both at most r_A2^{-j}. Hence B(c',2r_A2^{-j}) contains s_I; set r'=2r_A2^{-j}. It is at most r_A for j\ge1.

Figure 1 depicts this step, writing \eta=r_A2^{-j} and F=\operatorname{aff}(s_1,\ldots,s_{I-1}) within the illustration. Only the v-dimensional projection must be encoded; the perpendicular error is absorbed by the decoded radius. The radius does not increase, but the balls need not be nested.

For j\ge1, j\log2\le\Delta_I<(j+1)\log2. Thus

For j=0, either \Delta_I=0 or \Delta_I<\log2, and the same upper bound holds with r'=r_A. These inequalities give (179) and, using the finite expectations already proved, \mathbb E|\log r'|<\infty.

Encode j by the unary prefix code of length j+1 bits. For j\ge1, append a fixed-length net index of \lceil v\log_2(1+4\cdot2^j)\rceil bits. Given A_*, the dimension v is known, so the combined code is prefix-free. Since 1+4\cdot2^j\le5\cdot2^j, its length is at most (1+v)j+C v+2. Now 1+v\le p and j\log2\le\Delta_I, so its expected length in nats is at most p\mathbb E\Delta_I+C_1p. We give the countable conditional entropy step explicitly. For a conditioning value a_* with finite conditional expected length, let \ell_{a_*}(c) be the bit length and let p_{a_*}(c) be the conditional code distribution. Kraft’s inequality [7], in the finite or countable form stated in [4, Section 2.4.2, Theorem 2.4.2], gives

Normalize q_{a_*}(c)=2^{-\ell_{a_*}(c)}/K_{a_*}. Its cross entropy is

For a finite partition of the code alphabet with one remaining tail atom, nonnegative relative entropy bounds the partition entropy by its q_{a_*} cross entropy, and that cross entropy is at most the displayed full cross entropy. Refining such partitions gives the countable entropy by monotone convergence. Hence H(C\mid a_*)\le(\log2)\mathbb E[\ell_{a_*}(C)\mid a_*]. Finite conditional expected length holds for almost every a_* because its average is finite. Averaging proves the first inequality in (180).

Gram–Schmidt with fixed conventions supplies measurable orthonormal coordinates from the predecessor differences, and the fixed ordering resolves net ties. Define the code arbitrarily on the null degeneracy set. The decoded ball is therefore measurable. The pointwise construction puts s_I in that decoded ball outside the null degeneracy set. The event \{\|s_I-c'(A')\|\le r'(A')\} is Borel and has probability one. Disintegrating it over A' shows that its conditional probability is one for almost every A'. Thus the decoded ball supports the conditional signal law. Conditioning an absolutely continuous law on a discrete code keeps absolute continuity almost surely. The conditional entropy chain rule gives the second inequality in (180), and its finite right side proves the remaining finiteness claim.□

Proof. Condition on the shared rule randomness. For almost every value, the joint initialization independence in Section 2 leaves the initial state independent of the signal and all sample rows. By Lemmas 2.1 and 2.2, the conditional uniform-prior experiment has Borel rule versions. We prove the displayed numerical bound for each such value, with its conditional success probability. Averaging that bound at the end handles shared randomness without requiring jointly selected Borel versions.

Pad an early-stopping program to T observations by retaining its terminal state and stopping index, and then ignoring the remaining pairs. At each index the padded state has at most W values, and the final output law uses only that state. Divide the observations into blocks of length K, allowing a shorter final block. Set

For every nonempty block length 1\le k\le K, the inequalities k+p+1<d and a\le(d-1)/2 hold once d is sufficiently large. Initially A is the signal-independent initial state and the containing ball is B(0,1), so \Phi=0.

At a block, select a replica and encode its new ball as above. Combining (177)–(180) gives

Indeed k+p-a\le0, while p\ge d/16 and \log W\le2d^2 make the width charge O(d). The cancellation has a direct explanation: the likelihood charges k\Delta_I, the code charges at most p\Delta_I, and the radius credit is a\Delta_I=(K+p)\Delta_I.

Every posterior draw has the correct joint marginal with the block destination. Uniformly selecting one draw therefore preserves the learner’s state–signal marginal, and recording its code changes no marginal law. Generate the next Gaussian block independently of the pair consisting of the current signal and augmented analysis variables. Since the learner’s transition uses the past only through its state, induction preserves the actual state–signal marginal at every boundary. The predecessor points and codes are never given to the learner. All required finiteness properties propagate by Lemma 11.5. Thus after b=\lceil T/K\rceil blocks,

For T=0 this holds directly with b=0.

Write n=d-1. Lemma 2.3 gives \mu(B(c_A,r_A))\le(2r_A)^n. A density supported in a set E has relative entropy at least -\log\mu(E), by comparison with \mu(\,\cdot\mid E). Therefore

almost surely, and

The unconditional signal law remains \mu, so \mathcal D(A)=I(S;A). The final A includes the padded state w, and hence \mathcal D(A)\ge I(S;w).

Under the product of \mu and the output marginal, angular success has probability at most \epsilon^n, by Lemma 2.3. Data processing through the terminal output and then through the success event gives

by (1). This holds with the success probability for the fixed shared seed. Combining it with the potential upper bound and (183) proves (181) with constants independent of that seed. Averaging proves the asserted bound for the original shared randomness as well.□

Proof. Put L=\log(1/\epsilon)\ge\log10. The last statement follows by averaging over the uniform signal, so it suffices to prove the average statement. There are at most (T+1)2^M terminal time–state pairs. For each fixed pair its fresh output law succeeds on uniform mass at most \epsilon^{d-1}, by the cap bound and integration over that output law. More explicitly, for a terminal pair h let a_h(s) be that fixed output law’s success probability at signal s, and let t_h(s)=\Pr(h\text{ is reached}\mid S=s). The pair’s contribution is

because 0\le t_h(s)\le1. Summing over all pairs, for almost every shared seed and hence after averaging, yields

Equivalently,

At indices where T\ge dL the conclusion is immediate. At the other indices, (184) gives

For all sufficiently large d, uniformly for L\ge\log10, \log(dL+1)\le dL/6, while (d-1)L\ge dL/2. Consequently dL\le3M\log2+3\log(3/2)=o(d^2) along such short indices. In particular \log((T+2)2^M)\le2d^2 eventually, so Proposition 11.6 applies. It gives

with absolute c_0>0,C_0. Above a sufficiently large absolute threshold for L, use K\ge d/16 and absorb the constants to obtain T\ge c_1dL.

For completeness, the local full-data argument supplies the remaining constant-accuracy range with explicit constants. If T\le d/8, reveal every row and label. The conditional unknown component is uniform on a residual sphere of radius R. By isotropy and Markov’s inequality,

On R\ge1/2, antipodal residual points correspond to signals separated by at least one, so a radius-\epsilon error ball with \epsilon\le1/10 contains at most one point of each pair. Conditional success is at most 1/2, also for a randomized estimate. Total success is at most

Thus T>d/8. This proves T\ge c_2dL throughout the bounded range of L left above. Taking the minimum of the absolute constants completes the proof, including nonmonotone accuracy sequences and early stopping.□

Proof. Writing f=d\nu/d\sigma, we have \Phi(\nu)=\int f\log(f/J_\nu)\,d\sigma, with value zero where f=0. Both f and J_\nu are linear in \nu. For x>0,y>0, the Hessian of x\log(x/y) has quadratic form (a-bx/y)^2/x; continuity at x=0 gives joint convexity on x\ge0,y>0. Integration proves the mixture assertion.

By Jensen and rotational invariance,

For the last bound, distances greater than one contribute at most one. On 2^{-i-1}<\|u-s\|\le2^{-i}, the contribution is at most 2^{2p}2^{-i(n-2p)}; its sum converges since n-2p>0. Apply the entropy inequality (2), equivalently \E_\nu F\le D(\nu\|\sigma)+\log\E_\sigma e^F, to F=2\log J_\nu. This logarithm is bounded for fixed \nu. It gives 2B(\nu)\le D(\nu\|\sigma)+Cd. Finally, D(\sigma\|\sigma)=0 and J_\sigma\ge2^{-p}.□

Proof. Writing H_g=(gg^{\mathsf T})^{1/2}, an orthogonal change of coordinates and a nonsingular change of label coordinates give

The spherical coordinate formula follows by splitting a normalized standard Gaussian into its \ell row-space coordinates and the remaining coordinates: the squared projected length is \operatorname{Beta}(\ell/2,(d-\ell)/2). Domination proves absolute continuity for \nu. Lebesgue differentiation proves the claim about cube limits, and their defining integrals are jointly Borel.

Under G\otimes\sigma, the logarithm in the displayed formula is integrable. The beta density has integrable logarithms at its two endpoints. Gram–Schmidt expresses \det(GG^{\mathsf T}) as a product of chi-square variables of positive degrees, each with integrable logarithm. Domination by H preserves this baseline integrability for S\sim\nu. The projected likelihood ratio p_\nu/p_\sigma has relative entropy at most D(\nu\|\sigma)\le\log H by data processing. Its negative logarithmic part has expectation at most 1/e, since t\log^-(t)\le1/e under the probability reference. Its positive part is then finite as well. This proves the first integrability assertion.

For a positive-probability w, the actual law of (G,S) given w is dominated by P(W=w)^{-1} times G\otimes\sigma. Its image therefore has a density, and the baseline logarithm is integrable; averaging over w restores its original finite expectation. The log ratio of the actual image density to p_\sigma has relative entropy I(W;GS\mid G)\le H(W) and negative part at most 1/e. Thus the actual log density is integrable. Moreover,

where the last inequality uses I(S;G)=0 and the chain rule. Data processing under s\mapsto Gs gives integrability of the log ratio between the actual image density and p_{\nu_W}; subtracting it proves the remaining claim. If a finite entering variable is first fixed, its signal law is bounded relative to \sigma, and the same argument applies to each positive-probability case and then to their finite average.□

Proof. For r_i=2^{1-i}, let m_i(s)=\nu(B(s,r_i)). Dyadic shells give

Since m_i(s)\le H(2r_i)^n and n-p\ge1, choosing C_0 large makes the sum over i>b_H at most 2^{-p}. The term i=0 is itself 2^{-p}. Choose the first maximizer j=j(s)\le b_H. This is measurable and satisfies

For fixed X, compare the actual projected density to

where \gamma_r is the N(0,r^2I_p) density. At y=Xs, retain the j-summand and restrict it to B(s,r_j). Jensen’s inequality for the logarithm on that normalized restriction and \E_X\|X(s-u)\|^2=p\|s-u\|^2\le pr_j^2 give

Integrate over s. The comparison density has finite cross entropy by this bound and its finite Gaussian-mixture upper bound. The actual differential entropy is finite by Lemma 12.2. Nonnegativity of relative entropy to Q_X(y)\,dy proves the result.□

Proof. For s\in B(z,r), J_\nu(s)\ge(2r)^{-p}\nu(B(z,r)). Integrating its reciprocal over the ball proves the first inequality; if the ball has zero \nu-mass there is nothing to prove. The second uses J_\nu\ge2^{-p}.

Apply Theorem 12.4 with m=r=q=k, \ell=p=2k, B=2^p, and D=2^{p+n}H, using the ambient-center cap bound of Lemma 2.3. The angular margin is exactly p-k-(k-1)=1, and the radial margin is n-p>0. Moreover 1+\log^+(D/B)\le C(d+1+\log H)\le C(b_H+2); the factor 2^p is absorbed in e^{Cd}. This proves (186). The local inverse factor behind this substitution is \|u-s\|^{-k}\dist(u-s,E)^{-k}, where E is a linear subspace with \dim E\le k-1.□

Proof. Condition first on V=v with positive probability. Put \nu=P_{S\mid v} and H_v=P(V=v)^{-1}. In this conditional experiment w always ranges over values with P(V=v,W=w)>0; for these values put \nu_w=P_{S\mid v,w} and H_{vw}=P(V=v,W=w)^{-1}. The two posteriors are bounded by H_v\sigma and H_{vw}\sigma. Introduce a k-row Gaussian matrix A' independent of (S,V,A,W), and put X=(A;A'), Y=XS. Within the conditional experiment X is independent of S, and W depends on S only through (X,Y). The chain rule gives

For example, I(S;W)=I(X,Y;W)-I(X;W\mid S), and I(X;S)=0 converts the difference of the two row-information terms into -I(X;S\mid W). All displayed differential entropies are finite by Lemma 12.2, and I(X;S\mid W)\le H(W).

For fixed w, use the finite nonzero measure \rho_w=\nu_w/J_{\nu_w} as a reference, and write a_w=\rho_w(\sphere). First normalize this reference. The relative entropy of the actual conditional law of (X,S) with respect to P_{X\mid w}\otimes(\rho_w/a_w) is

Indeed, \log J_{\nu_w} is bounded for this v,w, and I(X;S\mid w)<\infty. Probability data processing under (X,s)\mapsto(X,Xs) makes the corresponding post-map relative entropy finite. For probability laws P\ll Q, the elementary bound

shows that a finite relative entropy has an integrable log density ratio. The post-map ratio is the actual conditional label density divided by p_{\rho_w}(X,Y)/a_w. Its logarithm is therefore integrable. Lemma 12.2 makes the logarithm of the actual conditional label density integrable as well, so \log p_{\rho_w}(X,Y) is integrable under the actual conditional law. Here p_{\rho_w} is the cube-limit density version; the same construction applies to a finite measure.

We may now expand both finite-reference divergences and subtract \log a_w from probability data processing. Before the map the divergence is I(X;S\mid w)+B(\nu_w), while after the map it is -h(Y\mid X,w)-\E[\log p_{\rho_w}(X,Y)\mid w]. Consequently,

This is precisely the finite-reference data-processing statement proved in Section 2, including when \rho_w has mass greater than one.

We now bound the last logarithm under the selected actual rows. Let Q be the original Gaussian law of A, still conditional on v, and write \kappa_w(a,as) for the Borel block probability of message w. For r_w(s)=\int\kappa_w(a,as)\,Q(da)>0, choose the conditional row law

when r_w(s)=0, assign Q_{s,w}=Q. The normalizer is positive for almost every (s,w) under the actual law, and this is a conditional version of the row law there. In particular Q_{s,w}\ll Q. Also

so the divergence is finite for almost every (s,w) under that law. The fresh A' retains its independent Gaussian law after conditioning on (A,s,w). For almost every such pair and for \delta>0, Jensen in A', followed by (2) with exponent k, gives

The last step uses the L^k triangle inequality and (186), whose fresh moment holds for every fixed s\in\sphere. The displayed row-charge inequality is used only for almost every (s,w) under the actual law, while \delta is positive.

Here is the exact null-set transfer in that passage. For each full-rank X, Lebesgue differentiation makes p_{\rho_w,1/a}(X,y) converge to p_{\rho_w}(X,y) for Lebesgue-almost every y. The failure set is jointly Borel by the cube definitions. Under the actual conditional law given (v,w), (X,S) is dominated by a finite multiple of \gamma_p\otimes\sigma; pushing forward shows that (X,Y) is absolutely continuous with respect to \gamma_p(dX)\,dy. Consequently it avoids this failure set, including after the actual rows have been tilted by w. Fatou applied to the nonnegative \log(1+p_{\rho_w,1/a}(X,Y)), after integrating (189) over s,w, proves the same integrated upper bound for \log(1+p_{\rho_w}(X,Y)), and hence for \log p_{\rho_w}. This argument does not invoke an unsmoothed moment at \rho_w-almost every fixed signal.

The preceding estimate supplies the quantitative positive-log bound; integrability of both signs was established before (188). Substituting Lemma 12.3 and (188)–(189) into (187), and using I(S;W)=\E_wD(\nu_w\|\sigma)-D(\nu\|\sigma), yields

Restore the average over v. \E\log H_V=H(V)\le\log N and \E\log H_{VW}=H(V,W)\le2\log N. Jensen bounds the averaged cutoff terms by C\log(d+1+2\log N), while \log N/k\le Cd. For fixed w, P_{S\mid W=w} is the finite mixture of \nu_w=P_{S\mid v,w} over v. Lemma 12.1 permits forgetting v, proving the drift.□

Proof. Fix the shared rule randomness with uniform-prior success at least 2/3, and apply Lemmas 2.2 and 2.1. Keep the internal transition and output randomness. Put L=\log(1/\epsilon). Under the product of the marginal laws of (S,\widehat S), angular success has probability at most \epsilon^{d-1}, by Lemma 2.3. Equation (1) therefore gives

Assume T<dL. The other case is already sufficient. The terminal state and stopping index have at most (T+1)2^M values, so the left side of (190) is at most M\log2+\log(T+1). Since \log(T+2)\le C+\log d+\log(L+1)\le C+\log d+L, absorption gives

For M=o(d^2), pad stopped states with their original terminal labels and indices and add unused rows to complete the last block. Every padded layer has at most N=(T+2)2^M states and \log N=o(d^2).

The initial conditional signal law is \sigma, because the model makes initialization independent of the signal conditional on the fixed shared rule randomness. Iterate Proposition 12.6 for \lceil T/k\rceil blocks and apply Lemma 12.1. For the final padded state F,

The output is generated from F and fresh randomness. Data processing with (190) gives L\le C(1+T/d). The 2/3 instance of Lemma 2.3 gives T>d/4 for this same prior and exact observation model. Thus 1+T/d\le5T/d, proving the claimed sample bound. The global-clock calculation controls only the padded width; the precision-dependent conclusion comes from the block drift.□

Proof. For the selected cell C,

using \sigma(C)\le (2r_j)^{d-1} and \log p_C\le 0. The log ratio here is at most \log(p_D/\sigma(D))+\log(p_C/p_D). The expected first term is at most I_V by relative entropy under the partition for each v; (191) bounds the other term. Since \alpha/(d-1)=1/2, the correction removes at most half the information, up to an additive O(d).□

Proof. The volume is positive almost surely, since \nu gives zero mass to affine spaces of dimension i<\alpha. This last fact follows by covering any bounded portion by O(r^{-i}) balls of radius r as r\downarrow 0, and suffices by conditioning successively on the previous draws.

We order the vectors z_i-u greedily, taking at each step one of largest distance to the span of those preceding. Every tuple admits such an ordering. By exchangeability, it suffices to bound the expectation restricted to the original order being greedy and multiply by k!; this also allows ties. In this order let \delta_i be the distance to the preceding span, with the norm used for the first vector. Then S=\prod_i\delta_i, and the distances are nonincreasing. Fix their length bins

We will first bound the probability of these bins and the greedy conditions, then sum their contributions to the inverse volume.

Given the first i-1 draws, let e_j, j<i, be their translated vectors’ successive Gram–Schmidt axes. Group these axes according to h=\ell_j. Greediness forces the projection of z_i-u onto each group to have norm at most 2^{-h}: before the first axis in that group was chosen, the residual norm of z_i-u was no greater than the distance chosen at that step. Its residual norm after all preceding axes is at most 2^{-\ell_i}.

In a group of dimension a_h, cover the ball of radius 2^{-h} by a net of radius 2^{-\ell_i}2^{-(\ell_i-h)}. Euclidean ball packing bounds its cardinality by (3\cdot 2^{2(\ell_i-h)})^{a_h}. The distinct group indices are integers h\le\ell_i, so their squared net errors sum to at most

Including the orthogonal residual, all allowed points z_i therefore lie in at most 3^{i-1}2^{2\sum_{j<i}(\ell_i-\ell_j)} ambient balls of radius 2\cdot2^{-\ell_i}. These necessary constraints involve only the preceding draws and the fixed bins. The local ball bound gives their conditional probability at most

We may multiply these bounds sequentially, imposing only the necessary constraints just described and never conditioning preceding draws on future greedy choices. Use the local estimate when \ell_i\ge0 and probability one otherwise. Put

The double sum in the product exponent satisfies

Indeed, each inner sum is (i-1)\ell_i-\sum_{j<i}\ell_j. Its first term is at most k\ell_i, subtracting nonnegative \ell_j can only decrease it, and each negative index contributes at most k times. The probability of the greedy and length conditions is consequently at most

On these bins, S^{-n}\le2^{nk}2^{n(P-N)}. When negative bins dominate, the large distances already make this inverse volume small; otherwise the local probability bound supplies the needed decay. For N\le2P, combining the two bounds gives the exponent

since \alpha-6k-n\ge3 and n\ge3 for large d. For N>2P, use probability at most one: then n(P-N)\le -(P+N), because (n+1)P\le(n-1)N for n\ge3. Thus either region contributes at most \exp(Cdk)2^{-(P+N)}. The sum of 2^{-(P+N)}, even over all integer tuples, is 3^k. This factor and k! are absorbed by \exp(Cdk), proving (194) at arbitrary length scales.□

Proof. Take k independent draws from \eta/q. By (193), scaling the space (also scaling u) by (C^d m_0/q)^{1/\alpha} makes (194) applicable. In the original space the bound for \mathbb E S^{-n} is multiplied by (C^d m_0/q)^{kn/\alpha}. For fixed draws, the probability that all \|A(z_i-u)\|_\infty\le a is bounded by (2a)^{nk}(2\pi)^{-nk/2} S^{-n}, by the maximum Gaussian density in k coordinates for each row. The A-expectation of the cube mass to the power k is q^k times the draws’ average of this event probability. Thus we get (195) for the mass divided by (2a)^n in place of the density. Fatou’s lemma proves it for the liminf. Constants use that n/\alpha is bounded.□

Proof. Conditional on V,D,A,b,W, the density of U relative to \lambda_{A,b} is

since the message given V,A,b no longer depends on U. Compare on this fiber with the subprobability density

where zero-denominator terms are omitted, and the indicator restricts to the specified bin of m_{\mu_w} as well as to D. Each included fiber density before its mixing weight has integral one. Omitting bins can only reduce the total mass, so the displayed mixture is a subprobability.

On the actual draw, the term of its bin has positive denominator almost surely. Indeed, a zero denominator with g_{0,A}(b)>0 makes f_w{\bf 1}_{D,\ t'} zero \lambda_{A,b}-almost everywhere. The actual conditional law is absolutely continuous on the fiber, and f_w(U)>0 almost surely. The log ratio of the true density to the comparison density is therefore

The last term averages to H(t\mid W,D). Once integrability is verified, the nonnegative expectation of this log ratio gives (198), by Jensen on each fiber against the subprobability.

We verify the logarithmic integrability needed here and in (197). The log densities \log f_V(U) and \log f_W(U) are integrable by the state probability bounds and x\log^-x\le1/e for densities relative to a probability. Both projection densities have integrable positive log parts: they are bounded above by g_{0,A}/p_v or g_{0,A}/p_w, and

has integrable positive log part. For this last assertion, Gram–Schmidt on Gaussian rows gives squared successive distances with conditional chi-square laws and integrable logarithms.

For the incoming density g_{v,D,A}, the Gaussian comparison also bounds the negative log part. A log density ratio under its numerator law has expected negative part at most 1/e when compared to a probability. The Gaussian comparison density has integrable negative log part by r\le2 and the squared norm estimate, while -\log p_D has finite expectation. Thus \log g_{v,D,A}(b) is integrable.

The displayed fiber log ratio now has integrable positive part, using the outgoing positive log bound, the incoming integrability, and the finite expected surprisal for t\mid W,D. Its expected negative part is at most 1/e, which remains true for comparison with a subprobability. The log ratio is therefore integrable, and its displayed decomposition also gives integrability of \log g_{w,D,t,A}(b). This justifies (198).□