arXiv:1001.2733v2 [cond-mat.stat-mech] 2 Jul 2010 Universality of Zipf’s Law Bernat Corominas-Murtra 1 and Ricard V. Sol´ e 1 , 2 , 3 1 ICREA-Complex Systems Lab, Universitat Pompeu Fabra, Parc de Recerca Biom`edica de Barcelona (PRBB) Dr. Aiguader 80, 08003 Barcelona, Spain $^{2}$Santa Fe Institute, 1399 Hyde Park Road, New Mexico 87501, USA 3 Institut de Biologia Evolutiva. CSIC-UPF. Passeig Maritim de la Barceloneta, 37-49, 08003 Barcelona, Spain Zipf’s law is the most common statistical distribution displaying scaling behavior. Cities, popu- lations or firms are just examples of this seemingly universal law. Although many different models have been proposed, no general theoretical explanation has been shown to exist for its universality. Here we show that Zipf’s law is, in fact, an inevitable outcome of a very general class of stochastic systems. Borrowing concepts from Algorithmic Information Theory, our derivation is based on the properties of the symbolic sequence obtained through successive observations over a system with an ubounded number of possible states. Specifically, we assume that the complexity of the description of the system provided by the sequence of observations is the one expected for a system evolving to a stable state between order and disorder. This result is obtained from a small set of mild, physically relevant assumptions. The general nature of our derivation and its model-free basis would explain the ubiquity of such a law in real systems. Scaling laws are common in both natural and artificial systems [1]. Their ubiquity and universality is one of the fundamental issues in statistical physics [2–4]. One of the most prominent examples of power law behavior is the so called Zipf’s law [5–7]. It was popularized by the linguist G. K. Zipf, who observed that it accounts for the frequency of words within written texts [5, 8]. But this law is extremely common, [9] and has been found in the distribution of populations in city sizes [5, 10–14], firm sizes in industrial countries [15], market fluctuations [16], money income [17, 18], Internet file sizes [19] or family names [20]. For instance, if we rank all the cities in a country from the largest (in population size) to the smallest, Zipf’s law states that the probability p ( s$_{i}$ ) that a given individual lives in the i -th most populated city ( i = 1 , ..., n ) falls off as a scaling law seems fairly robust through time: in spite of widespread political and social changes, the statisti- cal behavior of words in written texts, cities or firms has remained the same over decades or even centuries [5, 7, 15, 23, 24]. Such robustness is remarkable, given that it indicates a large insensitivity to multiple sources of external perturbation. In spite of their disparate na- ture, all seem to rapidly achieve the Zipf’s law regime and remain there. To account for the emergence and robustness of Zipf’s law, several mechanisms have been proposed, in- cluding auto-catalytic processes [25–27], extinction dy- namics [28, 29], intermittency [30, 31], coherent noise [32], coagulation-fragmentation processes [33, 34], self- organized criticality [35], communicative conflicts [36, 37], random typewriting [38, 46], multiplicative dynam- ics [39, 40] or stochastic processes in systems with inter- acting units with complex internal structure [41]. The diverse character of such mechanisms sharing a common scaling exponent strongly points towards the hypothesis that some fundamental property (beyond a given specific dynamical mechanism) is at work. Such a universal trend asks for a generic explanation, which should avoid the use of a particular set of rules. with the exponent, γ ≈ 1, and being Z the normalization constant, i.e., We address the problem from a very general, mechanism-free viewpoint; by studying the statistical properties of the sequence of successive observations over the system. More precisely, our observations can be un- derstood as a sequence of symbols of a given alphabet (depending on the nature of the system) following some probability distribution. The elements of this alphabet can be coded in some way -for example, bits. From this conceptual starting point, we borrow concepts from algo- rithmic information theory (AIT) and propose a charac- terization of a wide family of stochastic systems, to which those systems displaying Zipf’s law would belong. Such a characterization imposes special features on the behav- ior of the entropy, whose study leads us to conclude that, under generic mathematical assumptions, Zipf’s law is Z =   ∑ i ≤ n i − γ   . (2) Although systems exhibiting Zipf’s-like statistics are clearly different in their constituent units, the nature of their interactions and intrinsic structure, most of them share a few essential commonalities. One is that they are stochastic, far from equilibrium systems changing in time, under mechanisms that prevent them to become homogeneous. Within the context of economic change, for example, wider varieties of goods and attraction for people are fueled by large developed areas. Increasing returns drive further growth and feedback between econ- omy and city sizes [21–23]. Moreover, the presence of p ( s$_{i}$ ) = 1 Z i − $^{γ}$, (1) I. INTRODUCTION