Stability and Euler limits

Main tools and problems

We consider random walks on the integer lattice that have a sufficiently homogeneous structure in the following sense: the jump probabilities from two points with the same number of zero coordinates, are the same. Let us denote the position of the random walk at time t by , when it starts at the point x.

To explain how the long run behaviour of the random walk can be understood by the LLN, we will discuss the example of the rw on in Figure 1a. If the rw starts at a point x sufficiently far away from the origin, then the position at time t is determined by a sum of independent and identically distributed random variables, provided t is small compared to x. Hence the LLN can be applied. More precisely, we consider the scaling where both time and space are scaled by the same factor. Then by the LLN we have the large space-time limit or Euler limit

with probability 1.

=1.00mm

0.2pt

The value p-q is called the drift. Figure 1b illustrates the path of the rw in the Euler limit, when p<q. It is almost trivial to understand that our rw is stable if p<q and unstable if p>q, but it should be proved formally. To this end, one can use Lyapunov functions, whose construction is based on this limit path [5]. The problem of 0-drift should be analysed by more refined methods based on the Central Limit Theorem (using diffusion approximations).

The case of a rw on is slightly more complicated. The Euler limit in the interior of the state space can be again obtained by the LLN. However, if the process starts at the boundary, then either it is left ultimately, or the process moves along it. By applying Birkhoff's ergodic theorem in the latter case, this drift is a composite of the expected jumpsizes from points in the interior and at the boundary, the respective weights being determined by the stationary distribution of a one-dimensional random walk (cf. [5]).

For the 2-dimensional rw, the Euler limit is still deterministic and it is also simple to distinguish between stability and instability. In higher dimensions new and interesting phenomena appear. Indeed, sufficiently general dynamical systems associated with these Euler limits arise from random walks. The most appealing of these phenomena are the following ones.

• Cyclicity. The Euler limit contains cyclic paths. Figure 2a is a null-recurrent random walk on , and Figure 2b is unstable.
  

  =.5mm

  .75pt

  

• Scattering. The Euler limit is non-deterministic. The simplest example is a rw on with drifts given in Figure 3. The rw starting at the point 0, will disappear with certain probabilities along one of the two paths starting at this point. Since in general there are only finitely many drift vectors (at most ), there are finitely many directions into which the process can disappear, and so our rws have a finite exit boundary.

=1mm

0.2pt

The following theoretical problems are of interest:

• existence of and convergence in probability to the Euler limit;
• characterisation of the properties of Euler paths that imply stability, instability and null-recurrence of the original rw.

Partial results exist for rws. Also for special rw type models results of this form exist, for example for queueing models (cf. [3]). The approach taken in the queueing literature is slightly different and will be discussed below.

In [6] we study these problems for so-called regular random walks. For the convergence proof we use inductive arguments: by assuming convergence to the Euler limit and exponential stability/instability of lower dimensional random walks and the existence of sufficiently nice Lyapunov functions, we prove the same property for random walks in a higher dimension. This long term project has started several years ago, but many problems in this work are still open.