Rank-driven Markov processes

DOI10.1007/S10955-011-0368-7MaRDI QIDQ664588zbMATH OpenOpenAlexFDO

Authors M. Grinfeld, Philip A. Knight, Andrew R. Wade

Publication date 2 March 2012

Published in Journal of Statistical Physics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1106.4194, http://dro.dur.ac.uk/10488/1/10488.pdf

zbMATH Keywords

phase transitioninteracting particle systemself-organized criticalityBak-Sneppen evolution modelMarkov process on order statistics

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Phase transitions (general) in equilibrium statistical mechanics (82B26) Interacting particle systems in time-dependent statistical mechanics (82C22)

Abstract: We study a class of Markovian systems of $N$ elements taking values in $[0,1]$ that evolve in discrete time $t$ via randomized replacement rules based on the ranks of the elements. These rank-driven processes are inspired by variants of the Bak--Sneppen model of evolution, in which the system represents an evolutionary 'fitness landscape' and which is famous as a simple model displaying self-organized criticality. Our main results are concerned with long-time large-$N$ asymptotics for the general model in which, at each time step, $K$ randomly chosen elements are discarded and replaced by independent $U[0,1]$ variables, where the ranks of the elements to be replaced are chosen, independently at each time step, according to a distribution $kapp{a}_N$ on ${1,2,\mathrm{...},N}^K$. Our main results are that, under appropriate conditions on $kapp{a}_N$, the system exhibits threshold behaviour at $s^{\ast }in[0,1]$, where $s^{\ast }$ is a function of $kapp{a}_N$, and the marginal distribution of a randomly selected element converges to $U[s^{\ast },1]$ as $toinfty$ and $Noinfty$. Of this class of models, results in the literature have previously been given for special cases only, namely the 'mean-field' or 'random neighbour' Bak--Sneppen model. Our proofs avoid the heuristic arguments of some of the previous work and use Foster--Lyapunov ideas. Our results extend existing results and establish their natural, more general context. We derive some more specialized results for the particular case where K=2. One of our technical tools is a result on convergence of stationary distributions for families of uniformly ergodic Markov chains on increasing state-spaces, which may be of independent interest.

Recommendations

• On rank driven dynamical systems
• A simple rank-based Markov chain with self-organized criticality
• Non-triviality of a discrete Bak--Sneppen evolution model
• Bak-Sneppen type models and coagulation-fragmentation processes
• Limit behavior of the Bak-Sneppen evolution model.

Cites work

• scientific article; zbMATH DE number 5159451 (Why is no real title available?)
• scientific article; zbMATH DE number 1190392 (Why is no real title available?)
• scientific article; zbMATH DE number 48363 (Why is no real title available?)
• scientific article; zbMATH DE number 1232095 (Why is no real title available?)
• scientific article; zbMATH DE number 3236503 (Why is no real title available?)
• A Markovian Function of a Markov Chain
• A survey of random processes with reinforcement
• Applied Probability and Queues
• Asymptotic behaviour of stationary distributions for countable Markov chains, with some applications
• Criteria for stochastic processes. II: Passage-time moments
• Critical thresholds and the limit distribution in the Bak-Sneppen model
• General Criteria of Integrability of Functions of Passage-Times for Nonnegative Stochastic Processes and Their Applications
• Hitting-time and occupation-time bounds implied by drift analysis with applications
• Limit behavior of the Bak-Sneppen evolution model.
• Markov Chains and Stochastic Stability
• Maximal avalanches in the Bak-Sneppen model
• Passage-time moments for nonnegative stochastic processes and an application to reflected random walks in a quadrant
• The anisotropic Bak-Sneppen model
• The existence of moments for stationary Markov chains
• Topics in the Constructive Theory of Countable Markov Chains

Cited in

(12)

• A simple rank-based Markov chain with self-organized criticality
• On a local version of the Bak-Sneppen model
• Ranking policies in discrete Markov decision processes
• Bak-Sneppen backwards
• Convergence in a multidimensional randomized Keynesian beauty contest
• On rank driven dynamical systems
• Convergence in the \(p\)-contest
• A differential equation for the asymptotic fitness distribution in the Bak-Sneppen model with five species
• Tagged particle dynamics in stochastic ranking process
• Rank-to-rank embeddings, Laver tables, and Galton-Watson processes
• Rigorous upper bound for the discrete Bak-Sneppen model
• Asymptotic fitness distribution in the Bak-Sneppen model of biological evolution with four species

This page was built for publication: Rank-driven Markov processes

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