Student Probability Seminar

Stabilization Time for a Type of Evolution on Binary Strings

Speaker: Mihai Nica

Location: Warren Weaver Hall 1314

Date: Thursday, March 14, 2013, 3:30 p.m.

Synopsis:

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