A survey of max-type recursive distributional equations

DOI10.1214/105051605000000142zbMath1105.60012arXivmath/0401388OpenAlexW2041345256MaRDI QIDQ558662

Antar Bandyopadhyay, David J. Aldous

Publication date: 13 July 2005

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

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

zbMATH Keywords

probability distributionfixed point equationprobabilistic analysis of algorithmscoupling from the pastbranching random walkcavity methodrandom matchingBranching processfrozen percolationmean-field model of distancemetric contractionprobability on trees

Mathematics Subject Classification ID

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

Related Items

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

Cites Work

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