Hostname: page-component-78c5997874-m6dg7 Total loading time: 0 Render date: 2024-11-07T23:30:21.329Z Has data issue: false hasContentIssue false
  • English
  • Français

A two-point Markov chain boundary-value problem

Part of: Stochastic processes Special processes

Published online by Cambridge University Press:  01 July 2016

D. J. Daley  and
L. D. Servi
D. J. Daley*
Affiliation:
Australian National University
L. D. Servi*
Affiliation:
GTE Laboratories Inc.
*
∗ Postal address: Statistics Research Section (IAS), School of Mathematical Sciences, Australian National University, GPO Box 4, Canberra ACT 2601, Australia.
∗∗ Postal address; GTE Laboratories Incorporated, 40 Sylvan Road, Waltham, MA 02254, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

The two-point Markov chain boundary-value problem discussed in this paper is a finite-time version of the quasi-stationary behaviour of Markov chains. Specifically, for a Markov chain {Xt:t = 0, 1, ·· ·}, given the time interval (0, n), the interest is in describing the chain at some intermediate time point r conditional on knowing both the behaviour of the chain at the initial time point 0 and that over the interval (0, n) it has avoided some subset B of the state space. The paper considers both ‘real time' estimates for r = n (i.e. the chain has avoided B since 0), and a posteriori estimates for r < n with at least partial knowledge of the behaviour of Xn. Algorithms to evaluate the distribution of Xr can be as small as O(n3) (and, for practical purposes, even O(n2 log n)). The estimates may be stochastically ordered, and the process (and hence, the estimates) may be spatially homogeneous in a certain sense. Maximum likelihood estimates of the sample path are furnished, but by example we note that these ML paths may differ markedly from the path consisting of the expected or average states. The scope for two-point boundary-value problems to have solutions in a Markovian setting is noted.

Several examples are given, together with a discussion and examples of the analogous problem in continuous time. These examples include the basic M/G/k queue and variants that include a finite waiting room, reneging, balking, and Bernoulli feedback, a pure birth process and the Yule process. The queueing examples include Larson's (1990) ‘queue inference engine'.

Keywords

M/G/k QUEUEMAXIMUM LIKELIHOOD SAMPLE PATHSVITERBI ALGORITHMCOMPUTATIONAL COMPLEXITYHIDDEN MARKOV MODELSQUEUE LENGTH INFERENCE

MSC classification

Primary: 60K25: Queueing theory
Secondary: 60G55: Point processes
Type
Research Article
Information
Advances in Applied Probability , Volume 25 , Issue 3 , September 1993 , pp. 607 - 630
Copyright
Copyright © Applied Probability Trust 1993 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Bertsimas, D. J. and Servi, L. D. (1992) Deducing queueing from transactional data: the queue inference engine revisited. Operat. Res. 40 (S2), 217–228.Google Scholar
Chung, K. L. (1960) Markov Chains with Stationary Transition Probabilities. Springer-Verlag, Berlin.Google Scholar
Daley, D. J. (1969) Quasi-stationary behaviour of a left-continuous random walk. Ann. Math. Statist. 40, 532–539.Google Scholar
Daley, D. J. and Servi, L. D. (1992) Exploiting Markov chains to infer queue-length from transitonal data. J. Appl. Prob. 29, 713–732.Google Scholar
Dimitrijevic, D. D. (1991) Inferring most likely queue length from transaction data. Submitted.Google Scholar
Feller, W. (1968) An Introduction to Probability Theory and Applications, Vol. I, 3rd edn. Wiley, New York.Google Scholar
Hall, S. A. and Larson, R. C. (1991) Using partial queue-length information to improve the queue inference engine's performance. Presented at ORSA/TIMS Conference, May, 1991.Google Scholar
Larson, R. C. (1990, 1991) The queue inference engine; deducing queue statistics from transactional data. Management Sci. 36, 586–601. Addendum 36, 1062.Google Scholar
Levinson, S. E., Rabiner, L. R. and Sondhi, M. M. (1983) An introduction to the application of the theory of probabilistic functions of a Markov process to automatic speech recognition. Bell System Tech. J. 62, 1035–1074.Google Scholar
Seneta, E. (1966) Quasi-stationary distributions and time-reversion in genetics (with discussion). J. R. Statist. Soc. B 28, 253–277.Google Scholar
Seneta, E. (1981) Non-negative Matrices and Markov Chains, 2nd edn. Springer-Verlag, New York.Google Scholar
Seneta, E. and Vere-Jones, D. (1966) On quasi-stationary distributions in discrete-time Markov chains with a denumerable infinity of states. J. Appl. Prob. 3, 403–434.Google Scholar
Stoyan, D. (1983) Comparison Methods for Queues and Other Stochastic Models, ed. Daley, D. J. Wiley, New York.Google Scholar
Viterbi, A. J. (1967) Error bounds for convolutional codes and an asymptotically optimal decoding algorithm. IEEE Trans. Inf. Theory 13, 260–269.Google Scholar