Frozen Random Walk

Tuesday, November 4, 2014 - 2:00pm - 3:00pm
Lind 305
Laura Florescu (New York University)
We explore a variant of the symmetric random walk on $\mathbb{Z}$ where particles are frozen if they are on the extreme quarter on any of the two sides. The motivation of this process arises from a theoretical computer science result related to the algorithm giving a 2 coloring of an $n$ set with all discrepancies less than $6 \sqrt{n}$. We are interested in the maximum of the process and the mass distribution. Related to this is a deterministic process where we start with mass $1$ at the origin, and at each step we freeze $1/2$ of the extremal mass and we split the remaining mass at each discrete point equally among its neighbors. Under the assumption that the scaled distribution converges, we determine the distribution, and the maximum $q\sqrt{t}$ where $q$ satisfies $\frac{1}{2}q^2=\frac{qe^{-q^2/2}}{\sqrt{2\pi}(\Phi(q)-\Phi(-q))}$. We present various simulation results supporting the claims of the existence of a scaling limit as well as the connection between the random and the deterministic process. We emphasize that in the deterministic case, the limit shape of the mass distribution is not a truncated Gaussian at the expected endpoints.

Joint work with Shirshendu Ganguly, Yuval Peres and Joel Spencer.