A survey of max-type recursive distributional equations
Top Cited Papers
- 1 May 2005
- journal article
- Published by Institute of Mathematical Statistics in The Annals of Applied Probability
- Vol. 15 (2) , 1047-1110
- https://doi.org/10.1214/105051605000000142
Abstract
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 . Here (ξi) and g(⋅) are given and the Xi are independent copies of the unknown distribution X. We survey this area, emphasizing examples where the function g(⋅) is essentially a “maximum” or “minimum” function. We draw attention to the theoretical question of endogeny: in the associated recursive tree process Xi, are the Xi measurable functions of the innovations process (ξi)?Keywords
All Related Versions
This publication has 53 references indexed in Scilit:
- A proof of Parisi’s conjecture on the random assignment problemProbability Theory and Related Fields, 2003
- An assignment problem at high temperatureThe Annals of Probability, 2003
- On the Probablistic Worst-Case Time of ``Find''Algorithmica, 2001
- Travelling-waves for the FKPP equation via probabilistic argumentsProceedings of the Royal Society of Edinburgh: Section A Mathematics, 1999
- Diffusion-limited aggregation on a treeProbability Theory and Related Fields, 1997
- Asymptotics in the random assignment problemProbability Theory and Related Fields, 1992
- Limit distributions for minimal displacement of branching random walksProbability Theory and Related Fields, 1991
- On the solution of the random link matching problemsJournal de Physique, 1987
- A replica analysis of the travelling salesman problemJournal de Physique, 1986
- The Efficient Construction of an Unbiased Random SequenceThe Annals of Mathematical Statistics, 1972