next up previous contents
Next: Queueing networks Up: Transient behaviour of Large Previous: Introduction

Stability and Euler limits

Main tools and problems

We consider random walks on the integer lattice tex2html_wrap_inline4372 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 tex2html_wrap_inline4376 , 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 tex2html_wrap_inline4380 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.




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 tex2html_wrap_inline4428 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.




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.

next up previous contents
Next: Queueing networks Up: Transient behaviour of Large Previous: Introduction

Fri Mar 20 16:01:06 MET 1998