On computing the expected discounted return in a markov chain

David F. Hitchcock and James B. Macqueen

Naval Research Logistics Quarterly, 1970, vol. 17, issue 2, 237-241

Abstract: The discounted return associated with a finite state Markov chain X1, X2… is given by g(X1)+ αg(X2) + α2g(X3) + …, where g(x) represents the immediate return from state x. Knowing the transition matrix of the chain, it is desired to compute the expected discounted return (present worth) given the initial state. This type of problem arises in inventory theory, dynamic programming, and elsewhere. Usually the solution is approximated by solving the system of linear equations characterizing the expected return. These equations can be solved by a variety of well‐known methods. This paper describes yet another method, which is a slight modification of the classical iterative scheme. The method gives sequences of upper and lower bounds which converge mono‐tonely to the solution. Hence, the method is relatively free of error control problems. Computational experiments were conducted which suggest that for problems with a large number of states, the method is quite efficient. The amount of computation required to obtain the solution increases much slower with an increase in the number of states, N, than with the conventional methods. In fact, computational time is more nearly proportional to N2, than to N3.

Date: 1970
References: Add references at CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/nav.3800170210

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:wly:navlog:v:17:y:1970:i:2:p:237-241

Access Statistics for this article

More articles in Naval Research Logistics Quarterly from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().