Modulated Branching Processes, Origins of Power Laws, and Queueing Duality

References

• Adamic L. A., Huberman B. A. Zipf's law and the Internet. Glottometrics (2002) 3:143–150Google Scholar
• Allen A. P., Li B., Charnov E. L. Population fluctuations, power laws and mixtures of lognormal distributions. Ecology Lett. (2001) 4(1):1–3Crossref, Google Scholar
• Amaral L. A. N., Buldyrev S. V., Havlin S., Leschhorn H., Maass P., Salinger M. A., Stanley H. E., Stanley M. H. Scaling behavior in economics: Empirical results for company growth. J. Physique I (1997) 7(April):621–633Crossref, Google Scholar
• Arrhenius O. Species and area. J. Ecology (1921) 9(1):95–99Crossref, Google Scholar
• Asmussen S.Applied Probability and Queues (1987) 2nd ed.(Springer-Verlag, New York) Google Scholar
• Asmussen S., Fiorini P., Lipsky L., Rolski T., Sheahan R. Asymptotic behavior of total times for jobs that must start over if a failure occurs. Math. Oper. Res. (2008) 33(4):932–944Link, Google Scholar
• Athreya K. B., Ney P. E.Branching Processes (1972) (Springer-Verlag, Berlin) Crossref, Google Scholar
• Auerbach F. Das Gesetz der bevölkerungskonzentration. Petermanns Geographische Mitteilungen (1913) 59:73–76Google Scholar
• Barabási A. L., Albert R., Jeong H. Mean-field theory for scale-free random networks. Physica A (1999) 272:173–187Crossref, Google Scholar
• Billingsley P.Probability and Measure (1995) 3rd ed.(John Wiley & Sons, New York) Google Scholar
• Blank A., Solomon S. Power laws in cities population, financial markets and Internet sites (scaling in systems with a variable number of components). Physica A (2000) 287:279–288Crossref, Google Scholar
• Breslau L., Cao P., Fan L., Phillips G., Shenker S. Web caching and Zipf-like distributions: Evidence and implications. Proc. IEEE INFOCOM 1999 (1999) 1New York:126–134Crossref, Google Scholar
• Brujic J., Hermans R. I., Walther Z. K. A., Fernandez J. M. Single-molecule force spectroscopy reveals signatures of glassy dynamics in the energy landscape of ubiquitin. Nature Phys. (2006) 2(4):282–286Crossref, Google Scholar
• Bucklew J. A.Large Deviation Techniques in Decision, Simulation, and Estimation (1990) (John Wiley & Sons, New York) Google Scholar
• Carlson J. M., Doyle J. Highly optimized tolerance: A mechanism for power laws in designed systems. Phys. Rev. E (1999) 60(2):1412–1427Crossref, Google Scholar
• Champernowne D. A model of income distribution. Econom. J. (1953) 63:318–351Google Scholar
• Chang C.-S. Stability, queue length, and delay of deterministic and stochastic queueing networks. IEEE Trans. Automatic Control (1994) 39(5):913–931Crossref, Google Scholar
• Connor E. F., McCoy E. D. The statistics and biology of the species-area relationship. Amer. Naturalist (1979) 113(6):791–833Crossref, Google Scholar
• Crovella M., Bestavros A. Self-similarity in World Wide Web traffic: Evidence and possible causes. IEEE/ACM Trans. Networking (1997) 5(6):835–846Crossref, Google Scholar
• Cunha C., Bestavros A., Crovella M. Characteristics of World Wide Web client-based traces. (1995) . Technical Report TR-95-010, Department of Computer Science, Boston University, BostonGoogle Scholar
• Dagum C. A systematic approach to the generation of income distribution models. J. Income Distribution (1997) 6(1):105–126Google Scholar
• de Haan L., Resnick S. I., Rootzén H., de Vries C. G. Extremal behaviour of solutions to a stochastic difference equation with applications to ARCH processes. Stochastic Processes Appl. (1989) 32(2):213–224Crossref, Google Scholar
• de Saporta B. Tail of the stationary solution of the stochastic equation yn+1 = anyn + bn with Markovian coefficients. Stochastic Processes Appl. (2005) 115(12):1954–1978Crossref, Google Scholar
• Dembo A., Zeitouni O.Large Deviations Techniques and Applications (1998) 2nd ed.(Springer-Verlag, New York) Crossref, Google Scholar
• Downey A. B. The structural cause of file size distributions. Proc. ACM SIGMETRICS 2001 (2001) New York:328–329Google Scholar
• Faloutsos M., Faloutsos P., Faloutsos C. On power-law relationships of the Internet topology. Proc. ACM SIGCOMM 1999 (1999) Cambridge, MA:251–262Crossref, Google Scholar
• Fiorini P. M., Sheahan R., Lipsky L. On unreliable computing systems when heavy-tails appear as a result of the recovery procedure. Proc. Conf. ACM SIGMETRICS Performance Evaluation Rev. (2005) 33MAMA 2005 WorkshopBanff, Alberta, Canada(2):15–17Crossref, Google Scholar
• Gabaix X. Zipf's law for cities: An explanation. Quart. J. Econom. (1999) 114(3):739–767Crossref, Google Scholar
• Gabaix X., Gopikrishnan P., Plerou V., Stanley H. E. A theory of power-law distributions in financial market fluctuations. Nature (2003) 423(6937):267–270Crossref, Google Scholar
• Ganesh A., O'Connell N., Wischik D.Big Queues (2004) (Springer-Verlag, Berlin) Crossref, Google Scholar
• Glynn P. W., Whitt W. Logarithmic asymptotics for steady-state tail probabilities in a single-server queue. Stud. Appl. Probab. (1994) 31:131–156Crossref, Google Scholar
• Goldie C. M. Implicit renewal theory and tails of solutions of random equations. Ann. Appl. Probab. (1991) 1(1):126–166Crossref, Google Scholar
• Gong W.-B., Liu Y., Misra V., Towsley D. Self-similarity and long range dependence on the Internet: A second look at the evidence, origins and implications. Comput. Networks (2005) 48(3):377–399Crossref, Google Scholar
• Huberman B. A., Adamic L. A. Evolutionary dynamics of the World Wide Web. (1999) . Technical report, Xerox Palo Alto Research Center, 1999. (Appears as the brief communication, “Growth dynamics of the World Wide Web” in Nature 399 130.)Google Scholar
• Huberman B. A., Adamic L. A. The nature of markets in the World Wide Web. Quart. J. Electronic Commerce (2000) 1:5–12Google Scholar
• Huynen M. A., van Nimwegen E. The frequency distribution of gene family sizes in complete genomes. Molecular Biol. Evolution (1998) 15(5):583–589Crossref, Google Scholar
• Ioannides Y. M., Overman H. G. Zipf's law for cities: An empirical examination. Regional Sci. Urban Econom. (2003) 33(2):127–137Crossref, Google Scholar
• Jelenković P. R., Lazar A. On the dependence of the queue tail distribution on multiple time scales of ATM multiplexers. Proc. Conf. Inform. Sci. Systems (1995) Baltimore:435–440Google Scholar
• Jelenković P. R., Momčilović P. Asymptotic loss probability in a finite buffer fluid queue with heterogeneous heavy-tailed on-off processes. Ann. Appl. Probab. (2003) 13(2):576–603Crossref, Google Scholar
• Jelenković P. R., Olvera-Cravioto M. Information ranking and power laws on trees. Adv. Appl. Probab. (2010) 42(4Crossref, Google Scholar
• Jelenković P. R., Tan J. Modulated branching processes and origins of power laws. Proc. 44th Annual Allerton Conf. Comm., Control, Comput. (2006) (University of Illinois at Urbana–Champaign, Urbana–Champaign) Google Scholar
• Jelenković P. R., Tan J. Is ALOHA causing power law delays? Proc. 20th Internat. Teletraffic Congress 2007 (2007) 4516Ottawa, Canada(Springer-Verlag, Berlin) 1149–1160Lecture Notes Comput. Sci.Crossref, Google Scholar
• Jelenković P. R., Tan J. Can retransmissions of superexponential documents cause subexponential delays? Proc. IEEE INFOCOM 2007 (2007) (IEEE Computer Society, Washington, DC) 892–900Crossref, Google Scholar
• Jelenković P. R., Tan J. Characterizing heavy-tailed distributions induced by retransmissions. (2007) . Technical Report EE2007-09-07, Department of Electrical Engineering, Columbia University, New York (September). Eprint arXiv:10709.1138. http://arxiv.org/labs/10709.1138Google Scholar
• Jelenković P. R., Tan J. Modulated branching processes, origins of power laws and queueing duality. (2007) . Technical Report EE2007-09-25, Department of Electrical Engineering, Columbia University, New York (September). Eprint arXiv:0709.4297. http://arxiv.org/abs/0709.4297Google Scholar
• Jelenković P. R., Lazar A. A., Semret N. The effect of multiple time scales and subexponentiality in MPEG video streams on queueing behavior. IEEE J. Selected Areas Comm. (1997) 15(6):1052–1071Crossref, Google Scholar
• Keeley J. E. Relating species abundance distributions to species-area curves in two Mediterranean-type shrublands. Diversity Distributions (2003) 9:253–259Crossref, Google Scholar
• Kesten H. Random difference equations and renewal theory for products of random matrices. Acta Mathematica (1973) 131:207–248Crossref, Google Scholar
• Kumar R., Raghavan P., Rajagopalan S., Sivakumar D., Tomkins A., Upfal E. Stochastic models for the Web graph. Proc. 41st Annual Sympos. Foundations Comput. Sci. (2000) (IEEE Computer Society, Washington, DC) 57–65Crossref, Google Scholar
• Leland W. E., Willinger W., Taqqu M. S., Wilson D. V. On the self-similar nature of Ethernet traffic. ACM SIGCOMM Comput. Comm. Rev. (1995) 25(1):202–213Crossref, Google Scholar
• Levy M., Solomon S. Dynamical explanation for the emergence of power law in a stock market model. Internat. J. Modern Phys. C (1996) 7(1):65–72Crossref, Google Scholar
• Levy M., Solomon S. Power laws are logarithmic Boltzmann laws. Internat. J. Modern Phys. C (1996) 7(4):595–601Crossref, Google Scholar
• Levy M., Solomon S. Spontaneous scaling emergence in generic stochastic systems. Internat. J. Modern Phys. C (1996) 7(5):745–756Crossref, Google Scholar
• Loynes R. M. The stability of a queue with non-independent inter-arrival and service times. Proc. Cambridge Philos. Soc. (1962) 58:497–520Crossref, Google Scholar
• Luscombe N. M., Qian J., Zhang Z., Johnson T., Gerstein M. The dominance of the population by a selected few: Power-law behaviour applies to a wide variety of genomic properties. Genome Biol. (2002) 3(8). Research0040.0041–0040.0047Crossref, Google Scholar
• Mandelbrot B. The Pareto-Levy law and the distribution of income. Internat. Econom. Rev. (1960) 1:79–106Crossref, Google Scholar
• Medina A., Matta I., Byers J. On the origin of power laws in Internet topologies. Comput. Comm. Rev. (2000) 30(2):18–28Crossref, Google Scholar
• Mitzenmacher M. A brief history of generative models for power law and lognormal distributions. Internet Math. (2004a) 1(2):226–251Crossref, Google Scholar
• Mitzenmacher M. Dynamic models for file sizes and double Pareto distributions. Internet Math. (2004b) 1(3):305–333Crossref, Google Scholar
• Olvera-Cravioto M., Blanchet J., Glynn P. W. On the transition from heavy traffic to heavy tails for the M/G/1 queue: The regularly varying case. Ann. Appl. Probab. (2010) . ForthcomingGoogle Scholar
• Pareto V.Cours d'Economie Politique (1896) (Droz, Geneva) Google Scholar
• Parr J. A note on the size distribution of cities over time. J. Urban Econom. (1985) 18(2):199–212Crossref, Google Scholar
• Plotkin J. B., Potts M. D., Yu D. W., Bunyavejchewin S., Condit R., Foster R., Hubbell S., et al. Predicting species diversity in tropical forests. Proc. Natl. Acad. Sci. USA (2000) 97(20):10850–10854Crossref, Google Scholar
• Preston F. W. The canonical distribution of commonness and rarity. Ecology (1962) 43(2):185–215410432Crossref, Google Scholar
• Reed W. J. The Pareto, Zipf and other power laws. Econom. Lett. (2001) 74:15–19Crossref, Google Scholar
• Reed W. J. The Pareto law of incomes—An explanation and an extension. Physica A (2003) 319:469–486Crossref, Google Scholar
• Reed W. J., Hughes B. D. From gene families and genera to incomes and Internet file sizes: Why power laws are so common in nature. Phys. Rev. E (2002) 66(6):67–103Crossref, Google Scholar
• Reed W. J., Jorgensen M. The double Pareto—Lognormal distribution—A new parametric model for size distributions. Comm. Statist.: Theory Methods (2004) 33(8):1733–1753Crossref, Google Scholar
• Rosen K. T., Resnick M. The size distribution of cities: An examination of the Pareto law and primacy. J. Urban Econom. (1980) 8(2):165–186Crossref, Google Scholar
• Rzhetsky A., Gomez S. M. Birth of scale-free molecular networks and the number of distinct DNA and protein domains per genome. Bioinformatics (2001) 17:988–996Crossref, Google Scholar
• Sornette D., Cont R. Convergent multiplicative processes repelled from zero: Power laws and truncated power laws. J. Physique I (1997) 7(3):431–444Crossref, Google Scholar
• Wichmann S. On the power-law distribution of language family sizes. J. Linguistics (2005) 41(1):117–131Crossref, Google Scholar
• Zipf G.Human Behavior and the Principle of Least Effort (1949) (Addison-Wesley, Cambridge, MA) Google Scholar