This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Gamarnik, D. Search for Related Content

On the Undecidability of Computing Stationary Distributions and Large Deviation Rates for Constrained Random Walks

MIT Sloan School of Management and Operations Research Center, Cambridge, Massachusetts 02139
gamarnik{at}mit.edu, http://www.mit.edu/gamarnik/home.html

We consider a constrained homogeneous random walk in ₊^d. 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
History: Received: August 26, 2003; revision received: December 12, 2005;