Multiperiodic Processes: Ergodic Sources with a Sublinear Entropy

We inspect the deductive connection between the neural scaling law and Zipf's law -- two statements discussed in machine learning and quantitative linguistics. The neural scaling law describes how the cross entropy rate of a foundation model -- such as a large language model -- changes with respect to the amount of training tokens, parameters, and compute. By contrast, Zipf's law posits that the distribution of tokens exhibits a power law tail. Whereas similar claims have been made in more specific settings, we show that the neural scaling law is a consequence of Zipf's law under certain broad assumptions that we reveal systematically. The derivation steps are as follows: We derive Heaps' law on the vocabulary growth from Zipf's law, Hilberg's hypothesis on the entropy scaling from Heaps' law, and the neural scaling from Hilberg's hypothesis. We illustrate these inference steps by a toy example of the Santa Fe process that satisfies all four statistical laws.

Estimating entropy from samples is fundamental in information theory and property testing. Shannon entropy measures average uncertainty and can be estimated to constant additive accuracy over a $k$-symbol alphabet using $Θ(k/\log k)$ samples. Min-entropy depends only on the most likely symbol. Both are special cases of order-$α$ R'{e}nyi entropy, $H_α$. We characterize the sample complexity of estimating min-entropy and R'{e}nyi entropy for $k$ and integer $α>1$; our lower bounds also hold for noninteger $α\ge1.001$. We prove that min-entropy estimation to constant additive accuracy has sample complexity $Θ(k\log k)$. The upper bound uses the largest empirical frequency and concentration via dyadic grouping. The matching lower bound hides a slightly heavier symbol at a uniformly random location. Thus, min-entropy requires $Θ(\log^2 k)$ more samples than Shannon entropy and corrects a previously stated $Θ(k/\log k)$ characterization. For every integer $2\leα\le c_0\log k$, we prove the matching fixed-accuracy bound $Θ_{c_0}(αk^{1-1/α})$. Previous results gave $Ω_α(k^{1-1/α})$ for fixed integer $α>1$ and $O_{c_0}(α^2k^{1-1/α})$ for all integer $α>1$. Our upper bound analyzes an unbiased falling-factorial estimator based on $α$-way collisions, while a hidden-heavy-coordinate construction gives the matching lower bound and shows that the factor $α$ is unavoidable. For every real $1.001\leα\le c_0\log k$, we prove the uniform lower bound $Ω_{c_0}(αk^{1-1/α})$. Finally, since $0\le H_α(p)-H_\infty(p)\le\log k/(α-1)$, min-entropy uniformly approximates $H_α$ when $α$ is a sufficiently large multiple of $\log k$. Combining this reduction with our min-entropy bounds gives $Θ_\varepsilon(k\log k)$ sample complexity in the high-order regime.

A randomized algorithm may terminate almost surely even though exceptional random tapes make it run forever. This paper studies the survival tail, the Kolmogorov complexity of one such tape, and the Hausdorff dimension of all of them. For each $s>0$ at which the powered repair matrices commute, the main theorem bounds $\sum_wP[w]^s$ over surviving prefixes $w$, uniformly over deterministic nonanticipating selectors. The case $s=1$ controls termination; the full family gives weak-source and dimension bounds. The source powers contain information absent even from the ordinary repair kernel and the complete stopping-time law. Under one common finite tape source, two overlapping disagreement-repair rules on a four-vertex path have the same ordinary kernels and the same stopping-time law for every selector, yet their nontermination dimensions can be arbitrarily close to zero and one. At one common source-power level, the same dominated tape source makes one rule run forever but gives the other an exponential stopping tail. The separation is caused by action labels that produce the same state transition and are therefore invisible at power one. For bounded-dependence $k$-SAT, conditional block min-entropy above the trace-growth threshold gives exponential termination, and the effective dimension of an individual infinite run is bounded by the trace growth induced by the clauses repaired infinitely often. Tree formulas asymptotically attain the maximum-degree dimension and global source bounds, while clique formulas attain the graph-specific one-step threshold in the stated regime. An exact backward likelihood identity complements these setwise results with tail and coding bounds for each run.