Front Propagation in Flipping Processes
T. Antal, D. ben-Avraham, E. Ben-Naim, and P.L. Krapivsky
We study a directed flipping process that underlies the performance of
the random edge simplex algorithm. In this stochastic process, which
takes place on a one-dimensional lattice whose sites may be either
occupied or vacant, occupied sites become vacant at a constant rate
and simultaneously cause all sites to the right to change their state.
This random process exhibits rich phenomenology. First, there is a
front, defined by the position of the left-most occupied site, that
propagates at a nontrivial velocity. Second, the front involves a
depletion zone with an excess of vacant sites. The total excess
$\Delta_k$ increases logarithmically, $\Delta_k \simeq \ln k$, with
the distance $k$ from the front. Third, the front exhibits
rejuvenation --- young fronts are vigorous but old fronts are
sluggish. We investigate these phenomena using a quasi-static
approximation, direct solutions of small systems, and numerical
simulations.
source,
ps,
pdf