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 distribution fixed point equation probabilistic analysis of algorithms coupling from the past branching random walk cavity method random matching Branching process frozen percolation mean-field model of distance metric contraction probability 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