Large deviations for Markov chains in the positive quadrant

A. A. Borovkov ; A. A. Mogul'skii

Trudy Matematicheskogo Instituta imeni V.A. Steklova, Tome 56 (2001) no. 5, pp. 803-916

Résumé

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.

Bibliographie

[1] R. Atar, P. Dupuis, Large Deviations and Queueing Networks: Methods for Rate Functions, Identification LCDS Technical Report, Brown University, 1998

[2] D. Bertsimas, I. Paschalidis, J. Tsitsiklis, “Large deviations analysis of the generalized processor sharing policy”, Queueing Systems, 32:4 (1999), 319–349 | DOI | MR | Zbl

[3] V. M. Blinovskij, R. L. Dobrushin, “Process level large deviations for a class of piecewise homogeneous random walks”, The Dynkin Festschrift: Markov Processes and Their Applications, ed. M. I. Freidlin, Birkha̋user, Boston, 1994, 1–59 | Zbl

[4] A. A. Borovkov, Ergodichnost i ustoichivost sluchainykh protsessov, Editorial URSS, M.; Institut matematiki SO RAN, Novosibirsk, 1999

[5] A. A. Borovkov, Teoriya veroyatnostei, Editorial URSS, M.; Institut matematiki SO RAN, Novosibirsk, 1999

[6] A. A. Borovkov, “Novye predelnye teoremy v granichnykh zadachakh dlya summ nezavisimykh slagaemykh”, Sib. matem. zhurn., 3:5 (1962), 645–694 | MR | Zbl

[7] A. A. Borovkov, “O preobrazovanii Kramera, bolshikh ukloneniyakh v granichnykh zadachakh i uslovnom printsipe invariantnosti”, Sib. matem. zhurn., 36:3 (1995), 493–509 | MR | Zbl

[8] A. A. Borovkov, “Ob uslovnykh raspredeleniyakh, svyazannykh s bolshimi ukloneniyami”, Sib. matem. zhurn., 37:4 (1996), 732–744 | MR | Zbl

[9] A. A. Borovkov, “Skhodimost raspredelenii funktsionalov ot sluchainykh protsessov”, UMN, 33:1 (1978), 3–41 | MR

[10] A. A. Borovkov, “Granichnye zadachi dlya sluchainykh bluzhdanii i bolshie ukloneniya v funktsionalnykh prostranstvakh”, Teoriya veroyatn. i ee primen., 12:4 (1967), 635–654 | MR | Zbl

[11] A. A. Borovkov, D. A. Korshunov, “Veroyatnosti bolshikh uklonenii dlya odnomernykh tsepei Markova, I”, Teoriya veroyatn. i ee primen., 41:1 (1996), 3–30 | MR | Zbl

[12] A. A. Borovkov, D. A. Korshunov, “Veroyatnosti bolshikh uklonenii dlya odnomernykh tsepei Markova, II”, Teoriya veroyatn. i ee primen., 45:3 (2000), 437–468 | MR | Zbl

[13] A. A. Borovkov, A. A. Mogulskii, “Integro-lokalnye predelnye teoremy dlya summ sluchainykh vektorov, vklyuchayuschie bolshie ukloneniya, I”, Teoriya veroyatn. i ee primen., 43:1 (1998), 3–17 | MR | Zbl

[14] A. A. Borovkov, A. A. Mogulskii, “Integro-lokalnye predelnye teoremy dlya summ sluchainykh vektorov, vklyuchayuschie bolshie ukloneniya, II”, Teoriya veroyatn. i ee primen., 45:1 (2000), 5–29 | MR | Zbl

[15] A. A. Borovkov, A. A. Mogulskii, “Bolshie ukloneniya i proverka statisticheskikh gipotez”, Trudy In-ta matematiki SO AN SSSR, 19, 1992 | MR

[16] A. A. Borovkov, A. A. Mogulskii, “Vtoraya funktsiya uklonenii i asimptoticheskie zadachi vosstanovleniya i dostizheniya granitsy dlya mnogomernykh bluzhdanii”, Sib. matem. zhurn., 37:4 (1996), 745–782 | MR | Zbl

[17] A. A. Borovkov, A. A. Mogulskii, “Large deviations for stationary Markov chains in quarter plane”, Abstracts of communications of the 23rd Conference on Stochastic Processes and their Applications, Singapore, 1995

[18] A. A. Borovkov, A. A. Mogulskii, “Large deviations for stationary Markov chains in quarter plane”, Proc. of the Seventh Japan-Russia Symposium on Probability Theory and Mathematical Statistics (Tokyo, 1995), eds. S. Watanabe et al., World Scientific, Singapore, 1996, 12–19 | MR | Zbl

[19] A. A. Borovkov, A. A. Mogulskii, A. A. Sakhanenko, “Predelnye teoremy dlya sluchainykh protsessov”, Itogi nauki i tekhniki. Sovr. probl. matem. Fund. napr., 82, VINITI, M., 1995

