Cascade models

a.k.a. cluster distributions, Galton-Watson models



\(\newcommand{\rv}[1]{\mathsf{#1}}\)

Models for, loosely, the total population size arising from all generations the offspring of some progenitor.

Let us suppose that each individual \(i\) who catches a certain strain of influenza will go on to infect a further \(\rv{n}_i\sim F\) others. Assume the population is infinite, that no one catches influenza twice and that the number of transmission of the disease is distributed the same for everyone who catches it. How many people, will ultimately catch the influenza, starting from one infected person?

The Galton-Watson version of this model considers this byu generation; We write \(\rv{x}(k)=\sum_{i \in k\text{th generation}} \rv{n}_i\) for the number of people infected in the \(k\)th generation. Writing \(F^{*k}\) for the \(k\)-fold convolution of \(F\), we have \[\rv{x}(k) \sim F^{\ast \rv{x}(k-1)}\] The sum over all these \[\sum_k \rv{x}(k)\] is the cascade size.

A type of count model for a Markov stochastic pure-birth branching process.

I say it is a count model, but it turns out there are continuous-state generalisations. See, e.g. (Burridge 2013a, 2013b).

The distribution of subcritical processes are sometimes tedious to calculate, although we can get a nice form for the generating function of a geometric offspring distribution cascade process.

Set \(\frac{1}{\lambda+1}=p\) and \(q=1-p\). We write \(G^{n}\equiv G\cdot G\cdot \dots \cdot G\cdot G\) for the \(n\)-fold composition of \(G\). Then the (non-critical) geometric offspring distribution branching process obeys the identity

\[ 1-G^n(s;\lambda) = \frac{\lambda^n(\lambda-1)(1-s)}{\lambda(\lambda^n-1)(1-s)+\lambda-1} \]

This can get us a formula for the first two factorial moments, and hence the vanilla moments and thus mean and variance etc

More generally the machinery of Lagrangian distributions is all we need to analyse these.

Maybe I should use (Dwass 1969) to get the moments? Dominic Yeo has a great explanation as always.

🏗 🏗 🏗

Lagrangian distributions

A clade of count distributions, which I would call “cascade size distribution”. For now, let’s get to the interesting new ones contained in this definition. They are unified to my mind by modelling cascade size of cluster processes. Specifically, if I have a given initial population and a given offspring distribution for some population of… things… a Lagrangian distribution gives me a model for the size of the total population. There are other interpretations of course (queueing is very popular), but this one is extremely useful for me. See (P. C. Consul and Shoukri 1988; P. C. Consul and Famoye 2006 Ch 6.2) for a deep dive on this. They introduce various exponential_families via the pgf, which is powerful and general, although it does obscure a lot of simplicity and basic workaday mathematics here where the forms of the mass functions do in fact turn out to be easy.

Terminology: the total cascade size of a subcritical branching process has a “delta Lagrangian” or “general Lagrangian” distribution, depending on whether the cluster has, respectively, a deterministic or random starting population. We will define the offspring distribution of such a branching process as \(G\sim G_Y(\eta, \alpha)\). Usually we also assume \(EG:=\eta< 1\), because otherwise the cascade size is infinite.

Borel-Tanner distribution

A delta Lagrangian distribution, the Borel distribution is the distribution of a cascade size starting from a population size of \(k=1\). We can generalize it to \(k>\), in which case it is the Borel-Tanner distribution.

Spelled
\(\operatorname{Borel-Tanner}(k,\eta)\)
Pmf
((X=x;k,)={}{}}
Mean
\(\frac{k}{1-\eta}\)
Variance
\(\frac{k\eta}{(1-\eta)^3}\)

Note to self: Wikipedia mentions an intriguing-sounding correspondence with random walks, which I should follow up Dwass (1969).

The only R implementation I could find for this is in VGAM, although it is not so complicated.

Poisson-Poisson Lagrangian

See (P. C. Consul and Famoye 2006 Ch 9.3). Also known as the Generalised Poisson, although there are many things called that.

Spelled
\(\operatorname{GPD}(\mu,\eta)\)
Pmf
\(\mathbb{P}(X=x;\mu,\eta)=\frac{\mu(\mu+ \eta x)^{x-1}}{x!e^{\mu+x\eta}}\)
Mean
\(\frac{\mu}{1-\eta}\)
Variance
\(\frac{\mu}{(1-\eta)^3}\)

Returning to the cascade interpretation: Suppose we have

  • an initial population is distributed \(\operatorname{Poisson}(\mu\))
  • and everyone in the population has a number of offspring distributed \(\operatorname{Poisson}(\eta\)).

Then the total population is distributed as \(\operatorname{GPD}(\mu, \eta)\).

Notice that this can produce long tails, in the sense that it can have a large variance with finite mean, but not heavy tails, in the sense of the variance becoming infinite while retaining a finite mean; both variance and expectation go to infinity together.

Here, I implemented the GPD for you in python. There are versions for R, presumably. A quick search turned up RMKDiscrete and LaplacesDemon.

General Lagrangian distribution

A larger family of Lagrangian distributions (the largest?) family is summarised in (P. Consul and Shenton 1972), in an unintuitive (for me) way.

One parameter: a differentiable (infinitely differentiable?) function, not necessarily a pgf, \(g: [0,1]\rightarrow \mathbb{R}\) such that \(g(0)\neq 0\text{ and } g(1)=1\). Now we define a pgf \(\psi(s)\) implicitly as the smallest root of the Lagrange transformation \(z=sg(z)\). The paradigmatic example of such a function is \(g:z\mapsto 1−p+pz\); let’s check how this fella out.

🏗

Spelled
?
Pmf
?
Mean
?
Variance
?

References

Bacry, Emmanuel, and Jean-François Muzy. 2016. “First- and Second-Order Statistics Characterization of Hawkes Processes and Non-Parametric Estimation.” IEEE Transactions on Information Theory 62 (4): 2184–2202. https://doi.org/10.1109/TIT.2016.2533397.
Bowman, K.O., and L.R. Shenton. 1989. “The Distribution of a Moment Estimator for a Parameter of the Generalized Poision Distribution.” Communications in Partial Differential Equations 14 (4): 867–93. https://doi.org/10.1080/03605308908820611.
Burridge, James. 2013a. “Cascade Sizes in a Branching Process with Gamma Distributed Generations.” arXiv:1304.3741 [math], April. http://arxiv.org/abs/1304.3741.
———. 2013b. “Crossover Behavior in Driven Cascades.” Physical Review E 88 (3): 032124. https://doi.org/10.1103/PhysRevE.88.032124.
Consul, P. C. 2014. “Lagrange and Related Probability Distributions.” In Wiley StatsRef: Statistics Reference Online. John Wiley & Sons, Ltd. http://onlinelibrary.wiley.com/doi/10.1002/9781118445112.stat01038/abstract.
Consul, P. C., and Felix Famoye. 1992. “Generalized Poisson Regression Model.” Communications in Statistics - Theory and Methods 21 (1): 89–109. https://doi.org/10.1080/03610929208830766.
———. 2006. Lagrangian Probability Distributions. Boston: Birkhäuser. https://books.google.com/books/about/Lagrangian_Probability_Distributions.html?id=UGbkIwT63qsC.
Consul, P. C., and Famoye Felix. 1989. “Minimum Variance Unbiased Estimation for the Lagrange Power Series Distributions.” Statistics 20 (3): 407–15. https://doi.org/10.1080/02331888908802188.
Consul, P. C., and L. R. Shenton. 1973. “Some Interesting Properties of Lagrangian Distributions.” Communications in Statistics 2 (3): 263–72. https://doi.org/10.1080/03610927308827073.
Consul, P.C., and M. M. Shoukri. 1984. “Maximum Likelihood Estimation for the Generalized Poisson Distribution.” Communications in Statistics - Theory and Methods 13 (12): 1533–47. https://doi.org/10.1080/03610928408828776.
Consul, P.C., and M.M. Shoukri. 1988. “Some Chance Mechanisms Related to a Generalized Poisson Probability Model.” American Journal of Mathematical and Management Sciences 8 (1-2): 181–202. https://doi.org/10.1080/01966324.1988.10737237.
Consul, P., and L. Shenton. 1972. “Use of Lagrange Expansion for Generating Discrete Generalized Probability Distributions.” SIAM Journal on Applied Mathematics 23 (2): 239–48. https://doi.org/10.1137/0123026.
Dwass, Meyer. 1969. “The Total Progeny in a Branching Process and a Related Random Walk.” Journal of Applied Probability 6 (3): 682–86. https://doi.org/10.2307/3212112.
HAIGHT, FRANK A., and MELVIN ALLEN BREUER. 1960. “The Borel-Tanner Distribution.” Biometrika 47 (1-2): 143–50. https://doi.org/10.1093/biomet/47.1-2.143.
Houdré, Christian. 2002. “Remarks on Deviation Inequalities for Functions of Infinitely Divisible Random Vectors.” The Annals of Probability 30 (3): 1223–37. https://doi.org/10.1214/aop/1029867126.
Imoto, Tomoaki. 2016. “Properties of Lagrangian Distributions.” Communications in Statistics - Theory and Methods 45 (3): 712–21. https://doi.org/10.1080/03610926.2013.835414.
Jánossy, L., and H. Messel. 1950. “Fluctuations of the Electron-Photon Cascade - Moments of the Distribution.” Proceedings of the Physical Society. Section A 63 (10): 1101. https://doi.org/10.1088/0370-1298/63/10/305.
———. 1951. “Investigation into the Higher Moments of a Nucleon Cascade.” Proceedings of the Royal Irish Academy. Section A: Mathematical and Physical Sciences 54: 245–62. http://www.jstor.org/stable/20488536.
Li, S, F Famoye, and C Lee. 2010. “On the Generalized Lagrangian Probability Distributions.” Journal of Probability and Statistical Science 8 (1): 113–23.
Messel, H. 1952. “The Solution of the Fluctuation Problem in Nucleon Cascade Theory: Homogeneous Nuclear Matter.” Proceedings of the Physical Society. Section A 65 (7): 465. https://doi.org/10.1088/0370-1298/65/7/301.
Messel, H., and R. B. Potts. 1952. “Note on the Fluctuation Problem in Cascade Theory.” Proceedings of the Physical Society. Section A 65 (10): 854. https://doi.org/10.1088/0370-1298/65/10/310.
Mishra, Swapnil, Marian-Andrei Rizoiu, and Lexing Xie. 2016. “Feature Driven and Point Process Approaches for Popularity Prediction.” In Proceedings of the 25th ACM International Conference on Information and Knowledge Management, 1069–78. CIKM ’16. New York, NY, USA: ACM. https://doi.org/10.1145/2983323.2983812.
Mutafchiev, Ljuben. 1995. “Local Limit Approximations for Lagrangian Distributions.” Aequationes Mathematicae 49 (1): 57–85. https://doi.org/10.1007/BF01827929.
Neyman, Jerzy. 1965. “Certain Chance Mechanisms Involving Discrete Distributions.” Sankhyā: The Indian Journal of Statistics, Series A (1961-2002) 27 (2/4): 249–58. http://www.jstor.org/stable/25049369.
Otter, Richard. 1948. “The Number of Trees.” Annals of Mathematics 49 (3): 583–99. https://doi.org/10.2307/1969046.
———. 1949. “The Multiplicative Process.” The Annals of Mathematical Statistics 20 (2): 206–24. https://doi.org/10.1214/aoms/1177730031.
Pardoux, Etienne, and Brice Samegni-Kepgnou. 2017. “Large Deviation Principle for Epidemic Models.” Journal of Applied Probability 54 (3): 905–20. https://doi.org/10.1017/jpr.2017.41.
Pazsit, I. 1987. “Note on the Calculation of the Variance in Linear Collision Cascades.” Journal of Physics D: Applied Physics 20 (2): 151. https://doi.org/10.1088/0022-3727/20/2/001.
Pitman, Jim. 1998. “Enumerations of Trees and Forests Related to Branching Processes and Random Walks.” In Microsurveys in Discrete Probability, edited by David Aldous and James Propp. Vol. 41. DIMACS Series in Discrete Mathematics and Theoretical Computer Science. Providence, Rhode Island: American Mathematical Society. https://doi.org/10.1090/dimacs/041.
Ramakrishnan, Alladi, and S. K. Srinivasan. 1956. “A New Approach to the Cascade Theory.” In Proceedings of the Indian Academy of Sciences-Section A, 44:263–73. Springer. http://link.springer.com/article/10.1007/BF03046051#page-1.
Rizoiu, Marian-Andrei, Lexing Xie, Scott Sanner, Manuel Cebrian, Honglin Yu, and Pascal Van Hentenryck. 2017. “Expecting to Be HIP: Hawkes Intensity Processes for Social Media Popularity.” In World Wide Web 2017, International Conference on, 1–9. WWW ’17. Perth, Australia: International World Wide Web Conferences Steering Committee. https://doi.org/10.1145/3038912.3052650.
Shoukri, M. M., and P. C. Consul. 1987. “Some Chance Mechanisms Generating the Generalized Poisson Probability Models.” In Biostatistics, edited by Ian B. MacNeill, Gary J. Umphrey, Allan Donner, and V. Krishna Jandhyala, 259–68. Dordrecht: Springer Netherlands. http://link.springer.com/10.1007/978-94-009-4794-8_15.
Sibuya, Masaaki, Norihiko Miyawaki, and Ushio Sumita. 1994. “Aspects of Lagrangian Probability Distributions.” Journal of Applied Probability 31: 185–97. https://doi.org/10.2307/3214956.
TANNER, J. C. 1961. “A Derivation of the Borel Distribution.” Biometrika 48 (1-2): 222–24. https://doi.org/10.1093/biomet/48.1-2.222.

No comments yet. Why not leave one?

GitHub-flavored Markdown & a sane subset of HTML is supported.