{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T03:11:16Z","timestamp":1649041876868},"reference-count":12,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIGMETRICS Perform. Eval. Rev."],"published-print":{"date-parts":[[2002,12]]},"abstract":"\n Our model is a constrained homogeneous random walk in\n Z<\/jats:italic>\n +<\/jats:sub>\n \n d<\/jats:italic>\n <\/jats:sc>\n . The convergence to stationarity for such a random walk can often be checked by constructing a Lyapunov function. The same Lyapunov function can also be used for computing approximately the stationary distribution of this random walk, using methods developed in [11]. In this paper we show that computing exactly the stationary probability for this type of random walks is an undecidable problem: no algorithm can exist to achieve this task. We then prove that computing large deviation rates for this model is also an undecidable problem. We extend these results to a certain type of queueing systems. The implication of these results is that no useful formulas for computing stationary probabilities and large deviations rates can exist in these systems.\n <\/jats:p>","DOI":"10.1145\/605521.605536","type":"journal-article","created":{"date-parts":[[2007,1,17]],"date-time":"2007-01-17T18:32:02Z","timestamp":1169058722000},"page":"38-40","source":"Crossref","is-referenced-by-count":0,"title":["Computing stationary probability distributions and large deviation rates for constrained random walks."],"prefix":"10.1145","volume":"30","author":[{"given":"David","family":"Gamarnik","sequence":"first","affiliation":[{"name":"IBM T.J. Watson Research Center, Yorktown Heights, NY"}]}],"member":"320","reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511984020"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.27.2.272.321"},{"key":"e_1_2_1_3_1","first-page":"129","article-title":"Classification of random walks in Z+d","volume":"12","author":"Ignatyuk I. A.","year":"1993","journal-title":"Selecta Mathematica"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1070\/RM1994v049n02ABEH002204"},{"key":"e_1_2_1_5_1","unstructured":"I. A. Kurkova and Yu. M. Suhov. Malyshev's theory and JS-queues. Asymptotics of stationary probabilities. Submitted 2001. I. A. Kurkova and Yu. M. Suhov. Malyshev's theory and JS-queues. Asymptotics of stationary probabilities. Submitted 2001."},{"issue":"6","key":"e_1_2_1_6_1","first-page":"1314","article-title":"Analytic method in the theoy of two-dimensional random walks","volume":"13","author":"Malyshev V. A.","year":"1972","journal-title":"Sib.Math.J."},{"key":"e_1_2_1_7_1","first-page":"526","article-title":"Classification of two-dimensional positive random walks and almost linear semimartingales","volume":"202","author":"Malyshev V. A.","year":"1972","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00967270"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.2307\/1427500"},{"key":"e_1_2_1_10_1","first-page":"755","article-title":"Ergodicity and transience conditions for random walks in the positive octant of space","volume":"217","author":"Menshikov M. V.","year":"1974","journal-title":"Soviet.Math.Dokl."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177004900"},{"key":"e_1_2_1_12_1","volume-title":"Chapman and Hall","author":"Shwartz A.","year":"1995"}],"container-title":["ACM SIGMETRICS Performance Evaluation Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/605521.605536","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,4]],"date-time":"2021-03-04T13:29:15Z","timestamp":1614864555000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/605521.605536"}},"subtitle":["the undecidability results."],"short-title":[],"issued":{"date-parts":[[2002,12]]},"references-count":12,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2002,12]]}},"alternative-id":["10.1145\/605521.605536"],"URL":"http:\/\/dx.doi.org\/10.1145\/605521.605536","relation":{},"ISSN":["0163-5999"],"issn-type":[{"value":"0163-5999","type":"print"}],"subject":["Computer Networks and Communications","Hardware and Architecture","Software"],"published":{"date-parts":[[2002,12]]}}}