×

Stabilization time for a type of evolution on binary strings. (English) Zbl 1334.60018

Summary: 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\dots 1100\dots 00\), 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,\dots,n-1\}\). We study the asymptotic behavior of this random variable as \(n\to\infty\), and we determine its limit distribution in the weak sense after suitable centering and scaling. When \(p\neq\frac{1}{2}\), the limit distribution is Gaussian. When \(p=\frac{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=\frac{1}{2}+\frac{\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]\).

MSC:

60F05 Central limit and other weak theorems
60K35 Interacting random processes; statistical mechanics type models; percolation theory
60C05 Combinatorial probability
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Billingsley, P.: Convergence of Probability Measures. Wiley, London (1999) · Zbl 0944.60003 · doi:10.1002/9780470316962
[2] Johansson, K.: Shape fluctuations and random matrices. Commun. Math. Phys. 209, 437-476 (2000) · Zbl 0969.15008 · doi:10.1007/s002200050027
[3] Karatzas, I., Shreve, S.E.: Brownian Motion and Stochastic Calculus. Springer, Berlin (1998) · Zbl 0734.60060 · doi:10.1007/978-1-4612-0949-2
[4] Liggett, T.M.: Interacting Particle Systems. Springer, Berlin (2005) · Zbl 1103.82016
[5] Pitman, J.W.: One-dimensional Brownian motion and the three-dimensional Bessel process. Adv. Appl. Probab. 7, 511-526 (1975) · Zbl 0332.60055 · doi:10.2307/1426125
[6] Rost, H.: Non-equilibrium behaviour of a many particle process: density profile and local equilibria. Zeitschrift fr Wahrscheinlichkeitstheorie und Verwandte Gebiete 58, 41-53 (1981) · Zbl 0451.60097 · doi:10.1007/BF00536194
[7] Stanley, R.P.: Enumerative Combinatorics, vol. 2. Cambridge University Press, Cambridge (1999) · Zbl 0928.05001 · doi:10.1017/CBO9780511609589
[8] Stroock, D.W., Varadhan, S.R.S.: Multidimensional Diffusion Processes. Springer, Berlin (1979) · Zbl 0426.60069
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.