Introduction
Softmax attention normalizes each query’s scores into a distribution over keys. In optimal-transport terms, softmax is one row-normalization step of the Sinkhorn algorithm for an entropic OT problem. It also solves a one-sided entropic OT problem exactly [21 , 39 ] . Iterating Sinkhorn to convergence also enforces the column marginal [43 ] ; with the uniform marginal used by Sinkformers, every key then receives the same total attention.
In causal language models, column balancing faces two obstructions (§ 2 ). First, the only lower-triangular doubly stochastic matrix is the identity, so balanced OT degenerates. Second, relaxing the column marginal is not enough: any column normalization whose column sums run over all rows makes the output of row t t t depend on row t + 1 t+1 t + 1 , whose query is computed from the token that row t t t is trained to predict. Under teacher forcing this leaks the label and lowers the validation loss artificially. Prefix column masses avoid this leakage [11 ] .
We address both obstructions with an unbalanced Sinkhorn iteration whose column scaling for row t t t uses only the prefix mass M t j = ∑ i ≤ t P i j M_{tj} = \sum_{i \le t} P_{ij} M t j = ∑ i ≤ t P ij . It is prefix-consistent by construction, interpolates between softmax (ρ = 0 \rho= 0 ρ = 0 ) and a strongly balancing regime (ρ → 1 \rho\to1 ρ → 1 ), and at its fixed point takes the form
log P t j = log K t j − γ log M t j − lse t , γ = ρ 1 − ρ \log P_{tj} = \log K_{tj} - \gamma\log M_{tj} - \operatorname{lse}_t,\qquad\gamma= \frac{\rho}{1-\rho} log P t j = log K t j − γ log M t j − lse t , γ = 1 − ρ ρ
where lse t \operatorname{lse}_t lse t is the log-normalizer of row t t t . In a preregistered comparison at 100M parameters, this operator lowers the validation loss at twice the training length by 0.45 nats relative to softmax. It also beats log-n n n softmax, which multiplies the scores by a factor growing like log t t t [5 , 28 ] , by 0.30. The correction − γ log M -\gamma\log M − γ log M enters the logits as an additive bias. Exploratory comparisons suggest that its distance dependence accounts for the gain: an explicit learnable log-distance bias with softmax achieves lower loss, at 40% of the cost.
We analyze the implicit prior of the causal OT operator: the attention pattern it produces when content does not discriminate between keys. The far mass at a given context length is the attention that queries put on keys more than the training length back. Here attention dilutes if the mass in every fixed-length recent window vanishes as the context grows (see § 6 for prior terminology). A relative prior is summable if its weights, as a function of distance, have a finite sum; a fixed window then keeps a share bounded away from zero, and the far mass stays bounded. The OT prior is not a function of distance alone, so for it we speak of dilution only.
Contributions.
Dilution. For scores bounded by B B B , as in pre-norm Transformers, and any ρ < 1 \rho< 1 ρ < 1 , every entry of the fixed point satisfies P t j ≤ ( e 2 B / t ) 1 − ρ P_{tj} \le(e^{2B}/t)^{1-\rho} P t j ≤ ( e 2 B / t ) 1 − ρ (Theorem 5 ), so the mass within any fixed-length recent window vanishes as the context grows: the implicit prior dilutes.
Exact prior. With constant scores, t P t , ⌊ s t ⌋ → ( log 1 / s ) − ρ / Γ ( 1 − ρ ) tP_{t,\lfloor st\rfloor} \to(\log1/s)^{-\rho}/\Gamma(1-\rho) t P t , ⌊ s t ⌋ → ( log 1/ s ) − ρ /Γ ( 1 − ρ ) uniformly on compact subsets of ( 0 , 1 ) (0,1) ( 0 , 1 ) (Theorems 6 and 7 ): the prior depends on the ratio t / j t/j t / j , and near the diagonal it is an exact power law d − ρ d^{-\rho} d − ρ (Theorem 8). The same limit holds after any fixed number k ≥ 2 k \ge2 k ≥ 2 of iterations (Theorem 9), and with i.i.d. bounded scores the fixed point factors into this prior times softmax-like content weights (Proposition 10).
Far mass of positional encodings. Writing positional schemes as potentials on the logits, we show that finite-dimensional group representations cannot produce a logarithmic kernel (Proposition 12). We classify common encodings by whether they keep a bounded far mass or dilute (Proposition 14), and give discrete near-boundary window-mass bounds under bounded content (Corollary 16).
Experiments. The OT operator’s gain over softmax holds in a preregistered test at 100M parameters, and exploratory analyses trace it to the distance prior (§ 5.1 ). Across fifteen positional schemes, far mass and long-context loss group by the cases of Proposition 14, not by the form of the bias (§ 5.2 ). Changing a trained model’s bias only beyond the training length moves its long-context loss in the predicted direction on all 30 checkpoints, and a margin on a learned exponent bounds the far mass during training (§ 5.3 ); CABLE beats RoPE with YaRN on every seed at three training lengths (§ 5.2 ).
Scope. All theory concerns causal attention with a prefix-consistent operator. Without a causal constraint the column marginal is a genuine constraint and none of the results apply; we return to this in § 7 . Our measure of extrapolation is the validation loss beyond the training length, which rewards not being disturbed by distant context rather than using it.
Background: attention as optimal transport under a causal mask
Attention. One head of a Transformer [48 ] maps queries q t q_t q t , keys k j k_j k j and values w j w_j w j (t , j = 1 , … , n t,j=1,\ldots,n t , j = 1 , … , n ; v v v will denote a scaling vector) to outputs y t = ∑ j P t j w j y_t=\sum_j P_{tj}w_j y t = ∑ j P t j w j with attention weights
P t j = exp ( S t j / ε ) ∑ j ′ ∈ M t exp ( S t j ′ / ε ) ( j ∈ M t ) , S t j = ⟨ q t , k j ⟩ d + b t j , (1) P_{tj}=\frac{\exp(S_{tj}/\varepsilon)}{\sum_{j'\in\mathcal{M}_t}\exp(S_{tj'}/\varepsilon)}\quad(j\in\mathcal{M}_t),\qquad S_{tj}=\frac{\langle q_t,k_j\rangle}{\sqrt{d}}+b_{tj}, \tag*{(1)} P t j = ∑ j ′ ∈ M t exp ( S t j ′ / ε ) exp ( S t j / ε ) ( j ∈ M t ) , S t j = d ⟨ q t , k j ⟩ + b t j , (1)
where d d d is the head dimension, b t j b_{tj} b t j an optional additive positional bias, and M t \mathcal{M}_t M t the keys that query t t t may attend to: M t = { 1 , … , t } \mathcal{M}_t=\{1,\ldots,t\} M t = { 1 , … , t } under the causal mask of a language model, with support M = { ( t , j ) : j ≤ t } \mathcal{M}=\{(t,j):j\le t\} M = {( t , j ) : j ≤ t } . With the kernel K = e S / ε K=e^{S/\varepsilon} K = e S / ε this is P = rownorm ( K ) P=\operatorname{rownorm}(K) P = rownorm ( K ) , where rownorm divides each row of K K K by its sum over M t \mathcal{M}_t M t . We keep the temperature ε \varepsilon ε explicit (all models use ε = 1 \varepsilon=1 ε = 1 ) because it is the entropic regularization strength: row t t t of softmax maximizes ∑ j ∈ M t P t j S t j + ε H ( P t ⋅ ) \sum_{j\in\mathcal{M}_t}P_{tj}S_{tj}+\varepsilon H(P_{t\cdot}) ∑ j ∈ M t P t j S t j + ε H ( P t ⋅ ) , H ( p ) = − ∑ j p j log p j H(p)=-\sum_jp_j\log p_j H ( p ) = − ∑ j p j log p j , over probability vectors [29 §§2.2–2.3] .
Entropic optimal transport and Sinkhorn. Entropic OT [7 , 34 ] , with cost − S t j -S_{tj} − S t j , sums this objective over the rows and constrains both marginals,
max P ≥ 0 ∑ t , j P t j S t j + ε H ( P ) s.t. P 1 = a , P T 1 = b , (2) \max_{P\ge0}\sum_{t,j}P_{tj}S_{tj}+\varepsilon H(P)\quad\text{s.t.}\quad P\mathbf{1}=\mathbf{a},\quad P^{\mathsf{T}}\mathbf{1}=\mathbf{b}, \tag*{(2)} P ≥ 0 max t , j ∑ P t j S t j + ε H ( P ) s.t. P 1 = a , P T 1 = b , (2)
with solution P = diag ( u ) K diag ( v ) P=\operatorname{diag}(u)K\operatorname{diag}(v) P = diag ( u ) K diag ( v ) . Sinkhorn’s algorithm alternates the row and column scalings,
u ← a / ( K v ) , v ← b / ( K T u ) , (3) u\leftarrow\mathbf{a}/(Kv),\qquad v\leftarrow\mathbf{b}/(K^{\mathsf{T}}u), \tag*{(3)} u ← a / ( K v ) , v ← b / ( K T u ) , (3)
each step enforcing one marginal exactly (divisions are entrywise). With a = 1 \mathbf{a}=\mathbf{1} a = 1 and the start v = 1 v=\mathbf{1} v = 1 the first row step gives P = rownorm ( K ) P=\operatorname{rownorm}(K) P = rownorm ( K ) : softmax is the first half iteration of Sinkhorn [39 ] . In the log domain log v j \log v_j log v j acts as a bias on key j j j that lowers the logits of keys receiving more than their share b j b_j b j .
Unbalanced transport and ρ \rho ρ . Replacing the hard column constraint in (2) by a penalty λ KL ( P T 1 ∥ b ) \lambda\operatorname{KL}(P^{\mathsf{T}}\mathbf{1}\mathbin{\|}\mathbf{b}) λ KL ( P T 1 ∥ b ) keeps the row step and damps the column step,
v ← ( b / K T u ) ρ , ρ = λ λ + ε ∈ [ 0 , 1 ] (4) v\leftarrow(\mathbf{b}/K^{\mathsf{T}}u)^\rho,\qquad\rho=\frac{\lambda}{\lambda+\varepsilon}\in[0,1] \tag*{(4)} v ← ( b / K T u ) ρ , ρ = λ + ε λ ∈ [ 0 , 1 ] (4)
[6 Table 1] . Only the fraction ρ \rho ρ of the balancing bias is applied: ρ = 1 \rho=1 ρ = 1 is balanced Sinkhorn and ρ = 0 \rho=0 ρ = 0 returns softmax. The row constraint stays hard, so every output is a weighted average of the values. Relaxing it too would give row t t t a total mass growing like a power of t t t under a causal mask. Outputs beyond the training length would then be larger than any seen in training.
Two obstructions to the column constraint.
Lemma 1 (Triviality of causal doubly stochastic matrices). A nonnegative lower-triangular matrix with all row and column sums equal to one is the identity.
Proof. Column n n n has a single entry P n n P_{nn} P nn , so P n n = 1 P_{nn}=1 P nn = 1 and row n n n has no other mass. Removing row and column n n n leaves a matrix with the same property; induct.
Relaxing the column marginal avoids this degeneracy, but column normalization over all rows couples row t t t to future queries. Under teacher forcing, these queries contain ground-truth future tokens, so their contributions to the column mass leak target information into row t t t (§ 1 ). We call an operator prefix-consistent if row t t t of its output depends only on rows 1 , … , t 1,\ldots,t 1 , … , t of its input, and require it under a causal mask.
The prefix-consistent unbalanced operator. Following the prefix-mass construction of Foss [11 ] , we replace the column mass by M t j = ∑ i = j t P i j M_{tj} = \sum_{i=j}^{t} P_{ij} M t j = ∑ i = j t P ij (j ≤ t j \le t j ≤ t ), the mass that column j j j has received from rows 1 , … , t 1,\ldots,t 1 , … , t . Starting from the all-ones array v ( 1 ) = 1 v^{(1)} = 1 v ( 1 ) = 1 , iteration k k k sets
P ( k ) = rownorm ( K ⊙ v ( k ) ) , log v ( k + 1 ) = ρ ( log v ( k ) − log M ( k ) ) , (5) P^{(k)} = \operatorname{rownorm}(K \odot v^{(k)}), \qquad\log v^{(k+1)} = \rho\left(\log v^{(k)} - \log M^{(k)}\right), \tag*{(5)} P ( k ) = rownorm ( K ⊙ v ( k ) ) , log v ( k + 1 ) = ρ ( log v ( k ) − log M ( k ) ) , (5)
where M ( k ) M^{(k)} M ( k ) is the prefix mass of P ( k ) P^{(k)} P ( k ) , ⊙ \odot ⊙ is the entrywise product, and log \log log acts entrywise. Unlike the vector v v v of (3) , v ( k ) v^{(k)} v ( k ) and M ( k ) M^{(k)} M ( k ) are lower-triangular arrays: the scaling that row t t t applies to key j j j depends on t t t . Every iteration ends with a row normalization, so the output is row-stochastic; k = 1 k = 1 k = 1 is softmax. The damping acts on the accumulated scaling v v v , as in unbalanced Sinkhorn; damping the relative update P ← P ⊙ M − ρ P \leftarrow P \odot M^{-\rho} P ← P ⊙ M − ρ instead would keep the balanced fixed point, the identity of Lemma 1 . At a fixed point log v = − γ log M \log v = -\gamma\log M log v = − γ log M with γ = ρ / ( 1 − ρ ) \gamma= \rho/(1-\rho) γ = ρ / ( 1 − ρ ) :
P t j = λ t K t j M t j − γ ( j ≤ t ) , ∑ j ≤ t P t j = 1 , P_{tj} = \lambda_t K_{tj} M_{tj}^{-\gamma}\quad(j \le t), \qquad\sum_{j \le t} P_{tj} = 1, P t j = λ t K t j M t j − γ ( j ≤ t ) , j ≤ t ∑ P t j = 1 ,
where λ t > 0 \lambda_t > 0 λ t > 0 is the normalizer of row t t t . The operator solves no single OT problem: row i < t i < t i < t is balanced against the prefix mass available at time i i i . The correction − γ log M t j -\gamma\log M_{tj} − γ log M t j acts as an additive bias. Under uniform attention M t j = ∑ i = j t 1 / i ≈ log ( t / j ) M_{tj} = \sum_{i=j}^{t} 1/i \approx\log(t/j) M t j = ∑ i = j t 1/ i ≈ log ( t / j ) grows with distance because distant keys have received attention from more queries. The correction therefore down-weights distant keys; § 3 derives the resulting prior. We use 1 / ( 1 + γ ) = 1 − ρ 1/(1+\gamma) = 1-\rho 1/ ( 1 + γ ) = 1 − ρ and γ / ( 1 + γ ) = ρ \gamma/(1+\gamma) = \rho γ / ( 1 + γ ) = ρ throughout, and write Λ t = ∑ i ≤ t λ i \Lambda_t = \sum_{i \le t} \lambda_i Λ t = ∑ i ≤ t λ i with Λ 0 = 0 \Lambda_0 = 0 Λ 0 = 0 ; Appendix § 9 collects the notation.
Bounded scores. In a pre-norm Transformer [54 ] every attention layer reads a LayerNorm output [3 ] , whose norm is bounded by a constant of the model, so queries, keys and every quantity computed linearly from the input are bounded independently of the length (bounded inputs ). The scores are bounded by B B B if ∣ S t j / ε ∣ ≤ B |S_{tj}/\varepsilon| \le B ∣ S t j / ε ∣ ≤ B for all t , j t,j t , j . This holds for dot-product scores with rotary encodings [45 ] , which preserve norms, and fails for biases that decrease without bound in the distance, such as ALiBi’s − m ( t − j ) -m(t-j) − m ( t − j ) [36 ] or a log-distance bias − c log ( 1 + t − j ) -c\log(1+t-j) − c log ( 1 + t − j ) . § 3 shows that attention dilutes under bounded scores. Avoiding dilution therefore requires a positional term with unbounded decay.
The implicit prior of causal OT attention
We derive the positional prior induced by the operator without an added positional encoding. The fixed point is computed row by row (§ 3.1 ); under bounded scores every fixed window loses its share of attention (§ 3.2 ); without content the prior has an explicit, scale-invariant shape (§ 3.3 ). The same limit holds with finite iterations and i.i.d. content (§ 3.4 ). All proofs are in Appendix § 10 . Throughout, ρ ∈ [ 0 , 1 ) \rho\in[0,1) ρ ∈ [ 0 , 1 ) and P P P is the fixed point (FP) unless stated otherwise; L L L denotes a window length, which in the experiments is the training length.
A row recursion
Prefix consistency turns (FP) into a recursion over rows. Given rows 1 , … , t − 1 1,\ldots,t-1 1 , … , t − 1 , let C j = M t − 1 , j ≥ 0 C_j=M_{t-1,j}\ge0 C j = M t − 1 , j ≥ 0 be the mass that column j j j has received (C t = 0 C_t=0 C t = 0 ). Since M t j = C j + P t j M_{tj}=C_j+P_{tj} M t j = C j + P t j , the unknowns x j = P t j x_j=P_{tj} x j = P t j of row t t t solve
x j ( C j + x j ) γ = λ t K t j ( j ≤ t ) , ∑ j x j = 1. (6) x_j(C_j+x_j)^\gamma=\lambda_tK_{tj}\quad(j\le t),\qquad\sum_j x_j=1. \tag*{(6)} x j ( C j + x j ) γ = λ t K t j ( j ≤ t ) , j ∑ x j = 1. (6)
Here C j C_j C j and K t j K_{tj} K t j are known from the previous rows and the scores; only the x j x_j x j and the normalizer λ t \lambda_t λ t are unknown, which is why we drop the row index.
Lemma 2. For any K > 0 K>0 K > 0 , (FP) has a unique solution, obtained row by row from (6) . Each x j x_j x j is increasing in λ t \lambda_t λ t and decreasing in C j C_j C j , and x j 1 + γ ≤ λ t K t j x_j^{1+\gamma}\le\lambda_tK_{tj} x j 1 + γ ≤ λ t K t j , i.e. P t j 1 + γ ≤ λ t K t j P_{tj}^{1+\gamma}\le\lambda_tK_{tj} P t j 1 + γ ≤ λ t K t j , with equality on the diagonal. At every fixed finite length, iteration (5) converges to this solution.
The mass a column has received is determined, up to a constant factor, by the normalizers of the rows that have seen it.
Lemma 3. For j ≤ t j\le t j ≤ t ,
∑ i = j t λ i K i j ≤ M t j 1 + γ ≤ ( 1 + γ ) ∑ i = j t λ i K i j . \sum_{i=j}^{t}\lambda_iK_{ij}\le M_{tj}^{1+\gamma}\le(1+\gamma)\sum_{i=j}^{t}\lambda_iK_{ij}. i = j ∑ t λ i K ij ≤ M t j 1 + γ ≤ ( 1 + γ ) i = j ∑ t λ i K ij . For constant scores the sum is Λ t − Λ j − 1 \Lambda_t-\Lambda_{j-1} Λ t − Λ j − 1 , the clock time elapsed since key j j j appeared. This elapsed time fixes M t j 1 + γ M_{tj}^{1+\gamma} M t j 1 + γ , and with it the correction − γ log M t j -\gamma\log M_{tj} − γ log M t j , up to a factor between 1 1 1 and 1 + γ 1+\gamma 1 + γ , which tends to 1 + γ 1+\gamma 1 + γ away from the diagonal (Lemma 18). Both lemmas hold for arbitrary scores.
Dilution
To bound fixed-window mass, we first bound the row normalizer. It sets the scale of every entry in a row and is at most of order 1 / t 1/t 1/ t :
Lemma 4. If ∣ S / ε ∣ ≤ B |S/\varepsilon|\le B ∣ S / ε ∣ ≤ B then λ t ≤ e B / t \lambda_t\le e^B/t λ t ≤ e B / t . With constant scores, t λ t ≤ 1 t\lambda_t\le1 t λ t ≤ 1 .
Theorem 5 (Dilution under bounded scores). If ∣ S / ε ∣ ≤ B |S/\varepsilon|\le B ∣ S / ε ∣ ≤ B , then for all j ≤ t j\le t j ≤ t
P t j ≤ ( e 2 B t ) 1 − ρ , ∑ t − L < j ≤ t P t j ≤ L ( e 2 B t ) 1 − ρ → t → ∞ 0. P_{tj}\le\left(\frac{e^{2B}}{t}\right)^{1-\rho},\qquad\sum_{t-L<j\le t}P_{tj}\le L\left(\frac{e^{2B}}{t}\right)^{1-\rho}\xrightarrow[t\to\infty]{}0. P t j ≤ ( t e 2 B ) 1 − ρ , t − L < j ≤ t ∑ P t j ≤ L ( t e 2 B ) 1 − ρ t → ∞ 0.
For every ρ < 1 \rho<1 ρ < 1 and every bounded content, no fixed window keeps a positive share of attention as the context grows: attention dilutes. The bound becomes informative only when t ≫ e 2 B t\gg e^{2B} t ≫ e 2 B and does not specify the attention pattern. With constant scores, we can compute that pattern exactly.
The scaling limit with constant scores
Constant scores isolate the operator’s positional prior. Let
C ρ = ( 1 + γ ) − ρ Γ ( 1 − ρ ) , a ∗ = C ρ − 1 / ( 1 − ρ ) = ( ( 1 + γ ) ρ Γ ( 1 − ρ ) ) 1 / ( 1 − ρ ) . C_\rho=(1+\gamma)^{-\rho}\Gamma(1-\rho),\qquad a^*=C_\rho^{-1/(1-\rho)}=\left(\frac{(1+\gamma)^\rho}{\Gamma(1-\rho)}\right)^{1/(1-\rho)}. C ρ = ( 1 + γ ) − ρ Γ ( 1 − ρ ) , a ∗ = C ρ − 1/ ( 1 − ρ ) = ( Γ ( 1 − ρ ) ( 1 + γ ) ρ ) 1/ ( 1 − ρ ) .
Theorem 6 (Asymptotics of the row normalizers). With constant scores, t λ t → a ∗ t\lambda_t\to a^* t λ t → a ∗ . For ρ = 1 / 2 \rho=1/2 ρ = 1/2 , a ∗ = 2 / π a^*=2/\pi a ∗ = 2/ π .
The bound of Lemma 4 is thus attained up to a factor that depends on ρ \rho ρ alone.
Theorem 7 (Scale-invariant limit shape of the implicit prior). With constant scores, for every δ ∈ ( 0 , 1 2 ) \delta\in(0,\frac{1}{2}) δ ∈ ( 0 , 2 1 ) , uniformly in s ∈ [ δ , 1 − δ ] s \in[\delta,1-\delta] s ∈ [ δ , 1 − δ ] ,
t P t , ⌊ s t ⌋ ⟶ f ( s ) = ( log 1 / s ) − ρ Γ ( 1 − ρ ) . tP_{t,\lfloor st\rfloor} \longrightarrow f(s)=\frac{(\log1/s)^{-\rho}}{\Gamma(1-\rho)}. t P t , ⌊ s t ⌋ ⟶ f ( s ) = Γ ( 1 − ρ ) ( log 1/ s ) − ρ .
The prior depends on the key only through its relative position s = j / t s=j/t s = j / t , and its total mass is ∫ 0 1 f = 1 \int_0^1 f=1 ∫ 0 1 f = 1 . It increases toward the query, where it has an integrable singularity at s = 1 s=1 s = 1 , and decays only logarithmically toward the start of the context (s → 0 s \to0 s → 0 ), so a key at any fixed fraction s s s of the context keeps a weight of order 1 / t 1/t 1/ t .
Theorem 7 excludes keys near the diagonal, which determine fixed-window mass. There log ( t / j ) ≈ d / t \log(t/j)\approx d/t log ( t / j ) ≈ d / t for d = t − j d=t-j d = t − j , and the limit becomes a power law.
Theorem 8 (Power law near the diagonal). Let z − 1 = 0 z_{-1}=0 z − 1 = 0 and let z d z_d z d solve z d γ ( z d − z d − 1 ) = 1 z_d^\gamma(z_d-z_{d-1})=1 z d γ ( z d − z d − 1 ) = 1 . With constant scores,
for fixed d ≥ 0 d \ge0 d ≥ 0 , t 1 − ρ P t , t − d → a ∗ 1 − ρ ( z d − z d − 1 ) t^{1-\rho}P_{t,t-d}\to a^{*\,1-\rho}(z_d-z_{d-1}) t 1 − ρ P t , t − d → a ∗ 1 − ρ ( z d − z d − 1 ) ;
for d = d t → ∞ d=d_t\to\infty d = d t → ∞ with d t / t → 0 d_t/t\to0 d t / t → 0 , P t , t − d = t ρ − 1 d − ρ Γ ( 1 − ρ ) − 1 ( 1 + o ( 1 ) ) P_{t,t-d}=t^{\rho-1}d^{-\rho}\Gamma(1-\rho)^{-1}(1+o(1)) P t , t − d = t ρ − 1 d − ρ Γ ( 1 − ρ ) − 1 ( 1 + o ( 1 )) .
The two regimes, fixed d d d in (1) and 1 ≪ d ≪ t 1\ll d\ll t 1 ≪ d ≪ t in (2), match: by Lemma 21, z d − z d − 1 ∼ ( 1 + γ ) − ρ d − ρ z_d-z_{d-1}\sim(1+\gamma)^{-\rho}d^{-\rho} z d − z d − 1 ∼ ( 1 + γ ) − ρ d − ρ , and since a ∗ 1 − ρ ( 1 + γ ) − ρ = 1 / Γ ( 1 − ρ ) a^{*\,1-\rho}(1+\gamma)^{-\rho}=1/\Gamma(1-\rho) a ∗ 1 − ρ ( 1 + γ ) − ρ = 1/Γ ( 1 − ρ ) , the limit in (1) behaves for large d d d like the power law d − ρ / Γ ( 1 − ρ ) d^{-\rho}/\Gamma(1-\rho) d − ρ /Γ ( 1 − ρ ) of (2). Together, these limits describe the fixed point at three distance scales: a discrete profile for d = O ( 1 ) d=O(1) d = O ( 1 ) , the power law d − ρ d^{-\rho} d − ρ for 1 ≪ d ≪ t 1\ll d\ll t 1 ≪ d ≪ t , and f ( s ) f(s) f ( s ) for d ∼ t d\sim t d ∼ t (Figure 1 ). Globally the prior depends on t / j t/j t / j , not on t − j t-j t − j : its scale invariance concerns relative position s = j / t s=j/t s = j / t , whereas a relative position bias depends on distance alone. For softmax every entry lies in [ e − 2 B / t , e 2 B / t ] [e^{-2B/t},e^{2B/t}] [ e − 2 B / t , e 2 B / t ] ; the OT operator attains the slower rate t − ( 1 − ρ ) t^{-(1-\rho)} t − ( 1 − ρ ) that Theorem 5 allows: for a fixed window, t 1 − ρ ∑ t − L < j ≤ t P t j → a ∗ 1 − ρ z L − 1 ≈ L 1 − ρ / Γ ( 2 − ρ ) t^{1-\rho}\sum_{t-L<j\le t}P_{tj}\to a^{*\,1-\rho}z_{L-1}\approx L^{1-\rho}/\Gamma(2-\rho) t 1 − ρ ∑ t − L < j ≤ t P t j → a ∗ 1 − ρ z L − 1 ≈ L 1 − ρ /Γ ( 2 − ρ ) (Remark 22), and for a window L = σ t L=\sigma t L = σ t the share tends to ∫ 1 − σ 1 f \int_{1-\sigma}^1 f ∫ 1 − σ 1 f .
Figure 1. The implicit prior with constant scores. Left: the last row of the fixed point at t = 2048 t = 2048 t = 2048 (markers, every 100th key) against the limit shape f ( s ) f(s) f ( s ) of Theorem 7 (lines). Right: the same row near the diagonal for ρ = 0.5 \rho= 0.5 ρ = 0.5 , multiplied by Γ ( 1 − ρ ) d ρ \Gamma(1-\rho)d^\rho Γ ( 1 − ρ ) d ρ so that the power law of Theorem 8(2) is the line 1. The fixed point (circles) follows the discrete profile of Theorem 8(1) at small d d d , the power law for 1 ≪ d ≪ t 1 \ll d \ll t 1 ≪ d ≪ t , and the limit shape f f f , here ( d / t ) ρ ( log t t − d ) − ρ (d/t)^\rho(\log\frac{t}{t-d})^{-\rho} ( d / t ) ρ ( log t − d t ) − ρ , as d d d approaches t t t .
Finite iterations and content
Implementations use finitely many iterations and scores that depend on content. The following results recover the same limit shape for finite iterations with constant scores and for the fixed point with i.i.d. bounded scores, respectively.
Theorem 9 (Limit shape after finitely many iterations). With constant scores and any fixed k ≥ 2 k\ge2 k ≥ 2 , the k k k -th iterate (5) satisfies t P t , ⌊ s t ⌋ ( k ) → f ( s ) tP^{(k)}_{t,\lfloor st\rfloor}\to f(s) t P t , ⌊ s t ⌋ ( k ) → f ( s ) uniformly on [ δ , 1 − δ ] [\delta,1-\delta] [ δ , 1 − δ ] .
Further iterations change only a constant, which the row normalization removes, so the prior is set by ρ \rho ρ , not by the number of iterations. Convergence in t t t is slow when k k k is small and ρ \rho ρ large: with two iterations at t = 4096 t=4096 t = 4096 the amplitude is 13% too large for ρ = 0.75 \rho=0.75 ρ = 0.75 (Appendix § 13 .§ 3 ). Lemma 2 gives convergence in k k k at fixed length, without a rate uniform in length.
Proposition 10 (Factorization of the fixed point under i.i.d. content). Let S t j S_{tj} S t j be i.i.d. with ∣ S / ε ∣ ≤ B |S/\varepsilon|\le B ∣ S / ε ∣ ≤ B and κ = E K \kappa=\mathbb{E}K κ = E K . Then, almost surely, λ t → a ∗ / κ \lambda_t\to a^*/\kappa λ t → a ∗ / κ and, for every δ ∈ ( 0 , 1 2 ) \delta\in(0,\frac{1}{2}) δ ∈ ( 0 , 2 1 ) ,
sup s ∈ [ δ , 1 − δ ] ∣ t P t , ⌊ s t ⌋ − K t , ⌊ s t ⌋ κ f ( s ) ∣ → 0. \sup_{s\in[\delta,1-\delta]}\left|tP_{t,\lfloor st\rfloor}-\frac{K_{t,\lfloor st\rfloor}}{\kappa}f(s)\right|\to0. s ∈ [ δ , 1 − δ ] sup t P t , ⌊ s t ⌋ − κ K t , ⌊ s t ⌋ f ( s ) → 0.
Under these assumptions, the fixed point factors asymptotically into the prior f f f and softmax-like content weights K / κ K/\kappa K / κ . The column mass averages content over many rows (numerically within 2%, Appendix § 13 .§ 2 ).
A potential view of positional biases
The OT correction − γ log M t j -\gamma\log M_{tj} − γ log M t j induces a positional prior that dilutes under bounded scores (§ 3 ). Avoiding dilution requires a positional term that decreases without bound in the distance. We now classify explicit positional schemes by whether they keep a bounded far mass, writing each as a potential on the logits:
log P t j = ⟨ R ( t ) q t , R ( j ) k j ⟩ + b t j − lse t , \log P_{tj} = \langle R(t)q_t, R(j)k_j\rangle+ b_{tj} - \operatorname{lse}_t, log P t j = ⟨ R ( t ) q t , R ( j ) k j ⟩ + b t j − lse t ,
with a multiplicative group action R R R (RoPE [45 ] , GRAPE-M [56 ] ), an additive or path potential b b b (ALiBi [36 ] , KERPLE [4 ] , GRAPE-A/AP, FoX [20 ] , CABLE, and the OT correction − γ log M -\gamma\log M − γ log M ), and the row’s log-normalizer lse t \operatorname{lse}_t lse t . A bias is relative if b t j = b ( t − j ) b_{tj} = b(t-j) b t j = b ( t − j ) for all j ≤ t j \le t j ≤ t . Proofs are in Appendix § 12 . Removing terms that depend only on the row simplifies several schemes:
Proposition 11. Adding r t r_t r t to row t t t of the logits, for any r t r_t r t that may depend on row t t t ’s content, leaves both softmax and the fixed point (FP) unchanged.
Consequently, a path potential whose increments do not depend on the endpoint, b t j = ∑ ℓ = j + 1 t ψ ( ℓ ) = c t − c j b_{tj} = \sum_{\ell=j+1}^{t}\psi(\ell) = c_t-c_j b t j = ∑ ℓ = j + 1 t ψ ( ℓ ) = c t − c j , is the column potential − c j -c_j − c j ; ALiBi and the Forgetting Transformer are of this kind (for ALiBi see also Litman and Guo [22, Prop. G.6]). CABLE [50 ] , b t j = g t ( S t − S j ) b_{tj} = g_t(S_t-S_j) b t j = g t ( S t − S j ) with a content clock S S S , reduces to the rank-one interaction − g t S j -g_tS_j − g t S j .
Kernels of finite-dimensional representations
Let position enter through a representation π ( d ) = A d \pi(d) = A^d π ( d ) = A d on a space of dimension m m m : the bias of query t t t on key j j j is b t j = b ( t − j ) b_{tj} = b(t-j) b t j = b ( t − j ) with the kernel b ( d ) = u ⊤ A d w b(d) = u^\top A^d w b ( d ) = u ⊤ A d w , where the vectors u , w ∈ R m u,w \in\mathbb{R}^m u , w ∈ R m are set by the encoding’s parameters and, for a multiplicative encoding, by the content. The results below hold for every u u u and w w w . This covers additive encodings built from group actions and, for orthogonal R R R , the dot-product score ⟨ R ( t ) q , R ( j ) k ⟩ = q ⊤ R ( j − t ) k \langle R(t)q,R(j)k\rangle= q^\top R(j-t)k ⟨ R ( t ) q , R ( j ) k ⟩ = q ⊤ R ( j − t ) k at fixed q , k q,k q , k .
Proposition 12. (i) For d ≥ m d \ge m d ≥ m , b ( d ) = ∑ k p k ( d ) μ k d b(d) = \sum_k p_k(d)\mu_k^d b ( d ) = ∑ k p k ( d ) μ k d is an exponential polynomial, with the nonzero eigenvalues μ k \mu_k μ k of A A A and polynomials p k p_k p k . (ii) No real b b b of this form satisfies b ( d ) / log d → − c b(d)/\log d \to-c b ( d ) / log d → − c with c ≠ 0 c \ne0 c = 0 . (iii) If the scores are bounded by B B B , softmax satisfies P t j ≤ e 2 B / t P_{tj} \le e^{2B}/t P t j ≤ e 2 B / t ; with an orthogonal multiplicative encoding and bounded inputs, attention therefore dilutes.
Part (ii) rules out logarithmic kernels for every finite-dimensional construction; part (iii) says that rotary-type encodings cannot avoid dilution on their own.
Which encodings keep a bounded far mass
We say that attention keeps a bounded far mass if, for some window L L L , the mass beyond distance L L L stays below a constant smaller than one for every t t t . This excludes dilution, where the mass beyond every fixed window tends to one. For a relative bias with bounded content, keeping a bounded far mass is the same as having summable weights ∑ d e b ( d ) < ∞ \sum_d e^{b(d)} < \infty ∑ d e b ( d ) < ∞ : the window’s share is ∑ d < L e b ( d ) \sum_{d<L} e^{b(d)} ∑ d < L e b ( d ) over ∑ d < t e b ( d ) \sum_{d<t} e^{b(d)} ∑ d < t e b ( d ) , up to the factor e ± 2 B e^{\pm2B} e ± 2 B . Biases that depend on content have no single sequence of weights, so for them, and in § 5 , we use far mass. A linear lower bound on the decay suffices:
Lemma 13. Let log K t j = a t j + b t j \log K_{tj} = a_{tj} + b_{tj} log K t j = a t j + b t j with ∣ a t j ∣ ≤ B \lvert a_{tj}\rvert\le B ∣ a t j ∣ ≤ B , b t t = 0 b_{tt} = 0 b tt = 0 and b t j ≤ − m 0 ( t − j ) b_{tj} \le-m_0(t-j) b t j ≤ − m 0 ( t − j ) , m 0 > 0 m_0 > 0 m 0 > 0 . For every fixed ρ ∈ [ 0 , 1 ) \rho\in[0,1) ρ ∈ [ 0 , 1 ) , the OT fixed point obeys
∑ d > L P t , t − d ≤ e 2 ( 1 − ρ ) B e − ( 1 − ρ ) m 0 ( L + 1 ) 1 − e − ( 1 − ρ ) m 0 \sum_{d>L} P_{t,t-d} \le\frac{e^{2(1-\rho)B}e^{-(1-\rho)m_0(L+1)}}{1-e^{-(1-\rho)m_0}} d > L ∑ P t , t − d ≤ 1 − e − ( 1 − ρ ) m 0 e 2 ( 1 − ρ ) B e − ( 1 − ρ ) m 0 ( L + 1 ) for every t t t ; softmax is the case ρ = 0 \rho= 0 ρ = 0 .
Proposition 14 (Far mass of common encodings). Assume bounded inputs (§ 2 ). For each head:
A L i B i ALiBi A L i B i , F o X FoX F o X , G R A P E GRAPE GR A P E -A A A , G R A P E GRAPE GR A P E -A P AP A P and O T OT O T on A L i B i ALiBi A L i B i (O 2 O2 O 2 ) keep a bounded far mass for all parameter values;
R o P E RoPE R o P E , G R A P E GRAPE GR A P E -M M M and the O T OT O T operator dilute for all parameter values;
a log-distance bias − c log ( 1 + d ) -c\log(1+d) − c log ( 1 + d ) keeps a bounded far mass if c > 1 c > 1 c > 1 and dilutes if c ≤ 1 c \le1 c ≤ 1 , and so does KERPLE’s − p log ( 1 + a d ) -p\log(1+ad) − p log ( 1 + a d ) with a > 0 a > 0 a > 0 and p p p in place of c c c ;
with an exponent c ( x t ) c(x_t) c ( x t ) set by the query’s input, on the distance (P 6 P6 P 6 ) or on a content clock (L C LC L C ), the head keeps a bounded far mass if inf x c ( x ) > 1 \inf_x c(x) > 1 inf x c ( x ) > 1 and dilutes if sup x c ( x ) ≤ 1 \sup_x c(x) \le1 sup x c ( x ) ≤ 1 , over the admissible inputs x x x ;
CABLE keeps a bounded far mass if its clock’s pre-activation is bounded below by a positive constant over the admissible inputs, and dilutes if it is never positive.
In the cases left open by the last two items, the outcome depends on the input sequence. The relative-bias sufficiency criterion is due to Qin et al. [38 ] ; the softmax dilution cases follow from dispersion [51 ] . The bound for O2 holds at the fixed point for each fixed ρ < 1 \rho< 1 ρ < 1 , and is not uniform as ρ → 1 \rho\to1 ρ → 1 .
Power priors near the boundary
Proposition 15 (Window mass of power-law priors). For the prior ( 1 + d ) − c (1+d)^{-c} ( 1 + d ) − c and constant content, the mass within distance L L L of the diagonal at row t t t is ( 1 − c ) S L t − ( 1 − c ) ( 1 + o ( 1 ) ) (1-c)S_Lt^{-(1-c)}(1+o(1)) ( 1 − c ) S L t − ( 1 − c ) ( 1 + o ( 1 )) for c < 1 c<1 c < 1 , S L / log t ( 1 + o ( 1 ) ) S_L/\log t(1+o(1)) S L / log t ( 1 + o ( 1 )) for c = 1 c=1 c = 1 , and tends to S L / ζ ( c ) > 0 S_L/\zeta(c)>0 S L / ζ ( c ) > 0 for c > 1 c>1 c > 1 , where S L = ∑ d < L ( 1 + d ) − c S_L=\sum_{d<L}(1+d)^{-c} S L = ∑ d < L ( 1 + d ) − c . Bounded content changes these quantities by at most a factor e ± 2 B e^{\pm2B} e ± 2 B .
The boundary c = 1 c=1 c = 1 dilutes only logarithmically. For a continuous retention-window formula, see Marín [24 Thm. 11.1] .
Corollary 16 (Log-distance exponents near one at finite length). For c = 1 + δ c=1+\delta c = 1 + δ with δ > 0 \delta>0 δ > 0 and constant content, the mass N t ( L ) N_t(L) N t ( L ) within distance L L L of the diagonal at row t ≥ max ( L , 2 ) t\ge\max(L,2) t ≥ max ( L , 2 ) satisfies
(i) S L 1 + log t ≤ N t ( L ) ≤ 2 S L log ( t + 1 ) if δ log ( t + 1 ) ≤ 1 ; \text{(i)}\quad\frac{S_L}{1+\log t}\le N_t(L)\le\frac{2S_L}{\log(t+1)}\quad\text{if }\delta\log(t+1)\le1; (i) 1 + log t S L ≤ N t ( L ) ≤ log ( t + 1 ) 2 S L if δ log ( t + 1 ) ≤ 1 ; (ii) S L ζ ( c ) ≤ N t ( L ) ≤ S L ζ ( c ) ( 1 − t − δ ) . \text{(ii)}\quad\frac{S_L}{\zeta(c)}\le N_t(L)\le\frac{S_L}{\zeta(c)(1-t^{-\delta})}. (ii) ζ ( c ) S L ≤ N t ( L ) ≤ ζ ( c ) ( 1 − t − δ ) S L . Bounded content changes these bounds by at most a factor e ± 2 B e^{\pm2B} e ± 2 B .
Up to lengths of order e 1 / δ e^{1/\delta} e 1/ δ the prior has the logarithmic window-mass scaling of c = 1 c=1 c = 1 . For c = 1.001 c=1.001 c = 1.001 and L = 512 L=512 L = 512 , even t = 32 L t=32L t = 32 L gives δ log ( t + 1 ) < 0.01 \delta\log(t+1)<0.01 δ log ( t + 1 ) < 0.01 , so this prior stays in the logarithmic regime throughout the shaded range in Figure 2 . It approaches its summable limit only once δ log t ≫ 1 \delta\log t\gg1 δ log t ≫ 1 .
Figure 2. Attention mass beyond a window L L L at row t t t for the prior ( 1 + d ) − c (1+d)^{-c} ( 1 + d ) − c with constant content (Corollary 16), against the context length. The shaded range is the one used in our experiments. The linear bias − m h d -m_hd − m h d (dotted) uses ALiBi’s slopes and keeps a bounded far mass (Lemma 13); its far mass is averaged over eight heads.
Experiments
All models are decoder-only pre-norm Transformers trained from scratch on FineWeb-Edu [32 ] (sample-10BT) with the GPT-2 tokenizer and evaluated on a held-out shard. Extrapolation is measured by the validation loss (nats per token) beyond the training length L L L ; L e x t L_{\mathrm{ext}} L ext is its mean at 2 L 2L 2 L and 4 L 4L 4 L . The far mass is the attention on keys more than L L L back, averaged over the queries in the second half of two validation sequences and over layers and heads. Four experiments were preregistered, with decision rules fixed and unit-tested before any run, and all reported runs come from committed code; analyses outside the preregistered rules are called exploratory where they appear. Configurations, the rules and their outcomes (Table 7 ), supplementary results, and the public code version are in Appendix § 14 . We first examine the source of the OT operator’s extrapolation gain (§ 5.1 ), then compare far mass and long-context loss across positional schemes and training lengths (§ 5.2 ), and finally change the tail of the bias, at test time and during training, to test its effect on loss (§ 5.3 ).
Table 7. Preregistered tests and their outcomes. Loss thresholds apply to mean paired gains; “every seed” and “every checkpoint” require consistent signs. Far-mass thresholds apply to seed means; all thresholds were fixed before the runs.
The positional effect of causal OT
We compare the prefix-consistent operator with softmax at 99.2M non-embedding parameters, RoPE, L = 1024 L = 1024 L = 1024 and 2B tokens, three seeds per arm: softmax, log-n n n softmax [5 , 28 ] , and the operator with ρ ∈ { 0.25 , 0.5 } \rho\in\{0.25, 0.5\} ρ ∈ { 0.25 , 0.5 } , run for a fixed number of iterations (5) whose residual is checked after training (Appendix § 14 .§ 1 ).
At 2 L 2L 2 L , the loss with ρ = 0.5 \rho= 0.5 ρ = 0.5 is lower than with softmax by 0.455 and with log-n n n softmax by 0.303, on every seed (Table 1 ).
Table 1. OT attention at 100M: validation loss in nats per token (mean ± sd over three seeds) at the training length (1024) and at twice the training length. The last row is an exploratory follow-up with the same configuration.
Exploratory analyses support a positional explanation of this gain. In separate 25M screening models with ρ = 0.5 \rho= 0.5 ρ = 0.5 , the correction B t j = − γ log M t j B_{tj} = -\gamma\log M_{tj} B t j = − γ log M t j averaged over all query–key pairs at the same distance d = t − j d = t - j d = t − j decays like − c log ( 1 + d ) -c \log(1 + d) − c log ( 1 + d ) with c ≈ 0.41 c \approx0.41 c ≈ 0.41 (R 2 ≈ 0.93 R^2 \approx0.93 R 2 ≈ 0.93 , against at most 0.75 for a linear fit), so it multiplies the attention weights by about ( 1 + d ) − c (1+d)^{-c} ( 1 + d ) − c ; with constant scores Theorem 8 gives c = ρ c = \rho c = ρ . An explicit learnable log-distance bias with softmax beats ρ = 0.5 \rho= 0.5 ρ = 0.5 at both lengths on every seed, at 40% of the cost (Table 1 , last row). In a separate exploratory evaluation at 2 L 2L 2 L , applying YaRN-t [33 ] to both softmax and OT (ρ = 0.5 \rho= 0.5 ρ = 0.5 ) shrinks their loss gap from 0.457 to 0.011 nats per token (Appendix § 14 .§ 3 ). The distance and content effects of the trained OT correction remain entangled in these comparisons (Appendix § 14 .§ 3 ).
Far mass and long-context loss across encodings and training lengths
The preregistered screening trains models with 25M non-embedding parameters, L = 512 L = 512 L = 512 and 0.5B tokens, two seeds per arm, with fifteen positional schemes (Table 6 ): RoPE alone (B0), additive distance biases with linear and logarithmic kernels and learned or input-gated exponents, a log bias on a content clock, three GRAPE encodings [56 ] , FoX [20 ] , CABLE [50 ] , and the OT operator on RoPE (O1) and on ALiBi (O2). Every scheme with a distance or path bias reaches
Table 6: Positional schemes, with d = t − j d = t - j d = t − j . “Bounded far mass” is the guarantee of Proposition 14 under bounded inputs, where the conditional cases are stated in full. c h ( x t ) c_h(x_t) c h ( x t ) is the positive exponent predicted from the layer input x t x_t x t at query position t t t . S t S_t S t accumulates learned tokenwise clock increments, and g t g_t g t is CABLE’s positive query-dependent weight (head indices suppressed). As in their papers, GRAPE-A, GRAPE-AP, FoX and CABLE are used without RoPE; so is P5. Every other arm with a bias adds it to RoPE.
Table 6.
L e x t ∈ [ 3.400 , 3.498 ] L_{\mathrm{ext}} \in[3.400, 3.498] L ext ∈ [ 3.400 , 3.498 ] , against 3.865 for RoPE alone and 3.573 for OT on RoPE. Contrary to our preregistered expectation, power-law biases do not extrapolate best: the linear family (CABLE, ALiBi, GRAPE-A, FoX) is at least as good. Comparing P1 (RoPE + log bias) with P5 (pure log bias without RoPE) shows that unscaled RoPE does not obstruct extrapolation when combined with a summable bias (L e x t = 3.432 L_{\mathrm{ext}} = 3.432 L ext = 3.432 vs 3.498; Table 9 ), while test-time windowing removes RoPE’s failure mode on B0 without retraining (§ 5.3 ).
Table 9: Screening at 25 M 25\mathrm{M} 25 M , L = 512 L = 512 L = 512 , means over two seeds, grouped by the cases of Proposition 14. Loss in nats per token over 2 M 2\mathrm{M} 2 M predictions; far mass from the probe of § 5 ; last column, the share of learned exponents above one, over heads, or heads × \times × queries for P6 and LC.
Table 9.
In an exploratory analysis of the thirty checkpoints, far mass and long-context loss vary together, with methods grouped as Proposition 14 predicts (Figure 3 ). The schemes that dilute for all parameters gain far mass with length, up to 0.63–0.90 at 16L L L , and their loss rises: the dilution of Theorem 5 is visible already at these lengths, although its bound is not. Those with a bounded far mass for all parameters stay at 0.01–0.02 and their loss keeps falling. Schemes whose far mass depends on learned parameters lie in between: CABLE learns an increasing content clock and keeps its far mass at 0.05, and the log-bias schemes follow their learned exponents, most of which stay below one (Table 9 ). The same grouping holds at 100M (Appendix § 14 .§ 3 ).
Figure 3. Exploratory: far mass (top) and validation loss (bottom) against the evaluation length at 25M, means over two seeds, one column per case of Proposition 14. Colours and marker shapes identify methods within each column. Each row shares its vertical axis. The inset magnifies far mass at 4×–16× in the bounded case. See Table 9 for individual values.
Across encodings trained at L = 512 L = 512 L = 512 , higher far mass is associated with higher long-context loss. At 100M, CABLE, the best screened scheme, also improved on RoPE with evaluation-time YaRN scaling (B0 + YaRN-t), but fell short of the original preregistered threshold. This threshold reflected unscaled RoPE’s seed variability, which greatly exceeded that of the paired loss differences. We therefore preregistered focused retests with new training seeds and a threshold based on paired differences, extending the comparison to longer training contexts (Appendix § 14 .§ 3 ). CABLE (using the learning rate selected in confirmation, 7.5 × 10 − 4 7.5 \times10^{-4} 7.5 × 1 0 − 4 ) achieves lower L e x t L_{\mathrm{ext}} L ext on every seed at all three training lengths, meeting the new criterion (Table 2 ). Part of this gap is already present at the training length. Measured from each arm’s own loss at L L L , the net gap beyond L L L remains positive and strictly above 0.01 on every single seed (0.028–0.041; Table 2 ), confirming that extrapolation gains do not merely reflect baseline modeling improvements. This net gap narrows with longer training contexts, alongside changes in model quality and effective context.
Table 2. Retest at 100M on new seeds: B0 + YaRN-t minus CABLE in L e x t L_{\mathrm{ext}} L ext (range over seeds), B0 minus CABLE at the training length (1×), and their difference, the gap beyond L L L measured from each arm’s own loss at L L L . Absolute losses are in Table 11 .
Interventions on the tail, at test time and during training
The summability criterion behind Proposition 14 motivates interventions on the bias tail. It concerns attention dilution under bounded content scores; it does not guarantee lower loss. We test whether removing tail decay raises long-context loss and imposing summable decay lowers it. On trained checkpoints at 25M and 100M, we change the total additive bias only at distances d > L d > L d > L , preserving the bias within the training length; measured 1× losses agree within 10 − 4 10^{-4} 1 0 − 4 . Cap replaces b ( t , j ) b(t,j) b ( t , j ) by b ( t , t − L ) b(t,t-L) b ( t , t − L ) , removing tail decay; repair continues it as b ( t , t − L ) − 1.5 [ log ( 1 + d ) − log ( 1 + L ) ] b(t,t-L)-1.5[\log(1+d)-\log(1+L)] b ( t , t − L ) − 1.5 [ log ( 1 + d ) − log ( 1 + L )] , a summable power-law tail; window subtracts m ( d − L ) m(d-L) m ( d − L ) from RoPE’s zero bias, with m m m the geometric mean of the ALiBi slopes. Caps are applied to the schemes with a bounded far mass, repairs to log-bias schemes and windows to RoPE alone. During training, we constrain the exponents of the learnable log bias (P1) to c > 1 c > 1 c > 1 , by the reparametrization c = 1 + softplus ( θ ) c = 1 + \operatorname{softplus}(\theta) c = 1 + softplus ( θ ) , and then to c ≥ 1 + δ 0 c \ge1 + \delta_0 c ≥ 1 + δ 0 with a margin δ 0 \delta_0 δ 0 chosen in advance from the far mass of the prior over the lengths in use (Appendix § 14 .§ 3 ).
The loss at the longest length moves in the preregistered direction on all 30 checkpoints, by +0.039 on average for caps, −0.200 for repairs and −2.25 for windows, and the far mass moves with it (Figure 4 , Table 12 ). The constraint c > 1 c > 1 c > 1 lowers the 32L L L loss by 0.575 relative to c < 1 c < 1 c < 1 on every seed, but the far mass still grows by 0.044 from 4L L L to 16L L L , above the preregistered tolerance 0.02, because many heads settle just above one, where by Corollary 16(i) they dilute like c = 1 c = 1 c = 1 . With δ 0 = 0.5 \delta_0 = 0.5 δ 0 = 0.5 the far mass grows by 0.004 and the 32L L L loss is 0.042 below that of δ 0 = 0 \delta_0 = 0 δ 0 = 0 on every seed, at a 1× loss 0.005 higher (Table 3 ); the growth falls with the margin on every seed, consistent with the prior-based prediction.
Figure 4. Test-time interventions beyond the training length: loss change at the longest length (16× at 25M, 8× at 100M) for each of the 30 checkpoints. Circles and squares mark 25M and 100M checkpoints, respectively. Dark bars show group means, and the panels have separate linear axes. See Table 12 for values and Figure 5 for loss curves of three checkpoints.
Table 3. Training-time margin at 25M, L = 512 L = 512 L = 512 : validation loss and far-mass growth from 4L L L to 16L L L (preregistered tolerance 0.02), means over three seeds. Far mass and the share of heads at the bound are in Appendix § 14 .§ 3 .
Table 12. Test-time interventions beyond the training length (Figure 4 ). Loss change in nats at 16× (25M) or 8× (100M), mean and range over checkpoints; far mass at the same length before and after. The 1× losses agree within 10 − 4 10^{-4} 1 0 − 4 in every case.
These test-time interventions establish that changing tail decay causally affects loss in the models and lengths tested. They do not establish that summability generally lowers loss, or isolate far mass from other changes, such as attention entropy (§ 7 ); finite evaluations cannot establish asymptotic summability. During training, the preselected margin δ 0 = 0.5 \delta_0 = 0.5 δ 0 = 0.5 controls far-mass growth in the tested setting, but δ 0 = 0.25 \delta_0 = 0.25 δ 0 = 0.25 also meets the tolerance (0.015), so the smallest sufficient margin is undetermined. At least linear decay controls far mass without an exponent margin (Lemma 13); in this experiment ALiBi also has lower 32L L L loss, by 0.030 relative to δ 0 = 0.5 \delta_0 = 0.5 δ 0 = 0.5 .
Related work
Attention as optimal transport. Sinkformers [39 ] and efficient balancing methods [10 , 47 ] study transport-based attention in non-causal models. Doubly stochastic attention can slow rank collapse, although pure self-attention still approaches rank one with depth [8 , 18 ] . Tran et al. [47 ] list the causal column marginal as an open problem. Sparse Sinkhorn attention [46 ] sorts key blocks. Foss [11 ] uses prefix masses and undamped updates P ← rownorm ( P / M ) P \leftarrow\operatorname{rownorm}(P/M) P ← rownorm ( P / M ) ; we analyze damped accumulated scalings (5) . GOAT learns a reference measure [21 , 22 ] ; our positional prior follows from prefix balancing. We use the damping of unbalanced Sinkhorn [6 , 12 , 41 ] . Convergence analyses for that algorithm fix matrix size [35 , 40 ] ; we study length asymptotics.
Positional biases and length extrapolation. Vetcha [52 ] studies score decompositions and convergent normalization. The relative, group-based and content-dependent schemes are described in § 4 . First Passage Attention uses path extrema [23 ] , outside our additive-path reduction. Qin et al. [38 ] prove a summability condition for sliding-window approximation, including KERPLE’s threshold; we classify far mass (Proposition 14). Marín [24, Thm. 11.1] derives a continuous retention-window formula for finite-length power priors. The report fits effective attention exponents in Section 9.1 and tests distance biases in Section 11.4. We bound discrete window mass under bounded content (Corollary 16), constrain explicit exponents and intervene only beyond the training length (§ 5.3 ). Scale-invariant attention designs distance-dependent Gaussian logits [1 ] ; our ratio prior follows from the constant-score OT fixed point (Theorem 7 ).
Dilution and temperature. Prior work uses attention dilution for diffuse linear attention [37 ] and length-induced flattening of softmax [55 ] . Gu [15, Thm. 6.1 proves vanishing mass on a fixed-size relevant set for independent scores from fixed relevant and irrelevant distributions with finite exponential moments. Here dilution means vanishing mass in each fixed-length recent window; uniform decay of individual attention weights implies it. Softmax dispersion is known [49 , 51 ] ; Godavarti [13 ] proves a far-mass lower bound under uniformly bounded logits. Theorem 5 extends this to the implicit prefix-mass correction. Score scaling and sparse normalizers counteract dispersion [5 , 28 , 49 ] ; geometric limits are studied by Mudarisov et al. [27 ] . Rotary selection [42 ] and data-aware rotations [19 ] can improve finite-length performance. Randomized YaRN changes training-time positions [25 ] ; our baseline uses evaluation-time scaling. Sharp attention can still retrieve the wrong position [44 ] ; concentration alone does not ensure retrieval.
Discussion and conclusion
We characterized the positional prior of prefix-consistent causal OT, proving dilution under bounded scores and an exact scale-invariant limit for constant scores. We classified common positional encodings by far mass and gave discrete window-mass bounds near the summability boundary. Language-model experiments connect positional decay to loss extrapolation through tail interventions and trained exponent margins, while exploratory comparisons favor explicit distance biases as an efficient alternative to OT.
Theoretical limitations. The exact prior shape requires constant or i.i.d. bounded scores; multilayer query–key correlations and representation rank collapse in trained models [8 , 18 ] may modify the local shape without altering the global summability bound. The dilution bound can be loose, and we have no convergence rate for the limiting shape or iteration bound uniform in context length. Furthermore, the uniform-target ablation modifies fixed-point dynamics non-linearly; a direct test-time replacement with the empirical distance-averaged profile B ˉ ( t − j ) \bar{B}(t-j) B ˉ ( t − j ) would provide an appealing complementary content-free reference for future work. The theory concerns prefix-consistent causal attention and classifies attention mass; it gives no general loss or retrieval guarantee and does not cover bidirectional or cross-attention.
Experimental limitations. Experiments use one corpus, 25M–100M models and limited lengths; the far-mass and retrieval probes are exploratory, and differences in optimization and model quality may affect the comparisons. The OT comparisons do not establish an independent benefit from column balancing, and bias interventions change far mass together with other attention properties (§ 5 ). The tested margin is sufficient in this setting, but may not be minimal; low far mass and stable loss do not establish effective distant retrieval or copying (Appendix § 14 .§ 3 ).
Declarations
Funding and competing interests. This research was self-funded by the author and received no external funding. The author declares no competing interests.
AI assistance. Anthropic Claude was used to assist with theoretical derivations, code implementation, and experimental analysis. OpenAI Codex assisted proof development, regression tests, literature checks and manuscript revision, including consistency checks against code and experimental records. The author takes responsibility for the content of this work.
Notation
The table lists the symbols used across several sections; the last column gives the first definition. Symbols that appear only within a proof are defined where they are used.
Table 16.
Proofs for Section 3
Notation is as in Appendix § 9 , with Λ 0 = 0 \Lambda_0 = 0 Λ 0 = 0 and M j − 1 , j = 0 M_{j-1,j} = 0 M j − 1 , j = 0 , the empty sum: column j j j receives no mass before row j j j , so the first increment of every column, on the diagonal, starts from zero (C t = 0 C_t = 0 C t = 0 in (6) ). Small positive parameters in the proofs are written ϑ \vartheta ϑ and ν \nu ν .
Structure. The row recursion gives well-posedness and the column-mass sandwich. Bounds on row normalizers give dilution and feed the bootstrap of Lemma 20. This proves Theorem 6 and, after averaging content, Proposition 10. The shape results follow from Theorem 6; finite iterations have a separate proof.
Elementary facts. We use three, labeled by what they concern: harmonic sums, monotone sums, and an integral. All are standard: (H) and (M) are the integral comparisons behind the asymptotics of harmonic numbers [14 §§6.3 and 9.5] , and (I) is Euler’s integral for the Gamma function [31, eq:5.2 .1]. We include one-line proofs.
(H) For integers 1 ≤ m ≤ t 1 \le m \le t 1 ≤ m ≤ t and 1 ≤ a ≤ b 1 \le a \le b 1 ≤ a ≤ b , ∑ i = m + 1 t 1 / i ≤ log ( t / m ) \sum_{i=m+1}^{t} 1/i \le\log(t/m) ∑ i = m + 1 t 1/ i ≤ log ( t / m ) , and ∑ i = a b 1 / i \sum_{i=a}^{b} 1/i ∑ i = a b 1/ i is at least both log ( ( b + 1 ) / a ) \log((b+1)/a) log (( b + 1 ) / a ) and ( b − a + 1 ) / b (b-a+1)/b ( b − a + 1 ) / b . The first two compare 1 / i 1/i 1/ i with ∫ d x / x \int dx/x ∫ d x / x over [ i − 1 , i ] [i-1,i] [ i − 1 , i ] and [ i , i + 1 ] [i,i+1] [ i , i + 1 ] ; the third bounds every term by 1 / b 1/b 1/ b .
(M) Let a < b a<b a < b be integers. If g g g is increasing on [ a , b ] [a,b] [ a , b ] , then ∑ k = a + 1 b g ( k ) ≤ ∫ a b g ≤ ∑ k = a b − 1 g ( k ) \sum_{k=a+1}^{b}g(k) \le\int_a^b g \le\sum_{k=a}^{b-1}g(k) ∑ k = a + 1 b g ( k ) ≤ ∫ a b g ≤ ∑ k = a b − 1 g ( k ) , since g ( k ) ≤ g ≤ g ( k + 1 ) g(k) \le g \le g(k+1) g ( k ) ≤ g ≤ g ( k + 1 ) on [ k , k + 1 ] [k,k+1] [ k , k + 1 ] ; if g g g is decreasing, the inequalities reverse, ∑ k = a + 1 b g ( k ) ≤ ∫ a b g ≤ ∑ k = a b − 1 g ( k ) \sum_{k=a+1}^{b}g(k) \le\int_a^b g \le\sum_{k=a}^{b-1}g(k) ∑ k = a + 1 b g ( k ) ≤ ∫ a b g ≤ ∑ k = a b − 1 g ( k ) , and the left one holds even when g g g has an integrable singularity at a a a . We apply it to the increasing u ↦ ( log ( t / u ) ) − θ u \mapsto(\log(t/u))^{-\theta} u ↦ ( log ( t / u ) ) − θ and u ↦ ( log ( ( t + 1 ) / u ) ) − θ u \mapsto(\log((t+1)/u))^{-\theta} u ↦ ( log (( t + 1 ) / u ) ) − θ with θ ∈ [ 0 , 1 ) \theta\in[0,1) θ ∈ [ 0 , 1 ) , and to the decreasing u ↦ u − θ u \mapsto u^{-\theta} u ↦ u − θ .
(I) For θ < 1 \theta<1 θ < 1 , ∫ 0 1 ( log 1 / s ) − θ d s = Γ ( 1 − θ ) \int_0^1(\log1/s)^{-\theta}\,ds=\Gamma(1-\theta) ∫ 0 1 ( log 1/ s ) − θ d s = Γ ( 1 − θ ) : substitute s = e − u s=e^{-u} s = e − u in Γ ( z ) = ∫ 0 ∞ u z − 1 e − u d u \Gamma(z)=\int_0^\infty u^{z-1}e^{-u}\,du Γ ( z ) = ∫ 0 ∞ u z − 1 e − u d u with z = 1 − θ z=1-\theta z = 1 − θ .
Well-posedness and the sandwich
Lemma 2. For any K > 0 K>0 K > 0 , (FP) has a unique solution, obtained row by row from (6) . Each x j x_j x j is increasing in λ t \lambda_t λ t and decreasing in C j C_j C j , and x j 1 + γ ≤ λ t K t j x_j^{1+\gamma}\le\lambda_tK_{tj} x j 1 + γ ≤ λ t K t j , i.e. P t j 1 + γ ≤ λ t K t j P_{tj}^{1+\gamma}\le\lambda_tK_{tj} P t j 1 + γ ≤ λ t K t j , with equality on the diagonal. At every fixed finite length, iteration (5) converges to this solution.
Proof. Row t t t of (FP) is (6) , which involves only rows 1 , … , t − 1 1,\ldots,t-1 1 , … , t − 1 through C C C . For fixed C ≥ 0 C\ge0 C ≥ 0 , ϕ C ( x ) = x ( C + x ) γ \phi_C(x)=x(C+x)^\gamma ϕ C ( x ) = x ( C + x ) γ is continuous and strictly increasing from 0 0 0 to ∞ \infty ∞ on ( 0 , ∞ ) (0,\infty) ( 0 , ∞ ) , so x j ( λ ) = ϕ C j − 1 ( λ K t j ) x_j(\lambda)=\phi_{C_j}^{-1}(\lambda K_{tj}) x j ( λ ) = ϕ C j − 1 ( λ K t j ) is well defined, continuous, strictly increasing in λ \lambda λ , with limits 0 0 0 and ∞ \infty ∞ . Hence ∑ j x j ( λ ) \sum_jx_j(\lambda) ∑ j x j ( λ ) takes the value 1 1 1 at exactly one λ t \lambda_t λ t . Induction on t t t gives existence and uniqueness. Since ϕ C \phi_C ϕ C is increasing in C C C , x j x_j x j decreases in C j C_j C j ; since C j ≥ 0 C_j\ge0 C j ≥ 0 , x j 1 + γ ≤ ϕ C j ( x j ) = λ t K t j x_j^{1+\gamma}\le\phi_{C_j}(x_j)=\lambda_tK_{tj} x j 1 + γ ≤ ϕ C j ( x j ) = λ t K t j , with equality when C j = 0 C_j=0 C j = 0 , i.e. on the diagonal.
For convergence, fix row t t t . Let K t = ( K t 1 , … , K t t ) ∈ ( 0 , ∞ ) t K_t=(K_{t1},\ldots,K_{tt})\in(0,\infty)^t K t = ( K t 1 , … , K tt ) ∈ ( 0 , ∞ ) t and v t ( k ) = ( v 1 ( k ) , … , v t ( k ) ) ∈ ( 0 , ∞ ) t v_t^{(k)}=(v_1^{(k)},\ldots,v_t^{(k)})\in(0,\infty)^t v t ( k ) = ( v 1 ( k ) , … , v t ( k ) ) ∈ ( 0 , ∞ ) t be the kernel and scaling vectors on its visible keys, and put z ( k ) = log v t ( k ) ∈ R t z^{(k)}=\log v_t^{(k)}\in\mathbb{R}^t z ( k ) = log v t ( k ) ∈ R t . For z ∈ R t z\in\mathbb{R}^t z ∈ R t and a fixed prefix-mass vector C = ( C 1 , … , C t ) ≥ 0 C=(C_1,\ldots,C_t)\ge0 C = ( C 1 , … , C t ) ≥ 0 , define p ( z ) = softmax ( log K t + z ) p(z)=\operatorname{softmax}(\log K_t+z) p ( z ) = softmax ( log K t + z ) and F C ( z ) = ρ [ z − log ( C + p ( z ) ) ] F_C(z)=\rho[z-\log(C+p(z))] F C ( z ) = ρ [ z − log ( C + p ( z ))] , both in R t \mathbb{R}^t R t , with logarithms taken entrywise. Thus p j ( z ( k ) ) = P t j ( k ) p_j(z^{(k)})=P_{tj}^{(k)} p j ( z ( k ) ) = P t j ( k ) and z ( k + 1 ) = F C ( k ) ( z ( k ) ) z^{(k+1)}=F_{C^{(k)}}(z^{(k)}) z ( k + 1 ) = F C ( k ) ( z ( k ) ) , where C j ( k ) = M t − 1 , j ( k ) ( C t ( k ) = 0 ) C_j^{(k)}=M_{t-1,j}^{(k)}(C_t^{(k)}=0) C j ( k ) = M t − 1 , j ( k ) ( C t ( k ) = 0 ) . With α j = p j ( z ) / ( C j + p j ( z ) ) ∈ ( 0 , 1 ] \alpha_j=p_j(z)/(C_j+p_j(z))\in(0,1] α j = p j ( z ) / ( C j + p j ( z )) ∈ ( 0 , 1 ] , for 1 ≤ j , ℓ ≤ t 1\le j,\ell\le t 1 ≤ j , ℓ ≤ t ,
∂ ( F C ( z ) ) j ∂ z ℓ = ρ [ ( 1 − α j ) 1 j = ℓ + α j p ℓ ( z ) ] . \frac{\partial(F_C(z))_j}{\partial z_\ell}=\rho\left[(1-\alpha_j)1_{j=\ell}+\alpha_jp_\ell(z)\right]. ∂ z ℓ ∂ ( F C ( z ) ) j = ρ [ ( 1 − α j ) 1 j = ℓ + α j p ℓ ( z ) ] .
These derivatives are nonnegative and sum to ρ \rho ρ over ℓ \ell ℓ , so F C F_C F C is a global ρ \rho ρ -contraction in ∥ ⋅ ∥ ∞ \lVert\cdot\rVert_\infty ∥ ⋅ ∥ ∞ . Row 1 has P 11 ( k ) = 1 P_{11}^{(k)}=1 P 11 ( k ) = 1 for all k k k . Inductively, convergence of rows before t t t gives C ( k ) → C ∗ C^{(k)}\to C^* C ( k ) → C ∗ . Let z ∗ z^* z ∗ be the unique fixed point of F C ∗ F_{C^*} F C ∗ . Then
∥ z ( k + 1 ) − z ∗ ∥ ∞ ≤ ρ ∥ z ( k ) − z ∗ ∥ ∞ + η k , η k = ∥ F C ( k ) ( z ∗ ) − F C ∗ ( z ∗ ) ∥ ∞ → 0. \lVert z^{(k+1)}-z^*\rVert_\infty\le\rho\lVert z^{(k)}-z^*\rVert_\infty+\eta_k,\qquad\eta_k=\lVert F_{C^{(k)}}(z^*)-F_{C^*}(z^*)\rVert_\infty\to0. ∥ z ( k + 1 ) − z ∗ ∥ ∞ ≤ ρ ∥ z ( k ) − z ∗ ∥ ∞ + η k , η k = ∥ F C ( k ) ( z ∗ ) − F C ∗ ( z ∗ ) ∥ ∞ → 0.
For ρ < 1 \rho<1 ρ < 1 this implies z ( k ) → z ∗ z^{(k)}\to z^* z ( k ) → z ∗ : iterate the inequality and split its geometrically weighted error sum at any fixed index. Induction completes the proof; the limit satisfies (FP). No rate uniform in t t t is asserted.
□
Lemma 3. For j ≤ t j\le t j ≤ t ,
∑ i = j t λ i K i j ≤ M t j 1 + γ ≤ ( 1 + γ ) ∑ i = j t λ i K i j . \sum_{i=j}^{t}\lambda_iK_{ij}\le M_{tj}^{1+\gamma}\le(1+\gamma)\sum_{i=j}^{t}\lambda_iK_{ij}. i = j ∑ t λ i K ij ≤ M t j 1 + γ ≤ ( 1 + γ ) i = j ∑ t λ i K ij .
Proof. Fix column j j j . Row i ≥ j i \ge j i ≥ j adds x = P i j x = P_{ij} x = P ij to C = M i − 1 , j C = M_{i-1,j} C = M i − 1 , j , with x ( C + x ) γ = λ i K i j x(C+x)^\gamma= \lambda_i K_{ij} x ( C + x ) γ = λ i K ij . Then
( C + x ) 1 + γ − C 1 + γ = ( 1 + γ ) ∫ C C + x u γ d u ∈ [ ( 1 + γ ) x C γ , ( 1 + γ ) x ( C + x ) γ ] . (7) (C+x)^{1+\gamma}-C^{1+\gamma}=(1+\gamma)\int_C^{C+x}u^\gamma\,\mathrm{d}u\in\left[(1+\gamma)xC^\gamma,(1+\gamma)x(C+x)^\gamma\right]. \tag*{(7)} ( C + x ) 1 + γ − C 1 + γ = ( 1 + γ ) ∫ C C + x u γ d u ∈ [ ( 1 + γ ) x C γ , ( 1 + γ ) x ( C + x ) γ ] . (7)
and the right end equals ( 1 + γ ) λ i K i j (1+\gamma)\lambda_iK_{ij} ( 1 + γ ) λ i K ij . Summing over i = j , … , t i=j,\ldots,t i = j , … , t gives the upper bound. For the lower bound, column mass never decreases, so P i j = λ i K i j M i j − γ ≥ λ i K i j M t j − γ P_{ij}=\lambda_iK_{ij}M_{ij}^{-\gamma}\ge\lambda_iK_{ij}M_{tj}^{-\gamma} P ij = λ i K ij M ij − γ ≥ λ i K ij M t j − γ for i ≤ t i\le t i ≤ t ; summing, M t j ≥ M t j − γ ∑ i = j t λ i K i j M_{tj}\ge M_{tj}^{-\gamma}\sum_{i=j}^t\lambda_iK_{ij} M t j ≥ M t j − γ ∑ i = j t λ i K ij .
The left end of (7) gives a second lower bound, used in Lemma 18, which is nearly tight where the increments are small against the accumulated mass. Since M j − 1 , j = 0 M_{j-1,j}=0 M j − 1 , j = 0 , the column mass telescopes over the rows that see it,
M t j 1 + γ = ∑ i = j t ( M i j 1 + γ − M i − 1 , j 1 + γ ) . M_{tj}^{1+\gamma}=\sum_{i=j}^t\left(M_{ij}^{1+\gamma}-M_{i-1,j}^{1+\gamma}\right). M t j 1 + γ = i = j ∑ t ( M ij 1 + γ − M i − 1 , j 1 + γ ) .
and the term of row i i i is the increment (7) with C = M i − 1 , j C=M_{i-1,j} C = M i − 1 , j and x = P i j x=P_{ij} x = P ij . On the diagonal C = 0 C=0 C = 0 , and the term is P j j 1 + γ = λ j K j j P_{jj}^{1+\gamma}=\lambda_jK_{jj} P j j 1 + γ = λ j K j j by Lemma 2 . For i > j i>j i > j , write the increment ratio r i = P i j / M i j ∈ ( 0 , 1 ] r_i=P_{ij}/M_{ij}\in(0,1] r i = P ij / M ij ∈ ( 0 , 1 ] , so that C = M i j − P i j = ( 1 − r i ) M i j C=M_{ij}-P_{ij}=(1-r_i)M_{ij} C = M ij − P ij = ( 1 − r i ) M ij ; the left end of (7) and P i j M i j γ = λ i K i j P_{ij}M_{ij}^{\gamma}=\lambda_iK_{ij} P ij M ij γ = λ i K ij from (FP) give
M i j 1 + γ − M i − 1 , j 1 + γ ≥ ( 1 + γ ) P i j ( ( 1 − r i ) M i j ) γ = ( 1 + γ ) ( 1 − r i ) γ λ i K i j . M_{ij}^{1+\gamma}-M_{i-1,j}^{1+\gamma}\ge(1+\gamma)P_{ij}\left((1-r_i)M_{ij}\right)^\gamma=(1+\gamma)(1-r_i)^\gamma\lambda_iK_{ij}. M ij 1 + γ − M i − 1 , j 1 + γ ≥ ( 1 + γ ) P ij ( ( 1 − r i ) M ij ) γ = ( 1 + γ ) ( 1 − r i ) γ λ i K ij .
Summing,
M t j 1 + γ ≥ λ j K j j + ( 1 + γ ) ∑ i = j + 1 t λ i K i j ( 1 − r i ) γ . (8) M_{tj}^{1+\gamma}\ge\lambda_jK_{jj}+(1+\gamma)\sum_{i=j+1}^t\lambda_iK_{ij}(1-r_i)^\gamma. \tag*{(8)} M t j 1 + γ ≥ λ j K j j + ( 1 + γ ) i = j + 1 ∑ t λ i K ij ( 1 − r i ) γ . (8)
Each term differs from the upper bound of Lemma 3 only by the factor ( 1 − r i ) γ (1-r_i)^\gamma ( 1 − r i ) γ , which tends to one as r i → 0 r_i\to0 r i → 0 ; for r i r_i r i near one, (8) is weaker than the lower bound of Lemma 3 .
Bounded scores: dilution, the a priori bound, and the increment ratio
Throughout this subsection the scores are bounded, ∣ S / ε ∣ ≤ B |S/\varepsilon|\le B ∣ S / ε ∣ ≤ B , that is K t j ∈ [ e − B , e B ] K_{tj}\in[e^{-B},e^B] K t j ∈ [ e − B , e B ] for all t , j t,j t , j ; constant scores are the case B = 0 B=0 B = 0 , K ≡ 1 K\equiv1 K ≡ 1 (Proposition 11), and every constant below is then to be read at B = 0 B=0 B = 0 . We first bound the row normalizers from above, which gives dilution, and then from below, together with the ratio of a row’s increment to a column’s mass; the last two results feed the proof of Theorem 6 and of Proposition 10.
Lemma 4. If ∣ S / ε ∣ ≤ B |S/\varepsilon|\le B ∣ S / ε ∣ ≤ B then λ t ≤ e B / t \lambda_t\le e^B/t λ t ≤ e B / t . With constant scores, t λ t ≤ 1 t\lambda_t\le1 t λ t ≤ 1 .
Proof. Rows 1 , … , t 1,\ldots,t 1 , … , t carry total mass t t t on columns 1 , … , t 1,\ldots,t 1 , … , t , so ∑ j ≤ t M t j = t \sum_{j\le t}M_{tj}=t ∑ j ≤ t M t j = t . By (FP) and Jensen’s inequality for the convex map u ↦ u − γ u\mapsto u^{-\gamma} u ↦ u − γ ,
1 = λ t ∑ j ≤ t K t j M t j − γ ≥ λ t e − B ∑ j ≤ t M t j − γ ≥ λ t e − B t ( 1 t ∑ j ≤ t M t j ) − γ = λ t e − B t . 1=\lambda_t\sum_{j\le t}K_{tj}M_{tj}^{-\gamma}\ge\lambda_te^{-B}\sum_{j\le t}M_{tj}^{-\gamma}\ge\lambda_te^{-B}t\left(\frac{1}{t}\sum_{j\le t}M_{tj}\right)^{-\gamma}=\lambda_te^{-B}t. 1 = λ t j ≤ t ∑ K t j M t j − γ ≥ λ t e − B j ≤ t ∑ M t j − γ ≥ λ t e − B t ( t 1 j ≤ t ∑ M t j ) − γ = λ t e − B t .
Theorem 5 (Dilution under bounded scores). If ∣ S / ε ∣ ≤ B |S/\varepsilon|\le B ∣ S / ε ∣ ≤ B , then for all j ≤ t j\le t j ≤ t
P t j ≤ ( e 2 B t ) 1 − ρ , ∑ t − L < j ≤ t P t j ≤ L ( e 2 B t ) 1 − ρ → t → ∞ 0. P_{tj}\le\left(\frac{e^{2B}}{t}\right)^{1-\rho},\qquad\sum_{t-L<j\le t}P_{tj}\le L\left(\frac{e^{2B}}{t}\right)^{1-\rho}\xrightarrow[t\to\infty]{}0. P t j ≤ ( t e 2 B ) 1 − ρ , t − L < j ≤ t ∑ P t j ≤ L ( t e 2 B ) 1 − ρ t → ∞ 0.
Proof. By Lemmas 2 and 4 , P t j 1 + γ ≤ λ t K t j ≤ e B ⋅ e B / t P_{tj}^{1+\gamma}\le\lambda_tK_{tj}\le e^B\cdot e^B/t P t j 1 + γ ≤ λ t K t j ≤ e B ⋅ e B / t ; take the power 1 / ( 1 + γ ) = 1 − ρ 1/(1+\gamma)=1-\rho 1/ ( 1 + γ ) = 1 − ρ . A window of length L L L has at most L L L entries.
The column sum and the normalization. Write
W t j = ∑ i = j t λ i K i j , so that W t j ≤ M t j 1 + γ ≤ ( 1 + γ ) W t j . W_{tj}=\sum_{i=j}^{t}\lambda_iK_{ij},\qquad\text{so that}\qquad W_{tj}\leq M_{tj}^{1+\gamma}\leq(1+\gamma)W_{tj}. W t j = i = j ∑ t λ i K ij , so that W t j ≤ M t j 1 + γ ≤ ( 1 + γ ) W t j .
by Lemma 3 , and e − B ( Λ t − Λ j − 1 ) < W t j ≤ e B ( Λ t − Λ j − 1 ) e^{-B}(\Lambda_t-\Lambda_{j-1})<W_{tj}\leq e^B(\Lambda_t-\Lambda_{j-1}) e − B ( Λ t − Λ j − 1 ) < W t j ≤ e B ( Λ t − Λ j − 1 ) ; with constant scores W t j = Λ t − Λ j − 1 W_{tj}=\Lambda_t-\Lambda_{j-1} W t j = Λ t − Λ j − 1 . Lemma 3 and − γ / ( 1 + γ ) = − ρ -\gamma/(1+\gamma)=-\rho − γ / ( 1 + γ ) = − ρ turn the row normalization 1 / λ t = ∑ j ≤ t K t j M t j − γ 1/\lambda_t=\sum_{j\leq t}K_{tj}M_{tj}^{-\gamma} 1/ λ t = ∑ j ≤ t K t j M t j − γ into
e − B ∑ j ≤ t ( ( 1 + γ ) W t j ) − ρ ≤ 1 λ t ≤ e B ∑ j ≤ t W t j − ρ . (9) e^{-B}\sum_{j\leq t}\bigl((1+\gamma)W_{tj}\bigr)^{-\rho}\leq\frac{1}{\lambda_t}\leq e^B\sum_{j\leq t}W_{tj}^{-\rho}. \tag*{(9)} e − B j ≤ t ∑ ( ( 1 + γ ) W t j ) − ρ ≤ λ t 1 ≤ e B j ≤ t ∑ W t j − ρ . (9)
The next two lemmas prepare the proofs of Theorem 6 , which explains how they are used, and of Proposition 10: an a priori lower bound on t λ t t\lambda_t t λ t from the right side of (S_B), and a bound on the ratio of a row’s increment to a column’s mass.
Lemma 17. If K t j ∈ [ e − B , e B ] K_{tj}\in[e^{-B},e^B] K t j ∈ [ e − B , e B ] for all t , j t,j t , j , then t λ t ≥ a B t\lambda_t\geq a_B t λ t ≥ a B for all t t t , where a B 1 − ρ = e − ( 1 + ρ ) B / ( 2 Γ ( 1 − ρ ) ) a_B^{1-\rho}=e^{-(1+\rho)B}/(2\Gamma(1-\rho)) a B 1 − ρ = e − ( 1 + ρ ) B / ( 2Γ ( 1 − ρ )) . For constant scores this is t λ t ≥ a 0 t\lambda_t\geq a_0 t λ t ≥ a 0 with a 0 1 − ρ = 1 / ( 2 Γ ( 1 − ρ ) ) a_0^{1-\rho}=1/(2\Gamma(1-\rho)) a 0 1 − ρ = 1/ ( 2Γ ( 1 − ρ )) .
Proof. Induction on t t t . Row 1 has the single entry P 11 = 1 P_{11}=1 P 11 = 1 , so λ 1 = 1 / K 11 ≥ e − B ≥ a B \lambda_1=1/K_{11}\geq e^{-B}\geq a_B λ 1 = 1/ K 11 ≥ e − B ≥ a B , since a B 1 − ρ ≤ e − ( 1 + ρ ) B ≤ e − ( 1 − ρ ) B a_B^{1-\rho}\leq e^{-(1+\rho)B}\leq e^{-(1-\rho)B} a B 1 − ρ ≤ e − ( 1 + ρ ) B ≤ e − ( 1 − ρ ) B . Assume λ i ≥ a B / i \lambda_i\geq a_B/i λ i ≥ a B / i for i < t i<t i < t . For m ≤ t − 2 m\leq t-2 m ≤ t − 2 , (H) gives Λ t − Λ m ≥ a B ∑ i = m + 1 t − 1 1 / i ≥ a B log ( t / ( m + 1 ) ) \Lambda_t-\Lambda_m\geq a_B\sum_{i=m+1}^{t-1}1/i\geq a_B\log(t/(m+1)) Λ t − Λ m ≥ a B ∑ i = m + 1 t − 1 1/ i ≥ a B log ( t / ( m + 1 )) , and Λ t − Λ t − 1 = λ t \Lambda_t-\Lambda_{t-1}=\lambda_t Λ t − Λ t − 1 = λ t . The right side of (S_B) with W t j ≥ e − B ( Λ t − Λ j − 1 ) W_{tj}\geq e^{-B}(\Lambda_t-\Lambda_{j-1}) W t j ≥ e − B ( Λ t − Λ j − 1 ) , then (M) and (I), give
1 λ t ≤ e ( 1 + ρ ) B ( λ t − ρ + a B − ρ ∑ k = 1 t − 1 ( log ( t / k ) ) − ρ ) ≤ e ( 1 + ρ ) B ( λ t − ρ + a B − ρ t Γ ( 1 − ρ ) ) . \frac{1}{\lambda_t}\leq e^{(1+\rho)B}\left(\lambda_t^{-\rho}+a_B^{-\rho}\sum_{k=1}^{t-1}\bigl(\log(t/k)\bigr)^{-\rho}\right)\leq e^{(1+\rho)B}\left(\lambda_t^{-\rho}+a_B^{-\rho}t\Gamma(1-\rho)\right). λ t 1 ≤ e ( 1 + ρ ) B ( λ t − ρ + a B − ρ k = 1 ∑ t − 1 ( log ( t / k ) ) − ρ ) ≤ e ( 1 + ρ ) B ( λ t − ρ + a B − ρ t Γ ( 1 − ρ ) ) .
With y = t λ t y=t\lambda_t y = t λ t this reads 1 ≤ e ( 1 + ρ ) B ( ( y / t ) 1 − ρ + y a B − ρ Γ ( 1 − ρ ) ) 1\leq e^{(1+\rho)B}\bigl((y/t)^{1-\rho}+ya_B^{-\rho}\Gamma(1-\rho)\bigr) 1 ≤ e ( 1 + ρ ) B ( ( y / t ) 1 − ρ + y a B − ρ Γ ( 1 − ρ ) ) . If y < a B y<a_B y < a B , the right side is below e ( 1 + ρ ) B a B 1 − ρ ( 1 + Γ ( 1 − ρ ) ) ≤ 2 e ( 1 + ρ ) B Γ ( 1 − ρ ) a B 1 − ρ = 1 e^{(1+\rho)B}a_B^{1-\rho}(1+\Gamma(1-\rho))\leq2e^{(1+\rho)B}\Gamma(1-\rho)a_B^{1-\rho}=1 e ( 1 + ρ ) B a B 1 − ρ ( 1 + Γ ( 1 − ρ )) ≤ 2 e ( 1 + ρ ) B Γ ( 1 − ρ ) a B 1 − ρ = 1 , because Γ ( 1 − ρ ) ≥ 1 \Gamma(1-\rho)\geq1 Γ ( 1 − ρ ) ≥ 1 ; contradiction. □
Lemma 18. Let K t j ∈ [ e − B , e B ] K_{tj}\in[e^{-B},e^B] K t j ∈ [ e − B , e B ] for all t , j t,j t , j and c B = e 3 B / a B c_B=e^{3B}/a_B c B = e 3 B / a B . For i ≥ j i\geq j i ≥ j ,
r i = P i j M i j ≤ λ i K i j W i j ≤ c B i − j + 1 . r_i=\frac{P_{ij}}{M_{ij}}\leq\frac{\lambda_iK_{ij}}{W_{ij}}\leq\frac{c_B}{i-j+1}. r i = M ij P ij ≤ W ij λ i K ij ≤ i − j + 1 c B .
for constant scores this is r i ≤ λ i / ( Λ i − Λ j − 1 ) ≤ 1 / ( a 0 ( i − j + 1 ) ) r_i\leq\lambda_i/(\Lambda_i-\Lambda_{j-1})\leq1/(a_0(i-j+1)) r i ≤ λ i / ( Λ i − Λ j − 1 ) ≤ 1/ ( a 0 ( i − j + 1 )) . Consequently the relative deficit
η t j = 1 − M t j 1 + γ ( 1 + γ ) W t j ∈ [ 0 , 1 ) \eta_{tj}=1-\frac{M_{tj}^{1+\gamma}}{(1+\gamma)W_{tj}}\in[0,1) η t j = 1 − ( 1 + γ ) W t j M t j 1 + γ ∈ [ 0 , 1 )
is small away from the diagonal. There are constants C 1 , C 2 C_1,C_2 C 1 , C 2 depending only on ρ \rho ρ and B B B such that for all t ≥ 1 t\geq1 t ≥ 1 :
for every ϑ ∈ ( 0 , 1 2 ) \vartheta\in(0,\frac12) ϑ ∈ ( 0 , 2 1 ) , 0 ≤ max ϑ t ≤ j ≤ ( 1 − ϑ ) t η t j ≤ C 1 log ( t + 1 ) ϑ t log 1 1 − ϑ 0\leq\max_{\vartheta t\leq j\leq(1-\vartheta)t}\eta_{tj}\leq\frac{C_1\log(t+1)}{\vartheta t\log\frac{1}{1-\vartheta}} 0 ≤ max ϑt ≤ j ≤ ( 1 − ϑ ) t η t j ≤ ϑt l o g 1 − ϑ 1 C 1 l o g ( t + 1 ) , which tends to 0;
for t / 2 ≤ j ≤ t t/2\leq j\leq t t /2 ≤ j ≤ t and d = t − j d=t-j d = t − j , 0 ≤ η t j ≤ C 2 1 + log ( d + 1 ) d + 1 0\leq\eta_{tj}\leq C_2\frac{1+\log(d+1)}{d+1} 0 ≤ η t j ≤ C 2 d + 1 1 + l o g ( d + 1 ) .
These are upper bounds; only their convergence to zero is used below.
Proof. Ratio. We use only the lower bound of Lemma 3 , M i j 1 + γ ≥ W i j M_{ij}^{1+\gamma} \ge W_{ij} M ij 1 + γ ≥ W ij . Raised to the decreasing power − ρ = − γ / ( 1 + γ ) -\rho=-\gamma/(1+\gamma) − ρ = − γ / ( 1 + γ ) and to the increasing power 1 − ρ = 1 / ( 1 + γ ) 1-\rho=1/(1+\gamma) 1 − ρ = 1/ ( 1 + γ ) , it bounds the numerator and the denominator of r i r_i r i :
P i j = λ i K i j M i j − γ = λ i K i j ( M i j 1 + γ ) − ρ ≤ λ i K i j W i j − ρ , M i j = ( M i j 1 + γ ) 1 − ρ ≥ W i j 1 − ρ . P_{ij}=\lambda_iK_{ij}M_{ij}^{-\gamma}=\lambda_iK_{ij}\left(M_{ij}^{1+\gamma}\right)^{-\rho}\le\lambda_iK_{ij}W_{ij}^{-\rho},\qquad M_{ij}=\left(M_{ij}^{1+\gamma}\right)^{1-\rho}\ge W_{ij}^{1-\rho}. P ij = λ i K ij M ij − γ = λ i K ij ( M ij 1 + γ ) − ρ ≤ λ i K ij W ij − ρ , M ij = ( M ij 1 + γ ) 1 − ρ ≥ W ij 1 − ρ .
dividing gives r i ≤ λ i K i j / W i j r_i\le\lambda_iK_{ij}/W_{ij} r i ≤ λ i K ij / W ij . By Lemma 4 , λ i K i j ≤ e 2 B / i \lambda_iK_{ij}\le e^{2B}/i λ i K ij ≤ e 2 B / i ; by Lemma 17 and (H), W i j ≥ e − B ( Λ i − Λ j − 1 ) ≥ e − B a B ∑ k = j i − 1 1 / k ≥ e − B a B ( i − j + 1 ) / i W_{ij}\ge e^{-B(\Lambda_i-\Lambda_{j-1})}\ge e^{-Ba_B\sum_{k=j}^{i-1}1/k}\ge e^{-Ba_B(i-j+1)/i} W ij ≥ e − B ( Λ i − Λ j − 1 ) ≥ e − B a B ∑ k = j i − 1 1/ k ≥ e − B a B ( i − j + 1 ) / i .
Deficit. η t j ≥ 0 \eta_{tj}\ge0 η t j ≥ 0 by Lemma 3 . For the upper bound, compare (8) with ( 1 + γ ) W t j = ( 1 + γ ) ∑ i = j t λ i K i j (1+\gamma)W_{tj}=(1+\gamma)\sum_{i=j}^t\lambda_iK_{ij} ( 1 + γ ) W t j = ( 1 + γ ) ∑ i = j t λ i K ij and use ( 1 − r ) γ ≥ 1 − max ( 1 , γ ) r (1-r)^\gamma\ge1-\max(1,\gamma)r ( 1 − r ) γ ≥ 1 − max ( 1 , γ ) r on [ 0 , 1 ] [0,1] [ 0 , 1 ] : with c γ = ( 1 + γ ) max ( 1 , γ ) c_\gamma=(1+\gamma)\max(1,\gamma) c γ = ( 1 + γ ) max ( 1 , γ ) , the deficit satisfies
( 1 + γ ) W t j − M t j 1 + γ ≤ γ λ j K j j + c γ ∑ i = j + 1 t λ i K i j r i . (1+\gamma)W_{tj}-M_{tj}^{1+\gamma}\le\gamma\lambda_jK_{jj}+c_\gamma\sum_{i=j+1}^{t}\lambda_iK_{ij}r_i. ( 1 + γ ) W t j − M t j 1 + γ ≤ γ λ j K j j + c γ i = j + 1 ∑ t λ i K ij r i .
It remains to bound this right side, with the ratio bound just proved, and the denominator of η \eta η in each range.
Case (1). For i ≥ j i\ge j i ≥ j , λ i K i j ≤ e 2 B / i ≤ e 2 B / j \lambda_iK_{ij}\le e^{2B}/i\le e^{2B}/j λ i K ij ≤ e 2 B / i ≤ e 2 B / j , which takes out a common factor. With the ratio bound and k = i − j k=i-j k = i − j ,
∑ i = j + 1 t λ i K i j r i ≤ e 2 B c B j ∑ k = 1 t − j 1 k + 1 = e 2 B c B j ∑ q = 2 t − j + 1 1 q ≤ e 2 B c B log ( t + 1 ) j . \sum_{i=j+1}^{t}\lambda_iK_{ij}r_i\le\frac{e^{2B}c_B}{j}\sum_{k=1}^{t-j}\frac{1}{k+1}=\frac{e^{2B}c_B}{j}\sum_{q=2}^{t-j+1}\frac{1}{q}\le\frac{e^{2B}c_B\log(t+1)}{j}. i = j + 1 ∑ t λ i K ij r i ≤ j e 2 B c B k = 1 ∑ t − j k + 1 1 = j e 2 B c B q = 2 ∑ t − j + 1 q 1 ≤ j e 2 B c B log ( t + 1 ) .
extending the sum to q ≤ t + 1 q\le t+1 q ≤ t + 1 and applying the first bound of (H) with m = 1 m=1 m = 1 . Together with γ λ j K j j ≤ γ e 2 B / j \gamma\lambda_jK_{jj}\le\gamma e^{2B}/j γ λ j K j j ≤ γ e 2 B / j , the deficit is at most e 2 B j − 1 ( γ + c γ c B log ( t + 1 ) ) e^{2B}j^{-1}(\gamma+c_\gamma c_B\log(t+1)) e 2 B j − 1 ( γ + c γ c B log ( t + 1 )) for every j j j . For j ≤ ( 1 − ϑ ) t j\le(1-\vartheta)t j ≤ ( 1 − ϑ ) t , Lemma 17 and (H) bound the denominator of η \eta η below by a constant,
( 1 + γ ) W t j ≥ ( 1 + γ ) e − a B B log t + 1 j ≥ ( 1 + γ ) e − a B B log 1 1 − ϑ . (1+\gamma)W_{tj}\ge(1+\gamma)e^{-a_BB\log\frac{t+1}{j}}\ge(1+\gamma)e^{-a_BB\log\frac{1}{1-\vartheta}}. ( 1 + γ ) W t j ≥ ( 1 + γ ) e − a B B l o g j t + 1 ≥ ( 1 + γ ) e − a B B l o g 1 − ϑ 1 .
For j ≥ ϑ t j\ge\vartheta t j ≥ ϑt the deficit is at most e 2 B ( ϑ t ) − 1 ( γ + c γ c B log ( t + 1 ) ) e^{2B}(\vartheta t)^{-1}(\gamma+c_\gamma c_B\log(t+1)) e 2 B ( ϑt ) − 1 ( γ + c γ c B log ( t + 1 )) ; since γ ≤ γ log ( t + 1 ) / log 2 \gamma\le\gamma\log(t+1)/\log2 γ ≤ γ log ( t + 1 ) / log 2 , dividing gives (1) with C 1 = e 3 B ( γ / log 2 + c γ c B ) / ( ( 1 + γ ) a B ) C_1=e^{3B}(\gamma/\log2+c_\gamma c_B)/((1+\gamma)a_B) C 1 = e 3 B ( γ / log 2 + c γ c B ) / (( 1 + γ ) a B ) , which does not depend on ϑ \vartheta ϑ .
Case (2). For j ≥ t / 2 j\ge t/2 j ≥ t /2 , λ i K i j ≤ e 2 B / i ≤ 2 e 2 B / t \lambda_iK_{ij}\le e^{2B}/i\le2e^{2B}/t λ i K ij ≤ e 2 B / i ≤ 2 e 2 B / t , and as in case (1), now with t − j = d t-j=d t − j = d ,
∑ i = j + 1 t λ i K i j r i ≤ 2 e 2 B c B t ∑ k = 1 d 1 k + 1 ≤ 2 e 2 B c B log ( d + 1 ) t , \sum_{i=j+1}^{t}\lambda_iK_{ij}r_i\le\frac{2e^{2B}c_B}{t}\sum_{k=1}^{d}\frac{1}{k+1}\le\frac{2e^{2B}c_B\log(d+1)}{t}, i = j + 1 ∑ t λ i K ij r i ≤ t 2 e 2 B c B k = 1 ∑ d k + 1 1 ≤ t 2 e 2 B c B log ( d + 1 ) ,
so the deficit is at most 2 e 2 B t ( γ + c γ c B log ( d + 1 ) ) \frac{2e^{2B}}{t}(\gamma+c_\gamma c_B\log(d+1)) t 2 e 2 B ( γ + c γ c B log ( d + 1 )) . By (H) the denominator is at least
( 1 + γ ) e − B a B ∑ k = j t 1 k ≥ ( 1 + γ ) e − B a B ( d + 1 ) t . (1+\gamma)e^{-Ba_B}\sum_{k=j}^{t}\frac{1}{k}\ge\frac{(1+\gamma)e^{-Ba_B}(d+1)}{t}. ( 1 + γ ) e − B a B k = j ∑ t k 1 ≥ t ( 1 + γ ) e − B a B ( d + 1 ) .
Dividing gives (2) with C 2 = 2 e 3 B max ( γ , c γ c B ) / ( ( 1 + γ ) a B ) C_2=2e^{3B}\max(\gamma,c_\gamma c_B)/((1+\gamma)a_B) C 2 = 2 e 3 B max ( γ , c γ c B ) / (( 1 + γ ) a B ) . For B = 0 B=0 B = 0 , c 0 = 1 / a 0 c_0=1/a_0 c 0 = 1/ a 0 and these constants reduce to those of the constant-score case. □
Auxiliary estimates: the ends of a row and a bootstrap
Two arguments recur in the proofs of Theorems 6 and 9 and Proposition 10, and we state them once.
The ends of a row. Write ℓ t j = log t + 1 j \ell_{tj}=\log\frac{t+1}{j} ℓ t j = log j t + 1 for 1 ≤ j ≤ t 1\le j\le t 1 ≤ j ≤ t . Each of these proofs bounds a row by the profile ℓ t j ρ \ell_{tj}^{\rho} ℓ t j ρ , and needs that the keys far from the query (j < ϑ t j<\vartheta t j < ϑt ) and near it (j > ( 1 − ϑ ) t j>(1-\vartheta)t j > ( 1 − ϑ ) t ) carry a share that vanishes with ϑ \vartheta ϑ , uniformly in t t t .
Lemma 19. Let v t j ≥ 0 v_{tj}\ge0 v t j ≥ 0 with v t j ≤ C ℓ t j − ρ v_{tj}\le C\ell_{tj}^{-\rho} v t j ≤ C ℓ t j − ρ for all 1 ≤ j ≤ t 1\le j\le t 1 ≤ j ≤ t . Then for ϑ ∈ ( 0 , 1 2 ) \vartheta\in(0,\frac{1}{2}) ϑ ∈ ( 0 , 2 1 ) and t ≥ 1 / ϑ t\ge1/\vartheta t ≥ 1/ ϑ ,
1 t ∑ j < ϑ t v t j ≤ C ϑ ( log 1 ϑ ) − ρ , 1 t ∑ j > ( 1 − ϑ ) t v t j ≤ 2 C ϑ 1 − ρ 1 − ρ . \frac{1}{t}\sum_{j<\vartheta t}v_{tj}\le C\vartheta\left(\log\frac{1}{\vartheta}\right)^{-\rho},\qquad\frac{1}{t}\sum_{j>(1-\vartheta)t}v_{tj}\le\frac{2C\vartheta^{1-\rho}}{1-\rho}. t 1 j < ϑt ∑ v t j ≤ C ϑ ( log ϑ 1 ) − ρ , t 1 j > ( 1 − ϑ ) t ∑ v t j ≤ 1 − ρ 2 C ϑ 1 − ρ . Proof. For j < ϑ t j<\vartheta t j < ϑt , ℓ t j ≥ log 1 ϑ \ell_{tj}\ge\log\frac{1}{\vartheta} ℓ t j ≥ log ϑ 1 , and there are fewer than ϑ t \vartheta t ϑt such j j j . For j > ( 1 − ϑ ) t j>(1-\vartheta)t j > ( 1 − ϑ ) t , log x ≥ 1 − 1 / x \log x\ge1-1/x log x ≥ 1 − 1/ x gives ℓ t j ≥ r / ( t + 1 ) \ell_{tj}\ge r/(t+1) ℓ t j ≥ r / ( t + 1 ) with r = t + 1 − j ≤ ϑ t + 1 ≤ 2 ϑ t r=t+1-j\le\vartheta t+1\le2\vartheta t r = t + 1 − j ≤ ϑt + 1 ≤ 2 ϑt , and (M) for the decreasing u ↦ u − ρ u\mapsto u^{-\rho} u ↦ u − ρ gives
1 t ∑ j > ( 1 − ϑ ) t ℓ t j − ρ ≤ ( t + 1 ) ρ t ∑ r ≤ 2 ϑ t r − ρ ≤ ( 2 t ) ρ t ( 2 ϑ t ) 1 − ρ 1 − ρ = 2 ϑ 1 − ρ 1 − ρ . \frac{1}{t}\sum_{j>(1-\vartheta)t}\ell_{tj}^{-\rho}\le\frac{(t+1)^\rho}{t}\sum_{r\le2\vartheta t}r^{-\rho}\le\frac{(2t)^\rho}{t}\frac{(2\vartheta t)^{1-\rho}}{1-\rho}=\frac{2\vartheta^{1-\rho}}{1-\rho}. t 1 j > ( 1 − ϑ ) t ∑ ℓ t j − ρ ≤ t ( t + 1 ) ρ r ≤ 2 ϑt ∑ r − ρ ≤ t ( 2 t ) ρ 1 − ρ ( 2 ϑt ) 1 − ρ = 1 − ρ 2 ϑ 1 − ρ .
A bootstrap. The proofs of Theorem 6 and Proposition 10 share one argument, which we isolate here as a statement about a positive sequence λ t ′ \lambda'_t λ t ′ : the row normalizers, rescaled by κ = E K \kappa=EK κ = E K in Proposition 10. Write Λ t ′ = ∑ i ≤ t λ i ′ \Lambda'_t=\sum_{i\le t}\lambda'_i Λ t ′ = ∑ i ≤ t λ i ′ , Λ 0 ′ = 0 \Lambda'_0=0 Λ 0 ′ = 0 , D t j = Λ t ′ − Λ j − 1 ′ D_{tj}=\Lambda'_t-\Lambda'_{j-1} D t j = Λ t ′ − Λ j − 1 ′ ,
J t ( ϑ ) = { j : ϑ t ≤ j ≤ ( 1 − ϑ ) t } , χ ( ϑ ) = ϑ 1 − ρ + ϑ ( log 1 ϑ ) − ρ , T ( x ) = x ρ C ρ . J_t(\vartheta)=\{j:\vartheta t\le j\le(1-\vartheta)t\},\qquad\chi(\vartheta)=\vartheta^{1-\rho}+\vartheta\left(\log\frac{1}{\vartheta}\right)^{-\rho},\qquad T(x)=\frac{x^\rho}{C_\rho}. J t ( ϑ ) = { j : ϑt ≤ j ≤ ( 1 − ϑ ) t } , χ ( ϑ ) = ϑ 1 − ρ + ϑ ( log ϑ 1 ) − ρ , T ( x ) = C ρ x ρ .
The row normalization expresses 1 / λ t ′ 1/\lambda'_t 1/ λ t ′ as a sum over the differences D t j D_{tj} D t j , which are built from the earlier normalizers, so an asymptotic bound i λ i ′ ≤ x i\lambda'_i\le x i λ i ′ ≤ x (or ≥ x \ge x ≥ x ) on the earlier rows yields a bound on the current one. The lemma assumes the two inequalities that make this work: in the middle range J t ( ϑ ) J_t(\vartheta) J t ( ϑ ) , a lower and an upper bound on 1 / λ t ′ 1/\lambda'_t 1/ λ t ′ carrying the same factor ( 1 + γ ) − ρ (1+\gamma)^{-\rho} ( 1 + γ ) − ρ , up to errors that vanish with ν \nu ν and ϑ \vartheta ϑ . Both then turn a bound x x x on the earlier rows into the bound T ( x ) T(x) T ( x ) on the current row. Since log T ( x ) = ρ log x − log C ρ \log T(x)=\rho\log x-\log C_\rho log T ( x ) = ρ log x − log C ρ has slope ρ < 1 \rho<1 ρ < 1 , T T T is a contraction in log scale; a ∗ = C ρ − 1 / ( 1 − ρ ) a^*=C_\rho^{-1/(1-\rho)} a ∗ = C ρ − 1/ ( 1 − ρ ) is its unique fixed point on ( 0 , ∞ ) (0,\infty) ( 0 , ∞ ) , and x ≤ T ( x ) x\le T(x) x ≤ T ( x ) if and only if x ≤ a ∗ x\le a^* x ≤ a ∗ . Applied to the limits superior and inferior, this pins both to a ∗ a^* a ∗ .
Lemma 20. Let λ t ′ > 0 \lambda'_t>0 λ t ′ > 0 with 0 < lim inf t λ t ′ ≤ lim sup t λ t ′ < ∞ 0<\liminf t\lambda'_t\le\limsup t\lambda'_t<\infty 0 < lim inf t λ t ′ ≤ lim sup t λ t ′ < ∞ , and suppose there is a constant C C C such that for every ϑ , ν ∈ ( 0 , 1 2 ) \vartheta,\nu\in(0,\frac{1}{2}) ϑ , ν ∈ ( 0 , 2 1 ) , for all large t t t ,
(i) 1 λ t ′ ≥ ∑ j ∈ J t ( ϑ ) ( ( 1 + γ ) ( 1 + ν ) D t j ) − ρ − ν t ; \text{(i)}\qquad\frac{1}{\lambda'_t}\ge\sum_{j\in J_t(\vartheta)}\left((1+\gamma)(1+\nu)D_{tj}\right)^{-\rho}-\nu t; (i) λ t ′ 1 ≥ j ∈ J t ( ϑ ) ∑ ( ( 1 + γ ) ( 1 + ν ) D t j ) − ρ − ν t ; (ii) 1 λ t ′ ≤ ∑ j ∈ J t ( ϑ ) ( ( 1 + γ ) ( 1 − ν ) D t j ) − ρ + t ( ν + C χ ( ϑ ) ) . \text{(ii)}\qquad\frac{1}{\lambda'_t}\le\sum_{j\in J_t(\vartheta)}\left((1+\gamma)(1-\nu)D_{tj}\right)^{-\rho}+t\bigl(\nu+C\chi(\vartheta)\bigr). (ii) λ t ′ 1 ≤ j ∈ J t ( ϑ ) ∑ ( ( 1 + γ ) ( 1 − ν ) D t j ) − ρ + t ( ν + C χ ( ϑ ) ) . Then t λ t ′ → a ∗ t\lambda'_t\to a^* t λ t ′ → a ∗ .
Proof. Let a ‾ = lim sup t λ t ′ \overline a=\limsup t\lambda'_t a = lim sup t λ t ′ and a ‾ = lim inf t λ t ′ \underline a=\liminf t\lambda'_t a = lim inf t λ t ′ , and I ϑ = ∫ ϑ 1 − ϑ ( log 1 s ) − ρ d s I_\vartheta=\int_\vartheta^{1-\vartheta}\left(\log\frac{1}{s}\right)^{-\rho}ds I ϑ = ∫ ϑ 1 − ϑ ( log s 1 ) − ρ d s , which tends to Γ ( 1 − ρ ) \Gamma(1-\rho) Γ ( 1 − ρ ) as ϑ → 0 \vartheta\to0 ϑ → 0 by (I).
Upper bound: a ‾ ≤ a ∗ \overline a\le a^* a ≤ a ∗ . Fix ϑ \vartheta ϑ and ν \nu ν , and i 0 i_0 i 0 with λ i ′ ≤ ( a ‾ + ν ) / i \lambda'_i\le(\overline a+\nu)/i λ i ′ ≤ ( a + ν ) / i for i ≥ i 0 i\ge i_0 i ≥ i 0 . For large t t t , every j ∈ J t ( ϑ ) j\in J_t(\vartheta) j ∈ J t ( ϑ ) satisfies j − 1 ≥ i 0 j-1\ge i_0 j − 1 ≥ i 0 , so (H) gives D t j ≤ ( a ‾ + ν ) log t j − 1 D_{tj}\le(\overline a+\nu)\log\frac{t}{j-1} D t j ≤ ( a + ν ) log j − 1 t . Since u ↦ ( log ( t / u ) ) − ρ u\mapsto(\log(t/u))^{-\rho} u ↦ ( log ( t / u ) ) − ρ is increasing, (M) and the substitution u = t s u=ts u = t s give ∑ j ∈ J t ( ϑ ) ( log t j − 1 ) − ρ ≥ t I ϑ ( 1 + o ( 1 ) ) \sum_{j\in J_t(\vartheta)}\left(\log\frac{t}{j-1}\right)^{-\rho}\ge tI_\vartheta(1+o(1)) ∑ j ∈ J t ( ϑ ) ( log j − 1 t ) − ρ ≥ t I ϑ ( 1 + o ( 1 )) , and (i) yields
1 a ‾ = lim inf t → ∞ 1 t λ t ′ ≥ ( ( 1 + γ ) ( 1 + ν ) ( a ‾ + ν ) ) − ρ I ϑ − ν . \frac{1}{\underline a}=\liminf_{t\to\infty}\frac{1}{t\lambda'_t}\ge((1+\gamma)(1+\nu)(\overline a+\nu))^{-\rho}I_\vartheta-\nu. a 1 = t → ∞ lim inf t λ t ′ 1 ≥ (( 1 + γ ) ( 1 + ν ) ( a + ν ) ) − ρ I ϑ − ν . Letting ν → 0 \nu\to0 ν → 0 and then ϑ → 0 \vartheta\to0 ϑ → 0 gives 1 / a ‾ ≥ ( ( 1 + γ ) a ‾ ) − ρ Γ ( 1 − ρ ) = C ρ a ‾ − ρ 1/\underline a\ge((1+\gamma)\overline a)^{-\rho}\Gamma(1-\rho)=C_\rho\overline a^{-\rho} 1/ a ≥ (( 1 + γ ) a ) − ρ Γ ( 1 − ρ ) = C ρ a − ρ , that is, a ‾ ≤ T ( a ‾ ) \overline a\le T(\overline a) a ≤ T ( a ) , so a ‾ ≤ a ∗ \overline a\le a^* a ≤ a ∗ .
Lower bound: a ‾ ≥ a ∗ \underline{a} \ge a^{*} a ≥ a ∗ . Fix ϑ \vartheta ϑ , ν < a ‾ \nu< \underline{a} ν < a , and i 1 i_{1} i 1 with λ i ′ ≥ ( a ‾ − ν ) / i \lambda'_{i} \ge(\underline{a}-\nu)/i λ i ′ ≥ ( a − ν ) / i for i ≥ i 1 i \ge i_{1} i ≥ i 1 . For large t t t , (H) gives D t j ≥ ( a ‾ − ν ) log t + 1 j D_{tj} \ge(\underline{a}-\nu)\log\frac{t+1}{j} D t j ≥ ( a − ν ) log j t + 1 for j ∈ J t ( ϑ ) j \in J_{t}(\vartheta) j ∈ J t ( ϑ ) , and by (M) and (I), ∑ j ≤ t ( log t + 1 j ) − ρ ≤ ( t + 1 ) Γ ( 1 − ρ ) \sum_{j \le t}\left(\log\frac{t+1}{j}\right)^{-\rho} \le(t+1)\Gamma(1-\rho) ∑ j ≤ t ( log j t + 1 ) − ρ ≤ ( t + 1 ) Γ ( 1 − ρ ) . So (ii) yields
1 a ‾ = lim sup t → ∞ 1 t λ t ≤ ( ( 1 + γ ) ( 1 − ν ) ( a ‾ − ν ) ) − ρ Γ ( 1 − ρ ) + ν + C χ ( ϑ ) . \frac{1}{\underline{a}}=\limsup_{t\to\infty}\frac{1}{t\lambda_t}\le\left((1+\gamma)(1-\nu)(\underline{a}-\nu)\right)^{-\rho}\Gamma(1-\rho)+\nu+C\chi(\vartheta). a 1 = t → ∞ lim sup t λ t 1 ≤ ( ( 1 + γ ) ( 1 − ν ) ( a − ν ) ) − ρ Γ ( 1 − ρ ) + ν + C χ ( ϑ ) .
Letting ν → 0 \nu\to0 ν → 0 and then ϑ → 0 \vartheta\to0 ϑ → 0 gives 1 / a ‾ ≤ C ρ a ‾ − ρ 1/\underline{a}\le C_{\rho}\underline{a}^{-\rho} 1/ a ≤ C ρ a − ρ , that is, a ‾ ≥ T ( a ‾ ) \underline{a}\ge T(\underline{a}) a ≥ T ( a ) , so a ‾ ≥ a ∗ \underline{a}\ge a^{*} a ≥ a ∗ . Since a ‾ ≤ a ‾ \underline{a}\le\overline{a} a ≤ a , both equal a ∗ a^{*} a ∗ .
Proof of Theorem 6
Theorem 6 (Asymptotics of the row normalizers). With constant scores, t λ t → a ∗ t\lambda_t\to a^{*} t λ t → a ∗ . For ρ = 1 / 2 \rho=1/2 ρ = 1/2 , a ∗ = 2 / π a^{*}=2/\pi a ∗ = 2/ π .
From here on, until Proposition 10, the scores are constant: K ≡ 1 K\equiv1 K ≡ 1 , so B = 0 B=0 B = 0 , W t j = Λ t − Λ j − 1 W_{tj}=\Lambda_t-\Lambda_{j-1} W t j = Λ t − Λ j − 1 , and Lemmas 17 and 18 hold with a 0 a_0 a 0 and c 0 = 1 / a 0 c_0=1/a_0 c 0 = 1/ a 0 . With m = j − 1 m=j-1 m = j − 1 , (SB) becomes the normalization sandwich
∑ m = 0 t − 1 ( ( 1 + γ ) ( Λ t − Λ m ) ) − ρ ≤ 1 λ t ≤ ∑ m = 0 t − 1 ( Λ t − Λ m ) − ρ , (10) \sum_{m=0}^{t-1}\left((1+\gamma)(\Lambda_t-\Lambda_m)\right)^{-\rho}\le\frac{1}{\lambda_t}\le\sum_{m=0}^{t-1}(\Lambda_t-\Lambda_m)^{-\rho}, \tag*{(10)} m = 0 ∑ t − 1 ( ( 1 + γ ) ( Λ t − Λ m ) ) − ρ ≤ λ t 1 ≤ m = 0 ∑ t − 1 ( Λ t − Λ m ) − ρ , (10)
whose two sides differ by the factor ( 1 + γ ) − ρ (1+\gamma)^{-\rho} ( 1 + γ ) − ρ .
Strategy. We apply Lemma 20 with λ ′ = λ \lambda'=\lambda λ ′ = λ , so that D t j = Λ t − Λ j − 1 D_{tj}=\Lambda_t-\Lambda_{j-1} D t j = Λ t − Λ j − 1 . Hypothesis (i) is the left side of (S). For (ii), the right side of (S) alone would not do: it lacks the factor ( 1 + γ ) − ρ (1+\gamma)^{-\rho} ( 1 + γ ) − ρ , and the argument of the lemma would give only lim inf t λ t ≥ Γ ( 1 − ρ ) − 1 / ( 1 − ρ ) \liminf t\lambda_t\ge\Gamma(1-\rho)^{-1/(1-\rho)} lim inf t λ t ≥ Γ ( 1 − ρ ) − 1/ ( 1 − ρ ) , which lies below a ∗ a^{*} a ∗ . Away from the diagonal, however, a row’s increment is negligible against the mass the column has accumulated, and Lemma 18(1) shows that M t j 1 + γ M_{tj}^{1+\gamma} M t j 1 + γ is then close to the upper end of Lemma 3 . This restores the factor in the middle range; the rest of the sum is the error C χ ( ϑ ) C\chi(\vartheta) C χ ( ϑ ) .
Proof. By Lemmas 4 and 17, a 0 ≤ t λ t ≤ 1 a_0\le t\lambda_t\le1 a 0 ≤ t λ t ≤ 1 . Fix ϑ , ν ∈ ( 0 , 1 2 ) \vartheta,\nu\in(0,\frac{1}{2}) ϑ , ν ∈ ( 0 , 2 1 ) .
Hypothesis (i). The terms on the left of (S) are positive, so keeping only j = m + 1 ∈ J t ( ϑ ) j=m+1\in J_t(\vartheta) j = m + 1 ∈ J t ( ϑ ) gives 1 / λ t ≥ ∑ j ∈ J t ( ϑ ) ( ( 1 + γ ) D t j ) − ρ 1/\lambda_t\ge\sum_{j\in J_t(\vartheta)}((1+\gamma)D_{tj})^{-\rho} 1/ λ t ≥ ∑ j ∈ J t ( ϑ ) (( 1 + γ ) D t j ) − ρ , which is at least the right side of (i).
Hypothesis (ii). Split the normalization 1 / λ t = ∑ j ≤ t M t j − γ 1/\lambda_t=\sum_{j\le t}M_{tj}^{-\gamma} 1/ λ t = ∑ j ≤ t M t j − γ into the middle range J t ( ϑ ) J_t(\vartheta) J t ( ϑ ) and the two ends. By Lemma 3 , Lemma 17 and (H),
M t j − γ = ( M t j 1 + γ ) − ρ ≤ ( Λ t − Λ j − 1 ) − ρ ≤ a 0 − ρ ℓ t j − ρ , (11) M_{tj}^{-\gamma}=(M_{tj}^{1+\gamma})^{-\rho}\le(\Lambda_t-\Lambda_{j-1})^{-\rho}\le a_0^{-\rho}\ell_{tj}^{-\rho}, \tag*{(11)} M t j − γ = ( M t j 1 + γ ) − ρ ≤ ( Λ t − Λ j − 1 ) − ρ ≤ a 0 − ρ ℓ t j − ρ , (11)
so by Lemma 19 the two ends contribute at most t C χ ( ϑ ) tC\chi(\vartheta) tC χ ( ϑ ) with C = 2 a 0 − ρ / ( 1 − ρ ) C=2a_0^{-\rho}/(1-\rho) C = 2 a 0 − ρ / ( 1 − ρ ) . In the middle range, Lemma 18(1) gives M t j 1 + γ ≥ ( 1 + γ ) ( 1 − η ˉ t ) D t j M_{tj}^{1+\gamma}\ge(1+\gamma)(1-\bar{\eta}_t)D_{tj} M t j 1 + γ ≥ ( 1 + γ ) ( 1 − η ˉ t ) D t j with η ˉ t → 0 \bar{\eta}_t\to0 η ˉ t → 0 , so for large t t t this part is at most ∑ j ∈ J t ( ϑ ) ( ( 1 + γ ) ( 1 − ν ) D t j ) − ρ \sum_{j\in J_t(\vartheta)}((1+\gamma)(1-\nu)D_{tj})^{-\rho} ∑ j ∈ J t ( ϑ ) (( 1 + γ ) ( 1 − ν ) D t j ) − ρ . Together these give (ii).
Lemma 20 gives t λ t → a ∗ t\lambda_t\to a^{*} t λ t → a ∗ . Finally, for ρ = 1 2 \rho=\frac{1}{2} ρ = 2 1 , γ = 1 \gamma=1 γ = 1 , C ρ = 2 − 1 / 2 Γ ( 1 2 ) = 2 − 1 / 2 π C_{\rho}=2^{-1/2}\Gamma(\frac{1}{2})=2^{-1/2}\sqrt{\pi} C ρ = 2 − 1/2 Γ ( 2 1 ) = 2 − 1/2 π , and a ∗ = C ρ − 1 / ( 1 − ρ ) = C ρ − 2 = 2 / π a^{*}=C_{\rho}^{-1/(1-\rho)}=C_{\rho}^{-2}=2/\pi a ∗ = C ρ − 1/ ( 1 − ρ ) = C ρ − 2 = 2/ π .
Proofs of Theorems 7 and 8
Theorem 7 (Scale-invariant limit shape of the implicit prior). *With constant scores, for every δ ∈ ( 0 , 1 2 ) \delta\in(0,\frac{1}{2}) δ ∈ ( 0 , 2 1 ) , uniformly in s ∈ [ δ , 1 − δ ] s\in[\delta,1-\delta] s ∈ [ δ , 1 − δ ] ,
t P t , ⌊ s t ⌋ ⟶ f ( s ) = ( log 1 / s ) − ρ Γ ( 1 − ρ ) . tP_{t,\lfloor st\rfloor}\longrightarrow f(s)=\frac{(\log1/s)^{-\rho}}{\Gamma(1-\rho)}. t P t , ⌊ s t ⌋ ⟶ f ( s ) = Γ ( 1 − ρ ) ( log 1/ s ) − ρ .
Proof. P t j = λ t M t j − γ P_{tj}=\lambda_t M_{tj}^{-\gamma} P t j = λ t M t j − γ . Take ϑ = δ \vartheta=\delta ϑ = δ in Lemma 18(1): M t j 1 + γ = ( 1 + γ ) ( Λ t − Λ j − 1 ) ( 1 + o ( 1 ) ) M_{tj}^{1+\gamma}=(1+\gamma)(\Lambda_t-\Lambda_{j-1})(1+o(1)) M t j 1 + γ = ( 1 + γ ) ( Λ t − Λ j − 1 ) ( 1 + o ( 1 )) uniformly for j = ⌊ s t ⌋ j=\lfloor st\rfloor j = ⌊ s t ⌋ , s ∈ [ δ , 1 − δ ] s\in[\delta,1-\delta] s ∈ [ δ , 1 − δ ] . Theorem 6 says that ω n = sup i ≥ n ∣ i λ i − a ∗ ∣ → 0 \omega_n=\sup_{i\ge n}|i\lambda_i-a^*|\to0 ω n = sup i ≥ n ∣ i λ i − a ∗ ∣ → 0 . Every i i i in Λ t − Λ j − 1 = ∑ i = j t λ i \Lambda_t-\Lambda_{j-1}=\sum_{i=j}^{t}\lambda_i Λ t − Λ j − 1 = ∑ i = j t λ i satisfies i ≥ j ≥ δ t − 1 i\ge j\ge\delta t-1 i ≥ j ≥ δ t − 1 , so
∣ Λ t − Λ j − 1 − a ∗ ∑ i = j t 1 i ∣ ≤ ω ⌈ δ t ⌉ − 1 ∑ i = j t 1 i ≤ ω ⌈ δ t ⌉ − 1 ( log 1 δ + 1 ) → 0 \left|\Lambda_t-\Lambda_{j-1}-a^*\sum_{i=j}^{t}\frac{1}{i}\right|\le\omega_{\lceil\delta t\rceil-1}\sum_{i=j}^{t}\frac{1}{i}\le\omega_{\lceil\delta t\rceil-1}\left(\log\frac{1}{\delta}+1\right)\to0 Λ t − Λ j − 1 − a ∗ i = j ∑ t i 1 ≤ ω ⌈ δ t ⌉ − 1 i = j ∑ t i 1 ≤ ω ⌈ δ t ⌉ − 1 ( log δ 1 + 1 ) → 0
for t t t large, with a bound that does not depend on s s s ; with (H), ∑ i = j t 1 / i = log ( 1 / s ) + O ( 1 / ( δ t ) ) \sum_{i=j}^{t}1/i=\log(1/s)+O(1/(\delta t)) ∑ i = j t 1/ i = log ( 1/ s ) + O ( 1/ ( δ t )) . Hence Λ t − Λ j − 1 = a ∗ log ( 1 / s ) + o ( 1 ) \Lambda_t-\Lambda_{j-1}=a^*\log(1/s)+o(1) Λ t − Λ j − 1 = a ∗ log ( 1/ s ) + o ( 1 ) uniformly in s ∈ [ δ , 1 − δ ] s\in[\delta,1-\delta] s ∈ [ δ , 1 − δ ] , and since a ∗ log ( 1 / s ) ≥ a ∗ log 1 1 − δ > 0 a^*\log(1/s)\ge a^*\log\frac{1}{1-\delta}>0 a ∗ log ( 1/ s ) ≥ a ∗ log 1 − δ 1 > 0 there, the additive o ( 1 ) o(1) o ( 1 ) is a factor 1 + o ( 1 ) 1+o(1) 1 + o ( 1 ) . Hence
t P t j = t λ t ( ( 1 + γ ) a ∗ log ( 1 / s ) ) − ρ ( 1 + o ( 1 ) ) → a ∗ ( ( 1 + γ ) a ∗ ) − ρ ( log 1 / s ) − ρ , tP_{tj}=t\lambda_t\left((1+\gamma)a^*\log(1/s)\right)^{-\rho}(1+o(1))\to a^*\left((1+\gamma)a^*\right)^{-\rho}(\log1/s)^{-\rho}, t P t j = t λ t ( ( 1 + γ ) a ∗ log ( 1/ s ) ) − ρ ( 1 + o ( 1 )) → a ∗ ( ( 1 + γ ) a ∗ ) − ρ ( log 1/ s ) − ρ ,
and a ∗ 1 − ρ ( 1 + γ ) − ρ = 1 / Γ ( 1 − ρ ) a^{*\,1-\rho}(1+\gamma)^{-\rho}=1/\Gamma(1-\rho) a ∗ 1 − ρ ( 1 + γ ) − ρ = 1/Γ ( 1 − ρ ) by the definition of a ∗ a^* a ∗ .
Near the diagonal the row normalizers vary little across the rows that a column has seen, so the column behaves as if every normalizer were equal. The discrete profile z d z_d z d of Theorem 8 is that column with all normalizers equal to one.
Lemma 21. Let z − 1 = 0 z_{-1}=0 z − 1 = 0 and let z d γ ( z d − z d − 1 ) = 1 z_d^\gamma(z_d-z_{d-1})=1 z d γ ( z d − z d − 1 ) = 1 . Then z d z_d z d is the mass of a column after d + 1 d+1 d + 1 rows when every row normalizer equals one, z d 1 + γ = ( 1 + γ ) ( d + 1 ) ( 1 + o ( 1 ) ) z_d^{1+\gamma}=(1+\gamma)(d+1)(1+o(1)) z d 1 + γ = ( 1 + γ ) ( d + 1 ) ( 1 + o ( 1 )) , and z d − z d − 1 ∼ ( 1 + γ ) − ρ d − ρ z_d-z_{d-1}\sim(1+\gamma)^{-\rho}d^{-\rho} z d − z d − 1 ∼ ( 1 + γ ) − ρ d − ρ .
Proof. Each increment is z d − z d − 1 = z d − γ z_d-z_{d-1}=z_d^{-\gamma} z d − z d − 1 = z d − γ , which is (6) for one column with λ = K = 1 \lambda=K=1 λ = K = 1 . The argument of Lemma 3 with λ ≡ 1 \lambda\equiv1 λ ≡ 1 gives d + 1 ≤ z d 1 + γ ≤ ( 1 + γ ) ( d + 1 ) d+1\le z_d^{1+\gamma}\le(1+\gamma)(d+1) d + 1 ≤ z d 1 + γ ≤ ( 1 + γ ) ( d + 1 ) , and (7) gives z d 1 + γ / z d − 1 1 + γ ∈ [ ( 1 + γ ) ( z d − 1 / z d ) γ , 1 + γ ] z_d^{1+\gamma}/z_{d-1}^{1+\gamma}\in[(1+\gamma)(z_{d-1}/z_d)^\gamma,1+\gamma] z d 1 + γ / z d − 1 1 + γ ∈ [( 1 + γ ) ( z d − 1 / z d ) γ , 1 + γ ] . Since the increments tend to 0 while z d → ∞ z_d\to\infty z d → ∞ , z d − 1 / z d → 1 z_{d-1}/z_d\to1 z d − 1 / z d → 1 , so z d 1 + γ = ( 1 + γ ) ( d + 1 ) ( 1 + o ( 1 ) ) z_d^{1+\gamma}=(1+\gamma)(d+1)(1+o(1)) z d 1 + γ = ( 1 + γ ) ( d + 1 ) ( 1 + o ( 1 )) and z d − z d − 1 = ( z d 1 + γ ) − ρ ∼ ( 1 + γ ) − ρ d − ρ z_d-z_{d-1}=(z_d^{1+\gamma})^{-\rho}\sim(1+\gamma)^{-\rho}d^{-\rho} z d − z d − 1 = ( z d 1 + γ ) − ρ ∼ ( 1 + γ ) − ρ d − ρ .
Power law near the diagonal
Theorem 8 (Power law near the diagonal). Let z − 1 = 0 z_{-1}=0 z − 1 = 0 and let z d z_d z d solve z d γ ( z d − z d − 1 ) = 1 z_d^\gamma(z_d-z_{d-1})=1 z d γ ( z d − z d − 1 ) = 1 . With constant scores,
for fixed d ≥ 0 d\ge0 d ≥ 0 , t 1 − ρ P t , t − d → a ∗ 1 − ρ ( z d − z d − 1 ) t^{1-\rho}P_{t,t-d}\to a^{*\,1-\rho}(z_d-z_{d-1}) t 1 − ρ P t , t − d → a ∗ 1 − ρ ( z d − z d − 1 ) ;
for d = d t → ∞ d=d_t\to\infty d = d t → ∞ with d t / t → 0 d_t/t\to0 d t / t → 0 , P t , t − d = t ρ − 1 d − ρ Γ ( 1 − ρ ) − 1 ( 1 + o ( 1 ) ) P_{t,t-d}=t^{\rho-1}d^{-\rho}\Gamma(1-\rho)^{-1}(1+o(1)) P t , t − d = t ρ − 1 d − ρ Γ ( 1 − ρ ) − 1 ( 1 + o ( 1 )) .
Proof. (1) The increments of column j = t − d j=t-d j = t − d in rows j , … , t j,\ldots,t j , … , t are determined by λ j , … , λ t \lambda_j,\ldots,\lambda_t λ j , … , λ t through (6) , continuously. If all equal λ \lambda λ , homogeneity (λ ↦ r λ \lambda\mapsto r\lambda λ ↦ r λ maps x ↦ r 1 − ρ x x\mapsto r^{1-\rho}x x ↦ r 1 − ρ x ) and Lemma 21 give P t , t − d = λ 1 − ρ ( z d − z d − 1 ) P_{t,t-d}=\lambda^{1-\rho}(z_d-z_{d-1}) P t , t − d = λ 1 − ρ ( z d − z d − 1 ) . By Theorem 6 , λ i / λ t → 1 \lambda_i/\lambda_t\to1 λ i / λ t → 1 uniformly for i ∈ [ t − d , t ] i\in[t-d,t] i ∈ [ t − d , t ] and λ t 1 − ρ = ( a ∗ / t ) 1 − ρ ( 1 + o ( 1 ) ) \lambda_t^{1-\rho}=(a^*/t)^{1-\rho}(1+o(1)) λ t 1 − ρ = ( a ∗ / t ) 1 − ρ ( 1 + o ( 1 )) ; continuity gives the claim.
(2) By Lemma 18(2), η t j → 0 \eta_{tj}\to0 η t j → 0 as d → ∞ d\to\infty d → ∞ , uniformly in t t t . By Theorem 6 , uniformly for i ∈ [ t − d , t ] i\in[t-d,t] i ∈ [ t − d , t ] , λ i = ( a ∗ + o ( 1 ) ) / i \lambda_i=(a^*+o(1))/i λ i = ( a ∗ + o ( 1 )) / i , so Λ t − Λ j − 1 = a ∗ ( d + 1 ) t ( 1 + o ( 1 ) ) \Lambda_t-\Lambda_{j-1}=a^*\frac{(d+1)}{t}(1+o(1)) Λ t − Λ j − 1 = a ∗ t ( d + 1 ) ( 1 + o ( 1 )) when d / t → 0 d/t\to0 d / t → 0 . Then
P t j = λ t ( ( 1 + γ ) ( Λ t − Λ j − 1 ) ( 1 − η t j ) ) − ρ = t ρ − 1 ( d + 1 ) − ρ a ∗ 1 − ρ ( 1 + γ ) − ρ ( 1 + o ( 1 ) ) , P_{tj}=\lambda_t\left((1+\gamma)(\Lambda_t-\Lambda_{j-1})(1-\eta_{tj})\right)^{-\rho}=t^{\rho-1}(d+1)^{-\rho}a^{*\,1-\rho}(1+\gamma)^{-\rho}(1+o(1)), P t j = λ t ( ( 1 + γ ) ( Λ t − Λ j − 1 ) ( 1 − η t j ) ) − ρ = t ρ − 1 ( d + 1 ) − ρ a ∗ 1 − ρ ( 1 + γ ) − ρ ( 1 + o ( 1 )) ,
and a ∗ 1 − ρ ( 1 + γ ) − ρ = 1 / Γ ( 1 − ρ ) a^{*\,1-\rho}(1+\gamma)^{-\rho}=1/\Gamma(1-\rho) a ∗ 1 − ρ ( 1 + γ ) − ρ = 1/Γ ( 1 − ρ ) . The two regimes match by Lemma 21.
Remark 22. Let N t ( L ) = ∑ t − L < j ≤ t P t j N_t(L)=\sum_{t-L<j\le t}P_{tj} N t ( L ) = ∑ t − L < j ≤ t P t j be the mass within distance L L L of the diagonal, with constant scores. Fixed window. By Theorem 8(1) for d = 0 , … , L − 1 d=0,\ldots,L-1 d = 0 , … , L − 1 the increments telescope, t 1 − ρ N t ( L ) → a ∗ 1 − ρ ∑ d < L ( z d − z d − 1 ) = a ∗ 1 − ρ z L − 1 t^{1-\rho}N_t(L)\to a^{*\,1-\rho}\sum_{d<L}(z_d-z_{d-1})=a^{*\,1-\rho}z_{L-1} t 1 − ρ N t ( L ) → a ∗ 1 − ρ ∑ d < L ( z d − z d − 1 ) = a ∗ 1 − ρ z L − 1 . By Lemma 21, z L − 1 = ( ( 1 + γ ) L ) 1 − ρ ( 1 + o ( 1 ) ) z_{L-1}=((1+\gamma)L)^{1-\rho}(1+o(1)) z L − 1 = (( 1 + γ ) L ) 1 − ρ ( 1 + o ( 1 )) as L → ∞ L\to\infty L → ∞ , and a ∗ 1 − ρ ( 1 + γ ) 1 − ρ = ( 1 + γ ) / Γ ( 1 − ρ ) = 1 / Γ ( 2 − ρ ) a^{*\,1-\rho}(1+\gamma)^{1-\rho}=(1+\gamma)/\Gamma(1-\rho)=1/\Gamma(2-\rho) a ∗ 1 − ρ ( 1 + γ ) 1 − ρ = ( 1 + γ ) /Γ ( 1 − ρ ) = 1/Γ ( 2 − ρ ) , so the limit is L 1 − ρ / Γ ( 2 − ρ ) ( 1 + o ( 1 ) ) L^{1-\rho}/\Gamma(2-\rho)(1+o(1)) L 1 − ρ /Γ ( 2 − ρ ) ( 1 + o ( 1 )) . Thus the rate t − ( 1 − ρ ) t^{-(1-\rho)} t − ( 1 − ρ ) of Theorem 5 is attained, while the dependence on L L L is L 1 − ρ L^{1-\rho} L 1 − ρ rather than the bound’s L L L . Proportional window. For L = σ t L=\sigma t L = σ t , N t ( L ) → ∫ 1 − σ 1 f N_t(L)\to\int_{1-\sigma}^{1}f N t ( L ) → ∫ 1 − σ 1 f : on [ 1 − σ , 1 − ϑ ] [1-\sigma,1-\vartheta] [ 1 − σ , 1 − ϑ ] by uniform convergence (Theorem 7 ), and the range j > ( 1 − ϑ ) t j>(1-\vartheta)t j > ( 1 − ϑ ) t contributes O ( ϑ 1 − ρ ) O(\vartheta^{1-\rho}) O ( ϑ 1 − ρ ) by (11) , Lemma 19 and λ t ≤ 1 / t \lambda_t\le1/t λ t ≤ 1/ t . As σ → 0 \sigma\to0 σ → 0 , ∫ 1 − σ 1 f = σ 1 − ρ / Γ ( 2 − ρ ) ( 1 + o ( 1 ) ) \int_{1-\sigma}^{1}f=\sigma^{1-\rho}/\Gamma(2-\rho)(1+o(1)) ∫ 1 − σ 1 f = σ 1 − ρ /Γ ( 2 − ρ ) ( 1 + o ( 1 )) since f ( s ) ∼ ( 1 − s ) − ρ / Γ ( 1 − ρ ) f(s)\sim(1-s)^{-\rho}/\Gamma(1-\rho) f ( s ) ∼ ( 1 − s ) − ρ /Γ ( 1 − ρ ) , which matches the fixed window with L = σ t L=\sigma t L = σ t .
Proof of Theorem 9 (finite iterations)
Theorem 9 (Limit shape after finitely many iterations). With constant scores and any fixed k ≥ 2 k \ge2 k ≥ 2 , the k k k -th iterate (5) satisfies P t , ⌊ s t ⌋ ( k ) → f ( s ) P_{t,\lfloor st\rfloor}^{(k)} \to f(s) P t , ⌊ s t ⌋ ( k ) → f ( s ) uniformly on [ δ , 1 − δ ] [\delta,1-\delta] [ δ , 1 − δ ] .
The proof is an induction on k k k , in which each step passes from the scaling limit of the scalings v t ( k ) v_t^{(k)} v t ( k ) to that of the row, and from the row to the column mass. The two passages do not depend on k k k , and we state them first as lemmas about arrays. Write ℓ ( s ) = log ( 1 / s ) \ell(s)=\log(1/s) ℓ ( s ) = log ( 1/ s ) , so that f = ℓ − ρ / Γ ( 1 − ρ ) f=\ell^{-\rho}/\Gamma(1-\rho) f = ℓ − ρ /Γ ( 1 − ρ ) , and
G ( s ) = ∫ s 1 f ( u ) d u u = 1 Γ ( 1 − ρ ) ∫ 0 ℓ ( s ) x − ρ d x = ℓ ( s ) 1 − ρ ( 1 − ρ ) Γ ( 1 − ρ ) ( x = ℓ ( u ) , d u / u = − d x ) . G(s)=\int_s^1 f(u)\,\frac{du}{u}=\frac{1}{\Gamma(1-\rho)}\int_0^{\ell(s)}x^{-\rho}\,dx=\frac{\ell(s)^{1-\rho}}{(1-\rho)\Gamma(1-\rho)}
\qquad(x=\ell(u),\ du/u=-dx). G ( s ) = ∫ s 1 f ( u ) u d u = Γ ( 1 − ρ ) 1 ∫ 0 ℓ ( s ) x − ρ d x = ( 1 − ρ ) Γ ( 1 − ρ ) ℓ ( s ) 1 − ρ ( x = ℓ ( u ) , d u / u = − d x ) .
“Uniformly” means uniformly in s ∈ [ δ , 1 − δ ] s\in[\delta,1-\delta] s ∈ [ δ , 1 − δ ] as t → ∞ t\to\infty t → ∞ , with j = ⌊ s t ⌋ j=\lfloor st\rfloor j = ⌊ s t ⌋ , for every δ ∈ ( 0 , 1 2 ) \delta\in(0,\frac12) δ ∈ ( 0 , 2 1 ) ; every compact subset of ( 0 , 1 ) (0,1) ( 0 , 1 ) lies in such an interval, and on it ℓ t , ⌊ s t ⌋ → ℓ ( s ) \ell_{t,\lfloor st\rfloor}\to\ell(s) ℓ t , ⌊ s t ⌋ → ℓ ( s ) uniformly and ℓ ( s ) ≥ log 1 1 − δ > 0 \ell(s)\ge\log\frac{1}{1-\delta}>0 ℓ ( s ) ≥ log 1 − δ 1 > 0 .
Lemma 23. Let v t j ≥ 0 v_{tj}\ge0 v t j ≥ 0 with v t j ≤ C ℓ t j − ρ v_{tj}\le C\ell_{tj}^{-\rho} v t j ≤ C ℓ t j − ρ for all j ≤ t j\le t j ≤ t , and v t , ⌊ s t ⌋ → V ℓ ( s ) − ρ v_{t,\lfloor st\rfloor}\to V\ell(s)^{-\rho} v t , ⌊ s t ⌋ → V ℓ ( s ) − ρ uniformly, for a constant V ≥ 0 V\ge0 V ≥ 0 . Then Σ t = t − 1 ∑ j ≤ t v t j → V Γ ( 1 − ρ ) \Sigma_t=t^{-1}\sum_{j\le t}v_{tj}\to V\Gamma(1-\rho) Σ t = t − 1 ∑ j ≤ t v t j → V Γ ( 1 − ρ ) .
Proof. By (I), V Γ ( 1 − ρ ) = V ∫ 0 1 ℓ − ρ V\Gamma(1-\rho)=V\int_0^1\ell^{-\rho} V Γ ( 1 − ρ ) = V ∫ 0 1 ℓ − ρ . Fix ϑ ∈ ( 0 , 1 2 ) \vartheta\in(0,\frac12) ϑ ∈ ( 0 , 2 1 ) and split both the sum and the integral at ϑ \vartheta ϑ and 1 − ϑ 1-\vartheta 1 − ϑ : Σ t = A f a r + A m i d + A n e a r \Sigma_t=A_{\mathrm{far}}+A_{\mathrm{mid}}+A_{\mathrm{near}} Σ t = A far + A mid + A near over j < ϑ t j<\vartheta t j < ϑt , j ∈ J t ( ϑ ) j\in J_t(\vartheta) j ∈ J t ( ϑ ) , j > ( 1 − ϑ ) t j>(1-\vartheta)t j > ( 1 − ϑ ) t , and ∫ 0 1 ℓ − ρ = I f a r + I m i d + I n e a r \int_0^1\ell^{-\rho}=I_{\mathrm{far}}+I_{\mathrm{mid}}+I_{\mathrm{near}} ∫ 0 1 ℓ − ρ = I far + I mid + I near over [ 0 , ϑ ] [0,\vartheta] [ 0 , ϑ ] , [ ϑ , 1 − ϑ ] [\vartheta,1-\vartheta] [ ϑ , 1 − ϑ ] , [ 1 − ϑ , 1 ] [1-\vartheta,1] [ 1 − ϑ , 1 ] . With the Riemann sum R t = t − 1 ∑ j ∈ J t ( ϑ ) ℓ ( j / t ) − ρ R_t=t^{-1}\sum_{j\in J_t(\vartheta)}\ell(j/t)^{-\rho} R t = t − 1 ∑ j ∈ J t ( ϑ ) ℓ ( j / t ) − ρ , the triangle inequality gives
∣ Σ t − V Γ ( 1 − ρ ) ∣ ≤ ∣ A m i d − V R t ∣ ⏟ ( 1 ) + V ∣ R t − I m i d ∣ ⏟ ( 2 ) + A f a r + A n e a r ⏟ ( 3 ) + V ( I f a r + I n e a r ) ⏟ ( 4 ) . \left|\Sigma_t-V\Gamma(1-\rho)\right|
\le
\underbrace{\left|A_{\mathrm{mid}}-VR_t\right|}_{(1)}
+\underbrace{V\left|R_t-I_{\mathrm{mid}}\right|}_{(2)}
+\underbrace{A_{\mathrm{far}}+A_{\mathrm{near}}}_{(3)}
+\underbrace{V\left(I_{\mathrm{far}}+I_{\mathrm{near}}\right)}_{(4)}. ∣ Σ t − V Γ ( 1 − ρ ) ∣ ≤ ( 1 ) ∣ A mid − V R t ∣ + ( 2 ) V ∣ R t − I mid ∣ + ( 3 ) A far + A near + ( 4 ) V ( I far + I near ) .
Only (1) uses the convergence: it is at most max j ∈ J t ( ϑ ) ∣ v t j − V ℓ ( j / t ) − ρ ∣ → 0 \max_{j\in J_t(\vartheta)}|v_{tj}-V\ell(j/t)^{-\rho}|\to0 max j ∈ J t ( ϑ ) ∣ v t j − V ℓ ( j / t ) − ρ ∣ → 0 . (2) tends to zero because ℓ − ρ \ell^{-\rho} ℓ − ρ is continuous on [ ϑ , 1 − ϑ ] [\vartheta,1-\vartheta] [ ϑ , 1 − ϑ ] . (3) is at most C ϑ ( log 1 ϑ ) − ρ + 2 C ϑ 1 − ρ / ( 1 − ρ ) C\vartheta(\log\frac1\vartheta)^{-\rho}+2C\vartheta^{1-\rho}/(1-\rho) C ϑ ( log ϑ 1 ) − ρ + 2 C ϑ 1 − ρ / ( 1 − ρ ) by Lemma 19. (4) is elementary: ℓ ≥ log 1 ϑ \ell\ge\log\frac1\vartheta ℓ ≥ log ϑ 1 on [ 0 , ϑ ] [0,\vartheta] [ 0 , ϑ ] and ℓ ( s ) ≥ 1 − s \ell(s)\ge1-s ℓ ( s ) ≥ 1 − s give I f a r ≤ ϑ ( log 1 ϑ ) − ρ I_{\mathrm{far}}\le\vartheta(\log\frac1\vartheta)^{-\rho} I far ≤ ϑ ( log ϑ 1 ) − ρ and I n e a r ≤ ϑ 1 − ρ / ( 1 − ρ ) I_{\mathrm{near}}\le\vartheta^{1-\rho}/(1-\rho) I near ≤ ϑ 1 − ρ / ( 1 − ρ ) . Hence
lim sup t → ∞ ∣ Σ t − V Γ ( 1 − ρ ) ∣ ≤ ( V + C ) ( ϑ ( log 1 ϑ ) − ρ + 2 ϑ 1 − ρ 1 − ρ ) . \limsup_{t\to\infty}\left|\Sigma_t-V\Gamma(1-\rho)\right|
\le(V+C)\left(\vartheta\left(\log\frac1\vartheta\right)^{-\rho}+\frac{2\vartheta^{1-\rho}}{1-\rho}\right). t → ∞ lim sup ∣ Σ t − V Γ ( 1 − ρ ) ∣ ≤ ( V + C ) ( ϑ ( log ϑ 1 ) − ρ + 1 − ρ 2 ϑ 1 − ρ ) .
for every ϑ ∈ ( 0 , 1 2 ) \vartheta\in(0,\frac12) ϑ ∈ ( 0 , 2 1 ) ; the left side does not depend on ϑ \vartheta ϑ .
Lemma 24. Let P i j ≥ 0 P_{ij}\ge0 P ij ≥ 0 for j ≤ i j\le i j ≤ i , with i P i j ≤ C ℓ i j − ρ iP_{ij}\le C\ell_{ij}^{-\rho} i P ij ≤ C ℓ ij − ρ for all j ≤ i j\le i j ≤ i and t P t , ⌊ s t ⌋ → f ( s ) tP_{t,\lfloor st\rfloor}\to f(s) t P t , ⌊ s t ⌋ → f ( s ) uniformly. Then M t , ⌊ s t ⌋ = ∑ i = ⌊ s t ⌋ t P i , ⌊ s t ⌋ → G ( s ) M_{t,\lfloor st\rfloor}=\sum_{i=\lfloor st\rfloor}^{t}P_{i,\lfloor st\rfloor}\to G(s) M t , ⌊ s t ⌋ = ∑ i = ⌊ s t ⌋ t P i , ⌊ s t ⌋ → G ( s ) uniformly.
Proof. Fix δ \delta δ and let s ∈ [ δ , 1 − δ ] s\in[\delta,1-\delta] s ∈ [ δ , 1 − δ ] , j = ⌊ s t ⌋ j=\lfloor st\rfloor j = ⌊ s t ⌋ . Column j j j is seen by rows i = j , … , t i=j,\ldots,t i = j , … , t , and row i i i sees it at relative position u i = j / i ∈ [ j / t , 1 ] u_i=j/i\in[j/t,1] u i = j / i ∈ [ j / t , 1 ] : M t j = ∑ i = j t i − 1 ( i P i j ) M_{tj}=\sum_{i=j}^t i^{-1}(iP_{ij}) M t j = ∑ i = j t i − 1 ( i P ij ) . Fix ϑ ∈ ( 0 , 1 2 ) \vartheta\in(0,\frac12) ϑ ∈ ( 0 , 2 1 ) and split the rows at u i = 1 − ϑ u_i=1-\vartheta u i = 1 − ϑ .
Rows with u i ≤ 1 − ϑ u_i\le1-\vartheta u i ≤ 1 − ϑ . Here u i ≥ j / t ≥ s − 1 / t ≥ δ / 2 u_i\ge j/t\ge s-1/t\ge\delta/2 u i ≥ j / t ≥ s − 1/ t ≥ δ /2 for t ≥ 2 / δ t\ge2/\delta t ≥ 2/ δ , so u i u_i u i lies in the fixed interval [ δ / 2 , 1 − ϑ ] [\delta/2,1-\vartheta] [ δ /2 , 1 − ϑ ] , and every row index i ≥ j ≥ δ t − 1 i\ge j\ge\delta t-1 i ≥ j ≥ δ t − 1 tends to infinity. The hypothesis, applied with min ( δ / 2 , ϑ ) \min(\delta/2,\vartheta) min ( δ /2 , ϑ ) in place of δ \delta δ , gives i P i j = f ( j / i ) + o ( 1 ) iP_{ij}=f(j/i)+o(1) i P ij = f ( j / i ) + o ( 1 ) uniformly in i i i and s s s . The error contributes o ( 1 ) ∑ i = j t 1 / i = o ( 1 ) o(1)\sum_{i=j}^t1/i=o(1) o ( 1 ) ∑ i = j t 1/ i = o ( 1 ) , since this sum is at most log ( 1 / δ ) + 1 \log(1/\delta)+1 log ( 1/ δ ) + 1 . The main part is ∑ i g ( i ) \sum_i g(i) ∑ i g ( i ) with g ( x ) = f ( j / x ) / x g(x)=f(j/x)/x g ( x ) = f ( j / x ) / x , which is positive and decreasing in x x x because f f f is increasing. By (M) it differs from
∫ j / ( 1 − ϑ ) t f ( j / x ) x d x = ∫ j / t 1 − ϑ f ( u ) d u u ( u = j / x ) \int_{j/(1-\vartheta)}^t\frac{f(j/x)}{x}\,dx
=
\int_{j/t}^{1-\vartheta}f(u)\,\frac{du}{u}
\qquad(u=j/x) ∫ j / ( 1 − ϑ ) t x f ( j / x ) d x = ∫ j / t 1 − ϑ f ( u ) u d u ( u = j / x )
by at most two terms of size g ( j / ( 1 − ϑ ) ) ≤ f ( 1 − ϑ ) / j → 0 g(j/(1-\vartheta)) \le f(1-\vartheta)/j \to0 g ( j / ( 1 − ϑ )) ≤ f ( 1 − ϑ ) / j → 0 (one from (M), one from rounding the lower limit to an integer), and the right side tends to ∫ s 1 − ϑ f ( u ) d u / u \int_s^{1-\vartheta} f(u)\,du/u ∫ s 1 − ϑ f ( u ) d u / u uniformly because j / t → s j/t \to s j / t → s uniformly.
*Rows with u i > 1 − ϑ u_i > 1-\vartheta u i > 1 − ϑ , i.e. j ≤ i < j / ( 1 − ϑ ) j \le i < j/(1-\vartheta) j ≤ i < j / ( 1 − ϑ ) , are the rows nearest the diagonal of column j j j ; here the bound on i P i j iP_{ij} i P ij replaces the convergence. With r = i + 1 − j r=i+1-j r = i + 1 − j , ℓ i j ≥ 1 − j i + 1 = r i + 1 \ell_{ij} \ge1-\frac{j}{i+1}=\frac{r}{i+1} ℓ ij ≥ 1 − i + 1 j = i + 1 r gives P i j ≤ C i ( i + 1 r ) ρ ≤ C j ( 3 j ) ρ r − ρ P_{ij} \le\frac{C}{i}\left(\frac{i+1}{r}\right)^\rho\le\frac{C}{j}(3j)^\rho r^{-\rho} P ij ≤ i C ( r i + 1 ) ρ ≤ j C ( 3 j ) ρ r − ρ , since j ≤ i j \le i j ≤ i and i + 1 ≤ 2 j + 1 ≤ 3 j i+1 \le2j+1 \le3j i + 1 ≤ 2 j + 1 ≤ 3 j . The range is r < ϑ j 1 − ϑ + 1 ≤ 2 ϑ j + 1 ≤ 3 ϑ j r < \frac{\vartheta j}{1-\vartheta}+1 \le2\vartheta j+1 \le3\vartheta j r < 1 − ϑ ϑ j + 1 ≤ 2 ϑ j + 1 ≤ 3 ϑ j once j ≥ 1 / ϑ j \ge1/\vartheta j ≥ 1/ ϑ , and (M) for the decreasing x ↦ x − ρ x \mapsto x^{-\rho} x ↦ x − ρ gives ∑ r = 1 R r − ρ ≤ R 1 − ρ / ( 1 − ρ ) \sum_{r=1}^{R} r^{-\rho} \le R^{1-\rho}/(1-\rho) ∑ r = 1 R r − ρ ≤ R 1 − ρ / ( 1 − ρ ) , so
∑ j ≤ i < j / ( 1 − ϑ ) P i j ≤ C j ( 3 j ) ρ ( 3 ϑ j ) 1 − ρ 1 − ρ = 3 C ϑ 1 − ρ 1 − ρ , \sum_{j\le i<j/(1-\vartheta)} P_{ij}
\le\frac{C}{j}(3j)^\rho\frac{(3\vartheta j)^{1-\rho}}{1-\rho}
= \frac{3C\vartheta^{1-\rho}}{1-\rho}, j ≤ i < j / ( 1 − ϑ ) ∑ P ij ≤ j C ( 3 j ) ρ 1 − ρ ( 3 ϑ j ) 1 − ρ = 1 − ρ 3 C ϑ 1 − ρ ,
in which the powers of j j j cancel. The missing integral ∫ 1 − ϑ 1 f ( u ) d u / u \int_{1-\vartheta}^{1} f(u)\,du/u ∫ 1 − ϑ 1 f ( u ) d u / u is at most 2 ϑ 1 − ρ / ( ( 1 − ρ ) Γ ( 1 − ρ ) ) 2\vartheta^{1-\rho}/((1-\rho)\Gamma(1-\rho)) 2 ϑ 1 − ρ / (( 1 − ρ ) Γ ( 1 − ρ )) , by u ≥ 1 2 u\ge\frac12 u ≥ 2 1 and ℓ ( u ) ≥ 1 − u \ell(u)\ge1-u ℓ ( u ) ≥ 1 − u . Letting ϑ → 0 \vartheta\to0 ϑ → 0 gives M t j → G ( s ) M_{tj}\to G(s) M t j → G ( s ) uniformly. □ \square □
Strategy. The proof does not use the fixed point. With constant scores every iterate is an explicit function of the previous one, and an induction on k k k shows first that every iterate has the order of the limit shape (Step 1) and then, with Lemmas 23 and 24 , that it converges to it (Step 2).
Unrolling (5) with v ( 1 ) = 1 v^{(1)}=1 v ( 1 ) = 1 gives log v ( k ) = − ∑ m = 1 k − 1 ρ k − m log M ( m ) \log v^{(k)}=-\sum_{m=1}^{k-1}\rho^{k-m}\log M^{(m)} log v ( k ) = − ∑ m = 1 k − 1 ρ k − m log M ( m ) ; with K ≡ 1 K\equiv1 K ≡ 1 , P ( k ) = rownorm ( v ( k ) ) P^{(k)}=\operatorname{rownorm}(v^{(k)}) P ( k ) = rownorm ( v ( k ) ) . Write h t j = ∑ i = j t 1 / i h_{tj}=\sum_{i=j}^{t}1/i h t j = ∑ i = j t 1/ i for the harmonic sums. For θ ∈ [ 0 , 1 ) \theta\in[0,1) θ ∈ [ 0 , 1 ) we use:
(R0) ℓ t j ≤ h t j ≤ 3 ℓ t j \ell_{tj}\le h_{tj}\le3\ell_{tj} ℓ t j ≤ h t j ≤ 3 ℓ t j (integral comparison; and h t j ≤ 1 / j + log ( t / j ) h_{tj}\le1/j+\log(t/j) h t j ≤ 1/ j + log ( t / j ) with ℓ t j ≥ 1 / ( 2 j ) \ell_{tj}\ge1/(2j) ℓ t j ≥ 1/ ( 2 j ) );
(R1) ∑ j = 1 t ℓ t j − θ ≍ t \sum_{j=1}^{t}\ell_{tj}^{-\theta}\asymp t ∑ j = 1 t ℓ t j − θ ≍ t , and it equals ( t + 1 ) Γ ( 1 − θ ) ( 1 + o ( 1 ) ) (t+1)\Gamma(1-\theta)(1+o(1)) ( t + 1 ) Γ ( 1 − θ ) ( 1 + o ( 1 )) by (M) and (I);
(R2) ∑ i = j t ℓ i j − θ / i ≍ ℓ t j 1 − θ \sum_{i=j}^{t}\ell_{ij}^{-\theta}/i\asymp\ell_{tj}^{1-\theta} ∑ i = j t ℓ ij − θ / i ≍ ℓ t j 1 − θ uniformly in 1 ≤ j ≤ t 1\le j\le t 1 ≤ j ≤ t (a Riemann sum for ∫ u − θ d u \int u^{-\theta}\,du ∫ u − θ d u ; the first term, i = j i=j i = j , has the order of ℓ j j 1 − θ \ell_{jj}^{1-\theta} ℓ j j 1 − θ ).
Here ≍ \asymp ≍ means two-sided bounds with constants depending only on θ \theta θ (and below on k , ρ k,\rho k , ρ ).
Step 1: two-sided bounds. We show by induction on k ≥ 2 k\ge2 k ≥ 2 that v ( k ) ≍ ℓ − ρ v^{(k)}\asymp\ell^{-\rho} v ( k ) ≍ ℓ − ρ , P ( k ) ≍ ℓ − ρ / t P^{(k)}\asymp\ell^{-\rho}/t P ( k ) ≍ ℓ − ρ / t and M ( k ) ≍ ℓ 1 − ρ M^{(k)}\asymp\ell^{1-\rho} M ( k ) ≍ ℓ 1 − ρ . For k = 1 k=1 k = 1 , P t j ( 1 ) = 1 / t P_{tj}^{(1)}=1/t P t j ( 1 ) = 1/ t and M t j ( 1 ) = h t j ≍ ℓ t j M_{tj}^{(1)}=h_{tj}\asymp\ell_{tj} M t j ( 1 ) = h t j ≍ ℓ t j by (R0), so v ( 2 ) = ( M ( 1 ) ) − ρ ≍ ℓ − ρ v^{(2)}=(M^{(1)})^{-\rho}\asymp\ell^{-\rho} v ( 2 ) = ( M ( 1 ) ) − ρ ≍ ℓ − ρ . From v ( k ) ≍ ℓ − ρ v^{(k)}\asymp\ell^{-\rho} v ( k ) ≍ ℓ − ρ , (R1) gives P ( k ) ≍ ℓ − ρ / t P^{(k)}\asymp\ell^{-\rho}/t P ( k ) ≍ ℓ − ρ / t and (R2) gives M ( k ) ≍ ℓ 1 − ρ M^{(k)}\asymp\ell^{1-\rho} M ( k ) ≍ ℓ 1 − ρ ; then v ( k + 1 ) = ( v ( k ) / M ( k ) ) ρ ≍ ( ℓ − ρ ℓ − ( 1 − ρ ) ) ρ = ℓ − ρ v^{(k+1)}=(v^{(k)}/M^{(k)})^\rho\asymp(\ell^{-\rho}\ell^{-(1-\rho)})^\rho=\ell^{-\rho} v ( k + 1 ) = ( v ( k ) / M ( k ) ) ρ ≍ ( ℓ − ρ ℓ − ( 1 − ρ ) ) ρ = ℓ − ρ .
Step 2: limits. We show by induction on k ≥ 2 k\ge2 k ≥ 2 that for a constant V k > 0 V_k>0 V k > 0
v t , ⌊ s t ⌋ ( k ) → V k ℓ ( s ) − ρ uniformly , (12) v^{(k)}_{t,\lfloor st\rfloor}\to V_k\ell(s)^{-\rho}\quad\text{uniformly}, \tag*{(12)} v t , ⌊ s t ⌋ ( k ) → V k ℓ ( s ) − ρ uniformly , (12)
and, in the induction step, that t P t , ⌊ s t ⌋ ( k ) → f ( s ) tP^{(k)}_{t,\lfloor st\rfloor}\to f(s) t P t , ⌊ s t ⌋ ( k ) → f ( s ) uniformly, which is the theorem. Step 1 provides a constant C C C with v t j ( k ) ≤ C ℓ t j − ρ v^{(k)}_{tj}\le C\ell_{tj}^{-\rho} v t j ( k ) ≤ C ℓ t j − ρ and t P t j ( k ) ≤ C ℓ t j − ρ tP^{(k)}_{tj}\le C\ell_{tj}^{-\rho} t P t j ( k ) ≤ C ℓ t j − ρ for all j ≤ t j\le t j ≤ t ; these bounds control the ends of a row, where the induction hypothesis says nothing.
Base case k = 2 k=2 k = 2 . v ( 1 ) = 1 v^{(1)}=1 v ( 1 ) = 1 , so P t j ( 1 ) = 1 / t P_{tj}^{(1)}=1/t P t j ( 1 ) = 1/ t and M t j ( 1 ) = h t j M_{tj}^{(1)}=h_{tj} M t j ( 1 ) = h t j . By (H), log t + 1 j ≤ h t j ≤ 1 j + log t j \log\frac{t+1}{j}\le h_{tj}\le\frac1j+\log\frac tj log j t + 1 ≤ h t j ≤ j 1 + log j t , and j ≥ δ t − 1 j\ge\delta t-1 j ≥ δ t − 1 , so M t , ⌊ s t ⌋ ( 1 ) → ℓ ( s ) M_{t,\lfloor st\rfloor}^{(1)}\to\ell(s) M t , ⌊ s t ⌋ ( 1 ) → ℓ ( s ) uniformly. Since ℓ \ell ℓ is bounded below by a positive constant and x ↦ x − ρ x\mapsto x^{-\rho} x ↦ x − ρ is uniformly continuous away from zero, v ( 2 ) = ( v ( 1 ) / M ( 1 ) ) ρ = ( M ( 1 ) ) − ρ v^{(2)}=(v^{(1)}/M^{(1)})^\rho=(M^{(1)})^{-\rho} v ( 2 ) = ( v ( 1 ) / M ( 1 ) ) ρ = ( M ( 1 ) ) − ρ satisfies ( I 2 ) (I_2) ( I 2 ) with V 2 = 1 V_2=1 V 2 = 1 .
Induction step. Assume ( I k ) (I_k) ( I k ) .
(a) Row normalizer and shape. By Step 1, ( I k ) (I_k) ( I k ) and Lemma 23 , Σ t = t − 1 ∑ j ≤ t v t j ( k ) → V k Γ ( 1 − ρ ) > 0 \Sigma_t=t^{-1}\sum_{j\le t}v_{tj}^{(k)}\to V_k\Gamma(1-\rho)>0 Σ t = t − 1 ∑ j ≤ t v t j ( k ) → V k Γ ( 1 − ρ ) > 0 . Since P t j ( k ) = v t j ( k ) / ( t Σ t ) P_{tj}^{(k)}=v_{tj}^{(k)}/(t\Sigma_t) P t j ( k ) = v t j ( k ) / ( t Σ t ) ,
t P t , ⌊ s t ⌋ ( k ) = v t , ⌊ s t ⌋ ( k ) Σ t → V k ℓ ( s ) − ρ V k Γ ( 1 − ρ ) = f ( s ) uniformly . tP_{t,\lfloor st\rfloor}^{(k)}
=\frac{v_{t,\lfloor st\rfloor}^{(k)}}{\Sigma_t}
\to\frac{V_k\ell(s)^{-\rho}}{V_k\Gamma(1-\rho)}
=f(s)
\quad\text{uniformly}. t P t , ⌊ s t ⌋ ( k ) = Σ t v t , ⌊ s t ⌋ ( k ) → V k Γ ( 1 − ρ ) V k ℓ ( s ) − ρ = f ( s ) uniformly .
(b) Column mass. By Step 1, (a) and Lemma 24 , M t , ⌊ s t ⌋ ( k ) → G ( s ) = ℓ ( s ) 1 − ρ / ( ( 1 − ρ ) Γ ( 1 − ρ ) ) M^{(k)}_{t,\lfloor st\rfloor}\to G(s)=\ell(s)^{1-\rho}/((1-\rho)\Gamma(1-\rho)) M t , ⌊ s t ⌋ ( k ) → G ( s ) = ℓ ( s ) 1 − ρ / (( 1 − ρ ) Γ ( 1 − ρ )) uniformly.
(c) Next iterate. On [ δ , 1 − δ ] [\delta,1-\delta] [ δ , 1 − δ ] , G ≥ G ( 1 − δ ) > 0 G\ge G(1-\delta)>0 G ≥ G ( 1 − δ ) > 0 , so the quotient v ( k ) / M ( k ) v^{(k)}/M^{(k)} v ( k ) / M ( k ) converges uniformly to V k ℓ − ρ / G V_k\ell^{-\rho}/G V k ℓ − ρ / G , and x ↦ x ρ x\mapsto x^\rho x ↦ x ρ is uniformly continuous on compact subsets of ( 0 , ∞ ) (0,\infty) ( 0 , ∞ ) . Hence
v t , ⌊ s t ⌋ ( k + 1 ) = ( v ( k ) M ( k ) ) t , ⌊ s t ⌋ ρ ⟶ ( V k ( 1 − ρ ) Γ ( 1 − ρ ) ) ρ ℓ ( s ) − ρ ⋅ ρ − ρ ( 1 − ρ ) = V k + 1 ℓ ( s ) − ρ , v^{(k+1)}_{t,\lfloor st\rfloor}=\left(\frac{v^{(k)}}{M^{(k)}}\right)^\rho_{t,\lfloor st\rfloor}\longrightarrow\left(V_k(1-\rho)\Gamma(1-\rho)\right)^\rho\ell(s)^{-\rho\cdot\rho-\rho(1-\rho)}=V_{k+1}\ell(s)^{-\rho}, v t , ⌊ s t ⌋ ( k + 1 ) = ( M ( k ) v ( k ) ) t , ⌊ s t ⌋ ρ ⟶ ( V k ( 1 − ρ ) Γ ( 1 − ρ ) ) ρ ℓ ( s ) − ρ ⋅ ρ − ρ ( 1 − ρ ) = V k + 1 ℓ ( s ) − ρ ,
with V k + 1 = ( V k ( 1 − ρ ) Γ ( 1 − ρ ) ) ρ > 0 V_{k+1}=(V_k(1-\rho)\Gamma(1-\rho))^\rho>0 V k + 1 = ( V k ( 1 − ρ ) Γ ( 1 − ρ ) ) ρ > 0 , which is ( I k + 1 ) (\mathcal{I}_{k+1}) ( I k + 1 ) .
The exponent identity ρ ⋅ ρ + ρ ( 1 − ρ ) = ρ \rho\cdot\rho+\rho(1-\rho)=\rho ρ ⋅ ρ + ρ ( 1 − ρ ) = ρ keeps the shape fixed from k = 2 k=2 k = 2 on; only V k V_k V k changes, and it cancels in the row normalization of (a). □
Proof of Proposition 10 (i.i.d. content)
Proposition 10 (Factorization of the fixed point under i.i.d. content). Let S t j S_{tj} S t j be i.i.d. with ∣ S / ε ∣ ≤ B |S/\varepsilon|\le B ∣ S / ε ∣ ≤ B and κ = E K \kappa=\mathbb{E}K κ = E K . Then, almost surely, t λ t → a ∗ / κ t\lambda_t\to a^*/\kappa t λ t → a ∗ / κ and, for every δ ∈ ( 0 , 1 2 ) \delta\in(0,\frac12) δ ∈ ( 0 , 2 1 ) ,
sup s ∈ [ δ , 1 − δ ] ∣ t P t , ⌊ s t ⌋ − K t , ⌊ s t ⌋ κ f ( s ) ∣ → 0. \sup_{s\in[\delta,1-\delta]}\left|tP_{t,\lfloor st\rfloor}-\frac{K_{t,\lfloor st\rfloor}}{\kappa}f(s)\right|\to0. s ∈ [ δ , 1 − δ ] sup t P t , ⌊ s t ⌋ − κ K t , ⌊ s t ⌋ f ( s ) → 0.
Let K = e S / ε K=e^{S/\varepsilon} K = e S / ε , with i.i.d. entries in [ e − B , e B ] [e^{-B},e^B] [ e − B , e B ] , and κ = E K \kappa=\mathbb{E}K κ = E K . Write
W t j = ∑ i = j t λ i K i j , λ t ′ = κ λ t , Λ t ′ = κ Λ t . W_{tj}=\sum_{i=j}^{t}\lambda_iK_{ij},\qquad\lambda'_t=\kappa\lambda_t,\qquad\Lambda'_t=\kappa\Lambda_t. W t j = i = j ∑ t λ i K ij , λ t ′ = κ λ t , Λ t ′ = κ Λ t .
so that Lemma 3 reads W t j ≤ M t j 1 + γ ≤ ( 1 + γ ) W t j W_{tj}\le M^{1+\gamma}_{tj}\le(1+\gamma)W_{tj} W t j ≤ M t j 1 + γ ≤ ( 1 + γ ) W t j . Constants C B C_B C B below depend only on B B B and ρ \rho ρ and may change from line to line; F t \mathcal{F}_t F t is the σ \sigma σ -field generated by rows 1 , … , t 1,\ldots,t 1 , … , t of K K K .
Strategy. In the constant-score proof, Λ t − Λ j − 1 \Lambda_t-\Lambda_{j-1} Λ t − Λ j − 1 plays two roles: it is the column sum that controls M t j M_{tj} M t j , and it is built from the row normalizers. With content, the column sum is W t j W_{tj} W t j and the row normalization weights each column by K t j K_{tj} K t j . Both sums average independent entries: W t j = Λ t ′ − Λ j − 1 ′ + o ( 1 ) W_{tj}=\Lambda'_{t}-\Lambda'_{j-1}+o(1) W t j = Λ t ′ − Λ j − 1 ′ + o ( 1 ) (Lemma 27) and ∑ j K t j M t j − γ = κ ∑ j M t j − γ + o ( t ) \sum_jK_{tj}M^{-\gamma}_{tj}=\kappa\sum_jM^{-\gamma}_{tj}+o(t) ∑ j K t j M t j − γ = κ ∑ j M t j − γ + o ( t ) (Lemma 28), almost surely and uniformly over the relevant ranges. The rescaled normalizers λ ′ \lambda' λ ′ then satisfy the constant-score equations up to vanishing errors, which are the hypotheses of the bootstrap Lemma 20. The column law of large numbers needs two tools: a deterministic bound on how much one entry moves a row’s normalizer (Lemma 25), and a maximal concentration inequality for martingales (Lemma 26).
Deterministic bounds. Every K K K with entries in [ e − B , e B ] [e^{-B},e^B] [ e − B , e B ] satisfies Lemmas 2 –4 , with λ t ≤ e B / t \lambda_t\le e^B/t λ t ≤ e B / t , and the bounded-score Lemmas 17 and 18:
(D1) t λ t ≥ a B t\lambda_t\ge a_B t λ t ≥ a B (Lemma 17).
(D2) r i ≤ c B / ( i − j + 1 ) r_i\le c_B/(i-j+1) r i ≤ c B / ( i − j + 1 ) , and for every ϑ ∈ ( 0 , 1 2 ) \vartheta\in(0,\frac12) ϑ ∈ ( 0 , 2 1 ) , η ˉ t = max ϑ t ≤ j ≤ ( 1 − ϑ ) t η t j → 0 \bar\eta_t=\max_{\vartheta t\le j\le(1-\vartheta)t}\eta_{tj}\to0 η ˉ t = max ϑt ≤ j ≤ ( 1 − ϑ ) t η t j → 0 (Lemma 18(1)).
(D3) For j ≤ ( 1 − ϑ ) t j\le(1-\vartheta)t j ≤ ( 1 − ϑ ) t , W t j ≥ e − B a B log t + 1 j ≥ e − B a B ϑ W_{tj}\ge e^{-B}a_B\log\frac{t+1}{j}\ge e^{-B}a_B\vartheta W t j ≥ e − B a B log j t + 1 ≥ e − B a B ϑ ; for every j ≥ ϑ t j\ge\vartheta t j ≥ ϑt , W t j ≤ e 2 B ( 1 + log 1 ϑ ) W_{tj}\le e^{2B}(1+\log\frac1\vartheta) W t j ≤ e 2 B ( 1 + log ϑ 1 ) , hence M t j ≤ C B ( 1 + log 1 ϑ ) M_{tj}\le C_B(1+\log\frac1\vartheta) M t j ≤ C B ( 1 + log ϑ 1 ) .
(D4) The near and far parts of a row are small: by Lemma 3 , K t j M t j − γ ≤ e B W t j − ρ ≤ C B ℓ t j − ρ K_{tj}M_{tj}^{-\gamma}\le e^BW_{tj}^{-\rho}\le C_B\ell_{tj}^{-\rho} K t j M t j − γ ≤ e B W t j − ρ ≤ C B ℓ t j − ρ , since W t j ≥ e − B a B log t + 1 j W_{tj}\ge e^{-B}a_B\log\frac{t+1}{j} W t j ≥ e − B a B log j t + 1 by (D1) and (H); so by Lemma 19, for t ≥ 1 / ϑ t\ge1/\vartheta t ≥ 1/ ϑ the parts with j < ϑ t j<\vartheta t j < ϑt and j > ( 1 − ϑ ) t j>(1-\vartheta)t j > ( 1 − ϑ ) t sum to at most C B t χ ( ϑ ) C_Bt\chi(\vartheta) C B t χ ( ϑ ) .
Two tools. Write Φ ( C , k ) \Phi(C,k) Φ ( C , k ) for the normalizer of a row with masses C = ( C j ′ ) j ′ ≤ i C=(C_{j'})_{j'\le i} C = ( C j ′ ) j ′ ≤ i and entries k = ( k j ′ ) j ′ ≤ i k=(k_{j'})_{j'\le i} k = ( k j ′ ) j ′ ≤ i , that is, the unique λ \lambda λ with F ( λ ; C , k ) = 1 F(\lambda;C,k)=1 F ( λ ; C , k ) = 1 , where F ( λ ; C , k ) = ∑ j ′ x j ′ F(\lambda;C,k)=\sum_{j'}x_{j'} F ( λ ; C , k ) = ∑ j ′ x j ′ and x j ′ ( C j ′ + x j ′ ) γ = λ k j ′ x_{j'}(C_{j'}+x_{j'})^\gamma=\lambda k_{j'} x j ′ ( C j ′ + x j ′ ) γ = λ k j ′ (Lemma 2 ).
Lemma 25. Let C ∈ [ 0 , ∞ ) i C\in[0,\infty)^i C ∈ [ 0 , ∞ ) i , and let k , k ′ ∈ [ e − B , e B ] i k,k'\in[e^{-B},e^B]^i k , k ′ ∈ [ e − B , e B ] i differ only in the coordinate j j j . If x = ( x j ′ ) x=(x_{j'}) x = ( x j ′ ) solves the row for ( C , k ) (C,k) ( C , k ) at λ = Φ ( C , k ) \lambda=\Phi(C,k) λ = Φ ( C , k ) , then
∣ log Φ ( C , k ′ ) − log Φ ( C , k ) ∣ ≤ ( 1 + γ ) e 2 B x j . \left|\log\Phi(C,k')-\log\Phi(C,k)\right|\le(1+\gamma)e^{2B}x_j. ∣ log Φ ( C , k ′ ) − log Φ ( C , k ) ∣ ≤ ( 1 + γ ) e 2 B x j .
Proof. The elasticity d log x / d log λ \mathrm{d}\log x/\mathrm{d}\log\lambda d log x / d log λ , the relative change of x x x per relative change of λ \lambda λ , follows by differentiating log x + γ log ( C + x ) = log λ + log k \log x+\gamma\log(C+x)=\log\lambda+\log k log x + γ log ( C + x ) = log λ + log k :
d log x d log λ = d log x d log k = C + x C + ( 1 + γ ) x ∈ [ 1 1 + γ , 1 ] . \frac{\mathrm{d}\log x}{\mathrm{d}\log\lambda}
=
\frac{\mathrm{d}\log x}{\mathrm{d}\log k}
=
\frac{C+x}{C+(1+\gamma)x}
\in\left[\frac{1}{1+\gamma},1\right]. d log λ d log x = d log k d log x = C + ( 1 + γ ) x C + x ∈ [ 1 + γ 1 , 1 ] .
the same in k k k because λ \lambda λ and k k k enter only through λ k \lambda k λk . It is used twice. First, at λ = Φ ( C , k ) \lambda=\Phi(C,k) λ = Φ ( C , k ) , replacing k j k_j k j by k j ′ k'_j k j ′ leaves every x j ′ x_{j'} x j ′ with j ′ ≠ j j'\ne j j ′ = j unchanged and multiplies x j x_j x j by a factor m m m with ∣ log m ∣ ≤ ∣ log ( k j ′ / k j ) ∣ ≤ 2 B |\log m|\le|\log(k'_j/k_j)|\le2B ∣ log m ∣ ≤ ∣ log ( k j ′ / k j ) ∣ ≤ 2 B , since the elasticity lies in ( 0 , 1 ] (0,1] ( 0 , 1 ] ; so the row sum becomes
F = 1 + ( m − 1 ) x j ∈ [ 1 − ( 1 − e − 2 B ) x j , 1 + ( e 2 B − 1 ) x j ] , F=1+(m-1)x_j\in\left[1-(1-e^{-2B})x_j,\ 1+(e^{2B}-1)x_j\right], F = 1 + ( m − 1 ) x j ∈ [ 1 − ( 1 − e − 2 B ) x j , 1 + ( e 2 B − 1 ) x j ] ,
and ∣ log F ∣ ≤ e 2 B x j |\log F|\le e^{2B}x_j ∣ log F ∣ ≤ e 2 B x j : above one by log ( 1 + u ) ≤ u \log(1+u)\le u log ( 1 + u ) ≤ u , below one by − log ( 1 − u ) ≤ u / ( 1 − u ) -\log(1-u)\le u/(1-u) − log ( 1 − u ) ≤ u / ( 1 − u ) with u = ( 1 − e − 2 B ) x j u=(1-e^{-2B})x_j u = ( 1 − e − 2 B ) x j and 1 − u ≥ e − 2 B 1-u\ge e^{-2B} 1 − u ≥ e − 2 B . Second, the elasticity of the row sum, d log F / d log λ = ∑ j ′ ( x j ′ / F ) d log x j ′ / d log λ \mathrm{d}\log F/\mathrm{d}\log\lambda=\sum_{j'}(x_{j'}/F)\,\mathrm{d}\log x_{j'}/\mathrm{d}\log\lambda d log F / d log λ = ∑ j ′ ( x j ′ / F ) d log x j ′ / d log λ , is a weighted mean of elasticities and so at least 1 / ( 1 + γ ) 1/(1+\gamma) 1/ ( 1 + γ ) ; restoring the row sum to one therefore moves log λ \log\lambda log λ by at most ( 1 + γ ) ∣ log F ∣ (1+\gamma)|\log F| ( 1 + γ ) ∣ log F ∣ .
:::
Lemma 26. Let S t = ∑ i = t 0 t X i S_t=\sum_{i=t_0}^{t}X_i S t = ∑ i = t 0 t X i , t ≥ t 0 t\ge t_0 t ≥ t 0 , be a martingale with respect to a filtration ( F t ) (\mathcal{F}_t) ( F t ) , with ∣ X i ∣ ≤ c i |X_i|\le c_i ∣ X i ∣ ≤ c i and V = ∑ i ≥ t 0 c i 2 < ∞ V=\sum_{i\ge t_0}c_i^2<\infty V = ∑ i ≥ t 0 c i 2 < ∞ . Then for u > 0 u>0 u > 0 , Pr ( sup t ≥ t 0 ∣ S t ∣ ≥ u ) ≤ 2 exp ( − u 2 / ( 2 V ) ) \Pr(\sup_{t\ge t_0}|S_t|\ge u)\le2\exp(-u^2/(2V)) Pr ( sup t ≥ t 0 ∣ S t ∣ ≥ u ) ≤ 2 exp ( − u 2 / ( 2 V )) .
This is the maximal form of the Azuma–Hoeffding inequality [2 , 16 ] : Hoeffding’s lemma gives E e θ S t ≤ e θ 2 V / 2 \mathbb{E}e^{\theta S_t}\le e^{\theta^2V/2} E e θ S t ≤ e θ 2 V /2 , and Doob’s maximal inequality for the submartingale e θ S t e^{\theta S_t} e θ S t with θ = u / V \theta=u/V θ = u / V , applied to S S S and − S -S − S , gives the bound.
Lemma 27. Almost surely,
max ϑ t ≤ j ≤ t ∣ W t j − ( Λ t ′ − Λ j − 1 ′ ) ∣ ⟶ 0 for every ϑ ∈ ( 0 , 1 ) . (13) \max_{\vartheta t\le j\le t}\left|W_{tj}-(\Lambda'_t-\Lambda'_{j-1})\right|\longrightarrow0\qquad\text{for every }\vartheta\in(0,1). \tag*{(13)} ϑt ≤ j ≤ t max W t j − ( Λ t ′ − Λ j − 1 ′ ) ⟶ 0 for every ϑ ∈ ( 0 , 1 ) . (13)
Proof. The difference is ∑ i = j t λ i ( K i j − κ ) \sum_{i=j}^{t}\lambda_i(K_{ij}-\kappa) ∑ i = j t λ i ( K ij − κ ) . Its weights depend on the summands: λ i \lambda_i λ i is computed from row i i i , which contains K i j K_{ij} K ij . We remove this dependence by leaving one entry out. For i ≥ j i\ge j i ≥ j let
λ i ( − j ) = Φ ( M i − 1 , ⋅ , ( K i 1 , … , K i , j − 1 , κ , K i , j + 1 , … , K i i ) ) , \lambda_i^{(-j)}=\Phi\left(M_{i-1,\mathord\cdot},(K_{i1},\ldots,K_{i,j-1},\kappa,K_{i,j+1},\ldots,K_{ii})\right), λ i ( − j ) = Φ ( M i − 1 , ⋅ , ( K i 1 , … , K i , j − 1 , κ , K i , j + 1 , … , K ii ) ) ,
the normalizer of row i i i with the actual masses and entries except that K i j K_{ij} K ij is replaced by κ \kappa κ . Let G i = σ ( F i − 1 , K i j ′ : j ′ ≠ j ) \mathcal{G}_i=\sigma(\mathcal{F}_{i-1},K_{ij'}:j'\ne j) G i = σ ( F i − 1 , K i j ′ : j ′ = j ) , so that F i − 1 ⊂ G i ⊂ F i \mathcal{F}_{i-1}\subset\mathcal{G}_i\subset\mathcal{F}_i F i − 1 ⊂ G i ⊂ F i and, the entries being independent, K i j K_{ij} K ij is independent of G i \mathcal{G}_i G i . Then λ i ( − j ) \lambda_i^{(-j)} λ i ( − j ) is G i \mathcal{G}_i G i -measurable: by the row recursion, M i − 1 , ⋅ M_{i-1,\mathord\cdot} M i − 1 , ⋅ is a measurable function of rows 1 , … , i − 1 1,\ldots,i-1 1 , … , i − 1 of K K K ; and Φ \Phi Φ is Borel, because F F F is continuous and increasing in λ \lambda λ (proof of Lemma 2 ), so { Φ ≤ c } = { F ( c ; ⋅ ) ≥ 1 } \{\Phi\le c\}=\{F(c;\mathord\cdot)\ge1\} { Φ ≤ c } = { F ( c ; ⋅ ) ≥ 1 } is closed. The modified row still has unit mass on columns 1 , … , i 1,\ldots,i 1 , … , i , so the proof of Lemma 4 gives λ i ( − j ) ≤ e B / i \lambda_i^{(-j)}\le e^B/i λ i ( − j ) ≤ e B / i . Define
S t ( j ) = ∑ i = j t X i , X i = λ i ( − j ) ( K i j − κ ) , R t ( j ) = ∑ i = j t ( λ i − λ i ( − j ) ) ( K i j − κ ) . S_t^{(j)}=\sum_{i=j}^{t}X_i,\qquad X_i=\lambda_i^{(-j)}(K_{ij}-\kappa),\qquad R_t^{(j)}=\sum_{i=j}^{t}(\lambda_i-\lambda_i^{(-j)})(K_{ij}-\kappa). S t ( j ) = i = j ∑ t X i , X i = λ i ( − j ) ( K ij − κ ) , R t ( j ) = i = j ∑ t ( λ i − λ i ( − j ) ) ( K ij − κ ) .
@page 29/42 starts_mid=0 ends_mid=1 Two tools. Write Φ ( C , k ) \Phi(C,k) Φ ( C , k ) for the normalizer of a row with masses C = ( C j ′ ) j ′ ≤ i C=(C_{j'})_{j'\le i} C = ( C j ′ ) j ′ ≤ i and entries k = ( k j ′ ) j ′ ≤ i k=(k_{j'})_{j'\le i} k = ( k j ′ ) j ′ ≤ i , that is, the unique λ \lambda λ with F ( λ ; C , k ) = 1 F(\lambda;C,k)=1 F ( λ ; C , k ) = 1 , where F ( λ ; C , k ) = ∑ j ′ x j ′ F(\lambda;C,k)=\sum_{j'}x_{j'} F ( λ ; C , k ) = ∑ j ′ x j ′ and x j ′ ( C j ′ + x j ′ ) γ = λ k j ′ x_{j'}(C_{j'}+x_{j'})^\gamma=\lambda k_{j'} x j ′ ( C j ′ + x j ′ ) γ = λ k j ′ (Lemma 2 ).
Lemma 25. Let C ∈ [ 0 , ∞ ) i C\in[0,\infty)^i C ∈ [ 0 , ∞ ) i , and let k , k ′ ∈ [ e − B , e B ] i k,k'\in[e^{-B},e^B]^i k , k ′ ∈ [ e − B , e B ] i differ only in the coordinate j j j . If x = ( x j ′ ) x=(x_{j'}) x = ( x j ′ ) solves the row for ( C , k ) (C,k) ( C , k ) at λ = Φ ( C , k ) \lambda=\Phi(C,k) λ = Φ ( C , k ) , then
∣ log Φ ( C , k ′ ) − log Φ ( C , k ) ∣ ≤ ( 1 + γ ) e 2 B x j . \left|\log\Phi(C,k')-\log\Phi(C,k)\right|\le(1+\gamma)e^{2B}x_j. ∣ log Φ ( C , k ′ ) − log Φ ( C , k ) ∣ ≤ ( 1 + γ ) e 2 B x j .
Proof. The elasticity d log x / d log λ \mathrm{d}\log x/\mathrm{d}\log\lambda d log x / d log λ , the relative change of x x x per relative change of λ \lambda λ , follows by differentiating log x + γ log ( C + x ) = log λ + log k \log x+\gamma\log(C+x)=\log\lambda+\log k log x + γ log ( C + x ) = log λ + log k :
d log x d log λ = d log x d log k = C + x C + ( 1 + γ ) x ∈ [ 1 1 + γ , 1 ] . \frac{\mathrm{d}\log x}{\mathrm{d}\log\lambda}
=
\frac{\mathrm{d}\log x}{\mathrm{d}\log k}
=
\frac{C+x}{C+(1+\gamma)x}
\in\left[\frac{1}{1+\gamma},1\right]. d log λ d log x = d log k d log x = C + ( 1 + γ ) x C + x ∈ [ 1 + γ 1 , 1 ] .
the same in k k k because λ \lambda λ and k k k enter only through λ k \lambda k λk . It is used twice. First, at λ = Φ ( C , k ) \lambda=\Phi(C,k) λ = Φ ( C , k ) , replacing k j k_j k j by k j ′ k'_j k j ′ leaves every x j ′ x_{j'} x j ′ with j ′ ≠ j j'\ne j j ′ = j unchanged and multiplies x j x_j x j by a factor m m m with ∣ log m ∣ ≤ ∣ log ( k j ′ / k j ) ∣ ≤ 2 B |\log m|\le|\log(k'_j/k_j)|\le2B ∣ log m ∣ ≤ ∣ log ( k j ′ / k j ) ∣ ≤ 2 B , since the elasticity lies in ( 0 , 1 ] (0,1] ( 0 , 1 ] ; so the row sum becomes
F = 1 + ( m − 1 ) x j ∈ [ 1 − ( 1 − e − 2 B ) x j , 1 + ( e 2 B − 1 ) x j ] , F=1+(m-1)x_j\in\left[1-(1-e^{-2B})x_j,\ 1+(e^{2B}-1)x_j\right], F = 1 + ( m − 1 ) x j ∈ [ 1 − ( 1 − e − 2 B ) x j , 1 + ( e 2 B − 1 ) x j ] ,
and ∣ log F ∣ ≤ e 2 B x j |\log F|\le e^{2B}x_j ∣ log F ∣ ≤ e 2 B x j : above one by log ( 1 + u ) ≤ u \log(1+u)\le u log ( 1 + u ) ≤ u , below one by − log ( 1 − u ) ≤ u / ( 1 − u ) -\log(1-u)\le u/(1-u) − log ( 1 − u ) ≤ u / ( 1 − u ) with u = ( 1 − e − 2 B ) x j u=(1-e^{-2B})x_j u = ( 1 − e − 2 B ) x j and 1 − u ≥ e − 2 B 1-u\ge e^{-2B} 1 − u ≥ e − 2 B . Second, the elasticity of the row sum, d log F / d log λ = ∑ j ′ ( x j ′ / F ) d log x j ′ / d log λ \mathrm{d}\log F/\mathrm{d}\log\lambda=\sum_{j'}(x_{j'}/F)\,\mathrm{d}\log x_{j'}/\mathrm{d}\log\lambda d log F / d log λ = ∑ j ′ ( x j ′ / F ) d log x j ′ / d log λ , is a weighted mean of elasticities and so at least 1 / ( 1 + γ ) 1/(1+\gamma) 1/ ( 1 + γ ) ; restoring the row sum to one therefore moves log λ \log\lambda log λ by at most ( 1 + γ ) ∣ log F ∣ (1+\gamma)|\log F| ( 1 + γ ) ∣ log F ∣ .
:::
Lemma 26. Let S t = ∑ i = t 0 t X i S_t=\sum_{i=t_0}^{t}X_i S t = ∑ i = t 0 t X i , t ≥ t 0 t\ge t_0 t ≥ t 0 , be a martingale with respect to a filtration ( F t ) (\mathcal{F}_t) ( F t ) , with ∣ X i ∣ ≤ c i |X_i|\le c_i ∣ X i ∣ ≤ c i and V = ∑ i ≥ t 0 c i 2 < ∞ V=\sum_{i\ge t_0}c_i^2<\infty V = ∑ i ≥ t 0 c i 2 < ∞ . Then for u > 0 u>0 u > 0 , Pr ( sup t ≥ t 0 ∣ S t ∣ ≥ u ) ≤ 2 exp ( − u 2 / ( 2 V ) ) \Pr(\sup_{t\ge t_0}|S_t|\ge u)\le2\exp(-u^2/(2V)) Pr ( sup t ≥ t 0 ∣ S t ∣ ≥ u ) ≤ 2 exp ( − u 2 / ( 2 V )) .
This is the maximal form of the Azuma–Hoeffding inequality [2 , 16 ] : Hoeffding’s lemma gives E e θ S t ≤ e θ 2 V / 2 \mathbb{E}e^{\theta S_t}\le e^{\theta^2V/2} E e θ S t ≤ e θ 2 V /2 , and Doob’s maximal inequality for the submartingale e θ S t e^{\theta S_t} e θ S t with θ = u / V \theta=u/V θ = u / V , applied to S S S and − S -S − S , gives the bound.
Lemma 27. Almost surely,
max ϑ t ≤ j ≤ t ∣ W t j − ( Λ t ′ − Λ j − 1 ′ ) ∣ ⟶ 0 for every ϑ ∈ ( 0 , 1 ) . (14) \max_{\vartheta t\le j\le t}\left|W_{tj}-(\Lambda'_t-\Lambda'_{j-1})\right|\longrightarrow0\qquad\text{for every }\vartheta\in(0,1). \tag*{(14)} ϑt ≤ j ≤ t max W t j − ( Λ t ′ − Λ j − 1 ′ ) ⟶ 0 for every ϑ ∈ ( 0 , 1 ) . (14)
Proof. The difference is ∑ i = j t λ i ( K i j − κ ) \sum_{i=j}^{t}\lambda_i(K_{ij}-\kappa) ∑ i = j t λ i ( K ij − κ ) . Its weights depend on the summands: λ i \lambda_i λ i is computed from row i i i , which contains K i j K_{ij} K ij . We remove this dependence by leaving one entry out. For i ≥ j i\ge j i ≥ j let
λ i ( − j ) = Φ ( M i − 1 , ⋅ , ( K i 1 , … , K i , j − 1 , κ , K i , j + 1 , … , K i i ) ) , \lambda_i^{(-j)}=\Phi\left(M_{i-1,\mathord\cdot},(K_{i1},\ldots,K_{i,j-1},\kappa,K_{i,j+1},\ldots,K_{ii})\right), λ i ( − j ) = Φ ( M i − 1 , ⋅ , ( K i 1 , … , K i , j − 1 , κ , K i , j + 1 , … , K ii ) ) ,
the normalizer of row i i i with the actual masses and entries except that K i j K_{ij} K ij is replaced by κ \kappa κ . Let G i = σ ( F i − 1 , K i j ′ : j ′ ≠ j ) \mathcal{G}_i=\sigma(\mathcal{F}_{i-1},K_{ij'}:j'\ne j) G i = σ ( F i − 1 , K i j ′ : j ′ = j ) , so that F i − 1 ⊂ G i ⊂ F i \mathcal{F}_{i-1}\subset\mathcal{G}_i\subset\mathcal{F}_i F i − 1 ⊂ G i ⊂ F i and, the entries being independent, K i j K_{ij} K ij is independent of G i \mathcal{G}_i G i . Then λ i ( − j ) \lambda_i^{(-j)} λ i ( − j ) is G i \mathcal{G}_i G i -measurable: by the row recursion, M i − 1 , ⋅ M_{i-1,\mathord\cdot} M i − 1 , ⋅ is a measurable function of rows 1 , … , i − 1 1,\ldots,i-1 1 , … , i − 1 of K K K ; and Φ \Phi Φ is Borel, because F F F is continuous and increasing in λ \lambda λ (proof of Lemma 2 ), so { Φ ≤ c } = { F ( c ; ⋅ ) ≥ 1 } \{\Phi\le c\}=\{F(c;\mathord\cdot)\ge1\} { Φ ≤ c } = { F ( c ; ⋅ ) ≥ 1 } is closed. The modified row still has unit mass on columns 1 , … , i 1,\ldots,i 1 , … , i , so the proof of Lemma 4 gives λ i ( − j ) ≤ e B / i \lambda_i^{(-j)}\le e^B/i λ i ( − j ) ≤ e B / i . Define
S t ( j ) = ∑ i = j t X i , X i = λ i ( − j ) ( K i j − κ ) , R t ( j ) = ∑ i = j t ( λ i − λ i ( − j ) ) ( K i j − κ ) . (15) S_t^{(j)}=\sum_{i=j}^{t}X_i,\qquad X_i=\lambda_i^{(-j)}(K_{ij}-\kappa),\qquad R_t^{(j)}=\sum_{i=j}^{t}(\lambda_i-\lambda_i^{(-j)})(K_{ij}-\kappa). \tag*{(15)} S t ( j ) = i = j ∑ t X i , X i = λ i ( − j ) ( K ij − κ ) , R t ( j ) = i = j ∑ t ( λ i − λ i ( − j ) ) ( K ij − κ ) . (15)
@page 29/42 starts_mid=0 ends_mid=1 Two tools. Write Φ ( C , k ) \Phi(C,k) Φ ( C , k ) for the normalizer of a row with masses C = ( C j ′ ) j ′ ≤ i C=(C_{j'})_{j'\le i} C = ( C j ′ ) j ′ ≤ i and entries k = ( k j ′ ) j ′ ≤ i k=(k_{j'})_{j'\le i} k = ( k j ′ ) j ′ ≤ i , that is, the unique λ \lambda λ with F ( λ ; C , k ) = 1 F(\lambda;C,k)=1 F ( λ ; C , k ) = 1 , where F ( λ ; C , k ) = ∑ j ′ x j ′ F(\lambda;C,k)=\sum_{j'}x_{j'} F ( λ ; C , k ) = ∑ j ′ x j ′ and x j ′ ( C j ′ + x j ′ ) γ = λ k j ′ x_{j'}(C_{j'}+x_{j'})^\gamma=\lambda k_{j'} x j ′ ( C j ′ + x j ′ ) γ = λ k j ′ (Lemma 2 ).
Lemma 25. Let C ∈ [ 0 , ∞ ) i C\in[0,\infty)^i C ∈ [ 0 , ∞ ) i , and let k , k ′ ∈ [ e − B , e B ] i k,k'\in[e^{-B},e^B]^i k , k ′ ∈ [ e − B , e B ] i differ only in the coordinate j j j . If x = ( x j ′ ) x=(x_{j'}) x = ( x j ′ ) solves the row for ( C , k ) (C,k) ( C , k ) at λ = Φ ( C , k ) \lambda=\Phi(C,k) λ = Φ ( C , k ) , then
∣ log Φ ( C , k ′ ) − log Φ ( C , k ) ∣ ≤ ( 1 + γ ) e 2 B x j . \left|\log\Phi(C,k')-\log\Phi(C,k)\right|\le(1+\gamma)e^{2B}x_j. ∣ log Φ ( C , k ′ ) − log Φ ( C , k ) ∣ ≤ ( 1 + γ ) e 2 B x j .
Proof. The elasticity d log x / d log λ \mathrm{d}\log x/\mathrm{d}\log\lambda d log x / d log λ , the relative change of x x x per relative change of λ \lambda λ , follows by differentiating log x + γ log ( C + x ) = log λ + log k \log x+\gamma\log(C+x)=\log\lambda+\log k log x + γ log ( C + x ) = log λ + log k :
d log x d log λ = d log x d log k = C + x C + ( 1 + γ ) x ∈ [ 1 1 + γ , 1 ] . \frac{\mathrm{d}\log x}{\mathrm{d}\log\lambda}
=
\frac{\mathrm{d}\log x}{\mathrm{d}\log k}
=
\frac{C+x}{C+(1+\gamma)x}
\in\left[\frac{1}{1+\gamma},1\right]. d log λ d log x = d log k d log x = C + ( 1 + γ ) x C + x ∈ [ 1 + γ 1 , 1 ] .
the same in k k k because λ \lambda λ and k k k enter only through λ k \lambda k λk . It is used twice. First, at λ = Φ ( C , k ) \lambda=\Phi(C,k) λ = Φ ( C , k ) , replacing k j k_j k j by k j ′ k'_j k j ′ leaves every x j ′ x_{j'} x j ′ with j ′ ≠ j j'\ne j j ′ = j unchanged and multiplies x j x_j x j by a factor m m m with ∣ log m ∣ ≤ ∣ log ( k j ′ / k j ) ∣ ≤ 2 B |\log m|\le|\log(k'_j/k_j)|\le2B ∣ log m ∣ ≤ ∣ log ( k j ′ / k j ) ∣ ≤ 2 B , since the elasticity lies in ( 0 , 1 ] (0,1] ( 0 , 1 ] ; so the row sum becomes
F = 1 + ( m − 1 ) x j ∈ [ 1 − ( 1 − e − 2 B ) x j , 1 + ( e 2 B − 1 ) x j ] , F=1+(m-1)x_j\in\left[1-(1-e^{-2B})x_j,\ 1+(e^{2B}-1)x_j\right], F = 1 + ( m − 1 ) x j ∈ [ 1 − ( 1 − e − 2 B ) x j , 1 + ( e 2 B − 1 ) x j ] ,
and ∣ log F ∣ ≤ e 2 B x j |\log F|\le e^{2B}x_j ∣ log F ∣ ≤ e 2 B x j : above one by log ( 1 + u ) ≤ u \log(1+u)\le u log ( 1 + u ) ≤ u , below one by − log ( 1 − u ) ≤ u / ( 1 − u ) -\log(1-u)\le u/(1-u) − log ( 1 − u ) ≤ u / ( 1 − u ) with u = ( 1 − e − 2 B ) x j u=(1-e^{-2B})x_j u = ( 1 − e − 2 B ) x j and 1 − u ≥ e − 2 B 1-u\ge e^{-2B} 1 − u ≥ e − 2 B . Second, the elasticity of the row sum, d log F / d log λ = ∑ j ′ ( x j ′ / F ) d log x j ′ / d log λ \mathrm{d}\log F/\mathrm{d}\log\lambda=\sum_{j'}(x_{j'}/F)\,\mathrm{d}\log x_{j'}/\mathrm{d}\log\lambda d log F / d log λ = ∑ j ′ ( x j ′ / F ) d log x j ′ / d log λ , is a weighted mean of elasticities and so at least 1 / ( 1 + γ ) 1/(1+\gamma) 1/ ( 1 + γ ) ; restoring the row sum to one therefore moves log λ \log\lambda log λ by at most ( 1 + γ ) ∣ log F ∣ (1+\gamma)|\log F| ( 1 + γ ) ∣ log F ∣ .
:::
Lemma 26. Let S t = ∑ i = t 0 t X i S_t=\sum_{i=t_0}^{t}X_i S t = ∑ i = t 0 t X i , t ≥ t 0 t\ge t_0 t ≥ t 0 , be a martingale with respect to a filtration ( F t ) (\mathcal{F}_t) ( F t ) , with ∣ X i ∣ ≤ c i |X_i|\le c_i ∣ X i ∣ ≤ c i and V = ∑ i ≥ t 0 c i 2 < ∞ V=\sum_{i\ge t_0}c_i^2<\infty V = ∑ i ≥ t 0 c i 2 < ∞ . Then for u > 0 u>0 u > 0 , Pr ( sup t ≥ t 0 ∣ S t ∣ ≥ u ) ≤ 2 exp ( − u 2 / ( 2 V ) ) \Pr(\sup_{t\ge t_0}|S_t|\ge u)\le2\exp(-u^2/(2V)) Pr ( sup t ≥ t 0 ∣ S t ∣ ≥ u ) ≤ 2 exp ( − u 2 / ( 2 V )) .
This is the maximal form of the Azuma–Hoeffding inequality [2 , 16 ] : Hoeffding’s lemma gives E e θ S t ≤ e θ 2 V / 2 \mathbb{E}e^{\theta S_t}\le e^{\theta^2V/2} E e θ S t ≤ e θ 2 V /2 , and Doob’s maximal inequality for the submartingale e θ S t e^{\theta S_t} e θ S t with θ = u / V \theta=u/V θ = u / V , applied to S S S and − S -S − S , gives the bound.
Lemma 27. Almost surely,
max ϑ t ≤ j ≤ t ∣ W t j − ( Λ t ′ − Λ j − 1 ′ ) ∣ ⟶ 0 for every ϑ ∈ ( 0 , 1 ) . (16) \max_{\vartheta t\le j\le t}\left|W_{tj}-(\Lambda'_t-\Lambda'_{j-1})\right|\longrightarrow0\qquad\text{for every }\vartheta\in(0,1). \tag*{(16)} ϑt ≤ j ≤ t max W t j − ( Λ t ′ − Λ j − 1 ′ ) ⟶ 0 for every ϑ ∈ ( 0 , 1 ) . (16)
Proof. The difference is ∑ i = j t λ i ( K i j − κ ) \sum_{i=j}^{t}\lambda_i(K_{ij}-\kappa) ∑ i = j t λ i ( K ij − κ ) . Its weights depend on the summands: λ i \lambda_i λ i is computed from row i i i , which contains K i j K_{ij} K ij . We remove this dependence by leaving one entry out. For i ≥ j i\ge j i ≥ j let
λ i ( − j ) = Φ ( M i − 1 , ⋅ , ( K i 1 , … , K i , j − 1 , κ , K i , j + 1 , … , K i i ) ) , \lambda_i^{(-j)}=\Phi\left(M_{i-1,\mathord\cdot},(K_{i1},\ldots,K_{i,j-1},\kappa,K_{i,j+1},\ldots,K_{ii})\right), λ i ( − j ) = Φ ( M i − 1 , ⋅ , ( K i 1 , … , K i , j − 1 , κ , K i , j + 1 , … , K ii ) ) ,
the normalizer of row i i i with the actual masses and entries except that K i j K_{ij} K ij is replaced by κ \kappa κ . Let G i = σ ( F i − 1 , K i j ′ : j ′ ≠ j ) \mathcal{G}_i=\sigma(\mathcal{F}_{i-1},K_{ij'}:j'\ne j) G i = σ ( F i − 1 , K i j ′ : j ′ = j ) , so that F i − 1 ⊂ G i ⊂ F i \mathcal{F}_{i-1}\subset\mathcal{G}_i\subset\mathcal{F}_i F i − 1 ⊂ G i ⊂ F i and, the entries being independent, K i j K_{ij} K ij is independent of G i \mathcal{G}_i G i . Then λ i ( − j ) \lambda_i^{(-j)} λ i ( − j ) is G i \mathcal{G}_i G i -measurable: by the row recursion, M i − 1 , ⋅ M_{i-1,\mathord\cdot} M i − 1 , ⋅ is a measurable function of rows 1 , … , i − 1 1,\ldots,i-1 1 , … , i − 1 of K K K ; and Φ \Phi Φ is Borel, because F F F is continuous and increasing in λ \lambda λ (proof of Lemma 2 ), so { Φ ≤ c } = { F ( c ; ⋅ ) ≥ 1 } \{\Phi\le c\}=\{F(c;\mathord\cdot)\ge1\} { Φ ≤ c } = { F ( c ; ⋅ ) ≥ 1 } is closed. The modified row still has unit mass on columns 1 , … , i 1,\ldots,i 1 , … , i , so the proof of Lemma 4 gives λ i ( − j ) ≤ e B / i \lambda_i^{(-j)}\le e^B/i λ i ( − j ) ≤ e B / i . Define
S t ( j ) = ∑ i = j t X i , X i = λ i ( − j ) ( K i j − κ ) , R t ( j ) = ∑ i = j t ( λ i − λ i ( − j ) ) ( K i j − κ ) . (17) S_t^{(j)}=\sum_{i=j}^{t}X_i,\qquad X_i=\lambda_i^{(-j)}(K_{ij}-\kappa),\qquad R_t^{(j)}=\sum_{i=j}^{t}(\lambda_i-\lambda_i^{(-j)})(K_{ij}-\kappa). \tag*{(17)} S t ( j ) = i = j ∑ t X i , X i = λ i ( − j ) ( K ij − κ ) , R t ( j ) = i = j ∑ t ( λ i − λ i ( − j ) ) ( K ij − κ ) . (17)
so that W t j − ( Λ t ′ − Λ j − 1 ′ ) = S t ( j ) + R t ( j ) W_{tj}-(\Lambda_t^\prime-\Lambda_{j-1}^\prime)=S_t^{(j)}+R_t^{(j)} W t j − ( Λ t ′ − Λ j − 1 ′ ) = S t ( j ) + R t ( j ) : a martingale part, whose weights are decoupled from the summands, and a leave-one-out error.
The martingale part. Since λ i ( − j ) \lambda_i^{(-j)} λ i ( − j ) is G i \mathcal{G}_i G i -measurable and bounded, and K i j K_{ij} K ij is independent of G i \mathcal{G}_i G i with mean κ \kappa κ ,
E [ X i ∣ G i ] = λ i ( − j ) E [ K i j − κ ] = 0 , hence E [ X i ∣ F i − 1 ] = 0 \mathbb{E}[X_i\mid\mathcal{G}_i]=\lambda_i^{(-j)}\mathbb{E}[K_{ij}-\kappa]=0,\qquad\text{hence}\qquad\mathbb{E}[X_i\mid\mathcal{F}_{i-1}]=0 E [ X i ∣ G i ] = λ i ( − j ) E [ K ij − κ ] = 0 , hence E [ X i ∣ F i − 1 ] = 0
by the tower property. Moreover X i X_i X i is F i \mathcal{F}_i F i -measurable, and since κ \kappa κ and K i j K_{ij} K ij lie in [ e − B , e B ] [e^{-B},e^B] [ e − B , e B ] ,
∣ X i ∣ ≤ e B i ( e B − e − B ) ≤ c i = e 2 B i , V j = ∑ i ≥ j c i 2 ≤ e 4 B j − 1 ( j ≥ 2 ) . |X_i|\leq\frac{e^B}{i}(e^B-e^{-B})\leq c_i=\frac{e^{2B}}{i},\qquad V_j=\sum_{i\geq j}c_i^2\leq\frac{e^{4B}}{j-1}\quad(j\geq2). ∣ X i ∣ ≤ i e B ( e B − e − B ) ≤ c i = i e 2 B , V j = i ≥ j ∑ c i 2 ≤ j − 1 e 4 B ( j ≥ 2 ) .
So ( S t ( j ) ) t ≥ j (S_t^{(j)})_{t\geq j} ( S t ( j ) ) t ≥ j is a martingale with respect to ( F t ) (\mathcal{F}_t) ( F t ) , and by Lemma 26,
Pr ( sup t ≥ j ∣ S t ( j ) ∣ ≥ u ) ≤ 2 exp ( − u 2 2 V j ) ≤ 2 exp ( − u 2 ( j − 1 ) 2 e 4 B ) ( u > 0 ) . \Pr\left(\sup_{t\geq j}|S_t^{(j)}|\geq u\right)\leq2\exp\left(-\frac{u^2}{2V_j}\right)\leq2\exp\left(-\frac{u^2(j-1)}{2e^{4B}}\right)\qquad(u>0). Pr ( t ≥ j sup ∣ S t ( j ) ∣ ≥ u ) ≤ 2 exp ( − 2 V j u 2 ) ≤ 2 exp ( − 2 e 4 B u 2 ( j − 1 ) ) ( u > 0 ) .
The right side is summable over j j j . By the Borel–Cantelli lemma, almost surely the event on the left occurs for only finitely many j j j ; applying this to u = 1 / n u=1/n u = 1/ n for every n ≥ 1 n\geq1 n ≥ 1 gives, almost surely,
sup j ≥ J sup t ≥ j ∣ S t ( j ) ∣ → 0 ( J → ∞ ) . \sup_{j\geq J}\sup_{t\geq j}|S_t^{(j)}|\to0\qquad(J\to\infty). j ≥ J sup t ≥ j sup ∣ S t ( j ) ∣ → 0 ( J → ∞ ) .
The leave-one-out error. Row i i i solves the row equation with masses C = M i − 1 , ⋅ C=M_{i-1,\cdot} C = M i − 1 , ⋅ , entries K i ⋅ K_{i\cdot} K i ⋅ and solution x j ′ = P i j ′ x_j^\prime=P_{ij}^\prime x j ′ = P ij ′ , and λ i ( − j ) \lambda_i^{(-j)} λ i ( − j ) changes only the entry j j j , from K i j K_{ij} K ij to κ ∈ [ e − B , e B ] \kappa\in[e^{-B},e^B] κ ∈ [ e − B , e B ] . By Lemma 25,
∣ log λ i ( − j ) − log λ i ∣ ≤ ( 1 + γ ) e 2 B P i j , |\log\lambda_i^{(-j)}-\log\lambda_i|\leq(1+\gamma)e^{2B}P_{ij}, ∣ log λ i ( − j ) − log λ i ∣ ≤ ( 1 + γ ) e 2 B P ij ,
hence ∣ λ i − λ i ( − j ) ∣ ≤ C B λ i P i j |\lambda_i-\lambda_i^{(-j)}|\leq C_B\lambda_iP_{ij} ∣ λ i − λ i ( − j ) ∣ ≤ C B λ i P ij , and with λ i ≤ e B / i ≤ e B / j \lambda_i\leq e^B/i\leq e^B/j λ i ≤ e B / i ≤ e B / j ,
∣ R t ( j ) ∣ ≤ C B ∑ i = j t λ i P i j ≤ C B j ∑ i = j t P i j = C B M t j j ≤ C B ( 1 + log 1 ϑ ) ϑ t |R_t^{(j)}|\leq C_B\sum_{i=j}^{t}\lambda_iP_{ij}\leq\frac{C_B}{j}\sum_{i=j}^{t}P_{ij}=\frac{C_BM_{tj}}{j}\leq\frac{C_B(1+\log\frac{1}{\vartheta})}{\vartheta t} ∣ R t ( j ) ∣ ≤ C B i = j ∑ t λ i P ij ≤ j C B i = j ∑ t P ij = j C B M t j ≤ ϑt C B ( 1 + log ϑ 1 )
for j ≥ ϑ t j\geq\vartheta t j ≥ ϑt , by (D3).
Lemma 28. Almost surely, for every ϑ ∈ ( 0 , 1 2 ) \vartheta\in(0,\frac12) ϑ ∈ ( 0 , 2 1 ) ,
1 t ∑ ϑ t ≤ j ≤ ( 1 − ϑ ) t ( K t j − κ ) M t − 1 , j − γ → 0 ; (18) \frac{1}{t}\sum_{\vartheta t\leq j\leq(1-\vartheta)t}(K_{tj}-\kappa)M_{t-1,j}^{-\gamma}\to0; \tag*{(18)} t 1 ϑt ≤ j ≤ ( 1 − ϑ ) t ∑ ( K t j − κ ) M t − 1 , j − γ → 0 ; (18) and for all K K K and ϑ t ≤ j ≤ ( 1 − ϑ ) t \vartheta t\leq j\leq(1-\vartheta)t ϑt ≤ j ≤ ( 1 − ϑ ) t ,
( 1 − max ( 1 , γ ) c B ϑ t ) M t − 1 , j − γ ≤ M t j − γ ≤ M t − 1 , j − γ . (19) \left(1-\frac{\max(1,\gamma)c_B}{\vartheta t}\right)M_{t-1,j}^{-\gamma}\leq M_{tj}^{-\gamma}\leq M_{t-1,j}^{-\gamma}. \tag*{(19)} ( 1 − ϑt max ( 1 , γ ) c B ) M t − 1 , j − γ ≤ M t j − γ ≤ M t − 1 , j − γ . (19) Proof. The weights are M t − 1 , j − γ M_{t-1,j}^{-\gamma} M t − 1 , j − γ rather than the M t j − γ M_{tj}^{-\gamma} M t j − γ of the row normalization: M t j M_{tj} M t j contains the own term P t j P_{tj} P t j , which depends on K t j K_{tj} K t j , whereas M t − 1 , j M_{t-1,j} M t − 1 , j is F t − 1 \mathcal{F}_{t-1} F t − 1 -measurable and the entries K t j K_{tj} K t j of row t t t are independent of F t − 1 \mathcal{F}_{t-1} F t − 1 . In the middle range the weights are bounded: by Lemma 3 and (D3) applied to row t − 1 t-1 t − 1 , M t − 1 , j − ρ ≤ W t − 1 , j − ρ ≤ ( e B / ( a B ϑ ) ) ρ = c w M_{t-1,j}^{-\rho}\leq W_{t-1,j}^{-\rho}\leq(e^B/(aB\vartheta))^\rho=c_w M t − 1 , j − ρ ≤ W t − 1 , j − ρ ≤ ( e B / ( a B ϑ ) ) ρ = c w ; near the diagonal they are not, and at j = t j=t j = t the mass M t − 1 , t M_{t-1,t} M t − 1 , t is zero. Conditionally on F t − 1 \mathcal{F}_{t-1} F t − 1 the sum is a sum of at most t t t independent centered terms, each in an interval of length 2 e B c w 2e^Bc_w 2 e B c w , so Hoeffding’s inequality [16 ] bounds the probability that it exceeds u t ut u t by 2 exp ( − u 2 t / ( 2 e 2 B c w 2 ) ) 2\exp(-u^2t/(2e^{2B}c_w^2)) 2 exp ( − u 2 t / ( 2 e 2 B c w 2 )) for u > 0 u>0 u > 0 , which is summable in t t t ; Borel–Cantelli over t t t and over rational u , ϑ u,\vartheta u , ϑ gives (11). The own term of row t t t changes the weights only by a factor: M t j = M t − 1 , j / ( 1 − r t ) M_{tj}=M_{t-1,j}/(1-r_t) M t j = M t − 1 , j / ( 1 − r t ) with r t ≤ c B / ( t − j + 1 ) ≤ c B / ( ϑ t ) r_t\leq c_B/(t-j+1)\leq c_B/(\vartheta t) r t ≤ c B / ( t − j + 1 ) ≤ c B / ( ϑt ) by (D2), and ( 1 − r ) γ ≥ 1 − max ( 1 , γ ) r (1-r)^\gamma\geq1-\max(1,\gamma)r ( 1 − r ) γ ≥ 1 − max ( 1 , γ ) r gives (19) .
Proof of Proposition 10. The normalizers. Fix an outcome in the almost-sure events of Lemmas 27 and 28; everything below is deterministic. We apply Lemma 20 to λ t ′ = κ λ t \lambda'_t=\kappa\lambda_t λ t ′ = κ λ t , so that D t j = Λ t ′ − Λ j − 1 ′ D_{tj}=\Lambda'_t-\Lambda'_{j-1} D t j = Λ t ′ − Λ j − 1 ′ and 1 / λ t ′ = κ − 1 ∑ j K t j M t j − γ 1/\lambda'_t=\kappa^{-1}\sum_j K_{tj}M_{tj}^{-\gamma} 1/ λ t ′ = κ − 1 ∑ j K t j M t j − γ . Compared with Theorem 6 there are three errors, each controlled by an earlier step: the content weights K t j K_{tj} K t j in the row sum (11), the own term of row t t t (19) , and the gap between W W W and D D D (10).
By Lemmas 4 and 17, κ a B ≤ t λ t ′ ≤ κ e B \kappa a_B\leq t\lambda'_t\leq\kappa e^B κ a B ≤ t λ t ′ ≤ κ e B . The lemma asks for (i) and (ii) for every ϑ ∈ ( 0 , 1 2 ) \vartheta\in(0,\frac{1}{2}) ϑ ∈ ( 0 , 2 1 ) and every tolerance ν 0 ∈ ( 0 , 1 2 ) \nu_0\in(0,\frac{1}{2}) ν 0 ∈ ( 0 , 2 1 ) , so fix both. For j ∈ J t ( ϑ ) j\in J_t(\vartheta) j ∈ J t ( ϑ ) , Lemma 17 and (H) give D t j ≥ κ a B log t + 1 j ≥ κ a B ϑ = d ϑ D_{tj}\geq\kappa a_B\log\frac{t+1}{j}\geq\kappa a_B\vartheta=d_\vartheta D t j ≥ κ a B log j t + 1 ≥ κ a B ϑ = d ϑ . Each of the three errors above tends to zero, and we make them small relative to a tolerance
ν = ν 0 c ϑ ≤ ν 0 2 , c ϑ = max ( 2 , 1 κ + ( ( 1 + γ ) d ϑ / 2 ) − ρ ) . \nu=\frac{\nu_0}{c_\vartheta}\leq\frac{\nu_0}{2},\qquad c_\vartheta=\max\left(2,\frac{1}{\kappa}+((1+\gamma)d_\vartheta/2)^{-\rho}\right). ν = c ϑ ν 0 ≤ 2 ν 0 , c ϑ = max ( 2 , κ 1 + (( 1 + γ ) d ϑ /2 ) − ρ ) .
chosen so that the errors add up to at most ν 0 \nu_0 ν 0 in (i) and (ii). Since D t j ≥ d ϑ D_{tj}\geq d_\vartheta D t j ≥ d ϑ , an additive error of at most ν d ϑ \nu d_\vartheta ν d ϑ in D t j D_{tj} D t j is a factor in [ 1 − ν , 1 + ν ] [1-\nu,1+\nu] [ 1 − ν , 1 + ν ] , and, as ν < 1 2 \nu<\frac{1}{2} ν < 2 1 ,
∑ j ∈ J t ( ϑ ) ( ( 1 + γ ) ( 1 ± ν ) D t j ) − ρ ≤ t ( ( 1 + γ ) d ϑ / 2 ) − ρ . (20) \sum_{j\in J_t(\vartheta)}((1+\gamma)(1\pm\nu)D_{tj})^{-\rho}\leq t((1+\gamma)d_\vartheta/2)^{-\rho}. \tag*{(20)} j ∈ J t ( ϑ ) ∑ (( 1 + γ ) ( 1 ± ν ) D t j ) − ρ ≤ t (( 1 + γ ) d ϑ /2 ) − ρ . (20)
For large t t t , depending on ϑ \vartheta ϑ , ν \nu ν and the fixed outcome, the following hold for all j ∈ J t ( ϑ ) j\in J_t(\vartheta) j ∈ J t ( ϑ ) : by (10) at rows t t t and t − 1 t-1 t − 1 and D t j − D t − 1 , j = λ t ′ ≤ κ e B / t D_{tj}-D_{t-1,j}=\lambda'_t\leq\kappa e^B/t D t j − D t − 1 , j = λ t ′ ≤ κ e B / t , both W t j W_{tj} W t j and W t − 1 , j W_{t-1,j} W t − 1 , j differ from D t j D_{tj} D t j by at most ν d ϑ \nu d_\vartheta ν d ϑ ; by Lemma 18(1) at row t − 1 t-1 t − 1 with ϑ / 2 \vartheta/2 ϑ /2 (note J t ( ϑ ) ⊂ J t − 1 ( ϑ / 2 ) J_t(\vartheta)\subset J_{t-1}(\vartheta/2) J t ( ϑ ) ⊂ J t − 1 ( ϑ /2 ) ), η ˉ t − 1 ≤ ν \bar{\eta}_{t-1}\leq\nu η ˉ t − 1 ≤ ν ; the factor in (19) is at least 1 − ν 1-\nu 1 − ν ; and the sum in (11) is at most ν t \nu t ν t in absolute value.
Hypothesis (i). Keeping the middle range and using (19) , (11), M t − 1 , j − γ ≥ M t j − γ ≥ ( ( 1 + γ ) W t j ) − ρ M_{t-1,j}^{-\gamma}\geq M_{tj}^{-\gamma}\geq((1+\gamma)W_{tj})^{-\rho} M t − 1 , j − γ ≥ M t j − γ ≥ (( 1 + γ ) W t j ) − ρ (Lemma 3 ) and W t j ≤ ( 1 + ν ) D t j W_{tj}\leq(1+\nu)D_{tj} W t j ≤ ( 1 + ν ) D t j ,
1 λ t ′ ≥ 1 − ν κ ∑ j ∈ J t ( ϑ ) K t j M t − 1 , j − γ ≥ ( 1 − ν ) ∑ j ∈ J t ( ϑ ) ( ( 1 + γ ) ( 1 + ν ) D t j ) − ρ − ν t κ . \frac{1}{\lambda'_t}\geq\frac{1-\nu}{\kappa}\sum_{j\in J_t(\vartheta)}K_{tj}M_{t-1,j}^{-\gamma}\geq(1-\nu)\sum_{j\in J_t(\vartheta)}((1+\gamma)(1+\nu)D_{tj})^{-\rho}-\frac{\nu t}{\kappa}. λ t ′ 1 ≥ κ 1 − ν j ∈ J t ( ϑ ) ∑ K t j M t − 1 , j − γ ≥ ( 1 − ν ) j ∈ J t ( ϑ ) ∑ (( 1 + γ ) ( 1 + ν ) D t j ) − ρ − κ ν t .
By (20) , the factor 1 − ν 1-\nu 1 − ν costs at most ν t ( ( 1 + γ ) d ϑ / 2 ) − ρ \nu t((1+\gamma)d_\vartheta/2)^{-\rho} ν t (( 1 + γ ) d ϑ /2 ) − ρ , so the total additive error is at most
ν t ( 1 κ + ( ( 1 + γ ) d ϑ / 2 ) − ρ ) ≤ ν c ϑ t = ν 0 t ; \nu t\left(\frac{1}{\kappa}+((1+\gamma)d_\vartheta/2)^{-\rho}\right)\leq\nu c_\vartheta t=\nu_0t; ν t ( κ 1 + (( 1 + γ ) d ϑ /2 ) − ρ ) ≤ ν c ϑ t = ν 0 t ;
with 1 + ν ≤ 1 + ν 0 1+\nu\leq1+\nu_0 1 + ν ≤ 1 + ν 0 this is (i) for ν 0 \nu_0 ν 0 .
Hypothesis (ii). The near and far parts of ∑ j K t j M t j − γ \sum_jK_{tj}M_{tj}^{-\gamma} ∑ j K t j M t j − γ are at most C B t χ ( ϑ ) CBt\chi(\vartheta) C B t χ ( ϑ ) by (D4). In the middle range, (19) and (11) give
∑ J t ( ϑ ) K t j M t j − γ ≤ κ ∑ J t ( ϑ ) M t − 1 , j − γ + ν t , \sum_{J_t(\vartheta)}K_{tj}M_{tj}^{-\gamma}\leq\kappa\sum_{J_t(\vartheta)}M_{t-1,j}^{-\gamma}+\nu t, J t ( ϑ ) ∑ K t j M t j − γ ≤ κ J t ( ϑ ) ∑ M t − 1 , j − γ + ν t ,
and Lemma 18(1) at row t − 1 t-1 t − 1 gives
M t − 1 , j 1 + γ ≥ ( 1 + γ ) ( 1 − η ˉ t − 1 ) W t − 1 , j ≥ ( 1 + γ ) ( 1 − ν ) 2 D t j . M_{t-1,j}^{1+\gamma}\geq(1+\gamma)(1-\bar{\eta}_{t-1})W_{t-1,j}\geq(1+\gamma)(1-\nu)^2D_{tj}. M t − 1 , j 1 + γ ≥ ( 1 + γ ) ( 1 − η ˉ t − 1 ) W t − 1 , j ≥ ( 1 + γ ) ( 1 − ν ) 2 D t j .
Dividing by κ \kappa κ , 1 / λ t ′ ≤ ∑ J t ( ϑ ) ( ( 1 + γ ) ( 1 − ν ) 2 D t j ) − ρ + t ( ν / κ + C χ ( ϑ ) ) 1/\lambda'_t\leq\sum_{J_t(\vartheta)}((1+\gamma)(1-\nu)^2D_{tj})^{-\rho}+t(\nu/\kappa+C\chi(\vartheta)) 1/ λ t ′ ≤ ∑ J t ( ϑ ) (( 1 + γ ) ( 1 − ν ) 2 D t j ) − ρ + t ( ν / κ + C χ ( ϑ )) with C = C B / κ C=C_B/\kappa C = C B / κ . Since ( 1 − ν ) 2 ≥ 1 − 2 ν ≥ 1 − ν 0 (1-\nu)^2\geq1-2\nu\geq1-\nu_0 ( 1 − ν ) 2 ≥ 1 − 2 ν ≥ 1 − ν 0 and ν / κ ≤ ν c ϑ = ν 0 \nu/\kappa\leq\nu c_\vartheta=\nu_0 ν / κ ≤ ν c ϑ = ν 0 , this is (ii) for ν 0 \nu_0 ν 0 .
Lemma 20 gives t λ t ′ → a ∗ t\lambda'_t\to a^* t λ t ′ → a ∗ , that is, t λ t → a ∗ / κ t\lambda_t\to a^*/\kappa t λ t → a ∗ / κ .
The shape. Let j = ⌊ s t ⌋ j=\lfloor st\rfloor j = ⌊ s t ⌋ with s ∈ [ δ , 1 − δ ] s\in[\delta,1-\delta] s ∈ [ δ , 1 − δ ] . By (D2), M t j 1 + γ = ( 1 + γ ) W t j ( 1 − η t j ) M_{tj}^{1+\gamma}=(1+\gamma)W_{tj}(1-\eta_{tj}) M t j 1 + γ = ( 1 + γ ) W t j ( 1 − η t j ) with η t j → 0 \eta_{tj}\to0 η t j → 0 uniformly. By (10), W t j = Λ t ′ − Λ j − 1 ′ + o ( 1 ) W_{tj}=\Lambda'_t-\Lambda'_{j-1}+o(1) W t j = Λ t ′ − Λ j − 1 ′ + o ( 1 ) , and as in the proof of Theorem 7 , t λ t ′ → a ∗ t\lambda'_t\to a^* t λ t ′ → a ∗ gives Λ t ′ − Λ j − 1 ′ = a ∗ log ( 1 / s ) + o ( 1 ) \Lambda'_t-\Lambda'_{j-1}=a^*\log(1/s)+o(1) Λ t ′ − Λ j − 1 ′ = a ∗ log ( 1/ s ) + o ( 1 ) , both uniformly in s s s . Since a ∗ log ( 1 / s ) ≥ a ∗ log 1 1 − δ > 0 a^*\log(1/s)\geq a^*\log\frac{1}{1-\delta}>0 a ∗ log ( 1/ s ) ≥ a ∗ log 1 − δ 1 > 0 ,
t P t j = t λ t K t j M t j − γ = a ∗ + o ( 1 ) κ K t j ( ( 1 + γ ) a ∗ log ( 1 / s ) ) − ρ ( 1 + o ( 1 ) ) = K t j κ f ( s ) ( 1 + o ( 1 ) ) tP_{tj}=t\lambda_tK_{tj}M_{tj}^{-\gamma}=\frac{a^*+o(1)}{\kappa}K_{tj}\left((1+\gamma)a^*\log(1/s)\right)^{-\rho}(1+o(1))=\frac{K_{tj}}{\kappa}f(s)(1+o(1)) t P t j = t λ t K t j M t j − γ = κ a ∗ + o ( 1 ) K t j ( ( 1 + γ ) a ∗ log ( 1/ s ) ) − ρ ( 1 + o ( 1 )) = κ K t j f ( s ) ( 1 + o ( 1 ))
uniformly, and K t j ≤ e B K_{tj}\leq e^B K t j ≤ e B turns the factor 1 + o ( 1 ) 1+o(1) 1 + o ( 1 ) into an additive o ( 1 ) o(1) o ( 1 ) .
Proofs for Section 4
Structure. The proofs are short and independent of one another, except that Proposition 14 collects results proved elsewhere. Two arguments recur: (B) Bounded content. If the content part of every score lies in [ − B , B ] [-B,B] [ − B , B ] , each softmax weight changes by a factor in [ e − B , e B ] [e^{-B},e^{B}] [ e − B , e B ] in the numerator and in the normalizer, so every ratio of attention masses changes by a factor in [ e − 2 B , e 2 B ] [e^{-2B},e^{2B}] [ e − 2 B , e 2 B ] . This reduces Proposition 15 and Corollary 16 to constant content.
(Z) The normalizer of a power prior. With constant content and the prior ( 1 + d ) − c (1+d)^{-c} ( 1 + d ) − c , the mass within distance L L L of the diagonal at row t t t is S L / Z t S_L/Z_t S L / Z t with Z t = ∑ d < t ( 1 + d ) − c = ∑ k = 1 t k − c Z_t=\sum_{d<t}(1+d)^{-c}=\sum_{k=1}^{t}k^{-c} Z t = ∑ d < t ( 1 + d ) − c = ∑ k = 1 t k − c , so the question is how Z t Z_t Z t grows.
Row shifts and finite-dimensional kernels
Proposition 11. Adding r t r_t r t to row t t t of the logits, for any r t r_t r t that may depend on row t t t ’s content, leaves both softmax and the fixed point (FP) unchanged.
Proof. Softmax: the numerator and the denominator of row t t t are multiplied by e r t e^{r_t} e r t . Fixed point: in (FP), K t j ↦ e r t K t j K_{tj}\mapsto e^{r_t}K_{tj} K t j ↦ e r t K t j is absorbed by λ t ↦ e − r t λ t \lambda_t\mapsto e^{-r_t}\lambda_t λ t ↦ e − r t λ t , and M M M depends only on P P P ; by Lemma 2 the solution is the same.
Proposition 12. (i) For d ≥ m d\ge m d ≥ m , b ( d ) = ∑ k p k ( d ) μ k d b(d)=\sum_k p_k(d)\mu_k^d b ( d ) = ∑ k p k ( d ) μ k d is an exponential polynomial, with the nonzero eigenvalues μ k \mu_k μ k of A A A and polynomials p k p_k p k . (ii) No real b b b of this form satisfies b ( d ) / log d → − c b(d)/\log d\to-c b ( d ) / log d → − c with c ≠ 0 c\ne0 c = 0 . (iii) If the scores are bounded by B B B , softmax satisfies P t j ≤ e 2 B / t P_{tj}\le e^{2B}/t P t j ≤ e 2 B / t ; with an orthogonal multiplicative encoding and bounded inputs, attention therefore dilutes.
Proof. (i) By the Cayley–Hamilton theorem, b ( d ) = u ⊤ A d w b(d)=u^\top A^d w b ( d ) = u ⊤ A d w satisfies a linear recurrence with constant coefficients, whose solutions are exponential polynomials in the nonzero eigenvalues of A A A for d ≥ m d\ge m d ≥ m [9 ] .
(ii) Let r ∗ r^* r ∗ be the largest ∣ μ k ∣ |\mu_k| ∣ μ k ∣ with p k ≠ 0 p_k\ne0 p k = 0 and m ∗ m^* m ∗ the largest degree among those terms. Then b ( d ) = d m ∗ r ∗ d ( τ ( d ) + o ( 1 ) ) b(d)=d^{m^*}r^{*d}(\tau(d)+o(1)) b ( d ) = d m ∗ r ∗ d ( τ ( d ) + o ( 1 )) , where τ ( d ) = ∑ k c k e i θ k d \tau(d)=\sum_k c_ke^{i\theta_kd} τ ( d ) = ∑ k c k e i θ k d has nonzero coefficients and distinct frequencies, so its mean square tends to ∑ k ∣ c k ∣ 2 > 0 \sum_k|c_k|^2>0 ∑ k ∣ c k ∣ 2 > 0 and ∣ τ ( d ) ∣ ≥ δ > 0 |\tau(d)|\ge\delta>0 ∣ τ ( d ) ∣ ≥ δ > 0 for infinitely many d d d . Hence b → 0 b\to0 b → 0 (r ∗ < 1 r^*<1 r ∗ < 1 ), b b b is bounded (r ∗ = 1 r^*=1 r ∗ = 1 , m ∗ = 0 m^*=0 m ∗ = 0 ), or ∣ b ( d ) ∣ ≥ δ 2 d |b(d)|\ge\frac{\delta}{2}d ∣ b ( d ) ∣ ≥ 2 δ d along a subsequence; none is compatible with b ( d ) / log d → − c ≠ 0 b(d)/\log d\to-c\ne0 b ( d ) / log d → − c = 0 .
(iii) The diagonal term bounds the normalizer below, so P t j = e S t j / ϵ / ∑ j ′ ≤ t e S t j ′ / ϵ ≤ e B / ( t e − B ) P_{tj}=e^{S_{tj}/\epsilon}/\sum_{j'\le t}e^{S_{tj'}/\epsilon}\le e^B/(te^{-B}) P t j = e S t j / ϵ / ∑ j ′ ≤ t e S t j ′ / ϵ ≤ e B / ( t e − B ) . For an orthogonal R R R , ∣ ⟨ R ( t ) q , R ( j ) k ⟩ ∣ ≤ ∣ q ∣ ∣ k ∣ |\langle R(t)q,R(j)k\rangle|\le|q||k| ∣ ⟨ R ( t ) q , R ( j ) k ⟩ ∣ ≤ ∣ q ∣∣ k ∣ by the Cauchy–Schwarz inequality, which is bounded under bounded inputs.
Far mass
Lemma 13. Let log K t j = a t j + b t j \log K_{tj}=a_{tj}+b_{tj} log K t j = a t j + b t j with ∣ a t j ∣ ≤ B |a_{tj}|\le B ∣ a t j ∣ ≤ B , b t t = 0 b_{tt}=0 b tt = 0 and b t j ≤ − m 0 ( t − j ) b_{tj}\le-m_0(t-j) b t j ≤ − m 0 ( t − j ) , m 0 > 0 m_0>0 m 0 > 0 . For every fixed ρ ∈ [ 0 , 1 ) \rho\in[0,1) ρ ∈ [ 0 , 1 ) , the OT fixed point obeys
∑ d > L P t , t − d ≤ e 2 ( 1 − ρ ) B e − ( 1 − ρ ) m 0 ( L + 1 ) 1 − e − ( 1 − ρ ) m 0 \sum_{d>L}P_{t,t-d}\le\frac{e^{2(1-\rho)B}e^{-(1-\rho)m_0(L+1)}}{1-e^{-(1-\rho)m_0}} d > L ∑ P t , t − d ≤ 1 − e − ( 1 − ρ ) m 0 e 2 ( 1 − ρ ) B e − ( 1 − ρ ) m 0 ( L + 1 ) for every t t t ; softmax is the case ρ = 0 \rho=0 ρ = 0 .
Proof. Lemma 2 gives λ t = P t t 1 + γ / K t t ≤ K t t − 1 ≤ e B \lambda_t=P_{tt}^{1+\gamma}/K_{tt}\le K_{tt}^{-1}\le e^B λ t = P tt 1 + γ / K tt ≤ K tt − 1 ≤ e B and P t j 1 + γ ≤ λ t K t j P_{tj}^{1+\gamma}\le\lambda_tK_{tj} P t j 1 + γ ≤ λ t K t j . Since 1 / ( 1 + γ ) = 1 − ρ 1/(1+\gamma)=1-\rho 1/ ( 1 + γ ) = 1 − ρ ,
P t , t − d ≤ ( λ t K t , t − d ) 1 − ρ ≤ e 2 ( 1 − ρ ) B e − ( 1 − ρ ) m 0 d . P_{t,t-d}\le(\lambda_tK_{t,t-d})^{1-\rho}\le e^{2(1-\rho)B}e^{-(1-\rho)m_0d}. P t , t − d ≤ ( λ t K t , t − d ) 1 − ρ ≤ e 2 ( 1 − ρ ) B e − ( 1 − ρ ) m 0 d .
Summing over d ≥ L + 1 d\ge L+1 d ≥ L + 1 gives the bound.
Proposition 14 (Far mass of common encodings). Assume bounded inputs (§ 2 ). For each head:
A L i B i ALiBi A L i B i , F o X FoX F o X , G R A P E GRAPE GR A P E -A A A , G R A P E GRAPE GR A P E -A P AP A P and O T OT O T on A L i B i ALiBi A L i B i (O 2 O2 O 2 ) keep a bounded far mass for all parameter values;
R o P E RoPE R o P E , G R A P E GRAPE GR A P E -M M M and the O T OT O T operator dilute for all parameter values;
a log-distance bias − c log ( 1 + d ) -c\log(1+d) − c log ( 1 + d ) keeps a bounded far mass if c > 1 c>1 c > 1 and dilutes if c ≤ 1 c\le1 c ≤ 1 , and so does K E R P L E KERPLE K E R P L E ’s − p log ( 1 + a d ) -p\log(1+ad) − p log ( 1 + a d ) with a > 0 a>0 a > 0 and p p p in place of c c c ;
with an exponent c ( x t ) c(x_t) c ( x t ) set by the query’s input, on the distance (P 6 P6 P 6 ) or on a content clock (L C LC L C ), the head keeps a bounded far mass if inf x c ( x ) > 1 \inf_x c(x)>1 inf x c ( x ) > 1 and dilutes if sup x c ( x ) ≤ 1 \sup_x c(x)\le1 sup x c ( x ) ≤ 1 , over the admissible inputs x x x ;
C A B L E CABLE C A B L E keeps a bounded far mass if its clock’s pre-activation is bounded below by a positive constant over the admissible inputs, and dilutes if it is never positive.
Proof. Under bounded inputs every linear function of the input lies in a fixed interval [ − A , A ] [-A,A] [ − A , A ] , with A A A depending on the function. Bounded far mass in the first item follows from Lemma 13 once b t j ≤ − m 0 ( t − j ) b_{tj}\le-m_0(t-j) b t j ≤ − m 0 ( t − j ) with m 0 > 0 m_0>0 m 0 > 0 ; each such bound on a path potential follows from a bound on its increments.
A L i B i ALiBi A L i B i , including O T OT O T on A L i B i ALiBi A L i B i , is linear with slope m 0 > 0 m_0>0 m 0 > 0 .
F o X FoX F o X : b t j = ∑ ℓ = j + 1 t log σ ( w ⊤ x ℓ + w 0 ) b_{tj}=\sum_{\ell=j+1}^{t}\log\sigma(w^\top x_\ell+w_0) b t j = ∑ ℓ = j + 1 t log σ ( w ⊤ x ℓ + w 0 ) . Under bounded inputs w ⊤ x ℓ + w 0 ≤ A F w^\top x_\ell+w_0\le A_F w ⊤ x ℓ + w 0 ≤ A F , so each increment is at most log σ ( A F ) = − log ( 1 + e − A F ) < 0 \log\sigma(A_F)=-\log(1+e^{-A_F})<0 log σ ( A F ) = − log ( 1 + e − A F ) < 0 , which is − m 0 -m_0 − m 0 .
G R A P E GRAPE GR A P E -A P AP A P : each increment is m h log σ ( ⟨ p t , R ℓ rms ( p ℓ ) ⟩ / d p ) m_h\log\sigma(\langle p_t,R_\ell\operatorname{rms}(p_\ell)\rangle/d_p) m h log σ (⟨ p t , R ℓ rms ( p ℓ )⟩ / d p ) . Since rms ( p ℓ ) \operatorname{rms}(p_\ell) rms ( p ℓ ) has norm d p \sqrt{d_p} d p and R ℓ R_\ell R ℓ is orthogonal, the argument is at most ∣ p t ∣ / d p ≤ A P |p_t|/\sqrt{d_p}\le A_P ∣ p t ∣/ d p ≤ A P by the Cauchy–Schwarz inequality, and each increment is at most − m h log ( 1 + e − A P ) -m_h\log(1+e^{-A_P}) − m h log ( 1 + e − A P ) .
G R A P E GRAPE GR A P E -A A A : b = − ω h d ( α t + β j ) b=-\omega_hd(\alpha_t+\beta_j) b = − ω h d ( α t + β j ) , where ω h = softplus ( ⋅ ) m h > 0 \omega_h=\operatorname{softplus}(\cdot)\,m_h>0 ω h = softplus ( ⋅ ) m h > 0 and the gates α t , β j \alpha_t,\beta_j α t , β j have the form softplus ( ⟨ rms ( q ) , v ^ ⟩ / D ) \operatorname{softplus}(\langle\operatorname{rms}(q),\hat v\rangle/\sqrt D) softplus (⟨ rms ( q ) , v ^ ⟩ / D ) . The argument lies in [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] because rms ( q ) \operatorname{rms}(q) rms ( q ) has norm D \sqrt D D and v ^ \hat v v ^ is a unit vector, so each gate lies in [ softplus ( − 1 ) , softplus ( 1 ) ] = [ 0.313 , 1.313 ] [\operatorname{softplus}(-1),\operatorname{softplus}(1)]=[0.313,1.313] [ softplus ( − 1 ) , softplus ( 1 )] = [ 0.313 , 1.313 ] and, whatever the inputs, α t + β j ≥ 0.626 \alpha_t+\beta_j\ge0.626 α t + β j ≥ 0.626 , so b ≤ − 0.62 ω h d b\le-0.62\omega_hd b ≤ − 0.62 ω h d .
Dilution : R o P E RoPE R o P E and G R A P E GRAPE GR A P E -M M M by Proposition 12(iii); the O T OT O T operator by Theorem 5 .
Log-distance biases : by Proposition 15, the mass within a fixed window tends to zero for c ≤ 1 c\le1 c ≤ 1 , and for c > 1 c>1 c > 1 the mass beyond L L L is at most e 2 B L 1 − c / ( c − 1 ) e^{2B}L^{1-c}/(c-1) e 2 B L 1 − c / ( c − 1 ) for every t t t . For K E R P L E KERPLE K E R P L E , ( 1 + a d ) / ( 1 + d ) (1+ad)/(1+d) ( 1 + a d ) / ( 1 + d ) lies between min ( a , 1 ) \min(a,1) min ( a , 1 ) and max ( a , 1 ) \max(a,1) max ( a , 1 ) , so the weights differ from those of − p log ( 1 + d ) -p\log(1+d) − p log ( 1 + d ) by bounded factors and the same conclusions hold.
Query-dependent exponents : P 6 P6 P 6 is the case v = 0 v=0 v = 0 , S t − S j = t − j S_t-S_j=t-j S t − S j = t − j , of L C LC L C , b t j = − c ( x t ) log ( 1 + S t − S j ) b_{tj}=-c(x_t)\log(1+S_t-S_j) b t j = − c ( x t ) log ( 1 + S t − S j ) with clock ticks 2 σ ( v ⊤ x ℓ ) ∈ [ κ , 2 ] 2\sigma(v^\top x_\ell)\in[\kappa,2] 2 σ ( v ⊤ x ℓ ) ∈ [ κ , 2 ] , κ = 2 σ ( − A ) > 0 \kappa=2\sigma(-A)>0 κ = 2 σ ( − A ) > 0 , so κ d ≤ S t − S j ≤ 2 d \kappa d\le S_t-S_j\le2d κ d ≤ S t − S j ≤ 2 d and b t t = 0 b_{tt}=0 b tt = 0 . If c ( x ) ≥ 1 + δ c(x)\ge1+\delta c ( x ) ≥ 1 + δ for all admissible x x x , the weight at distance d d d is at most e 2 B ( 1 + κ d ) − 1 − δ e^{2B}(1+\kappa d)^{-1-\delta} e 2 B ( 1 + κ d ) − 1 − δ times the diagonal one, whose tail sum beyond L L L tends to zero uniformly in t t t . If c ( x ) ≤ 1 c(x)\le1 c ( x ) ≤ 1 for all x x x , every weight at distance d d d is between e − 2 B ( 1 + 2 d ) − 1 e^{-2B}(1+2d)^{-1} e − 2 B ( 1 + 2 d ) − 1 and e 2 B e^{2B} e 2 B times the diagonal one, so the mass within L L L is at most e 4 B L / ∑ d < t ( 1 + 2 d ) − 1 → 0 e^{4B}L/\sum_{d<t}(1+2d)^{-1}\to0 e 4 B L / ∑ d < t ( 1 + 2 d ) − 1 → 0 .
CABLE : b t j = g t ( S t − S j ) b_{tj}=g_t(S_t-S_j) b t j = g t ( S t − S j ) with S t − S j = − ∑ ℓ = j + 1 t max ( a ℓ , 0 ) S_t-S_j=-\sum_{\ell=j+1}^{t}\max(a_\ell,0) S t − S j = − ∑ ℓ = j + 1 t max ( a ℓ , 0 ) for the clock’s pre-activation a ℓ a_\ell a ℓ , and g t = softplus ( ⋅ ) ≥ g 0 > 0 g_t=\operatorname{softplus}(\cdot)\ge g_0>0 g t = softplus ( ⋅ ) ≥ g 0 > 0 . If a ℓ ≥ a 0 > 0 a_\ell\ge a_0>0 a ℓ ≥ a 0 > 0 for all admissible inputs, b ≤ − g 0 a 0 ( t − j ) b\le-g_0a_0(t-j) b ≤ − g 0 a 0 ( t − j ) and Lemma 13 applies. If a ℓ ≤ 0 a_\ell\le0 a ℓ ≤ 0 always, S S S is constant and b ≡ 0 b\equiv0 b ≡ 0 ; C A B L E CABLE C A B L E has no R o P E RoPE R o P E , so the scores are bounded content alone and softmax dilutes as in Proposition 12(iii). □ \square □
Power priors
Proposition 15 (Window mass of power-law priors). *For the prior ( 1 + d ) − c (1+d)^{-c} ( 1 + d ) − c and constant content, the mass within distance L L L of the diagonal at row t t t is ( 1 − c ) S L t − ( 1 − c ) ( 1 + o ( 1 ) ) (1-c)S_L t^{-(1-c)}(1+o(1)) ( 1 − c ) S L t − ( 1 − c ) ( 1 + o ( 1 )) for c < 1 c<1 c < 1 , S L / log t ( 1 + o ( 1 ) ) S_L/\log t\,(1+o(1)) S L / log t ( 1 + o ( 1 )) for c = 1 c=1 c = 1 , and tends to S L / ζ ( c ) > 0 S_L/\zeta(c)>0 S L / ζ ( c ) > 0 for c > 1 c>1 c > 1 , where S L = ∑ d < L ( 1 + d ) − c S_L=\sum_{d<L}(1+d)^{-c} S L = ∑ d < L ( 1 + d ) − c . Bounded content changes these quantities by at most a factor e ± 2 B e^{\pm2B} e ± 2 B .
Proof. By (Z) the window mass is S L / Z t S_L/Z_t S L / Z t . Comparing the decreasing k − c k^{-c} k − c with its integral, as in (M) of Appendix § 10 : for c < 1 c<1 c < 1 , Z t = t 1 − c ( 1 − c ) − 1 ( 1 + o ( 1 ) ) Z_t=t^{1-c}(1-c)^{-1}(1+o(1)) Z t = t 1 − c ( 1 − c ) − 1 ( 1 + o ( 1 )) ; for c = 1 c=1 c = 1 , Z t = log t ( 1 + o ( 1 ) ) Z_t=\log t(1+o(1)) Z t = log t ( 1 + o ( 1 )) ; for c > 1 c>1 c > 1 , Z t Z_t Z t increases to ζ ( c ) \zeta(c) ζ ( c ) . For c > 1 c>1 c > 1 the far mass beyond L L L is moreover at most
1 Z t ∑ d ≥ L ( 1 + d ) − c ≤ ∑ k ≥ L + 1 k − c ≤ ∫ L ∞ x − c d x = L 1 − c c − 1 \frac{1}{Z_t}\sum_{d\ge L}(1+d)^{-c}\le\sum_{k\ge L+1}k^{-c}\le\int_L^\infty x^{-c}\,dx=\frac{L^{1-c}}{c-1} Z t 1 d ≥ L ∑ ( 1 + d ) − c ≤ k ≥ L + 1 ∑ k − c ≤ ∫ L ∞ x − c d x = c − 1 L 1 − c
for every t t t , since Z t ≥ 1 Z_t\ge1 Z t ≥ 1 (the diagonal term). Bounded content enters through (B).
Corollary 16 (Log-distance exponents near one at finite length). For c = 1 + δ c=1+\delta c = 1 + δ with δ > 0 \delta>0 δ > 0 and constant content, the mass N t ( L ) N_t(L) N t ( L ) within distance L L L of the diagonal at row t ≥ max ( L , 2 ) t\ge\max(L,2) t ≥ max ( L , 2 ) satisfies
(i) S L 1 + log t ≤ N t ( L ) ≤ 2 S L log ( t + 1 ) if δ log ( t + 1 ) ≤ 1 ; \text{(i)}\quad\frac{S_L}{1+\log t}\le N_t(L)\le\frac{2S_L}{\log(t+1)}\quad\text{if }\delta\log(t+1)\le1; (i) 1 + log t S L ≤ N t ( L ) ≤ log ( t + 1 ) 2 S L if δ log ( t + 1 ) ≤ 1 ; (ii) S L ζ ( c ) ≤ N t ( L ) ≤ S L ζ ( c ) ( 1 − t − δ ) . \text{(ii)}\quad\frac{S_L}{\zeta(c)}\le N_t(L)\le\frac{S_L}{\zeta(c)(1-t^{-\delta})}. (ii) ζ ( c ) S L ≤ N t ( L ) ≤ ζ ( c ) ( 1 − t − δ ) S L . Bounded content changes these bounds by at most a factor e ± 2 B e^{\pm2B} e ± 2 B .
Proof. By (Z), N t ( L ) = S L / Z t N_t(L)=S_L/Z_t N t ( L ) = S L / Z t with Z t = ∑ k = 1 t k − 1 − δ Z_t=\sum_{k=1}^{t}k^{-1-\delta} Z t = ∑ k = 1 t k − 1 − δ . Let ϕ δ ( x ) = ∫ 1 x y − 1 − δ d y = ( 1 − x − δ ) / δ \phi_\delta(x)=\int_1^x y^{-1-\delta}\,dy=(1-x^{-\delta})/\delta ϕ δ ( x ) = ∫ 1 x y − 1 − δ d y = ( 1 − x − δ ) / δ . Since x ↦ x − 1 − δ x\mapsto x^{-1-\delta} x ↦ x − 1 − δ is decreasing, integral comparison gives
ϕ δ ( t + 1 ) ≤ Z t ≤ 1 + ϕ δ ( t ) . \phi_\delta(t+1)\le Z_t\le1+\phi_\delta(t). ϕ δ ( t + 1 ) ≤ Z t ≤ 1 + ϕ δ ( t ) .
Write u = δ log x ≥ 0 u=\delta\log x\ge0 u = δ log x ≥ 0 , so that ϕ δ ( x ) = ( 1 − e − u ) / δ \phi_\delta(x)=(1-e^{-u})/\delta ϕ δ ( x ) = ( 1 − e − u ) / δ ; from u − 1 2 u 2 ≤ 1 − e − u ≤ min ( u , 1 ) u-\frac{1}{2}u^2\le1-e^{-u}\le\min(u,1) u − 2 1 u 2 ≤ 1 − e − u ≤ min ( u , 1 ) , dividing by δ \delta δ gives log x ( 1 − 1 2 δ log x ) ≤ ϕ δ ( x ) ≤ min ( log x , 1 / δ ) \log x(1-\frac{1}{2}\delta\log x)\le\phi_\delta(x)\le\min(\log x,1/\delta) log x ( 1 − 2 1 δ log x ) ≤ ϕ δ ( x ) ≤ min ( log x , 1/ δ ) . (i) Z t ≤ 1 + ϕ δ ( t ) ≤ 1 + log t Z_t\le1+\phi_\delta(t)\le1+\log t Z t ≤ 1 + ϕ δ ( t ) ≤ 1 + log t gives the lower bound. If δ log ( t + 1 ) ≤ 1 \delta\log(t+1)\le1 δ log ( t + 1 ) ≤ 1 , then ϕ δ ( t + 1 ) ≥ 1 2 log ( t + 1 ) \phi_\delta(t+1)\ge\frac{1}{2}\log(t+1) ϕ δ ( t + 1 ) ≥ 2 1 log ( t + 1 ) , which gives the upper bound. (ii) Z t ≤ ζ ( c ) Z_t\le\zeta(c) Z t ≤ ζ ( c ) gives the lower bound. The tail satisfies ζ ( c ) − Z t = ∑ k > t k − c ≤ ∫ t ∞ x − c d x = t − δ / δ \zeta(c)-Z_t=\sum_{k>t}k^{-c}\le\int_t^\infty x^{-c}\,dx=t^{-\delta}/\delta ζ ( c ) − Z t = ∑ k > t k − c ≤ ∫ t ∞ x − c d x = t − δ / δ , and Z t ≥ ϕ δ ( t + 1 ) ≥ ( 1 − t − δ ) / δ Z_t\ge\phi_\delta(t+1)\ge(1-t^{-\delta})/\delta Z t ≥ ϕ δ ( t + 1 ) ≥ ( 1 − t − δ ) / δ , so ζ ( c ) / Z t ≤ 1 + t − δ / ( 1 − t − δ ) = 1 / ( 1 − t − δ ) \zeta(c)/Z_t\le1+t^{-\delta}/(1-t^{-\delta})=1/(1-t^{-\delta}) ζ ( c ) / Z t ≤ 1 + t − δ / ( 1 − t − δ ) = 1/ ( 1 − t − δ ) , which is the upper bound. Bounded content enters through (B).
Numerical checks of the theory
We check finite-length identities and bounds (Appendix § 13 .§ 1 ), compare finite lengths with the limits (Appendix § 13 .§ 2 ), and measure effects the theory does not quantify (Appendix § 13 .§ 3 ). The tests are in packages/geoattn-core/tests/. “Recursion” solves (6) row by row in float64; “operator” runs the iteration (5) in float32.
Finite-length identities and bounds
These checks hold entrywise up to rounding, or fail. In test_unbalanced_recursion: the recursion agrees with the operator after 400 iterations to 10 − 6 10^{-6} 1 0 − 6 , for constant and random scores (Lemma 2 ); both bounds of Lemma 3 hold, with equality on the diagonal; t λ t ≤ e B t\lambda_t \le e^B t λ t ≤ e B , and with constant scores t λ t ≥ a 0 t\lambda_t \ge a_0 t λ t ≥ a 0 for ρ \rho ρ up to 0.9 and r i ≤ 1 / ( a 0 ( i − j + 1 ) ) r_i \le1/(a_0(i-j+1)) r i ≤ 1/ ( a 0 ( i − j + 1 )) (Lemmas 4 , 17, 18); and max j P t j ≤ ( e 2 B / t ) 1 − ρ \max_j P_{tj} \le(e^{2B}/t)^{1-\rho} max j P t j ≤ ( e 2 B / t ) 1 − ρ for B ∈ { 0 , 1 , 3 } B \in\{0,1,3\} B ∈ { 0 , 1 , 3 } (Theorem 5 ). In test_potential_framework: row terms leave softmax and the fixed point unchanged while a column term does not (Proposition 11); the far mass of a linear bias is bounded uniformly in the length, GRAPE-A, FoX and GRAPE-AP decay at least linearly, and CABLE’s stopped clock is a counterexample (Lemma 13, Proposition 14); and both bounds of Corollary 16, as well as those on Z t Z_t Z t and ϕ δ \phi_\delta ϕ δ in its proof, hold for δ \delta δ from 10 − 3 10^{-3} 1 0 − 3 to 1, L ≤ 512 L \le512 L ≤ 512 and t ≤ 10 5 t \le10^5 t ≤ 1 0 5 ; at c = 1.5 c=1.5 c = 1.5 and t = 10 4 t=10^4 t = 1 0 4 the upper bound in (ii) is within 1% of the window mass.
Comparison with the limits
Table 4 compares finite lengths with the limits as t → ∞ t \to\infty t → ∞ ; the tolerances describe the tested settings, not uniform error bounds.
Table 4. Limit statements against finite lengths. Tests in test_unbalanced_scaling, except Theorem 6 (test_unbalanced_recursion) and the last row (test_potential_framework).
For constant scores, t λ t t\lambda_t t λ t at t = 128 , 512 , 2048 t=128,512,2048 t = 128 , 512 , 2048 is 0.8449, 0.8410, 0.8398 (a ∗ = 0.8393 a^*=0.8393 a ∗ = 0.8393 ) for ρ = 0.25 \rho=0.25 ρ = 0.25 , 0.6471, 0.6398, 0.6375 (0.6366) for ρ = 0.5 \rho=0.5 ρ = 0.5 , and 0.3833, 0.3743, 0.3715 (0.3704) for ρ = 0.75 \rho=0.75 ρ = 0.75 ; longer single computations at n = 4096 n=4096 n = 4096 are closer still. The limit shape: t P t , ⌊ s t ⌋ tP_{t,\lfloor st\rfloor} t P t , ⌊ s t ⌋ is compared with f ( s ) f(s) f ( s ) for ρ ∈ { 0.25 , 0.5 , 0.75 } \rho\in\{0.25,0.5,0.75\} ρ ∈ { 0.25 , 0.5 , 0.75 } and s ∈ { 0.05 , 0.3 , 0.7 , 0.95 } s \in\{0.05,0.3,0.7,0.95\} s ∈ { 0.05 , 0.3 , 0.7 , 0.95 } , for example 0.515 against 0.514 at ρ = 0.5 \rho=0.5 ρ = 0.5 , s = 0.3 s=0.3 s = 0.3 . Near the diagonal (ρ = 0.5 \rho=0.5 ρ = 0.5 ), t 1 − ρ P t , t − d t^{1-\rho}P_{t,t-d} t 1 − ρ P t , t − d at d = 0 , 1 , 2 , 8 , 64 d=0,1,2,8,64 d = 0 , 1 , 2 , 8 , 64 is 0.7982, 0.4933, 0.3809, 0.2008, 0.0706, against 0.7979, 0.4931, 0.3808, 0.2008, 0.0709 from the discrete profile and 0.0705 from the power law at d = 64 d=64 d = 64 . With i.i.d. scores uniform on [ − B , B ] [-B,B] [ − B , B ] , the mean of t P κ / ( K f ) tP_\kappa/(Kf) t P κ / ( K f ) over the last 64 rows lies in [0.996, 1.017] for ρ ∈ { 0.5 , 0.75 } \rho\in\{0.5,0.75\} ρ ∈ { 0.5 , 0.75 } , B ∈ { 1 , 3 } B \in\{1,3\} B ∈ { 1 , 3 } and s s s near 0.05, 0.3, 0.7, 0.9.
Effects the theory does not quantify
The theorems give limits, not rates; the following are measured, not proved.
Finite iterations. With k = 2 k = 2 k = 2 the main deviation in the tested settings is the amplitude: t P / f tP/f tP / f is nearly constant in s s s but not one. It is 1.20, 1.13 and 1.09 at n = 1024 n = 1024 n = 1024 , 4096, 16384 for ρ = 0.75 \rho= 0.75 ρ = 0.75 , 1.76 at n = 4096 n = 4096 n = 4096 for ρ = 0.9 \rho= 0.9 ρ = 0.9 , and within 1.3% of one at n = 4096 n = 4096 n = 4096 for ρ = 0.5 \rho= 0.5 ρ = 0.5 . With k = 3 k = 3 k = 3 the error is mainly a tilt in s s s , of 4–15% for ρ ≥ 0.75 \rho\ge0.75 ρ ≥ 0.75 at n = 4096 n = 4096 n = 4096 –16384 (scripts/finite_iteration_rate.py).
The fixed point. The error of t λ t t\lambda_t t λ t above shrinks roughly like t − 0.9 t^{-0.9} t − 0.9 over the tested lengths for all three values of ρ \rho ρ . This is the approach to the limit in t t t , not the convergence of the iteration in k k k .
i.i.d. content. At n = 4096 n = 4096 n = 4096 the standard deviation of t P K / ( K f ) tP_K/(Kf) t P K / ( K f ) over the last 64 rows grows with B B B and ρ \rho ρ , from 0.015 to 0.098: a mean close to one coexists with appreciable row-to-row variation.
Experimental details and supplementary results
Setup
Data and training. FineWeb-Edu [32 ] sample-10BT at revision 87f09149, tokenized with the GPT-2 tokenizer, documents separated by end-of-text tokens. Validation uses shard 013 (20M tokens, hash prefix 318c97404e7d7482); all file hashes are recorded in the data manifest. Models are decoder-only pre-norm Transformers with tied embeddings, trained with AdamW, warmup and cosine decay under bf16 autocast (Table 5 ); arms differ only in their position encoding and normalizer (Table 6 ). The OT arms use a fused Triton kernel for the prefix iteration, with k = 13 k = 13 k = 13 (ρ = 0.5 \rho= 0.5 ρ = 0.5 ) and k = 7 k = 7 k = 7 (ρ = 0.25 \rho= 0.25 ρ = 0.25 ) iterations chosen so that the fixed-point residual is at most 10 − 4 10^{-4} 1 0 − 4 ; each run re-measured the residual after training. Gradients flow through the k k k unrolled iterations, not through the fixed point. Per head, these iterations cost O ( k n 2 ) O(kn^2) O ( k n 2 ) work at length n n n . The kernel stores prefix carries at row-block boundaries and recomputes within blocks during backward; at fixed block size the saved state remains O ( k n 2 ) O(kn^2) O ( k n 2 ) . The learnable log-distance exponents are c h = softplus ( θ h ) c_h = \operatorname{softplus}(\theta_h) c h = softplus ( θ h ) , initialized log-spaced in [ 0.1 , 1 ] [0.1, 1] [ 0.1 , 1 ] over the heads; P6 and LC add a linear gate of the layer input to θ h \theta_h θ h , and KERPLE’s p h p_h p h , a h a_h a h start uniform in ( 0 , 2 ) (0, 2) ( 0 , 2 ) and ( 0 , 1 ) (0, 1) ( 0 , 1 ) as in its code.
Table 5: Training configurations; 32,768 tokens per step at both scales. Arms differ only in their position encoding and normalizer; their settings are the overrides listed in the accompanying configuration files (configs/exp0002/arms.yaml).
Table 5.
Evaluation. Losses at different lengths average over the same initial predicted tokens of the validation stream: 2M in the main 100M evaluations and in the interventions, 262,144 in the far-mass probe. The far mass evaluates two validation sequences per length (2 N 2N 2 N tokens) because computing full attention couplings across all layers and heads at lengths up to 16 L 16L 16 L is memory-intensive; with N / 2 N/2 N /2 queries per sequence evaluated across 14 layers and 12 heads, each probe averages over hundreds of thousands of attention rows, yielding negligible sequence-to-sequence variation (< 0.01 < 0.01 < 0.01 ). For each query in the second half of a sequence, the attention on keys more than one training length back is averaged over these queries, layers and heads. YaRN-t is applied to trained checkpoints at evaluation time. For evaluation length N N N and training length L L L , the scaling factor is s = max ( 1 , N / L ) s = \max(1, N/L) s = max ( 1 , N / L ) . A RoPE frequency ω \omega ω that makes L ω / ( 2 π ) L\omega/(2\pi) L ω / ( 2 π ) rotations within the training window becomes ω / s \omega/s ω / s up to one rotation and stays ω \omega ω from 32 rotations onward, with linear interpolation in the rotation count in between. To adjust the attention temperature, queries and keys are both scaled by 1 + 0.1 log s 1 + 0.1\log s 1 + 0.1 log s , which multiplies their dot products by ( 1 + 0.1 log s ) 2 (1 + 0.1\log s)^2 ( 1 + 0.1 log s ) 2 .
Preregistered tests
Table 7 lists the four preregistered experiments with their tests and outcomes. Loss tests compare a mean paired difference (same seed or same checkpoint) with a threshold and require the same sign on every seed or checkpoint. In the encoding comparison the threshold is δ e = max ( 2 σ e , 0.01 ) = 0.117 \delta_e = \max(2\sigma_e, 0.01) = 0.117 δ e = max ( 2 σ e , 0.01 ) = 0.117 , where σ e \sigma_e σ e is the seed standard deviation of B0’s L e x t L_{\mathrm{ext}} L ext ; the main test also requires CABLE to beat B0 by δ e \delta_e δ e and to stay within 0.01 of B0’s 1× loss. Because δ e \delta_e δ e far exceeds the seed standard deviation of the paired differences (0.0013–0.0027), the retests use the threshold 0.01 on new seeds and are reported separately. For the test-time interventions, the threshold applies to the mean over all checkpoints of one intervention type, pooled across arms and scales; Table 12 splits these sets by scale only for reporting, so the 100M LC repair mean (− 0.009 -0.009 − 0.009 ) is not tested on its own.
Supplementary results
OT mechanism (exploratory). In the 25M screening models, the distance part explains a layer-averaged 11–27% of the variance of the OT correction across ρ ∈ { 0.1 , 0.25 , 0.5 , 0.75 } \rho\in\{0.1, 0.25, 0.5, 0.75\} ρ ∈ { 0.1 , 0.25 , 0.5 , 0.75 } , and 18–19% at ρ = 0.5 \rho= 0.5 ρ = 0.5 . To remove the operator’s built-in distance decay, the uniform-target operator replaces the target column mass 1 by T t j = ∑ i = 1 t 1 / i T_{tj} = \sum_{i=1}^{t} 1/i T t j = ∑ i = 1 t 1/ i , the mass that uniform attention delivers, that is, log M t j ( k ) \log M_{tj}^{(k)} log M t j ( k ) by log ( M t j ( k ) / T t j ) \log(M_{tj}^{(k)}/T_{tj}) log ( M t j ( k ) / T t j ) in (5) ; its fixed point is P t j = λ t K t j ( M t j / T t j ) − γ P_{tj} = \lambda_t K_{tj}(M_{tj}/T_{tj})^{-\gamma} P t j = λ t K t j ( M t j / T t j ) − γ , and with constant scores the correction vanishes. Its 2 L 2L 2 L loss is above that of both the original target and softmax, and adding it to the log-distance bias worsens both lengths (Table 8 a). Since the target also changes the fixed point, this does not isolate the content part. At 100M, applying YaRN-t to both softmax and OT reduces their loss gap at 2 L 2L 2 L by 97.7% (Table 8 b). A single 100M ρ = 0.5 \rho= 0.5 ρ = 0.5 run at half the learning rate is worse at both lengths; this comparison tests only that lower rate. The prefix operator also reduces attention sinks, the mass on the first token [53 ] ; we did not find this to matter for extrapolation. Across evaluation lengths from L L L to 8 L 8L 8 L (512 to 4096), the post-training fixed-point residual remains bounded below 7.4 × 10 − 5 7.4 \times10^{-5} 7.4 × 1 0 − 5 for ρ ≤ 0.5 \rho\le0.5 ρ ≤ 0.5 and 3.0 × 10 − 4 3.0 \times10^{-4} 3.0 × 1 0 − 4 for ρ = 0.75 \rho= 0.75 ρ = 0.75 , confirming that extrapolation degradation does not stem from fixed-point solver divergence.
Table 8 : Exploratory OT ablations, validation loss in nats per token. (a) Screening configuration (25 M 25\mathrm{M} 25 M , L = 512 L = 512 L = 512 , ρ = 0.5 \rho= 0.5 ρ = 0.5 , k = 13 k = 13 k = 13 ), means over two seeds. (b) The 100 M 100\mathrm{M} 100 M checkpoints of Table 1 at 2 L = 2048 2L = 2048 2 L = 2048 on about 1 M 1\mathrm{M} 1 M predictions, means over three seeds; the gap is softmax minus OT.
Table 8.
Screening. Table 9 gives the screening results by arm. B0 with YaRN-t reaches L e x t = 3.461 L_{\mathrm{ext}} = 3.461 L ext = 3.461 . With the same bias, adding OT is slightly worse (O2 against ALiBi: +0.005 and +0.004 on the two seeds).
Confirmation and retests at 100M. The confirmation trains eight arms with three seeds each (Table 10 ): B0, log-n n n softmax, ALiBi, CABLE and LC (screening ranks 1 and 2; LC exploratory), GRAPE-M, GRAPE-AP and O2; B0 + YaRN-t is evaluated on the B0 checkpoints. CABLE was trained at two learning rates, and a preregistered rule selected the one with lower 1 × 1\times 1 × loss. CABLE beats B0 + YaRN-t in L e x t L_{\mathrm{ext}} L ext by 0.058 (0.059, 0.060, 0.056 per seed), below δ e = 0.117 \delta_e = 0.117 δ e = 0.117 , with a 1 × 1\times 1 × loss 0.017 lower than B0. Both GRAPE variants and O2 have higher L e x t L_{\mathrm{ext}} L ext than CABLE, and O2 is above ALiBi on every seed (by 0.0031–0.0047). Table 11 gives the absolute losses of the retests.
Table 10. Confirmation at 100M: validation loss in nats per token (mean ± sd over three seeds). YaRN-t is defined only for arms with RoPE. CABLE uses the learning-rate variant selected by the preregistered rule.
Table 11. Retest at 100M on new seeds: validation loss in nats per token (mean ± sd) at the training length (1 × 1\times 1 × ) and L e x t L_{\mathrm{ext}} L ext .
Test-time interventions. The interventions act on the total additive bias of each head after loading a trained checkpoint and are applied in both the reference and the fused attention; Table 12 lists the checkpoints, and Figure 5 shows one 25 M 25\mathrm{M} 25 M checkpoint per intervention. LC repair starts from its original content-clock bias at d = L d = L d = L , then extends the tail in token distance with exponent 1.5. Both LC checkpoints show lower far mass and loss at 8 L 8L 8 L , as predicted for stronger tail suppression; the smaller loss reduction accompanies LC’s lower initial far mass, and the fixed exponent can also weaken decay in heads with learned exponents above 1.5. While a clock-consistent repair extending learned clock increments rather than token distance could preserve token-rate sensitivity, LC’s pre-existing decay (0.36 far mass) leaves less room for improvement than the diluting arms. An exploratory repair of the three 100 M 100\mathrm{M} 100 M token-distance log-bias checkpoints (Table 1 , last row) changes loss in the same direction.
Figure 5. Loss against the evaluation length for one 25M checkpoint per intervention, before (dark grey) and after; the curves coincide up to the training length by construction.
Training-time constraints. Table 13 reports both training-time experiments. The first constrains the P1 exponents to c = 1 + softplus ( θ ) > 1 c = 1 + \operatorname{softplus}(\theta) > 1 c = 1 + softplus ( θ ) > 1 or c = σ ( θ ) < 1 c = \sigma(\theta) < 1 c = σ ( θ ) < 1 ; the second imposes c ≥ 1 + δ 0 c \ge1 + \delta_0 c ≥ 1 + δ 0 . Under c > 1 c > 1 c > 1 , many heads settle just above one (per-seed minima 1.0001–1.0002); their transition scales exceed e 10 e^{10} e 10 , so they remain in regime (i) of Corollary 16 through 32L L L . The margin follows from a window, a length range and a tolerance; the indicator δ 0 log n ≈ 1 \delta_0 \log n \approx1 δ 0 log n ≈ 1 alone does not decide whether a tolerance is met. For the prior ( 1 + d ) − c (1 + d)^{-c} ( 1 + d ) − c with all heads at c = 1 + δ 0 c = 1 + \delta_0 c = 1 + δ 0 , L = 512 L = 512 L = 512 and the far mass averaged as in § 5 , the growth from 4L L L to 16L L L is 0.088, 0.043 and 0.010 for δ 0 = 0.1 \delta_0 = 0.1 δ 0 = 0.1 , 0.25, 0.5, so of these only 0.5 meets the tolerance 0.02, although δ 0 log 16 L ≈ 1 \delta_0 \log16L \approx1 δ 0 log 16 L ≈ 1 already at δ 0 = 0.1 \delta_0 = 0.1 δ 0 = 0.1 .
Table 13. Training-time constraints on the P1 exponents at 25M, L = 512 L = 512 L = 512 , means over three seeds: validation loss, far mass at 16×, its growth from 4× to 16×, measured and predicted by the prior with the learned exponents (without content scores; post hoc in the upper block), and the share of heads at the bound (c < 1.1 c < 1.1 c < 1.1 in the upper block, within 0.01 of 1 + δ 0 1 + \delta_0 1 + δ 0 in the lower). The lower block extends Table 3 .
Far mass and distant use at 100M (exploratory). Table 14 gives the far mass and two distant-use probes on the confirmation checkpoints. From 4× to 16× the loss of B0 and GRAPE-M rises by 1.35–1.41, while the arms with a bounded far mass keep a flat loss; LC is in between (+0.38, with 44% of per-query exponents above one). Retrieval places a passkey [26 ] or a needle [17 ] at five depths, with 20 trials per depth. At 4× the other arms succeed only at the depth closest to the query, if at all, whereas CABLE’s passkey accuracy is 0.62 even at the farthest depth, about 3,700 tokens back (needle: 0.05). On the repetitive passkey filler, CABLE’s content increments Δ S l = ReLU ( w c x l + b c ) \Delta S_l = \operatorname{ReLU}(w_c x_l + b_c) Δ S l = ReLU ( w c x l + b c ) vanish, so its clock effectively pauses and measures semantic rather than token distance: its far mass is 0.19–0.20 at 8×, and its attention to the key span is 0.04 at 4× (others ≤ 0.003). In every CABLE checkpoint one to three heads of layers 5–6 put 0.6–1.0 of their attention on the passkey. Conversely, on natural text needles where the clock ticks continuously, accuracy drops to 0.05 at the farthest depth, showing that this retrieval relies on low-information fillers rather than general distant access. Copying gain [30 ] is the loss reduction on the final 128-token target when its copy replaces a fragment Δ tokens earlier, on 5L-token sequences with 64 shared trials; a shuffled copy gains at most 0.02. CABLE’s gains hold within 0.006 on five new seeds and are 0.17 and 0.07 at Δ = 2 L \Delta= 2L Δ = 2 L , 4 L 4L 4 L for training length 2048.
Table 14. Exploratory far mass and distant use at 100M, L = 1024 L = 1024 L = 1024 , means over three seeds (two for LC’s far mass and copying gain due to an incomplete seed-0 backup; see Section E.4). Retrieval accuracy is averaged over five key depths; copying gain in nats at distance Δ \Delta Δ (N = 5 L N = 5L N = 5 L ). Unfused reference arms at 16 × 16\times 16 × (16k) exceed the 48GB GPU memory cap. CABLE uses the selected learning-rate variant (7.5 × 10 − 4 7.5 \times10^{-4} 7.5 × 1 0 − 4 ).
Table 14 : Exploratory far mass and distant use at 100M, L = 1024 L = 1024 L = 1024 , means over three seeds (two for LC’s far mass and copying gain due to an incomplete seed-0 backup; see Section E.4). Retrieval accuracy is averaged over five key depths; copying gain in nats at distance Δ \Delta Δ (N = 5 L N = 5L N = 5 L ). Unfused reference arms at 16 × 16\times 16 × (16k) exceed the 48GB GPU memory cap. CABLE uses the selected learning-rate variant (7.5 × 10 − 4 7.5 \times10^{-4} 7.5 × 1 0 − 4 ).
Compute and code
Public code: https://github.com/homw314159-spec/causal-ot-attention , tag v0.1.0 (commit e60a38f). The public release has a fresh history; the reported runs record clean development commits and were not rerun for this release. The file configs/reproduction.yaml provides training recipes; docs/experiments.md maps the protocols and probes to scripts. It summarizes the preregistrations rather than publishing their original change logs. Development history, data and checkpoints are not distributed. Table 15 lists the training runs by experiment, with the identifiers used in the code.
Table 15. Training runs. Confirmation runs lost with the first machine were retrained and reproduce their 1 × 1\times 1 × losses to 0.0011. In the retest at 4096, both arms of a seed ran on the same machine.
Table 15 : Training runs. Confirmation runs lost with the first machine were retrained and reproduce their 1 × 1\times 1 × losses to 0.0011. In the retest at 4096, both arms of a seed ran on the same machine.