A survey of max-type recursive distributional equations

DOI10.1214/105051605000000142zbMATH Open1105.60012arXivmath/0401388OpenAlexW2041345256MaRDI QIDQ558662FDOQ558662

Authors: David Aldous, Antar Bandyopadhyay 

Publication date: 13 July 2005

Published in: The Annals of Applied Probability (Search for Journal in Brave)

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),igeq 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)?

Full work available at URL: https://arxiv.org/abs/math/0401388

Recommendations

• Endogeny for the logistic recursive distributional equation
• On a linear recursive distributional equation
• A new characterization of endogeny
• On stochastic recursive equations of sum and max type
• Power laws on weighted branching trees

zbMATH Keywords

probability distributionprobabilistic analysis of algorithmsfixed point equationbranching random walkcoupling from the pastcavity methodrandom matchingBranching processfrozen percolationmean-field model of distancemetric contractionprobability on trees

Mathematics Subject Classification ID

Probability distributions: general theory (60E05) Characterization and structure theory of statistical distributions (62E10) Analysis of algorithms and problem complexity (68Q25) Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics (82B44)

Cites Work

• Title not available (Why is that?)
• Mass transportation problems. Vol. 1: Theory. Vol. 2: Applications
• Title not available (Why is that?)
• Percolation
• An Introduction to Metric Spaces and Fixed Point Theory
• Title not available (Why is that?)
• The asymptotic behavior of fragmentation processes
• The contraction method for recursive algorithms
• The \(\zeta(2)\) limit in the random assignment problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Chance and Stability
• Title not available (Why is that?)
• Diffusion-limited aggregation on a tree
• Martingale convergence in the branching random walk
• Chernoff's theorem in the branching random walk
• Discounted branching random walks
• Gibbs measures and phase transitions
• Iterated Random Functions
• Title not available (Why is that?)
• A proof of Parisi's conjecture on the random assignment problem
• Fixed points of the smoothing transformation
• The `birth-and-assassination' process
• Postulates for subadditive processes
• Asymptotic properties and absolute continuity of laws stable by random weighted mean.
• Limit theorems for the minimal position in a branching random walk with independent logconcave displacements
• On fixed points of Poisson shot noise transforms
• Limit distributions for minimal displacement of branching random walks
• Travelling-waves for the FKPP equation via probabilistic arguments
• A fixed point theorem for distributions
• Elementary fixed points of the BRW smoothing transforms with infinite number of summands
• Density approximation and exact simulation of random variables that are solutions of fixed-point equations
• The percolation process on a tree where infinite clusters are frozen
• On the value of a random minimum spanning tree problem
• Asymptotics in the random assignment problem
• Fixed points of a generalized smoothing transformation and applications to the branching random walk
• Martingales and profile of binary search trees
• Scaling and universality in continuous length combinatorial optimization
• Higher-order Lindley equations
• Lindley-type equations in the branching random walk
• Title not available (Why is that?)
• The Efficient Construction of an Unbiased Random Sequence
• A characterization of the set of fixed points of the quicksort transformation
• A Metropolis-type optimization algorithm on the infinite tree
• An assignment problem at high temperature
• On a Pitman-Yor problem
• The cavity method at zero temperature
• A surprising Poisson process arising from a species competition model.
• Fixed points with finite variance of a smoothing transformation.
• Cost-volume relationship for flows through a disordered network
• Greedy Search on the Binary Tree with Random Edge-Weights
• On the Critical Value for ‘Percolation’ of Minimum-Weight Trees in the Mean-Field Distance Model
• Title not available (Why is that?)
• Percolation–like scaling exponents for minimal paths and trees in the stochastic mean field model
• On the probabilistic worst-case time of ``find

Cited In (90)

• An exactly solvable continuous-time Derrida-Retaux model
• Gallager error-correcting codes for binary asymmetric channels
• The Derrida-Retaux conjecture on recursive models
• The densest subgraph problem in sparse random graphs
• Tail asymptotics of maximums on trees in the critical case
• Runoff on rooted trees
• Matchings on infinite graphs
• Belief propagation for optimal edge cover in the random complete graph
• Behavior near the extinction time in self-similar fragmentations. II: Finite dislocation measures.
• Phase transitions in semidefinite relaxations
• Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models
• Einstein relation for biased random walk on Galton-Watson trees
• Solutions to complex smoothing equations
• Minimal position and critical martingale convergence in branching random walks, and directed polymers on disordered trees
• Different aspects of a random fragmentation model
• Tail behavior of solutions of linear recursions on trees
• Determining Factors Behind the PageRank Log-Log Plot
• Stochastic fixed-point equations
• Recursive construction of continuum random trees
• The functional equation of the smoothing transform
• Kingman's model with random mutation probabilities: convergence and condensation. I
• Replica symmetry of the minimum matching
• A Stochastic Maximin Fixed-Point Equation Related to Game Tree Evaluation
• Regular variation of fixed points of the smoothing transform
• A necessary and sufficient condition for the tail-triviality of a recursive tree process
• Dynamics and endogeny for recursive processes on trees
• Endogeny for the logistic recursive distributional equation
• Local times of subdiffusive biased walks on trees
• The mean field traveling salesman and related problems
• Two-sided bounds for \(L_p\)-norms of combinations of products of independent random variables
• A simple method to find all solutions to the functional equation of the smoothing transform
• Linear stochastic equations in the critical case
• Implicit renewal theory and power tails on trees
• The free energy in the Derrida-Retaux recursive model
• Ergodicity of a bounded Markov chain with attractiveness towards the centre
• Recursive equations for the predictive distributions of some determinantal processes
• Convergence of the population dynamics algorithm in the Wasserstein metric
• Random recurrence equations and ruin in a Markov-dependent stochastic economic environment
• A binary embedding of the stable line-breaking construction
• Self-similar real trees defined as fixed points and their geometric properties
• Singularity analysis via the iterated kernel method
• Maximums on trees
• Fixed points of the smoothing transform: two-sided solutions
• Bootstrap percolation in living neural networks
• Frozen percolation on the binary tree is nonendogenous
• Stationary waiting time in parallel queues with synchronization
• A stochastic fixed point equation for weighted minima and maxima
• On stochastic recursive equations of sum and max type
• Weighted enumeration of spanning subgraphs in locally tree-like graphs
• Convergence rates in the implicit renewal theorem on trees
• Lines of descent in the deterministic mutation-selection model with pairwise interaction
• Recursive tree processes and the mean-field limit of stochastic flows
• The endpoint distribution of directed polymers
• Constructive Markov chains indexed by \(\mathbb Z\)
• Parking on a random tree
• On the freezing of variables in random constraint satisfaction problems
• Implicit renewal theorem for trees with general weights
• Smoothing equations for large Pólya urns
• Parking on supercritical Galton-Watson trees
• Title not available (Why is that?)
• A new characterization of endogeny
• Tightness for a family of recursion equations
• Limit theorems for random spatial drainage networks
• The Noisy Veto-Voter Model: A Recursive Distributional Equation on [0, 1]
• A max-type recursive model: some properties and open questions
• Quasi-equilibria and click times for a variant of Muller's ratchet
• A phase transition between endogeny and nonendogeny
• Central limit theorems for combinatorial optimization problems on sparse Erdős-Rényi graphs
• Rankings in directed configuration models with heavy tailed in-degrees
• Inverting the cut-tree transform
• The role of uncertainty in the design of sustainable and precautionary management strategies for fisheries
• Stationary random metrics on hierarchical graphs via \((\min,+)\)-type recursive distributional equations
• The phase diagram of Lévy spin glasses
• Importance sampling for maxima on trees
• The weighted branching process
• Regular variation in a fixed-point problem for single- and multi-class branching processes and queues
• Stochastic recursions on directed random graphs
• Probabilistic Relation between In-Degree and PageRank
• Weighted branching and a pathwise renewal equation
• Annihilation and coalescence on binary trees
• A recursive distributional equation for the stable tree
• Spectrum of Lévy-Khintchine random Laplacian matrices
• On a linear recursive distributional equation
• Thin tails of fixed points of the nonhomogeneous smoothing transform
• Minimax functions on Galton-Watson trees
• Asymptotically linear iterated function systems on the real line
• The sustainability probability for the critical Derrida-Retaux model
• All solutions of the stochastic fixed point equation of the Quicksort process
• The dual Derrida-Retaux conjecture
• Combinatorial games on Galton-Watson trees involving several-generation-jump moves

This page was built for publication: A survey of max-type recursive distributional equations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q558662)