A two-point Markov chain boundary-value problem

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'.