This paper is concerned with a discrete Markov process related to an underlying weighted graph. With this graph we associate an urn containing p types of balls which correspond to the p vertices of the graph, and such that the number of balls of each type is proportional to the weight of the related vertex. A drawing scheme from the urn is defined which leads to Markovian non-homogeneous transition probabilities. Many kinds of weighted graphs are found to have a strong convergence property; this is that the number of balls drawn from the urn at the end of any single draw converges in probability to the total number of balls in the urn, as this tends to infinity.

A stochastic model for a periodic screening program is presented in which the natural history of a chronic disease is assumed to follow a progressive path from a preclinical state to a clinical state. The sampling of preclinical state sojourn times by screening examinations generates bounds on the preclinical state recurrence times. The distribution of the bounded forward recurrence time is derived and used to obtain the distribution and mean of the lead time, and relationships for calculating the proportion of preclinical cases detected. These expressions are derived in terms of the preclinical state sojourn-time distribution and adjustible parameters important in the design of a periodic screening program.

This paper is concerned with the problem of selecting the transition intensities for a Markov chain in continuous time so as to minimise the long-term average cost. Sufficient conditions are established for an optimal stationary policy using unbounded solutions of the optimality equation. This is a development of recent work on Markovian decision processes in discrete time. The theory is illustrated by considering a simple birth and death process with controlled immigration.

A discrete-time Markov decision model with a denumerable set of states and unbounded costs is considered. It is shown that the optimality equation of dynamic programming along with some additional, easily checked, conditions may be used to establish the optimality or ∊ -optimality of policies with respect to the average expected cost criterion. The results are used to derive optimal policies in two queueing examples.

We consider a batch service queue which is controlled by switching the server on and off, and by controlling the batch size and timing of services. These batch sizes cannot exceed a fixed number Q, which we call the service capacity. Costs are charged for switching the server on and off, for serving customers and for holding them in the system. Viewing the system as a semi-Markov decision process, we show that the policies which minimize the expected continuously discounted cost and the expected cost per unit time over an infinite time horizon are of the following form: at a review point if the server is off, leave the server off until the number of customers x reaches an optimal level M, then turn the server on and serve min (x, Q) customers; and when the server is on, serve customers in batches of size min(x, Q) until the number of customers falls below an optimal level m(m ≦ M) and then turn the server off. An example for computing these optimal levels is also presented.

A single-server queue with batch arrivals in a non-homogeneous Poisson process and with balking is studied with respect to the busy period, using supplementary variables. A system of integral equations is obtained on the base of which the transforms are expressed in series. For the homogeneous case, assuming finite waiting room, the solutions are obtained via Cramer's rule. This gives asymptotic expressions for the expectations for large arrival intensity. An efficiency measure giving the long run loss probability is given. For a special case contour integral representations are given as solutions.