This article is cited in
46 papers
Large deviations for Markov chains in the positive quadrant
A. A. Borovkov,
A. A. Mogul'skii Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences
Abstract:
The paper deals with so-called
$N$-partially space-homogeneous time-homogeneous Markov chains
$X(y,n)$,
$n=0,1,2,\dots$,
$X(y,0)=y$, in the positive quadrant
$\mathbb R^{2+}=\{x=(x_2,x_2):x_1\geqslant0,\ x_2\geqslant0\}$.
These Markov chains are characterized by the following property of the transition probabilities
$P(y,A)=\mathsf P(X(y,1)\in A)$:
for some $N\geqslant 0$ the measure $P(y,dx)$ depends only on $x_2$, $y_2$, and $x_1-y_1$ in the domain $x_1>N$, $y_1>N$, and only on $x_1$, $y_1$, and $x_2-y_2$ in the domain $x_2>N$, $y_2>N$.
For such chains the asymptotic behaviour of
$$
\ln\mathsf P\Bigl(\frac 1sX(y,n)\in B\Bigr), \qquad \ln\mathsf P\bigl(X(y,n)\in x+B\bigr)
$$
is found for a fixed set
$B$ as
$s\to\infty$,
$|x|\to\infty$, and
$n\to\infty$.
Some other conditions on the growth of parameters are also considered, for example,
$|x-y|\to\infty$,
$|y|\to\infty$. A study is made of the structure of the most probable trajectories, which give the main contribution to this asymptotics, and a number of other results pertaining to the topic are established.
Similar results are obtained for the narrower class of 0-partially homogeneous ergodic
chains under less restrictive moment conditions on the transition probabilities
$P(y,dx)$.
Moreover, exact asymptotic expressions for the probabilities
$\mathsf P(X(0,n)\in x+B)$ are found for 0-partially homogeneous ergodic chains under some additional conditions.
The interest in partially homogeneous Markov chains in positive octants is due to the mathematical aspects (new and interesting problems arise in the framework of general large
deviation theory) as well as applied issues, for such chains prove to be quite accurate mathematical models for numerous basic types of queueing and communication networks such as the widely known Jackson networks, polling systems, or communication networks associated with the ALOHA algorithm. There is a vast literature dealing with the analysis of these objects.
The present paper is an attempt to find the extent to which an asymptotic analysis is possible for Markov chains of this type in their
general form without using any special properties of the specific applications mentioned above. It turns out that such an analysis is quite possible, though difficult, in the
two-dimensional case. However, even in the three-dimensional case one encounters new fundamental difficulties which, at the present state of the art, render the problem insoluble or at least extremely hard to solve.
UDC:
519.21
MSC: Primary
60F10,
60J10; Secondary
60G50,
60K25,
50K30 Received: 30.01.2000
DOI:
10.4213/rm398