Benford's Law from Turing Ensembles and Integer Partitions

2025/02/22 by Kolpakov, Alexander, Rocke, Aidan · 1 citation
#Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Physical sciences #H.1.1 #Information Theory (cs.IT) #Mathematical Physics (math-ph)

paper · doi:10.48550/arxiv.2502.16314

Abstract

We develop two complementary generative mechanisms that explain when and why Benford's first-digit law arises. First, a probabilistic Turing machine (PTM) ensemble induces a geometric law for codelength. Maximizing its entropy under a constraint on halting length yields Benford statistics. This model shows a phase transition with respect to the halt probability. Second, a constrained partition model (Einstein-solid combinatorics) recovers the same logarithmic profile as the maximum-entropy solution under a coarse-grained entropy-rate constraint, clarifying the role of non-ergodicity (ensemble vs. trajectory averages). We also perform numerical experiments that corroborate our conclusions.

Cited by

• Lagrangians, Renormalization, and Quantization in Prefix Coding

Related

• Entropy Principle in Direct Derivation of Benford's Law
• The Newcomb–Benford law: Scale invariance and a simple Markov process based on it
• Thermodynamics of Benford's First Digit Law
• Multiplicative Turing ensembles, Pareto’s law, and creativity
• Benford's Law and Continuous Dependent Random Variables