A survey of max-type recursive distributional equations

By David J. Aldous, Antar Bandyopadhyay. 2004

245 citations recorded by the source corpus.

In certain problems in a variety of applied probability settings (from probabilistic analysis of algorithms to statistical physics), the central requirement is to solve a recursive distributional equation of the form X =^d g((\xi_i,X_i),i\geq 1). Here (\xi_i) and g(\cdot) are given and the X_i are independent copies of the unknown distribution X. We survey this area, emphasizing examples where the function g(\cdot) is essentially a ``maximum'' or ``minimum'' function. We draw attention to the theoretical question of endogeny: in the associated recursive tree process X_i, are the X_i measurable functions of the innovations process (\xi_i)?

Subfields: Artificial Intelligence, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/20efaeb14cbcfd9777907afca5425a7637a44291

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Zhan Shi
2. Gerold Alsmeyer
3. M. Meiners
4. Ofer Zeitouni
5. Johan Wästlund
6. J. Biggins
7. Yueyun Hu
8. Elie Aidékon

In Statistics and Probability

1. Zhan Shi
2. Ofer Zeitouni
3. Gerold Alsmeyer
4. M. Meiners
5. Maury Bramson
6. Johan Wästlund
7. J. Biggins
8. Yueyun Hu

Citations in the corpus

• TIGHTNESS FOR A FAMILY OF RECURSION EQUATIONS (2006, background): “(See [5] for a survey of recursions arising in these and similar contexts.”
• Fixed points of the smoothing transform: two-sided solutions (2010, background): “[23] and [1] and the references therein.”
• The mean field traveling salesman and related problems (2010, result): “See also [3, 4] for other results based on weak convergence.”
• Minimal position and critical martingale convergence in branching random walks, and directed polymers on disordered trees (2007, background): “See, for example, Bachmann [4] and Bramson and Zeitouni [14], as well as Section 5 of the survey paper by Aldous and Bandyopadhyay [2].”
• The functional equation of the smoothing transform (2009, methodology): “For further information we refer to the survey by Aldous and Bandyopadhyay [2].”