A Survey of Max-Type Recursive Distributional Equations

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 $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)$ ?

[Joint work with David J. Aldous]