×
Olvera-Cravioto, Mariana

Convergence of the population dynamics algorithm in the Wasserstein metric. (English) Zbl 1441.60053

Electron. J. Probab. 24, Paper No. 61, 27 p. (2019).
The author is interested in weighted branching processes as solutions of stochastic fixed-point equations in distribution (SFPE) of the form \(R \stackrel{\mathcal D}= \Phi(Q,N,\{C_i\},\{R_i\})\), where \((Q,N,\{C_i\}\) is a random vector of real-valued elements, \(N\) a natural number, and \(\{R_i\}\) a sequence of i.i.d. copies of \(R\), independent of \((Q,N,\{C_i\})\). In case of non-uniqueness these solutions can be characterized by the only attracting one among them, which can thus be constructed by iterating the SFPE. The focus here is on the “population dynamics algorithm” described in [M. Mézard and A. Montanari, Information, physics and computation. Oxford: Oxford University Press (2009; Zbl 1163.94001)]. Using an iterative bootstrap technique, it is superior to naïve Monte Carlo methods. However, as the samples thus obtained are neither independent nor exactly distributed according to the target distribution, convergence of the algorithm must be investigated. On the basis of Lipschitz conditions and suitable boundedness assumptions, the author proves convergence in the Wasserstein metric [C. Villani, Optimal transport. Old and new. Berlin: Springer (2009; Zbl 1156.53003)] of order \(p\geq 1\). She also shows consistency of the estimators based on the sample pool produced by the algorithm. Illustrating the broad spectrum of applications, four explicit examples are given: The linear SFPE or “smoothing transform”, the maximum SFPE or “high order Lindley equation”, the discounted tree-sum SFPE, and the “free-entropy” SFPE. For further examples the reader is referred to [G. Alsmeyer et al., Ann. Probab. 40, No. 5, 2069–2105 (2012; Zbl 1266.39022)].
Reviewer: Heinrich Hering (Rockenberg)

Cited in 2 Documents

MSC:

60H25 Random operators and equations (aspects of stochastic analysis)
60J80 Branching processes (Galton-Watson, birth-and-death, etc.)

Keywords:

population dynamics; weighted branching process; distributional fixed point equation; iteration bootstrap; Wasserstein metric

Citations:

Zbl 1163.94001; Zbl 1156.53003; Zbl 1266.39022
PDF BibTeX XML Cite
\textit{M. Olvera-Cravioto}, Electron. J. Probab. 24, Paper No. 61, 27 p. (2019; Zbl 1441.60053)
Full Text: DOI arXiv Euclid
  • logo of hbz
  • logo of WorldCat

References:

[1] M. Aebi, P. Embrechts, and T. Mikosch, Stochastic discounting, aggregate claims, and the bootstrap, Adv. Appl. Prob. 26 (1994), 183-206. · Zbl 0807.62083
[2] D.J. Aldous and A. Bandyopadhyay, A survey of max-type recursive distributional equation, Annals of Applied Probability 15 (2005), no. 2, 1047-1110. · Zbl 1105.60012
[3] G. Alsmeyer, J.D. Biggins, and M. Meiners, The functional equation of the smoothing transform, Ann. Probab. 40 (2012), no. 5, 2069-2105. · Zbl 1266.39022
[4] G. Alsmeyer and P. Dyszewski, Thin tails of fixed points of the nonhomogeneous smoothing transform, Stochastic Processes and their Applications 127 (2017), no. 9, 3014-3041. · Zbl 1372.60095
[5] G. Alsmeyer and M. Meiners, Fixed points of inhomogeneous smoothing transforms, J. Differ. Equ. Appl. 18 (2012), no. 8, 1287-1304. · Zbl 1275.60019
[6] G. Alsmeyer and M. Meiners, Fixed points of the smoothing transform: Two-sided solutions, Probab. Theory Rel. 155 (2013), no. 1-2, 165-199. · Zbl 1279.60026
[7] K.B. Athreya, Discounted branching random walks, Advances in Applied Probability 17 (1985), 53-66. · Zbl 0561.60089
[8] J.D. Biggins, Lindley-type equations in the branching random walk, Stochastic Process. Appl. 75 (1998), 105-133.
[9] S. Bobkov and M. Ledoux, One-dimensional empirical measures, order statistics, and Kantorovich transport distances, To appear in Memoirs of the American Mathematical Society (2017).
[10] N. Chen, N. Litvak, and M. Olvera-Cravioto, Generalized PageRank on directed configuration networks, Random Structures & Algorithms 51 (2017), no. 2, 237-274. · Zbl 1370.05199
[11] N. Chen and M. Olvera-Cravioto, Efficient simulation for branching linear recursions, Proceedings of the Winter Simulation Conference 2015 (Huntington Beach, CA), 2015, pp. 2716-2727.
[12] E. del Barrio, E. Giné, and C. Matrán, Central limit theorems for the Wasserstein distance between the empirical and the true distributions, Annals of Probability (1999), 1009-1071. · Zbl 0958.60012
[13] A. Dembo and A. Montanari, Ising models on locally tree-like graphs, Ann. Appl. Probab. 20 (2010), no. 2, 565-592. · Zbl 1191.82025
[14] L. Devroye, On the probabilistic worst-case time of FIND, Algorithmica 31 (2001), 291-303. · Zbl 1021.68030
[15] L. Devroye, J. Fill, and R. Neininger, Perfect simulation from the quicksort limit distribution, Electronic Communications in Probability 5 (2000), 95-99. · Zbl 0958.65012
[16] L. Devroye and R. Neininger, Density approximation and exact simulation of random variables that are solutions of fixed-point equations, Advances in Applied Probability 34 (2002), 441-468. · Zbl 1010.65002
[17] J.A. Fill and S. Janson, Approximating the limiting Quicksort distribution, Random Structures Algorithms 19 (2001), no. 3-4, 376-406. · Zbl 0990.68053
[18] N. Fournier and A. Guillin, On the rate of convergence in Wasserstein distance of the empirical measure, Probab. Theory Relat. Fields 162 (2015), 707-738. · Zbl 1325.60042
[19] A.M. Iksanov, Elementary fixed points of the BRW smoothing transforms with infinite number of summands, Stochastic Process. Appl. 114 (2004), 27-50. · Zbl 1081.60017
[20] S. Janson, On the tails of the limiting quicksort distribution, Electron. Commun. Probab. 20 (2015), no. 81, 1-7. · Zbl 1347.68107
[21] P.R. Jelenković and M. Olvera-Cravioto, Information ranking and power laws on trees, Adv. Appl. Prob. 42 (2010), no. 4, 1057-1093. · Zbl 1211.60026
[22] P.R. Jelenković and M. Olvera-Cravioto, Implicit renewal theorem for trees with general weights, Stochastic Process. Appl. 122 (2012), no. 9, 3209-3238. · Zbl 1258.60040
[23] P.R. Jelenković and M. Olvera-Cravioto, Implicit renewal theory and power tails on trees, Adv. Appl. Prob. 44 (2012), no. 2, 528-561. · Zbl 1253.60076
[24] P.R. Jelenković and M. Olvera-Cravioto, Maximums on trees, Stochastic Processes and their Applications 125 (2015), 217-232. · Zbl 1316.60131
[25] F.I. Karpelevich, M.Ya. Kelbert, and Yu.M. Suhov, Higher-order Lindley equations, Stochastic Process. Appl. 53 (1994), 65-96. · Zbl 0840.60084
[26] J. Lee and M. Olvera-Cravioto, PageRank on inhomogeneous random digraphs, ArXiv:1707.02492 (2017).
[27] Q. Liu, Fixed points of a generalized smoothing transformation and applications to the branching random walk, Adv. Appl. Prob. 30 (1998), 85-112. · Zbl 0909.60075
[28] M. Maślanka, Tail asymptotics of maximums on trees in the critical case, Electr. Commun. Probab. 23 (2018), 1-11.
[29] M. Mezard and A. Montanari, Information, physics, and computation, Oxford University Press, 2009. · Zbl 1163.94001
[30] M. Olvera-Cravioto and O. Ruiz-Lacedelli, Parallel queues with synchronization, ArXiv:1501.00186 (2014).
[31] U. Rösler, A limit theorem for “Quicksort”, RAIRO Theor. Inform. Appl. 25 (1991), 85-100.
[32] U. Rösler and L. Rüschendorf, The contraction method for recursive algorithms, Algorithmica 29 (2001), no. 1-2, 3-33.
[33] C. Villani, Optimal transport, old and new, Springer, New York, 2009. · Zbl 1156.53003
[34] Y. Volkovich and N. Litvak, Asymptotic analysis for personalized web search, Adv. Appl. Prob. 42 (2010), no. 2, 577-604. · Zbl 1209.68180
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.