Scale-free and power law distributions via fixed points and convergence of (thinning and conditioning) transformations

Richard Arratia (University of Southern California)
Thomas M. Liggett (UCLA)
Malcolm J. Williamson (Center For Communications Research)


In discrete contexts such as the degree distribution for a graph, scale-free has traditionally been defined to be power-law. We propose a reasonable interpretation of scale-free, namely, invariance under the  transformation of $p$-thinning, followed by conditioning on being positive.

For each $\beta \in (1,2)$, we show that there is a unique distribution which is a fixed point of this transformation; the distribution is power-law-$\beta$, and different from the usual Yule-Simon power law-$\beta$ that arises in preferential attachment models.

In addition to characterizing these fixed points, we prove convergence results for iterates of the transformation.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-10

Publication Date: June 27, 2014

DOI: 10.1214/ECP.v19-2923


  • Albert, Réka; Barabási, Albert-László. Statistical mechanics of complex networks. Rev. Modern Phys. 74 (2002), no. 1, 47--97. MR1895096
  • Aldous, David J.; Bandyopadhyay, Antar. A survey of max-type recursive distributional equations. Ann. Appl. Probab. 15 (2005), no. 2, 1047--1110. MR2134098
  • Bingham, N. H.; Goldie, C. M.; Teugels, J. L. Regular variation. Encyclopedia of Mathematics and its Applications, 27. Cambridge University Press, Cambridge, 1989. xx+494 pp. ISBN: 0-521-37943-1 MR1015093
  • Bollobás, Béla; Riordan, Oliver M. Mathematical results on scale-free random graphs. Handbook of graphs and networks, 1--34, Wiley-VCH, Weinheim, 2003. MR2016117
  • Durrett, Richard; Liggett, Thomas M. Fixed points of the smoothing transformation. Z. Wahrsch. Verw. Gebiete 64 (1983), no. 3, 275--301. MR0716487
  • Feller, William. An introduction to probability theory and its applications. Vol. II. Second edition John Wiley & Sons, Inc., New York-London-Sydney 1971 xxiv+669 pp. MR0270403
  • Grimmett, Geoffrey. Percolation. Springer-Verlag, New York, 1989. xii+296 pp. ISBN: 0-387-96843-1 MR0995460
  • Hagerup, Torben; Rüb, Christine. A guided tour of Chernoff bounds. Inform. Process. Lett. 33 (1990), no. 6, 305--308. MR1045520
  • Kallenberg, Olav. Random measures. Third edition. Akademie-Verlag, Berlin; Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London, 1983. 187 pp. ISBN: 0-12-394960-2 MR0818219
  • Kallenberg, Olav. Foundations of modern probability. Second edition. Probability and its Applications (New York). Springer-Verlag, New York, 2002. xx+638 pp. ISBN: 0-387-95313-2 MR1876169
  • Kaluza, Th. Über die Koeffizienten reziproker Potenzreihen. (German) Math. Z. 28 (1928), no. 1, 161--170. MR1544949
  • N. Krishnaji. Characterization of the Pareto distributions through a model of underreported incomes. Econometrica, 38(2):251--255, 1970.
  • Liggett, Thomas M. Total positivity and renewal theory. Probability, statistics, and mathematics, 141--162, Academic Press, Boston, MA, 1989. MR1031283
  • Patil, G. P.; Ratnaparkhi, M. V. On additive and multiplicative damage models and the characterizations of linear and logarithmic exponential families. Canad. J. Statist. 7 (1979), no. 1, 61--64. MR0549794
  • Sato, Ken-iti. Lévy processes and infinitely divisible distributions. Translated from the 1990 Japanese original. Revised by the author. Cambridge Studies in Advanced Mathematics, 68. Cambridge University Press, Cambridge, 1999. xii+486 pp. ISBN: 0-521-55302-4 MR1739520
  • Shanbhag, D. N. On renewal sequences. Bull. London Math. Soc. 9 (1977), no. 1, 79--80. MR0428497
  • Steutel, F. W. Preservation of infinite divisibility under mixing and related topics. Mathematical Centre Tracts, 33 Mathematisch Centrum, Amsterdam 1970 v+99 pp. MR0278355
  • Warde, W. D.; Katti, S. K. Infinite divisibility of discrete distributions. II. Ann. Math. Statist. 42 (1971), 1088--1090. MR0293691

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.