Deterministic walks in random media: evidence of generic scale invariance

Deterministic walks over a random set of points in one and two dimensions (d=1,2) are considered. Points (cities'') are randomly scattered in R^d following a uniform distribution. A walker (a tourist’‘), at each time step, goes to the nearest neighbor city that has not been visited in the past \tau steps. Each initial city leads to a trajectory composed of a transient part and a final p-cycle attractor. The distribution of transient times, p-cycles and number of cities per attractor are studied. It is shown numerically that transient times (for d=1,2) follow a Poisson law with a $\tau$ dependent decay but the density of p-cycles follows a power law D(p) \propto p^{-\alpha(\tau)} for d=2. For large \tau, the expoent tends to \alpha ~ 5/2. Some analytical results are given for the d=1 case. Since the power law is robust and does not depend on free parameters, this system presents ``generic scale invariance’'. Applications to animal exploratory behavior and other local minimization problems are suggested.