Range-Renewal Processes: SLLNs and Power Laws

Abstract

Given n samples (viewed as an n-tuple) of a γ-regular discrete distribution π, in this article the authors concern with the weighted and unweighted graphs induced by the n samples. They first prove a series of SLLN results (of Dvoretzky-Erdös’ type). Then they show that the vertex weights of the graphs under investigation obey asymptotically power law distributions with exponent 1 + γ. They also give a conjecture that the degrees of unweighted graphs would exhibit asymptotically power law distributions with constant exponent 2. This exponent is obviously independent of the parameter γ ∈ (0, 1), which is a surprise to us at first sight.

Keywords

Range renewal process / Strong law of large numbers / Power law

References

[1] Adamic L A, Huberman B A. Power-law distribution of the world wide web. Science, 2000, 287: 2115

[2] Albert R, Barabási A-L. Statistical mechanics of complex networks. Rev. Mod. Phys., 2002, 74: 47-97

[3] Athreya K B. On the range of recurrent Markov chains. Statist. Probab. Lett., 1985, 3: 143-145

[4] Bahadur R R. On the number of distinct values in a large sample from an infinite discrete distribution. Proc. Nat. Inst. Sci. India Part A, 1960, 26(supplement II): 67-75

[5] Barabási A-L. Scale-free networks: A decade and beyond. Science, 2009, 325: 412

[6] Barabási A-L, Albert R. Emergence of scaling in random networks. Science, 1999, 286: 509

[7] Bass R F, Kumagai T. Laws of the iterated logarithm for the range of random walks in two and three dimensions. Ann. Probab., 2002, 30: 1369-1396

[8] Bingham N H, Goldie C M, Teugels J L. Regular Variation, 1987, Cambridge: Cambridge University Press

[9] Chosid L, Isaac R. On the range of recurrent Markov chains. Ann. Probab., 1978, 6: 680-687

[10] Chosid L, Isaac R. Correction to: “On the range of recurrent Markov chains”, [Ann. Probab. 6(4), 1978, 680–687; MR 57 #14146]. Ann. Probab., 1980, 8(5): 1000

[11] Derriennic, Y., Quelques applications du théorème ergodique sous-additif, (French. English summary) Conference on Random Walks (Kleebach, 1979) (French), 183–201, 4, Astérisque, 74, 1980, Soc. Math. France, Paris.

[12] Durrett R. Probability: Theory and Examples, 2019 5th ed. Cambridge: Cambridge University Press

[13] Dvoretzky A, Erdös P. Some problems on random walk in space, 1951, Berkeley and Los Angeles: University of California Press 353-367

[14] Erdös P, Taylor S J. Some problems concerning the structure of random walk paths. Acta Math. Acad. Sci. Hungar., 1960, 11: 137-162

[15] Feller, W., An Introduction to Probability Theory and Its Applications, 2nd ed., 2, Wiley Publishing, Inc. (Chinese translation edition, Posts & Telecom Press, 2008).

[16] Glynn P W. On the range of a regenerative sequence. Stoch. Proc. Appl., 1985, 20: 105-113

[17] Glynn P W, Sigman K. Uniform cesàro limit theorems for synchronous processes with applications to queues. Stoch. Proc. Appl., 1992, 40: 29-43

[18] Hamana Y. The fluctuation result for the multiple point range of two-dimensional recurrent random walks. Ann. Probab., 1997, 25: 598-639

[19] Hamana Y. An almost sure invariance principle for the range of random walks. Stoch. Proc. Appl., 1998, 78: 131-143

[20] Iosifescu M, Kraaikamp C. Metrical Theory of Continued Fractions, Mathematics and Its Applications, 2002, Dordrecht: Kluwer Academic Publishers 547

[21] Jain N C, Pruitt W E. The range of transient random walk. J. Anal. Math., 1971, 24: 369-393

[22] Jain N C, Pruitt W E. The law of the iterated logarithm for the range of random walk. Ann. Math. Statist., 1972, 43: 1692-1697

[23] Jain N C, Pruitt W E. Further limit theorems for the range of random walk. J. Anal. Math., 1974, 27: 94-117

[24] Karamata J. Sur un mode de croissance régulière, Théorèmes fondamentaux, (French). Bull. Soc. Math. France, 1933, 61: 55-62

[25] Le Gall J-F. ropriétés d’intersection des marches aléatoires, I, Convergence vers le temps local d’intersection. Comm. Math. Phys., 1986, 104: 471-507

[26] Révész P. Random Walk in Random and Non-Random Environments, 2005 2nd ed. Hackensack, NJ: World Scientific Publishing Co. Pte. Ltd. xvi+380 pp

[27] Salminen P, Vallois P. On first range times of linear diffusions. J. Theoret. Probab., 2005, 18: 567-593

[28] Vallois P. The range of a simple random walk on ℤ. Adv. in Appl. Probab., 1996, 28: 1014-1033

[29] Vallois P, Tapiero C S. Range reliability in random walks. Math. Methods Oper. Res., 1997, 45: 325-345

[30] Hofstad R. Random Graphs and Complex Networks (Cambridge Series in Statistical and Probabilistic Mathematics), 2016, Cambridge: Cambridge University Press