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