Understanding scaling through history-dependent processes with collapsing sample space

Abstract

History-dependent processes are ubiquitous in natural and social systems. Many such stochastic processes, especially those that are associated with complex systems, become more constrained as they unfold, meaning that their sample-space, or their set of possible outcomes, reduces as they age. We demonstrate that these sample-space reducing (SSR) processes necessarily lead to Zipf's law in the rank distributions of their outcomes. We show that by adding noise to SSR processes the corresponding rank distributions remain exact power-laws, $p(x)\sim x^{-\lambda }$, where the exponent directly corresponds to the mixing ratio of the SSR process and noise. This allows us to give a precise meaning to the scaling exponent in terms of the degree to how much a given process reduces its sample-space as it unfolds. Noisy SSR processes further allow us to explain a wide range of scaling exponents in frequency distributions ranging from $\alpha =2$ to $\infty$. We discuss several applications showing how SSR processes can be used to understand Zipf's law in word frequencies, and how they are related to diffusion processes in directed networks, or ageing processes such as in fragmentation processes. SSR processes provide a new alternative to understand the origin of scaling in complex systems without the recourse to multiplicative, preferential, or self-organised critical processes.

7 pages, 5 figures in Proceedings of the National Academy of Sciences USA (published ahead of print April 13, 2015)

References in corpus (15)

• Emergence of scaling in random networks
• Power-law distributions in empirical data
• Power laws, Pareto distributions and Zipf's law
• How Popular is Your Paper? An Empirical Study of the Citation Distribution
• When do generalized entropies apply? How phase space volume determines entropy
• Universality of Zipf's Law
• Power-law distributions and Levy-stable intermittent fluctuations in stochastic systems of many autocatalytic elements
• Scaling and Multiscaling in Models of Fragmentation
• Spontaneous Scaling Emergence in Generic Stochastic Systems
• How multiplicity determines entropy and the derivation of the maximum entropy principle for complex systems
• Emergence of Zipf's Law in the Evolution of Communication
• Emergence of good conduct, scaling and Zipf laws in human behavioral sequences in an online world
• Generalized (c,d)-entropy and aging random walks
• Theory of Zipf's Law and of General Power Law Distributions with Gibrat's law of Proportional Growth
• A comprehensive classification of complex statistical systems and an ab-initio derivation of their entropy and distribution functions

Cited by in corpus (33)

• Large-scale analysis of Zipf's law in English texts
• Complex systems: physics beyond physics
• Power-law size distributions in geoscience revisited
• Dynamics on expanding spaces: modeling the emergence of novelties
• Fitting Power-laws in empirical data with estimators that work for all exponents
• Control of critical behavior in a small-scale social system
• Dynamical approach to Zipf's law
• The three faces of entropy for complex systems -- information, thermodynamics and the maxent principle
• Taylor's law in innovation processes
• Log-log Convexity of Type-Token Growth in Zipf's Systems
• Zipf and Heaps laws from dependency structures in component systems
• When Shannon and Khinchin meet Shore and Johnson: equivalence of information theory and statistical inference axiomatics
• A Master Equation for Power Laws
• Maximal Diversity and Zipf's Law
• Zipf's and Taylor's Laws
• Sample space reducing cascading processes produce the full spectrum of scaling exponents
• Zipf's law for cosmic structures: how large are the greatest structures in the universe?
• Extreme robustness of scaling in sample space reducing processes explains Zipf's law in diffusion on directed networks
• Phase space volume scaling of generalized entropies and anomalous diffusion scaling governed by corresponding non-linear Fokker-Planck equations
• Heaps' law, statistics of shared components and temporal patterns from a sample-space-reducing process
• Information geometry of scaling expansions of non-exponentially growing configuration spaces
• Exact solution for a sample space reducing stochastic process
• From Boltzmann to Zipf through Shannon and Jaynes
• Scaling Laws for Function Diversity and Specialization Across Socioeconomic and Biological Complex Systems
• Maximum configuration principle for driven systems with arbitrary driving
• Damping effect in innovation processes: case studies from Twitter
• Power-law intensity distribution in $\gamma$-decay cascades -- Nuclear Structure as a Scale-Free Random Network
• Correspondence between noisy sample space reducing process and records in correlated random events
• A short-ranged memory model with preferential growth
• On multidimensional record patterns
• Scaling in simple continued fraction
• Ulam's History-dependent Random Adding Process
• Understanding Zipf's law of word frequencies through sample-space collapse in sentence formation