|
Article Excerpt
We consider a constrained homogeneous random walk in [Z.sup.d.sub.+]. Such random walks are used to model various stochastic processes, most importantly multiclass Markovian queueing networks operating under state-dependent scheduling policies. These applications motivate the need to compute various performance measures, including stationary probability distributions and large deviations rates. In this paper, we show that computing the stationary probability distributions exactly is an algorithmically undecidable problem. That is no algorithm can possibly exist to solve this task. The problem remains undecidable even if a linear Lyapunov function that verifies positive recurrence of the underlying random walk is available as a part of the input. We then prove that computing large deviation rates for this model is also an undecidable problem. Specifically, we show that it is an undecidable problem to determine finiteness of large deviations rates.
Key words: positive recurrence; Lyapunov functions; undecidability
1. Introduction. The model considered in this paper is a constrained homogeneous random walk in a d-dimensional nonnegative orthant [Z.sup.d.sub.+], where [Z.sup.d.sub.+] is the space of d-dimensional vectors with integer nonnegative components. In this model, the transitions occur only between states separated by an [[parallel]*[parallel].sub.max] distance at most 1, and the transition probabilities depend only on the face in which the current state resides, not on the magnitude of its components. This model was introduced by Malyshev [26, 27, 28] and Menshikov [30], and, ever since, random walks in [Z.sup.d.sub.+] have assumed a prominent role in modeling and analysis of queueing networks of certain types, for example Markovian multiclass queueing networks. The problems of obtaining the conditions for positive recurrence (stability) and computing large deviation rates were analyzed in a variety of papers (Ignatiouk-Robert [18, 19], Ignatyuk and Malyshev [20], Ignatyuk et al. [21], Fayolle [13], Malyshev [26, 27, 28, 29]).
A comprehensive study of constrained random walks in [Z.sup.d.sub.+] was conducted by Fayolle et al. in their book [14], and many additional results appeared after that book was published. A connection between constrained random walks and general dynamical systems on compact manifolds was established by Malyshev [29]. Exact conditions for positive recurrence were obtained in Malyshev [27], Menshikov [30], and Ignatyuk and Malyshev [20] for the cases d = 2, 3, 4. The large deviations principle was established and the large deviations rates were computed for the case d = 2 and for homogeneous random walks in [Z.sub.+] x [Z.sup.d] for general d by Ignatyuk et al. in [21]. The computation of large deviations rates is quite involved, even for d = 2, and was left as an open problem for higher dimensions. Similar large deviations parameters were computed by Kurkova and Suhov [25] in a queueing model corresponding to a join-the-shortest queueing system. The questions of computing large deviations rates were considered in the contexts of both large deviations of processes and large deviations of stationary measures. Can large deviations rates be computed for an arbitrary homogeneous random walk in [Z.sup.d.sub.+]? One of the two main results is of the present paper is to show that this is an algorithmically nonresolvable problem.
Analysis of homogeneous random walks in [Z.sup.d.sub.+], that arise specifically in the context of multiclass queueing networks, became a subject of particularly active research efforts during the past two decades. Many interesting and deep results were established that connect stability of such queueing networks with the stability of corresponding fluid models, obtained by law of large numbers type of rescaling. This research direction was initiated in pioneering works by Rybko and Stolyar [34] and Dai [10], where it was shown that stability of a fluid model implies stability of the underlying queueing system. The converse of this result is not true in general--see Dai et al. [12], Bramson [9]--but is true under some stronger conditions--Dai [11], Meyn [31]. Despite these results, no full characterization of stable queueing networks was known prior to Gamarnik [15] and Bertsimas et al. [3]. Specifically, it was shown by the author in Gamarnik [15] that stability property of constrained random walks in [L.sup.d.sub.+], as well as of queueing systems operating under a certain class of so-called generalized priority policies, is an undecidable property. Recently, the result was significantly strengthened by establishing undecidability results for the class of multiclass queueing networks operating under static buffer priority type scheduling policies (Bertsimas et al. [3]).
The question of computing stationary distributions comes naturally after the question of stability. Several results are available again in the context of multiclass queueing networks. Some of the results were obtained using quadratic Lyapunov functions (Bertsimas et al. [5], Kumar and Kumar [24], Kumar and Meyn [23]), using piecewise linear Lyapunov functions (Bertsimas et al. [4]), and using more-direct methods (Bertsimas and Nino-Mora [1, 2]). However, all of the results obtain only bounds on the stationary probabilities. Computing the stationary probabilities exactly seems beyond the existing techniques, outside of a class of product form--type networks, where the stationary probabilities are expressed in a simple way through the parameters of the network. Can stationary probability distributions be computed in general for homogeneous random walks in [Z.sup.d.sub.+]? The answer is negative, and this is the second main result of the present paper.
2. Our results. It was established by the author in [15] that positive recurrence of a constrained homogeneous random walk in [Z.sup.d.sub.+] is an undecidable property. In other words, no algorithm can exist that, given the description of a random walk (the set of 2d transition matrices corresponding to [2.sup.d] faces of [Z.sup.d.sub.+]) determines whether the walk is or is not positive recurrent. This result was also established for queueing systems operating under the class of so-called generalized priority policies that was also introduced in Gamarnik [15]. This result explains the difficulty in obtaining exact characterization of stable random walks in [Z.sup.d.sub.+] and queueing systems.
In the current paper, we continue the decidability analysis of constrained random walks by asking the following questions: given a constrained homogeneous random walk in [Z.sup.d.sub.+], can we compute its stationary distribution and can we compute large deviations rates? To put these questions into a proper computation theoretic framework, we pose the following corresponding decision problems: given a constrained homogeneous random walk, that possesses a unique stationary distribution [pi]; given a state q [member of] [Z.sup.d.sub.+], (for example q = 0); and given a rational value r > 0, determine whether the stationary probability [pi](q) corresponding to this state satisfies [pi](q) [less than or equal to] r. Similarly, given a constrained homogeneous random walk, that possesses a unique stationary distribution [pi]; given a vector v [member of] [R.sup.d.sub.+]; and given a rational value r < 0, determine whether
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (1)
provided this limit exists. Here we let [??]x[??] = ([??] [x.sub.1][??], ..., [??][x.sub.d][??]) for any x [memberof] [R.sup.d]. Limit (1) is called the large deviation rate in the direction v and it is an important object in the analysis of random walks. As we mentioned in the previous paragraph, even existence of a stationary distribution is an undecidable property. However, in some cases, positive recurrence can be checked by constructing a suitable Lyapunov function. Can this Lyapunov function provide some help in computing the stationary distribution? We establish in this paper that the decision problems [pi](q) [less than or equal to] r, L(v) [less than or equal to] r are undecidable. These problems remain undecidable even if a simple linear-type Lyapunov function witnessing positive recurrence is available as a part of the input. For the problem of computing large deviations rates, we even show that distinguishing the case L(v) < [infinity]...
|
