Stabilization time for a type of evolution on binary strings

DOI10.1007/S10959-013-0515-YMaRDI QIDQ895894zbMATH OpenOpenAlexFDO

Authors Jacob Funk, Mihai Nica, Michael Noyes

Publication date 7 December 2015

Published in Journal of Theoretical Probability (Search for Journal in Brave)

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

zbMATH Keywords

interacting particle systemsscaling limitscombinatorial probabilitybinary stringsweak limit theoremsstabilization time

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Combinatorial probability (60C05)

Abstract: We consider a type of evolution on {0,1}^n which occurs in discrete steps whereby at each step, we replace every occurrence of the substring "01" by "10". After at most n-1 steps we will reach a string of the form 11..1100..11, which we will call a "stabilized" string and we call the number of steps required the "stabilization time". If we choose each bit of the string independently to be a 1 with probability p and a 0 with probability 1-p, then the stabilization time of a string in {0,1}^n is a random variable with values in 0,1,...,n-1}. We study the asymptotic behavior of this random variable as n goes to infinity and we determine its limit distribution after suitable centering and scaling . When p is not 1/2, the limit distribution is Gaussian. When p = 1/2, the limit distribution is a chi_3 distribution. We also explicitly compute the limit distribution in a threshold setting where p=p_n varies with n given by p_n = 1/2 + lambda / 2 sqrt{n} for lambda > 0 a fixed parameter. This analysis gives rise to a one parameter family of distributions that fit between a chi_3 and a Gaussian distribution. The tools used in our arguments are a natural interpretation of strings in {0,1}^n as Young diagrams, and a connection with the known distribution for the maximal height of a Brownian path on [0,1].

Recommendations

• Evolution of a random string: stabilization laws
• A stabilization law for two semi-infinite interacting strings of characters
• Probability and time to fixation of an evolving sequence
• Stabilization of generic trees of strings
• Time-asymptotic convergence rates towards the discrete evolutionary stable distribution
• Artificial Evolution
• Optimal decay rates for the stabilization of a string network
• Kolmogorov-Loveland stochasticity for finite strings
• scientific article; zbMATH DE number 508770
• Stochastic stability and time-dependent mutations

Cites work

• scientific article; zbMATH DE number 3664138 (Why is no real title available?)
• scientific article; zbMATH DE number 51724 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 1354815 (Why is no real title available?)
• Interacting particle systems. With a new postface.
• Non-equilibrium behaviour of a many particle process: Density profile and local equilibria
• One-dimensional Brownian motion and the three-dimensional Bessel process
• Shape fluctuations and random matrices

Cited in

(1)

• A stabilization law for two semi-infinite interacting strings of characters

This page was built for publication: Stabilization time for a type of evolution on binary strings

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