[20] R. L. Dobrushin, E. A. Pechersky, “Large deviations for random processes with independent increments on infinite intervals”, Probability Theory and Mathematical Statistics, Lectures presented at the semester (St. Petersburg, Russia, March 2–April 23, 1993), eds. I. A. Ibragimov et al., Gordon Breach, Amsterdam, 1996, 41–74 | MR | Zbl

[21] R. L. Dobrushin, E. A. Pechersky, “Large deviations for tandem queueing systems”, J. Appl. Math. Stochastic Anal., 7 (1995), 301–330 | DOI | MR

[22] P. Dupuis, R. Ellis, “Large deviations for Markov processes with discontinuous statistics. II: Random walks”, Probab. Theory Relat. Fields, 91 (1992), 153–194 | DOI | MR | Zbl

[23] P. Dupuis, R. Ellis, “The large deviations principle for a general class of queueing systems, I”, Trans. Amer. Math. Soc., 348:8 (1995), 2689–2751 | DOI | MR

[24] P. Dupuis, R. Ellis, A Weak Convergence Approach to the Theory of Large Deviations, Willey, Chichester, 1997 | Zbl

[25] P. Dupuis, H. Ishii, H. M. Soner, “A viscosing solution approach to the asymptotic analysis of queueing systems”, Ann. Probab., 18 (1990), 226–255 | DOI | MR | Zbl

[26] G. Fayolle, V. A. Malyshev, M. V. Menshikov, Topics in the Constructive Theory of Countable Markov Chains, Cambridge Univ. Press, Cambridge, 1995 | Zbl

[27] A. Ganesh, V. Anantharam, “Stationary tail probabilities in exponential server tandems with renewal arrivals”, Queueing Systems, 22:3–4 (1996), 203–247 | DOI | MR | Zbl

[28] I. Ignatiouk-Robert, “Large deviations of Jackson network”, Ann. Appl. Probab., 10:3 (2000), 962–1001 | DOI | MR | Zbl

[29] I. A. Ignatyuk, V. A. Malyshev, V. V. Scherbakov, “Vliyanie granits v zadachakh o bolshikh ukloneniyakh”, UMN, 49:2 (1995), 43–102 | MR

[30] K. Majewski, “Heavy traffic approximations of large deviations of feedforward queueing networks”, Queueing Systems, 28:1–3 (1998), 125–155 | DOI | MR | Zbl

[31] K. Majewski, “Large deviations on the steady-state distribution of reflected processes with applications to queueing systems”, Queueing Systems, 29:2–4 (1998), 351–381 | DOI | MR | Zbl

[32] S. P. Meyn, R. L. Tweedie, Markov Chains and Stochastic Stability, Springer-Verlag, Berlin, 1993 | Zbl

[33] A. A. Mogulskii, “Veroyatnosti bolshikh uklonenii dlya sluchainykh bluzhdanii”, Trudy In-ta matematiki SO AN SSSR, 3, 1983, 93–124 | MR

[34] A. A. Mogulskii, “Bolshie ukloneniya dlya mnogomernykh sluchainykh bluzhdanii”, Teoriya veroyatn. i ee primen., 21:2 (1976), 309–323 | MR | Zbl

[35] A. A. Mogulskii, B. A. Rogozin, “Sluchainye bluzhdaniya v polozhitelnom kvadrante. I: Lokalnye teoremy”, Matematicheskie trudy, 2:2 (1999), 57–97 | MR | Zbl

[36] A. A. Mogulskii, B. A. Rogozin, “Sluchainye bluzhdaniya v polozhitelnom kvadrante. II: Integralnye teoremy”, Matematicheskie trudy, 3:1 (2000), 48–118 | MR | Zbl

[37] E. Nummelin, Obschie neprivodimye tsepi Markova i neotritsatelnye operatory, Mir, M., 1989

[38] N. O'Connell, “Large deviations for departures from a shared buffer”, J. Appl. Probab., 34 (1997), 753–766 | DOI | MR | Zbl

[39] A. Puhalskii, “Moderate deviations for queues in critical loading”, Queueing Systems, 31:3–4 (1999), 359–392 | DOI | MR | Zbl

[40] A. Shwartz, A. Weiss, Large Deviations for Performance Analysis, Queues Communication and Computing, Chapman Hall, London, 1995 | Zbl

[41] A. V. Skorokhod, “Predelnye teoremy dlya sluchainykh protsessov”, Teoriya veroyatn. i ee primen., 1:2 (1956), 289–319 | MR

[42] S. R. S. Varadhan, “Asymptotic probabilities and differential equations”, Comm. Pure Appl. Math., 19:3 (1966), 261–286 | DOI | MR | Zbl

[43] A. D. Venttsel, Predelnye teoremy i bolshie ukloneniya dlya markovskikh sluchainykh protsessov, Nauka, M., 1986 | Zbl

[44] T. Zajik, “Rough asymptotics for tandem non-homogeneous $M/G/\infty$ queues via Poissonized empirical processes”, Queueing Systems, 29 (1998), 161–174 | DOI | MR