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((ξ_i,X_i),i\geq 1). Here (ξ_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 (ξ_i)?

Published at http://dx.doi.org/10.1214/105051605000000142 in the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (3)

• Percolation-like Scaling Exponents for Minimal Paths and Trees in the Stochastic Mean Field Model
• Bivariate Uniqueness and Endogeny for Recursive Distributional Equations : Two Examples
• Cost-volume relationships for flows through a disordered network

Cited by in corpus (73)

• Phase Transitions in Semidefinite Relaxations
• On the freezing of variables in random constraint satisfaction problems
• Tightness for a family of recursion equations
• On Bootstrap Percolation in Living Neural Networks
• The functional equation of the smoothing transform
• Singularity analysis via the iterated kernel method
• Random recurrence equations and ruin in a Markov-dependent stochastic economic environment
• Recurrence and transience for the frog model on trees
• Determining factors behind the PageRank log-log plot
• Gallager error correcting codes for binary asymmetric channels
• The phase diagram of Lévy spin glasses
• Parking on a random tree
• The densest subgraph problem in sparse random graphs
• A stochastic fixed point equation for weighted minima and maxima
• Fixed points of multivariate smoothing transforms with scalar weights
• Limit theory for the random on-line nearest-neighbour graph
• The critical density for the frog model is the degree of the tree
• The free energy in the Derrida--Retaux recursive model
• An exactly solvable continuous-time Derrida--Retaux model
• Parallel queues with synchronization
• Percolation-like Scaling Exponents for Minimal Paths and Trees in the Stochastic Mean Field Model
• The phase transition for parking on Galton--Watson trees
• A Necessary and Sufficient Condition for the Tail-Triviality of a Recursive Tree Process
• Efficient Simulation for Branching Linear Recursions
• Limit theorems for random spatial drainage networks
• Recovery thresholds in the sparse planted matching problem
• Convergence of multivariate belief propagation, with applications to cuckoo hashing and load balancing
• Tightness of LP via Max-product Belief Propagation
• A new characterization of endogeny
• A min-type stochastic fixed-point equation related to the smoothing transformation
• Belief propagation for optimal edge cover in the random complete graph
• The Derrida--Retaux conjecture on recursive models
• Replica Symmetry and Combinatorial Optimization
• Implicit Renewal Theorem for Trees with General Weights
• Lines of descent in the deterministic mutation-selection model with pairwise interaction
• Chaînes de Markov Constructives Indexées par Z
• Random tree recursions: which fixed points correspond to tangible sets of trees?
• The cavity method for counting spanning subgraphs subject to local constraints
• Matchings on infinite graphs
• Right-Most Position of a Last Progeny Modified Branching Random Walk
• Einstein relation for biased random walk on Galton--Watson trees
• Behavior near the extinction time in self-similar fragmentations II: Finite dislocation measures
• Fixed points of the smoothing transform: Two-sided solutions
• Cost-volume relationships for flows through a disordered network
• In-Degree and PageRank of Web pages: Why do they follow similar power laws?
• Pemantle's min-plus binary tree
• Local times of subdiffusive biased walks on trees
• Coupling on weighted branching trees
• Marketing in Random Networks
• Two-sided bounds for $L_p$-norms of combinations of products of independent random variables
• Annihilation and coalescence on binary trees
• Quasi-equilibria and click times for a variant of Muller's ratchet
• Thin tails of fixed points of the nonhomogeneous smoothing transform
• Localization and free energy asymptotics in disordered statistical mechanics and random growth models
• Different Aspects of a Model for Random Fragmentation Processes
• Belief propagation : an asymptotically optimal algorithm for the random assignment problem
• Personalized PageRank dimensionality and algorithmic implications
• Smoothing equations for large Pólya urns
• Prime chains and Pratt trees
• Counting without sampling. New algorithms for enumeration problems using statistical physics
• Dynamics and Endogeny for recursive processes on trees
• Combinatorial games on Galton-Watson trees involving several-generation-jump moves
• Finite-depth scaling and an exact Bernoulli-leaf identity for the min-plus process on the binary tree
• The sustainability probability for the critical Derrida-Retaux model
• A recursive distribution equation for the stable tree
• Cut-off method for endogeny of recursive tree processes
• Belief propagation for minimum weight many-to-one matchings in the random complete graph
• Bivariate Uniqueness and Endogeny for the Logistic Recursive Distributional Equation
• Linear stochastic equations in the critical case
• The area of a self-similar fragmentation
• Minimal position and critical martingale convergence in branching random walks, and directed polymers on disordered trees
• A Local Mean Field Analysis of Security Investments in Networks
• Tail behavior of solutions of linear recursions on trees