Stabilization Time for a Type of Evolution on Binary Strings

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 ] .