Stabilization Time for a Type of Evolution on Binary Strings

Jacob Funk, Mihai Nica, Michael NoyesJournal of Theoretical Probability 2013 · DOI · arXiv

Abstract

This paper investigates the stabilization time of a deterministic evolution rule on binary strings, where every "01" pair is replaced by "10" at each discrete time step. We analyze the limit distribution of this stabilization time for random strings of length $n$ as $n \to \infty$. Our findings reveal a phase transition at bit density $p=1/2$, where the distribution shifts from Gaussian ($p > 1/2$) to a $\chi_3$ distribution ($p = 1/2$). We also characterize a one-parameter family of distributions that bridges these two regimes in the threshold setting.

Introduction

Consider a binary string of length $n$ composed of 0s and 1s. We define an evolution process where, at each discrete time step, every occurrence of the substring "01" is simultaneously replaced by "10". This process continues until no "01" substrings remain, resulting in a sorted string where all 1s precede all 0s (e.g., 11...100...0).

The stabilization time, denoted $T_n^p$, is the number of steps required to reach this stable state. When the initial string is random—with each bit being a 1 with probability $p$—$T_n^p$ becomes a random variable. This problem intersects with combinatorics, specifically the study of Young diagrams, and statistical mechanics, relating to exclusion processes.

Methodology

The analysis proceeds through several key transformations:

Geometric Mapping to Young Diagrams

The authors first establish a bijection between binary strings and Young diagrams. A binary string can be viewed as a path on a grid; the area "above" this path corresponds to a Young diagram $Y$. The stabilization time is proven to be exactly equal to the "depth" of this diagram.

Mapping a binary string to a Young diagram $Y$

Random Walk Translation

For strings starting with 0 and ending with 1, the stabilization time can be mapped to a one-dimensional random walk $S_k$. Specifically, the time is related to the maximum value of the walk relative to its endpoint: $T \approx \max(S_k) - \frac{1}{2}S_n$. This allows the use of probabilistic tools designed for random walks.

Visualizing the path $\pi(\omega)$ and its corresponding random walk $S(\omega)$

Diffusion Limits and Change of Measure

To find the limit distribution as $n \to \infty$, the discrete random walk is approximated by continuous Brownian motion using Donsker’s Theorem. For the critical threshold where $p \approx 1/2$, the Girsanov Theorem is applied to calculate the density by treating the process as Brownian motion with a specific drift $\lambda$.

Key Results and Insights

The study identifies three distinct regimes for the scaled stabilization time:

  1. Gaussian Regime ($p > 1/2$): When 1s are more frequent, the law of large numbers dominates. The stabilization time, after centering and scaling, converges to a standard Gaussian distribution $N(0, p(1-p))$.
  2. Critical Regime ($p = 1/2$): At the point of maximum uncertainty, the distribution shifts to a $\chi_3/2$ distribution. The explicit density is given by $f(x) = \frac{8\sqrt{2}}{\sqrt{\pi}}x^2 e^{-2x^2}$.
  3. Threshold Bridge: By setting $p = \frac{1}{2} + \frac{\lambda}{2\sqrt{n}}$, the authors identify a family of distributions $\nu_\lambda$ with density: $$d\nu_\lambda(x) = \frac{4\sqrt{2}}{\lambda\sqrt{\pi}} e^{-\frac{1}{2}\lambda^2} \sinh(2\lambda x) x e^{-2x^2} dx$$ This formula successfully recovers the $\chi_3$ density as $\lambda \to 0$ and the Gaussian density as $\lambda \to \infty$.

Conclusion

This work provides a rigorous characterization of the stabilization time for a simple yet fundamental sorting evolution. The discovery of the $\nu_\lambda$ family provides a complete picture of the phase transition at $p=1/2$. Future research could extend these results to continuous-time processes like the Asymmetric Simple Exclusion Process (ASEP) or explore similar dynamics in higher-dimensional grids.

Summary updated

BibTeX
@article{funk2013stabilization,
  author = {Jacob Funk and Mihai Nica and Michael Noyes},
  title = {{Stabilization Time for a Type of Evolution on Binary Strings}},
  journal = {Journal of Theoretical Probability},
  year = {2013},
  doi = {10.1007/s10959-013-0515-y},
}
Figure