Deterministic Walks in Random Media

Abstract

Deterministic walks over a random set of $N$ points in one and two dimensions ( $d\phantom{\rule{0ex}{0ex}}=\phantom{\rule{0ex}{0ex}}1,2$) are considered. Points (``cities'') are randomly scattered in ${\mathbf{R}}^{d}$ following a uniform distribution. A walker (``tourist''), at each time step, goes to the nearest neighbor city that has not been visited in the past $\ensuremath{\tau}$ steps. Each initial city leads to a different trajectory composed of a transient part and a final $p$-cycle attractor. Transient times (for $d\phantom{\rule{0ex}{0ex}}=\phantom{\rule{0ex}{0ex}}1,2$) follow an exponential law with a $\ensuremath{\tau}$-dependent decay time but the density of $p$ cycles can be approximately described by $D(p)\ensuremath{\propto}{p}^{\ensuremath{-}\ensuremath{\alpha}(\ensuremath{\tau})}$. For $\ensuremath{\tau}\ensuremath{\gg}1$ and $\ensuremath{\tau}/N\ensuremath{\ll}1$, the exponent is independent of $\ensuremath{\tau}$. Some analytical results are given for the $d\phantom{\rule{0ex}{0ex}}=\phantom{\rule{0ex}{0ex}}1$ case.