In this paper, some results on the asymptotic behavior of Markov renewal processes with auxiliary paths (MRPAP's) proved in other papers ([28], [29]) are applied to queueing theory. This approach to queueing problems may be regarded as an improvement of the method of Fabens [7] based on the theory of semi-Markov processes. The method of Fabens was also illustrated by Lambotte in [18], [32]. In the present paper the ordinary M/G/1 queue is generalized to allow service times to depend on the queue length immediately after the previous departure. Such models preserve the MRPAP-structure of the ordinary M/G/1 system. Recently, the asymptotic behaviour of the embedded Markov chain (MC) of this queueing model was studied by several authors. One aim of this paper is to answer the question of the relationship between the limiting distribution of the embedded MC and the limiting distribution of the original process with continuous time parameter. It turns out that these two limiting distributions coincide. Moreover some properties of the embedded MC and the embedded semi-Markov process are established. The discussion of the M/G/1 queue closes with a study of the rate-of-convergence at which the queueing process attains equilibrium.

Part I [21] treated the case of a finite number of independent random uniform s-flats in an ‘admissible’ subset of Ed (s = 0, · · ·, d − 1). In this second part, the natural and fruitful ‘Poisson extension’ to a ‘countable number of independent random uniform s-flats in Ed itself” is considered. It is worth mentioning at the outset that to have read Part I is not a prerequisite for reading the present paper. Although results of that part are often applied here, they serve only in an auxiliary capacity, thereby allowing the main thread of the theory to be developed without interruption.

In this last part the Fn(i) and Mn(i) are considered as random variables whose distributions are described by the model and various mating rules of Section 2. Several convergence results will be proved for those specific mating rules, but we begin with the more general convergence theorem 6.1. The proof of this theorem brings out the basic idea of this section, namely that when Fn and Mn are large, Fn + 1(i) and Mn + 1(i) will, with high probability, be close to a certain function of Fn(·) and Mn(·) (roughly the conditional expectation of Fn+1(i) and Mn + 1(i) given Fn(·) and Mn(·)). As we already indicated in Section 2, this leads (outside the exceptional set) to the approximate equality for some transformation T of the form (1.4), (1.5). More generally for fixed k except on a set whose probability is small when Fn and Mn are large. If the theorems of Section 3 or 4 apply, Tk(fn(·), mn(·)) will be close to a fixed vector ζ when k is large and thus there is hope that fn(·) and mn(·) will converge, once Fn and Mn become large. We therefore have to put on some conditions which will make Fn and Mn grow. This is the role of (6.34) and, to some extent, also of (6.17). The main difficulty is that the expected size of the (n + 1)th generation, given the nth generation, depends on the frequencies of the different types present in the nth generation. Even if (6.34) holds, the conditional expected size of the (n + 1)th generation, given the nth generation, may actually be smaller than the size of the nth generation for certain directions fn(·), m(·).

This paper is a sequel to [7], in which heavy traffic limit theorems were proved for various stochastic processes arising in a single queueing facility with r arrival channels and s service channels. Here we prove similar theorems for sequences of such queueing facilities. The same heavy traffic behavior prevails in many cases in this more general setting, but new heavy traffic behavior is observed when the sequence of traffic intensities associated with the sequence of queueing facilities approaches the critical value (ρ = 1) at appropriate rates.

Throughout this paper we shall be concerned with a sequence of mutually independent and identically distributed random variables ξ1 ξ2, · · ·, ξn, · · · taking on real values. We shall use the notation ζn = ξ1 + · · · + ξn for n = 1, 2, · · · and ζ0 = 0.

In this work Markov chains governed by complicated processes are introduced and investigated (Section 1). In Section 2 an ergodic theorem for these processes is formulated, while in Section 3 the sojourn time of the process in a fixed region is studied; in Section 4 some examples are considered. The processes studied are of practical importance in the description of mass service systems and the theory of reliability for which the time intervals between successive demands cannot be assumed to be mutually independent random variables. It is shown that the dependence parameter r of these processes, if it is sufficiently large, allows us to formulate a relationship between the time intervals in question.

The stepping stone model of population structure, of finite length, is analysed with special reference to the variance, and correlation coefficients of gene frequencies. Explicit formulas for these quantities are obtained. The model is also analysed for the genetic variability maintained in the population. In order to check the validity of the analytical results, several numerical computations were carried out using two different methods: iterations and Monte Carlo experiments. The values obtained by these numerical methods agree well with the theoretical values obtained by formulas derived analytically.

Consider the bivariate sequence of r.v.'s {(Jn, Xn), n ≧ 0} with X0 = - ∞ a.s. The marginal sequence {Jn} is an irreducible, aperiodic, m-state M.C., m < ∞, and the r.v.'s Xn are conditionally independent given {Jn}. Furthermore P{Jn = j, Xn ≦ x | Jn − 1 = i} = pijHi(x) = Qij(x), where H1(·), · · ·, Hm(·) are c.d.f.'s. Setting Mn = max {X1, · · ·, Xn}, we obtain P{Jn = j, Mn ≦ x | J0 = i} = [Qn(x)]i, j, where Q(x) = {Qij(x)}. The limiting behavior of this probability and the possible limit laws for Mn are characterized.

Theorem. Let ρ(x) be the Perron-Frobenius eigenvalue of Q(x) for real x; then:

(a)ρ(x) is a c.d.f.;

(b) if for a suitable normalization {Qijn(aijnx + bijn)} converges completely to a matrix {Uij(x)} whose entries are non-degenerate distributions then Uij(x) = πjρU(x), where πj = limn → ∞pijn and ρU(x) is an extreme value distribution;

(c) the normalizing constants need not depend on i, j;

(d) ρn(anx + bn) converges completely to ρU(x);

(e) the maximum Mn has a non-trivial limit law ρU(x) iff Qn(x) has a non-trivial limit matrix U(x) = {Uij(x)} = {πjρU(x)} or equivalently iff ρ(x) or the c.d.f. πi = 1mHiπi(x) is in the domain of attraction of one of the extreme value distributions. Hence the only possible limit laws for {Mn} are the extreme value distributions which generalize the results of Gnedenko for the i.i.d. case.

As in [4] and [5], we study service facilities with r arrival channels and s service channels. However, here we assume that customers, immediately upon arrival, randomly select one of the s service channels. Successive customers make this choice independently, choosing server i with probability pi, p1 + · · · + ps = 1. Customers are then served by the servers they select in order of their arrival without defections. The average processing rates as well as the server selection probabilities may vary from server to server, but again we assume the r arrival channels are independent and independent of the service channels. The service channels are not independent, however, because of the random server selection. For simplicity, we only consider a single queueing system; the extension to sequences follows immediately using the argument of [5].

This paper is concerned with the general problem of choosing an optimal stopping time for a Brownian motion process, where the cost associated with any trajectory depends only on its final time and position.

Some results for a general Markov branching-diffusion process are presented, and applied to a model recently considered by Bailey. Moments of the limiting distributions of certain natural measures of the spatial location and dispersion of the population are shown to be expressible in terms of the Lauricella FD-type hypergeometric functions, when the population multiplies according to the simple birth and death process with λ > μ.

This paper discusses the transient and limiting behavior of a system of queues, consisting of two service units in tandem in which the second unit has finite capacity. When the second unit reaches full capacity, a phenomenon termed “blocking” occurs. A wide class of rules to resolve blocking is defined and studied in a unified way.

The input to the first unit is assumed to be Poisson, the service times in the first unit are independent with a general, common distribution. When the system is not blocked, the second unit releases its customers according to a state-dependent, death process.

The analysis of the time-dependence relies heavily on several imbedded Markov renewal processes. In particular, the analog of the busy period for the M/G/1 queue is modeled here as a “Markov renewal branching process”. The study of this process requires the definition of a class of matrix functions which generalizes some classical definitions of matrix function. In terms of these “matrix functions” we are led to consider functional iterates and a matrix analog of Takács' functional equation for the transform of the distribution of the busy period in the M/G/1 model.

We further discuss the joint distribution of the queue lengths in units I and II and its marginal and limiting distributions.

A final section is devoted to an informal discussion on how the numerical analysis of this system of queues may be organized.

A reasonably general but greatly simplified model for a finite sexually reproducing population is considered. We restrict ourselves to the case where there are distinct, non-overlapping generations, but there is hope that the techniques will also be applicable to some very simple minded continuous time models with overlapping generations (see also Section 5, Example 3). There are t∞ < ∞ different types of females and t1 < ∞ types of males and our main concern is the asymptotic behavior of the variables and

The queueing systems considered in this paper consist of r independent arrival channels and s independent service channels, where as usual the arrival and service channels are independent. Arriving customers form a single queue and are served in the order of their arrival without defections. We shall treat two distinct modes of operation for the service channels. In the standard system a waiting customer is assigned to the first available service channel and the servers (servers ≡ service channels) are shut off when they are idle. Thus the classical GI/G/s system is a special case of our standard system. In the modified system a waiting customer is assigned to the service channel that can complete his service first and the servers are not shut off when they are idle. While the modified system is of some interest in its own right, we introduce it primarily as an analytical tool. Let λi denote the arrival rate (reciprocal of the mean interarrival time) in the ith arrival channel and μj the service rate (reciprocal of the mean service time) in the jth service channel. Then is the total arrival rate to the system and is the maximum service rate of the system. As a measure of congestion we define the traffic intensity ρ = λ/μ.