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.
=.5mm
.75pt
0.2pt
The following theoretical problems are of interest:
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.