Search

In this paper, we study the classification of matrix GI/M/1-type Markov chains with a tree structure. We show that the Perron–Frobenius eigenvalue of a Jacobian matrix provides information for classifying these Markov chains. A fixed-point approach is utilized. A queueing application is presented to show the usefulness of the classification method developed in this paper.

A classical P��lya urn scheme is a Markov process whose evolution is encoded by a replacement matrix $(R_{i,j})_{1\leq i,j\leq d}$. At every discrete time-step, we draw a ball uniformly at random, denote its colour $c$, and replace it in the urn together with $R_{c,j}$ balls of colour $j$ (for all $1\leq j\leq d$). We are interested in multi-drawing P��lya urns, where the replacement rule depends on the random drawing of a set of $m$ balls from the urn (with or without replacement). This generalisation has already been studied in the literature, in particular by Kuba & Mahmoud (ArXiv:1503.09069 and 1509.09053), where second order asymptotic results are proved for $2$-colour urns under the balanced and the affinity assumptions. The main idea of this work is to apply stochastic approximation methods to this problem, which enables us to remove the affinity hypothesis of Kuba & Mahmoud and generalise the result to more-than-two-colour urns. We also give some partial results in the two-colour non-balanced case., This new arxiv version (v6) corrects a mistake that we discovered in the previous versions of this paper (v1-5). The mistake was in Theorem 1$(a)$ and in the last sentence of Theorem 4. In this new version, Theorem 1$(a)$ has been corrected, and Theorem 4 has been deleted

A service unit I, with Poisson input and general service times is in series with a unit II, with negative-exponential service times. The intermediate waitingroom can accomodate at most k persons and a customer cannot leave unit I when the waitingroom is full. The paper shows that this system of queues can be studied in terms of an imbedded semi-Markov process. Equations for the time dependent distributions are given, but the main emphasis of the paper is on the equilibrium conditions and on asymptotic results. 1. Description of the model The system of queues, discussed in this paper, consists of two units. Customers arrive at a first unit (I) according to a homogeneous Poisson process of rate 2. Their service times in unit I are independent, identically distributed random variables with common distribution function H(.). We assume that H(.) has a positive, finite mean a and we will denote the Laplace-Stieltjes transform of H( ) by h(s), Re s 0. Upon completion of service in unit I, all customers go on to a second unit (II) via a finite waitingroom. We assume that there can be not more than k customers in unit II and in the waitingroom at any time. If upon completion of service in unit I a customer finds the waitingroom full, then the unit I blocks until a service in unit II is completed. At that time he is allowed to enter the waitingroom. We assume that the service times in unit II are independent, identically distributed random variables with a negative-exponential distribution with mean 1/a. The service times in unit II are also stochastically independent of those in unit I and of the arrival process. The case k = 1, i.e., when no customers can wait between the two units, was studied by B. Avi-Itzhak and M. Yadin[1], T. Suzuki [11] and N. U. Prabhu [7]. These authors allow the service times in the second unit to have a general distribution. In the case of general k, we impose the requirement that these service Received 3 July 1967. Research supported in part by Office of Naval Research Contract NONR 1100(26). 123 This content downloaded from 157.55.39.217 on Mon, 18 Apr 2016 07:16:32 UTC All use subject to http://about.jstor.org/terms

