Hostname: page-component-78c5997874-xbtfd Total loading time: 0 Render date: 2024-11-05T16:38:37.794Z Has data issue: false hasContentIssue false
  • English
  • Français

Coupling on weighted branching trees

Part of: Stochastic analysis Markov processes Probability theory on algebraic and topological structures

Published online by Cambridge University Press:  10 June 2016

Ningyuan Chen  and
Mariana Olvera-Cravioto
Ningyuan Chen*
Affiliation:
Columbia University
Mariana Olvera-Cravioto*
Affiliation:
Columbia University
*
* Postal address: Industrial Engineering and Operations Research Department, Columbia University, 321 S. W. Mudd Building, 500 W. 120th Street, New York, NY 10027, USA.
* Postal address: Industrial Engineering and Operations Research Department, Columbia University, 321 S. W. Mudd Building, 500 W. 120th Street, New York, NY 10027, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper we consider linear functions constructed on two different weighted branching processes and provide explicit bounds for their Kantorovich–Rubinstein distance in terms of couplings of their corresponding generic branching vectors. Motivated by applications to the analysis of random graphs, we also consider a variation of the weighted branching process where the generic branching vector has a different dependence structure from the usual one. By applying the bounds to sequences of weighted branching processes, we derive sufficient conditions for the convergence in the Kantorovich–Rubinstein distance of linear functions. We focus on the case where the limits are endogenous fixed points of suitable smoothing transformations.

Keywords

Weighted branching processessmoothing transformcouplingKantorovich–Rubinstein distanceWasserstein distanceweak convergence

MSC classification

Primary: 60J80: Branching processes (Galton-Watson, birth-and-death, etc.)
Secondary: 60B10: Convergence of probability measures 60H25: Random operators and equations
Type
Research Article
Information
Advances in Applied Probability , Volume 48 , Issue 2 , June 2016 , pp. 499 - 524
Copyright
Copyright © Applied Probability Trust 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Alsmeyer, G. and Iksanov, A. (2009).A log-type moment result for perpetuities and its application to martingales in supercritical branching random walks.Electron. J. Prob. 14,289–313.Google Scholar
[2]Alsmeyer, G. and Meiners, M. (2012).Fixed points of inhomogeneous smoothing transforms.J. Differ. Equ. Appl. 18,1287–1304.Google Scholar
[3]Alsmeyer, G. and Meiners, M. (2013).Fixed points of the smoothing transform: two-sided solutions.Prob. Theory Relat. Fields 155,165–199.CrossRefGoogle Scholar
[4]Alsmeyer, G.,Biggins, J. D. and Meiners, M. (2012).The functional equation of the smoothing transform.Ann. Prob. 40,2069–2105.Google Scholar
[5]Bickel, P. J. and Freedman, D. A. (1981).Some asymptotic theory for the bootstrap.Ann. Statist. 9,1196–1217.CrossRefGoogle Scholar
[6]Biggins, J. D. (1977).Martingale convergence in the branching random walk.J. Appl. Prob. 14,25–37.Google Scholar
[7]Bollobás, B. (2001).Random Graphs,2nd edn.Cambridge University Press.Google Scholar
[8]Chen, N. and Olvera-Cravioto, M. (2013).Directed random graphs with given degree distributions.Stoch. Systems 3,147–186.Google Scholar
[9]Chen, N.,Litvak, N. and Olvera-Cravioto, M. (2014).Ranking algorithms on directed configuration networks. Preprint. Available at http://arxiv.org/abs/1409.7443.Google Scholar
[10]Durrett, R. (2010).Probability: Theory and Examples,4th edn.Cambridge University Press.Google Scholar
[11]Fill, J. A. and Janson, S. (2001).Approximating the limiting Quicksort distribution.Random Structures Algorithms 19,376–406.Google Scholar
[12]Iksanov, A. M. (2004).Elementary fixed points of the BRW smoothing transforms with infinite number of summands.Stoch. Process. Appl. 114,27–50.Google Scholar
[13]Iksanov, A. and Meiners, M. (2015).Fixed points of multivariate smoothing transforms with scalar weights.ALEA Latin Amer. J. Prob. Math. Statist. 12,69–114.Google Scholar
[14]Jelenković, P. R. and Olvera-Cravioto, M. (2010).Information ranking and power laws on trees.Adv. Appl. Prob. 42,1057–1093.Google Scholar
[15]Jelenković, P. R. and Olvera-Cravioto, M. (2012).Implicit renewal theorem for trees with general weights.Stoch. Process. Appl. 122,3209–3238.Google Scholar
[16]Liu, Q. (1998).Fixed points of a generalized smoothing transformation and applications to the branching random walk.Adv. Appl. Prob. 30,85–112.Google Scholar
[17]Liu, Q. (2000).On generalized multiplicative cascades.Stoch. Process. Appl. 86,263–286.Google Scholar
[18]Lyons, R. (1997).A simple path to Biggins' martingale convergence for branching random walk. In Classical and Modern Branching Processes,Springer,New York, pp.217–221.Google Scholar
[19]Neininger, R. (2001).On a multivariate contraction method for random recursive structures with applications to Quicksort.Random Structures Algorithms 19,498–524.Google Scholar
[20]Olvera-Cravioto, M. (2012).Tail behavior of solutions of linear recursions on trees.Stoch. Process. Appl. 122,1777–1807.Google Scholar
[21]Rösler, U. (1991).A limit theorem for ``Quicksort''.RAIRO Inf. Théor. Appl. 25,85–100.Google Scholar
[22]Rösler, U. and Rüschendorf, L. (2001).The contraction method for recursive algorithms.Algorithmica 29,3–33.Google Scholar
[23]van der Hofstad, R. (2014).Random graphs and complex networks. Preprint. Available at http://www.win.tue.nl/~rhofstad/NotesRGCN.html.Google Scholar
[24]van der Hofstad, R.,Hooghiemstra, G. and Van Mieghem, P. (2005).Distances in random graphs with finite variance degrees.Random Structures Algorithms 27,76–123.Google Scholar
[25]Villani, C. (2009).Optimal Transport: Old and New.Springer,Berlin.Google Scholar
[26]Volkovich, Y. and Litvak, N. (2010).Asymptotic analysis for personalized web search.Adv. Appl. Prob. 42,577–604.Google Scholar
[27]Williams, D. (1991).Probability with Martingales.Cambridge University Press.CrossRefGoogle Scholar