Stabilization Time for a Type of Evolution on Binary Strings

Jacob Funk (), Mihai Nica () and Michael Noyes ()
Additional contact information
Jacob Funk: Department of Operations Research and Financial Engineering, Princeton University, Sherrerd Hall
Mihai Nica: Courant Institute of Mathematical Sciences
Michael Noyes: Department of Mathematics, Bard High School Early College

Journal of Theoretical Probability, 2015, vol. 28, issue 3, 848-865

Abstract: Abstract We consider a type of evolution on $$\{0,1\}^{n}$$ { 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$$ n - 1 steps, we will reach a string of the form $$11\cdots 1100\cdots 00$$ 11 ⋯ 1100 ⋯ 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$$ p and a 0 with probability $$1-p$$ 1 - p , then the stabilization time of a string in $$\{0,1\}^{n}$$ { 0 , 1 } n is a random variable with values in $$\{0,1,\ldots n-1\}$$ { 0 , 1 , … n - 1 } . We study the asymptotic behavior of this random variable as $$n\rightarrow \infty $$ n → ∞ , and we determine its limit distribution in the weak sense after suitable centering and scaling. When $$p \ne \frac{1}{2}$$ p ≠ 1 2 , the limit distribution is Gaussian. When $$p = \frac{1}{2}$$ p = 1 2 , the limit distribution is a $$\chi _3$$ χ 3 distribution. We also explicitly compute the limit distribution in a threshold setting where $$p=p_n$$ p = p n varies with $$n$$ n given by $$p_n = \frac{1}{2}+ \frac{\lambda / 2}{\sqrt{n}}$$ p n = 1 2 + λ / 2 n for $$\lambda > 0$$ λ > 0 a fixed parameter. This analysis gives rise to a one parameter family of distributions that fit between a $$\chi _3$$ χ 3 and a Gaussian distribution. The tools used in our arguments are a natural interpretation of strings in $$\{0,1\}^{n}$$ { 0 , 1 } n as Young diagrams, and a connection with the known distribution for the maximal height of a Brownian path on $$[0,1]$$ [ 0 , 1 ] .

Keywords: Interacting particle systems and their scaling limits; Weak limit theorems; Combinatorial probability; 60F05; 60K99; 60C05 (search for similar items in EconPapers)
Date: 2015
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10959-013-0515-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jotpro:v:28:y:2015:i:3:d:10.1007_s10959-013-0515-y

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10959

DOI: 10.1007/s10959-013-0515-y

Access Statistics for this article

Journal of Theoretical Probability is currently edited by Andrea Monica

More articles in Journal of Theoretical Probability from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().