We introduce a notion of $k$th order stochastic monotonicity and duality that allows one to unify the notion used in insurance mathematics (sometimes refereed to as Siegmund's duality) for the study of ruin probability and the duality responsible for the so-called put - call symmetries in option pricing. Our general $k$th order duality can be financially interpreted as put - call symmetry for powered options. The main objective of the present paper is to develop an effective analytic approach to the analysis of duality leading to the full characterization of $k$th order duality of Markov processes in terms of their generators, which is new even for the well-studied case of put -call symmetries., Comment: To appear in Journal of Applied Probability 52:1 (March 2015)

In this paper, we give an analytic solution for graphs with n nodes and E edges for which the probability of obtaining a given graph G is specified in terms of the degree sequence of G. We describe how this model naturally appears in the context of load balancing in communication networks, namely Peer-to-Peer overlays. We then analyse the degree distribution of such graphs and show that the degrees are concentrated around their mean value. Finally, we derive asymptotic results on the number of edges crossing a graph cut and use these results $(i)$ to compute the graph expansion and conductance, and $(ii)$ to analyse the graph resilience to random failures., Comment: 18 pages

In this paper we study the α-stable continuous-state branching processes (for α ∈ (1, 2]) and the α-stable continuous-state branching processes conditioned never to become extinct in the light of positive self-similarity. Understanding the interaction of the Lamperti transformation for continuous-state branching processes and the Lamperti transformation for positive, self-similar Markov processes gives access to a number of explicit results concerning the paths of α-stable continuous-state branching processes and α-stable continuous-state branching processes conditioned never to become extinct.

Consider N players, respectively owning x1, x2, …, xN monetary units, who play a sequence of games, winning from and losing to each other integer amounts according to fixed rules. The sequence stops as soon as (at least) one player is ruined. We are interested in the ruin process of these N players, i.e. in the probability that a given player is ruined first, and also in the expected ruin time. This problem is called the N-player ruin problem. In this paper, the problem is set up as a multivariate absorbing Markov chain with an absorbing state corresponding to the ruin of each player. This is then discussed in the context of phase-type distributions where each phase is represented by a vector of size N and the distribution has as many absorbing points as there are ruin events. We use this modified phase-type distribution to obtain an explicit solution to the N-player problem. We define a partition of the set of transient states into different levels, and on it give an extension of the folding algorithm (see Ye and Li (1994)). This provides an efficient computational procedure for calculating some of the key measures.

The sooner and later waiting time problems have been extensively studied and applied in various areas of statistics and applied probability. In this paper, we give a comprehensive study of ordered series and later waiting time distributions of a number of simple patterns with respect to nonoverlapping and overlapping counting schemes in a sequence of Markov dependent multistate trials. Exact distributions and probability generating functions are derived by using the finite Markov chain imbedding technique. Examples are given to illustrate our results.

We consider an infinite capacity buffer where the incoming fluid traffic belongs to K different types modulated by K independent Markovian on-off processes. The kth input process is described by three parameters: (λk, μk, rk), where 1/λk is the mean off time, 1/μk is the mean on time, and rk is the constant peak rate during the on time. The buffer empties the fluid at rate c according to a first come first served (FCFS) discipline. The output process of type k fluid is neither Markovian, nor on-off. We approximate it by an on-off process by defining the process to be off if no fluid of type k is leaving the buffer, and on otherwise. We compute the mean on time τkon and mean off time τkoff. We approximate the peak output rate by a constant rko so as to conserve the fluid. We approximate the output process by the three parameters (λko, μko, rko), where λko = 1/τkoff, and μko = 1/τkon. In this paper we derive methods of computing τkon, τkoff and rko for k = 1, 2,…, K. They are based on the results for the computation of expected reward in a fluid queueing system during a first passage time. We illustrate the methodology by a numerical example. In the last section we conduct a similar output analysis for a standard M/G/1 queue with K types of customers arriving according to independent Poisson processes and requiring independent generally distributed service times, and following a FCFS service discipline. For this case we are able to get analytical results.

Let X t be an n-dimensional diffusion process and S(t) be a set-valued function. Suppose X t is invisible when it is hidden by S(t), but we can see the process exactly otherwise. In this paper, we derive the optimal estimator E[f(X 1) | X s 1 X s ∉S(s), 0 ≤ s ≤ 1] for a bounded Borel function f. We illustrate some computations for Gauss-Markov processes.

We consider a continuous-time Markov additive process (J t ,S t ) with (J t ) an irreducible Markov chain on E = {1,…,s}; it is known that (S t /t) satisfies the large deviations principle as t → ∞. In this paper we present a variational formula H for the rate function κ∗ and, in some sense, we have a composition of two large deviations principles. Moreover, under suitable hypotheses, we can consider two other continuous-time Markov additive processes derived from (J t ,S t ): the averaged parameters model (J t ,S t (A)) and the fluid model (J t ,S t (F)). Then some results of convergence are presented and the variational formula H can be employed to show that, in some sense, the convergences for (J t ,S t (A)) and (J t ,S t (F)) are faster than the corresponding convergences for (J t ,S t ).

This paper considers the occurrence of patterns in sequences of independent trials from a finite alphabet; Gani and Irle (1999) have described a finite state automaton which identifies exactly those sequences of symbols containing the specific pattern, which may be thought of as the word of interest. Each word generates a particular Markov chain. Motivated by a result of Guibas and Odlyzko (1981) on stochastic monotonicity for the random times when a particular word is completed for the first time, a new level-crossing ordering is introduced for stochastic processes. A process {Yn : n = 0, 1, …} is slower in level-crossing than a process {Zn }, if it takes {Yn } stochastically longer than {Zn } to exceed any given level. This relation is shown to be useful for the comparison of stochastic automata, and is used to investigate this ordering for Markov chains in discrete time.

Technology developed in a predecessor paper (Chen and Seneta (1996)) is applied to provide, in a unified manner, a sharpening of bivariate Bonferroni-type bounds on P(v 1≥r, v 2≥u) obtained by Galambos and Lee (1992; upper bound) and Chen and Seneta (1986; lower bound).

The random triangle model was recently introduced as a random graph model that captures the property of transitivity that is often found in social networks, i.e. the property that given that two vertices are second neighbors, they are more likely to be neighbors. For parameters p ∊ [0,1] and q ≥ 1, and a finite graph G = (V, E), it assigns to elements η of {0,1} E probabilities which are proportional to where t(η) is the number of triangles in the open subgraph. In this paper the behavior of the random triangle model on the two-dimensional triangular lattice is studied. By mapping the system onto an Ising model with external field on the hexagonal lattice, it is shown that phase transition occurs if and only if p = (q−1)−2/3 and q > q c for a critical value q c which turns out to equal It is furthermore demonstrated that phase transition cannot occur unless p = p c (q), the critical value for percolation of open edges for given q. This implies that for q ≥ q c , p c (q) = (q−1)−2/3.

In this paper, we consider a certain class of Markov renewal processes where the matrix of the transition kernel governing the Markov renewal process possesses some block-structured property, including repeating rows. Duality conditions and properties are obtained on two probabilistic measures which often play a key role in the analysis and computations of such a block-structured process. The method used here unifies two different concepts of duality. Applications of duality are also provided, including a characteristic theorem concerning recurrence and transience of a transition matrix with repeating rows and a batch arrival queueing model.

In this paper we study the asymptotic behavior of the tail of the stationary backlog distribution in a single server queue with constant service capacity c, fed by the so-called M/G/∞ input process or Cox input process. Asymptotic lower bounds are obtained for any distribution G and asymptotic upper bounds are derived when G is a subexponential distribution. We find the bounds to be tight in some instances, e.g. when G corresponds to either the Pareto or lognormal distribution and c − ρ < 1, where ρ is the arrival rate at the buffer.

Erlang's functionB(λ,C) gives the blocking probability that occurs when Poisson traffic of intensity λ is offered to a link consisting ofCcircuits. However, when dimensioning a telecommunications network, it is more convenient to use the inverseC(λ,B) of Erlang's function, which gives the number of circuits needed to carry Poisson traffic λ with blocking probability at mostB. This paper derives simple bounds forC(λ,B). These bounds are close to each other and the upper bound provides an accurate linear approximation toC(λ,B) which is asymptotically exact in the limit as λ approaches infinity withBfixed

In this paper the integrated three-valued telegraph process is examined. In particular, the third-order equations governing the distributions , (where N(t) denotes the number of changes of the telegraph process up to time t) are derived and recurrence relationships for them are obtained by solving suitable initial-value problems. These recurrence formulas are related to the Fourier transform of the conditional distributions and are used to obtain explicit results for small values of k. The conditional mean values (where V(0) denotes the initial velocity of motions) are obtained and discussed.

The exact solution for the transient distribution of the queue length and busy period of the M/M/1 queue in terms of modified Bessel functions has been proved in a variety of ways. Methods of the past range from spectral analysis (Lederman and Reuter (1954)), combinatorial arguments (Champernowne (1956)), to generating functions coupled with Laplace transforms (Clarke (1956)). In this paper, we present a novel approach that ties the computation of these transient distributions directly to the random sample path behavior of the M/M/1 queue. The use of Laplace transforms is minimized, and the use of generating functions is eliminated completely. This is a method that could prove to be useful in developing a similar transient analysis for queueing networks.

This paper discusses a renewal process whose time development between renewals is described by a Markov process. The process may be controlled by choosing the times at which renewal occurs, the objective of the control being to maximise the long-term average rate of reward. Let γ ∗ denote the maximum achievable rate. We consider a specific policy in which a sequence of estimates of γ ∗ is made. This sequence is defined inductively as follows. Initially an (a priori)estimate γo is chosen. On making the nth renewal one estimates γ ∗ in terms of γ o, the total rewards obtained in the first n renewal cycles and the total length of these cycles. γ n then determines the length of the (n + 1)th cycle. It is shown that γ n tends to γ ∗ as n tends to∞, and that this policy is optimal. The time at which the (n + 1)th renewal is made is determined by solving a stopping problem for the Markov process with continuation cost γ n per unit time and stopping reward equal to the renewal reward. Thus, in general, implementation of this policy requires a knowledge of the transition probabilities of the Markov process. An example is presented in which one needs to know essentially nothing about the details of this process or the fine details of the reward structure in order to implement the policy. The example is based on a problem in biology.

The paper considers an extension to the reversible counters system of Lampard [1]. In Lampard's model the input processes are two independent Poisson processes; this results in a gamma Markov sequence for the time-interval between successive output pulses and a negative binomial Markov sequence for the counts at the times of out-put pulses. We consider the input process to be a bivariate Poisson process and show that the first out-put process given above is not affected, while the second out-put-process becomes of a type studied in the theory of branching processes.

The problem of interest is to determine the optimal ordering so as to minimize the long run average cost. Clearly if the P sub i were known the optimal ordering would simply be to order the elements in decreasing order of the P sub i's. In fact even if the P sub i's were unknown we could do as well asymptotically by ordering the elements at each unit of time in decreasing order of the number of previous requests for them. In this paper we first consider the case in which the only memory allowed at any time is the ordering of the elements at that time; in other words, the only type of reordering rules we allow are ones in which the reordered permutation of elements at any time is only allowed to depend on the present ordering and the position of the element requested. We also consider the above problem under the previse that additional memory is allowed. In particular we allow the decision-maker to utilize such rules as 'only make a change (according to some preassigned rule) if the same element has been requested k times in a row.' We show that as k approaches infinity we can do as well as if we knew the values of the P sub i, and in addition we show that the convergence is monotone.

This paper is about representations for equilibrium sojourn time distributions in Jackson networks of queues. For a network with N single-server nodes let hi be the Laplace transform of the residual system sojourn time for a customer ‘arriving' to node i, ‘arrival' meaning external input or internal transfer. The transforms {hi : i = 1, ···, N} are shown to satisfy a system of equations we call the network flow equations. These equations lead to a general recursive representation for the higher moments of the sojourn time variables {Ti : i = 1, ···, N}. This recursion is discussed and then, by way of illustration, applied to the single-server Markovian queue with feedback.

Let X(t) be a continuous time Markov process on the integers such that, if σ is a time at which X makes a jump, X(σ)– X(σ–) is distributed independently of X(σ–), and has finite mean μ and variance. Let q(j) denote the residence time parameter for the state j. If tn denotes the time of the nth jump and Xn ≡ X(tb), it is easy to deduce limit theorems for from those for sums of independent identically distributed random variables. In this paper, it is shown how, for μ > 0 and for suitable q(·), these theorems can be translated into limit theorems for X(t), by using the continuous mapping theorem.

One of the major difficulties in attempting to apply known queueing theory results to real problems is that almost always these results assume a time-stationary Poisson arrival process, whereas in practice the actual process is almost invariably non-stationary. In this paper we consider single-server infinite-capacity queueing models in which the arrival process is a non-stationary process with an intensity function ∧(t), t ≧ 0, which is itself a random process. We suppose that the average value of the intensity function exists and is equal to some constant, call it λ, with probability 1. We make a conjecture to the effect that ‘the closer {∧(t), t ≧ 0} is to the stationary Poisson process with rate λ ' then the smaller is the average customer delay, and then we verify the conjecture in the special case where the arrival process is an interrupted Poisson process.

The paper characterizes point processes with the order statistic property without the unnecessary condition of finiteness of the first moment of the process, a condition imposed by previous researchers. It shows that the class of these processes is composed only of mixed Poisson processes up to a time-scale transformation and of the mixed sample processes. It also introduces a multivariate analog of the order statistic property and characterizes completely the class of multivariate point processes with this property.

This paper considers the autocorrelation function of queue length and the corresponding spectral density (i.e., its Fourier transform). Some general expressions are obtained using generating functions and matrices, and applied to M/M/1 and M [x]/M/∞ queues.

The model considered in this paper describes a queueing system in which the station is dismantled at the end of a busy period and re-established on arrival of a new customer, in such a way that the closing-down process consists of N1 phases of random duration and that a customer 𝒞n who arrives while the station is being closed down must wait a random time idn(i = 1, ···, N1) if the ith phase is going on at the arrival instant. (For each fixed index i, the random variables idn are identically distributed.) A customer 𝒞n arriving when the closing-down of the station is already accomplished has to wait a random time (N1 + 1)dn corresponding to the set up time of the station. Besides, a customer 𝒞n who arrives when the station is busy has to wait an additional random time 0dn. We thus have (N1 + 2) types of “delay” (additional waiting time). Similarly, we consider (N2 + 2) types of service time and (N3 + 2) probabilities of joining the queue. This may be formulated as a model with (N + 2) types of triplets (delay, service time, probability of joining the queue). We consider the general case where the random variables defining the model all have an arbitrary distribution.The process {wn}, where wn denotes the waiting time of customer 𝒞n if he joins the queue at all, is not necessarily Markovian, so that we first study (by algebraic considerations) the transient behaviour of a Markovian process {vn} related to {wn}, and then derive the distribution of the variables wn.