Detecting Block GI/M/1 and Block M/G/1 Matrices from Model Specifications

Steven Bersonl and Richard Muntz
Additional contact information
Steven Bersonl: UCLA, Computer Science Department
Richard Muntz: UCLA, Computer Science Department

Chapter 1 in Computations with Markov Chains, 1995, pp 1-19 from Springer

Abstract: Abstract Given a high level specification of a Markov chain, it is desirable to be able to determine if the state space of the Markov chain is finite. If the state space is finite, the entire transition matrix can be generated. If the state space of the Markov chain is infinite, although it is impossible to generate the entire transition matrix, it still may be possible to solve the Markov chain. One interesting and useful class of denumerable state space Markov chains that can be solved consists of those that have a block GI/M/1 or a block M/G/1 form. Block GI/M/1 and block M/G/1 matrices, though infinite, have a repeating structure that allows analytical solution. If it can be detected from the specification that the Markov chain is block GI/M/1 or block M/G/1, then our system can automatically apply matrix analytical methods to obtain a solution. In this paper, a high level specification language for Markov chains is proposed such that the existence of block GI/M/1 or block M/G/1 form may be verified directly from the specification. An algorithm is given to determine whether a Markov chain with a 2 dimensional state space specified in this language is infinite and, if so, whether it can be represented in block GI/M/1 or block M/G/1 form. It is shown that in general, it is undecidable whether a matrix specified in this language with a state space vector of dimension greater than 2 can be represented as a block GI/M/1 or block M/G/1 matrix. Finally a second, less powerful specification language, is provided for which the question is decidable for a specification with a state space vector of any finite dimension.

Date: 1995
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4615-2241-6_1

Ordering information: This item can be ordered from
http://www.springer.com/9781461522416

DOI: 10.1007/978-1-4615-2241-6_1

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().