Search

This paper considers the comparison of two $$\left( {s,S} \right)$$ production inventory systems with retrials of unsatisfied customers. The time for producing and adding each item to the inventory is exponentially distributed with rate $$\beta$$ . However, a production rate $$\alpha \beta$$ higher than $$\beta$$ is used at the beginning of the production. The higher production rate will reduce customers’ loss when inventory level approaches zero. The demand from customers is according to a Poisson process. Service times are exponentially distributed. Upon arrival, the customers enter into a buffer of finite capacity. An arriving customer, who finds the buffer full, moves to an orbit. They can retry from there and inter-retrial times are exponentially distributed. The two models differ in the capacity of the buffer. The aim is to find the minimum value of total cost by varying different parameters and compare the efficiency of the models. The optimum value of $$\alpha$$ corresponding to minimum total cost is an important evaluation. Matrix analytic method is used to find an algorithmic solution to the problem. We also provide several numerical or graphical illustrations.

To reduce automobile exhaust pollution, traffic congestion and parking difficulties, bike-sharing systems are rapidly developed in many countries and more than 500 major cities in the world over the past decade. In this paper, we discuss a large-scale bike-sharing system under Markovian environment, and propose a mean-field matrix-analytic method in the study of bike-sharing systems through combining the mean-field theory with the time-inhomogeneous queues as well as the nonlinear QBD processes. Firstly, we establish an empirical measure process to express the states of this bike-sharing system. Secondly, we apply the mean-field theory to establishing a time-inhomogeneous MAP(t)/MAP(t)/1/K+2L+1 queue, and then to setting up a system of mean-field equations. Thirdly, we use the martingale limit theory to show the asymptotic independence of this bike-sharing system, and further analyze the limiting interchangeability as N goes to infinity and t goes to infinity. Based on this, we discuss and compute the fixed point in terms of a nonlinear QBD process. Finally, we analyze performance measures of this bike-sharing system, such as, the mean of stationary bike number at any station and the stationary probability of problematic stations. Furthermore, we use numerical examples to show how the performance measures depend on the key parameters of this bike-sharing system. We hope the methodology and results of this paper are applicable in the study of more general large-scale bike-sharing systems., 45 pages; 10 figures

In this paper we are concerned with a stochastic model for the spread of an epidemic in a closed homogeneously mixing population when an infective can go through several stages of infection before being removed. The transitions between stages are governed by either a Markov process or a semi-Markov process. An infective of any stage makes contacts amongst the population at the points of a Poisson process. Our main purpose is to derive the distribution of the final epidemic size and severity, as well as an approximation by branching, using simple matrix analytic methods. Some illustrations are given, including a model with treatment discussed by Gani (2006).

We consider a class of discrete time Markov chains with state space [0,1] and the following dynamics. At each time step, first the direction of the next transition is chosen at random with probability depending on the current location. Then the length of the jump is chosen independently as a random proportion of the distance to the respective end point of the unit interval, the distributions of the proportions being fixed for each of the two directions. Chains of that kind were subjects of a number of studies and are of interest for some applications. Under simple broad conditions, we establish the ergodicity of such Markov chains and then derive closed form expressions for the stationary densities of the chains when the proportions are beta distributed with the first parameter equal to 1. Examples demonstrating the range of stationary distributions for processes described by this model are given, and an application to a robot coverage algorithm is discussed., 14 pages, 4 figures

We present an update formula that allows the expression of the deviation matrix of a continuous-time Markov process with denumerable state space having generator matrix Q* through a continuous-time Markov process with generator matrix Q. We show that under suitable stability conditions the algorithm converges at a geometric rate. By applying the concept to three different examples, namely, the M/M/1 queue with vacations, the M/G/1 queue, and a tandem network, we illustrate the broad applicability of our approach. For a problem in admission control, we apply our approximation algorithm to Markov decision theory for computing the optimal control policy. Numerical examples are presented to highlight the efficiency of the proposed algorithm.

A finite-state Markov chain M can be regarded as a linear transform operating on the set of probability distributions over its node set. The iterative applications of M to an initial probability distribution μ 0 will generate a trajectory of probability distributions. Thus, a set of initial distributions will induce a set of trajectories. It is an interesting and useful task to analyze the dynamics of M as defined by this set of trajectories. The novel idea here is to carry out this task in a symbolic framework. Specifically, we discretize the probability value space [0,1] into a finite set of intervals I = { I 1 , I 2 ,..., I m }. A concrete probability distribution μ over the node set {1, 2,..., n } of M is then symbolically represented as D , a tuple of intervals drawn from I where the i th component of D will be the interval in which μ( i ) falls. The set of discretized distributions D is a finite alphabet. Hence, the trajectory, generated by repeated applications of M to an initial distribution, will induce an infinite string over this alphabet. Given a set of initial distributions, the symbolic dynamics of M will then consist of a language of infinite strings L over the alphabet D . Our main goal is to verify whether L meets a specification given as a linear-time temporal logic formula φ. In our logic, an atomic proposition will assert that the current probability of a node falls in the interval I from I . If L is an ω-regular language, one can hope to solve our model-checking problem (whether L ⊧ φ?) using standard techniques. However, we show that, in general, this is not the case. Consequently, we develop the notion of an ϵ-approximation, based on the transient and long-term behaviors of the Markov chain M . Briefly, the symbolic trajectory ξ' is an ϵ-approximation of the symbolic trajectory ξ iff (1) ξ' agrees with ξ during its transient phase; and (2) both ξ and ξ' are within an ϵ-neighborhood at all times after the transient phase. Our main results are that one can effectively check whether (i) for each infinite word in L , at least one of its ϵ-approximations satisfies the given specification; (ii) for each infinite word in L , all its ϵ-approximations satisfy the specification. These verification results are strong in that they apply to all finite state Markov chains.

We consider Markovian multiserver retrial queues where a blocked customer has two opportunities for abandonment: at the moment of blocking or at the departure epoch from the orbit. In this queueing system, the number of customers in the system (servers and buffer) and that in the orbit form a level-dependent quasi-birth-and-death (QBD) process whose stationary distribution is expressed in terms of a sequence of rate matrices. Using a simple perturbation technique and a matrix analytic method, we derive Taylor series expansion for nonzero elements of the rate matrices with respect to the number of customers in the orbit. We also obtain explicit expressions for all the coefficients of the expansion. Furthermore, we derive tail asymptotic formulae for the joint stationary distribution of the number of customers in the system and that in the orbit. Numerical examples reveal that the tail probability of the model with two types of nonpersistent customers is greater than that of the corresponding model with one type of nonpersistent customers., Submitted for review

We prove that heat-bath chains (which we define in a general setting) have no negative eigenvalues. Two applications of this result are presented: one to single-site heat-bath chains for spin systems and one to a heat-bath Markov chain for sampling contingency tables. Some implications of our main result for the analysis of the mixing time of heat-bath Markov chains are discussed. We also prove an alternative characterisation of heat-bath chains, and consider possible generalisations., 15 pages. Minor edits to address referee's comments

Cataloged from PDF version of article. Infinite level-dependent quasi-birth-and-death (LDQBD) processes can be used to model Markovian systems with countably infinite multidimensional state spaces. Recently it has been shown that sums of Kronecker products can be used to represent the nonzero blocks of the transition rate matrix underlying an LDQBD process for models from stochastic chemical kinetics. This paper extends the form of the transition rates used recently so that a larger class of models including those of call centers can be analyzed for their steady-state. The challenge in the matrix analytic solution then is to compute conditional expected sojourn time matrices of the LDQBD model under low memory and time requirements after truncating its countably infinite state space judiciously. Results of numerical experiments are presented using a Kronecker-based matrix-analytic solution on models with two or more countably infinite dimensions and rules of thumb regarding better implementations are derived. In doing this, a more recent approach that reduces memory requirements further by enabling the computation of steady-state expectations without having to obtain the steady-state distribution is also considered. (C) 2013 Elsevier B.V. All rights reserved.

International audience; Solving Markov chains is, in general, difficult if the state space of the chain is very large (or infinite) and lacking a simple repeating structure. One alternative to solving such chains is to construct models that are simple to analyze and provide bounds for a reward function of interest. We present a new bounding method for Markov chains inspired by Markov reward theory: Our method constructs bounds by redirecting selected sets of transitions, facilitating an intuitive interpretation of the modifications of the original system. We show that our method is compatible with strong aggregation of Markov chains; thus we can obtain bounds for an initial chain by analyzing a much smaller chain. We illustrate our method by using it to prove monotonicity results and bounds for assemble-to-order systems.

We deal with finite-buffer queueing systems fed by a Markovian point process. This class includes the queues of type M/G/1/N, 𝑀 𝑋 /G/1/N, PH/G/1/N, MMPP/G/1/N, MAP/G/1/N, and BMAP/G/1/N and is commonly used in the performance evaluation of network traffic buffering processes. Typically, such queueing systems are studied in the stationary regime using matrix-analytic methods connected with M/G/1-type Markov processes. Herein, another method for finding transient and stationary characteristics of these queues is presented. The approach is based on finding a closed-form formula for the Laplace transform of the time-dependent performance measure of interest. The method can be used for finding all basic characteristics like queue size distribution, workload distribution, loss ratio, time to buffer overflow, and so forth. To demonstrate this, several examples for different combinations of arrival processes and characteristics are presented. In addition, the most complex results are illustrated via numerical calculations based on an IP traffic parameterization.

In this paper we extend the results of the research started by the first author, in which Karlin-McGregor diagonalization of certain reversible Markov chains over countably infinite general state spaces by orthogonal polynomials was used to estimate the rate of convergence to a stationary distribution. We use a method of Koornwinder to generate a large and interesting family of random walks which exhibits a lack of spectral gap, and a polynomial rate of convergence to the stationary distribution. For the Chebyshev type subfamily of Markov chains, we use asymptotic techniques to obtain an upper bound of order $O({\log{t} \over \sqrt{t}})$ and a lower bound of order $O({1 \over \sqrt{t}})$ on the distance to the stationary distribution regardless of the initial state. Due to the lack of a spectral gap, these results lie outside the scope of geometric ergodicity theory., To appear in the Proceedings of the AMS

In this paper we consider the first passage process of a spectrally negative Markov additive process (MAP). The law of this process is uniquely characterized by a certain matrix function, which plays a crucial role in fluctuation theory. We show how to identify this matrix using the theory of Jordan chains associated with analytic matrix functions. This result provides us with a technique that can be used to derive various further identities.

In 1990, Ramaswami proved that, given a Markov renewal process of M/G/1 type, it is possible to construct a Markov renewal process of GI/M/1 type such that the matrix transforms G (z, s) for the M/G/1-type process and R (z, s) for the GI/M/1-type process satisfy a duality relationship. In his 1996 PhD thesis, Bright used time reversal arguments to show that it is possible to define a different dual for positive-recurrent and transient processes of M/G/1 type and GI/M/1 type. Here we compare the properties of the Ramaswami and Bright dual processes and show that the Bright dual has desirable properties that can be exploited in the design of algorithms for the analysis of Markov chains of GI/M/1 type and M/G/1 type.

We analyze the problem of the numerical solution of structured Markov chains encountered in queuing models: we describe the main computational problems and present the most advanced algorithms currently available for their solutions.

Charles Stein has introduced a general approach to proving approx- imation theorems in probability theory. The method is being actively used for normal and Poisson approximation. This paper uses the method to derive rates of convergence of some simple Markov chains to their stationary distribution. The main purpose is to present Stein's general approach in a simple setting where the many choices can be examined and compared.

We study irreducible time-homogenous Markov chains with finite state space in discrete time. We obtain results on the sensitivity of the stationary distribution and other statistical quantities with respect to perturbations of the transition matrix. We define a new closeness relation between transition matrices, and use graph-theoretic techniques, in contrast with the matrix analysis techniques previously used., Comment: 22 pages

We consider the parallel computation of the stationary probability distribution vector of ergodic Markov chains with large state spaces by preconditioned Krylov subspace methods. The parallel preconditioner is obtained as an explicit approximation, in factorized form, of a particular generalized inverse of the generator matrix of the Markov process. Graph partitioning is used to parallelize the whole algorithm, resulting in a two-level method. Conditions that guarantee the existence of the preconditioner are given, and the results of a parallel implementation are presented. Our results indicate that this method is well suited for problems in which the generator matrix can be explicitly formed and stored. © 2001 IMACS. Published by Elsevier Science B.V. All rights reserved.

We present an algorithmic approach to find the stationary probability distribution of M/G/1-type Markov chains which arise frequently in performance analysis of computer and communication networks. The approach unifies finite- and infinite-level Markov chains of this type through a generalized state-space representation for the probability generating function of the stationary solution. When the underlying probability generating matrices are rational, the solution vector for level k, x/sub k/, is shown to be in the matrix-geometric form x/sub k+1/=gF/sup k/H, k/spl ges/0, for the infinite-level case, whereas it takes the modified form x/sub k+1/=g/sub 1/F/sup k//sub 1/H/sub 1/+g/sub 2/F/sup K-k-1//sub 2/H/sub 2/, 0/spl les/k/spl les/K, for the finite-level case. The matrix parameters in the above two expressions can be obtained by decomposing the generalized system into forward and backward subsystems, or, equivalently, by finding bases for certain generalized invariant subspaces of a regular pencil /spl lambda/E-A. We note that the computation of such bases can efficiently be carried out using advanced numerical linear algebra techniques including matrix-sign function iterations with quadratic convergence rates or ordered generalized Schur decomposition. The simplicity of the matrix-geometric form of the solution allows one to obtain various performance measures of interest easily, e.g., overflow probabilities and the moments of the level distribution, which is a significant advantage over conventional recursive methods.

Various notions of geometric ergodicity for Markov chains on general state spaces exist. In this paper, we review certain relations and implications among them. We then apply these results to a collection of chains commonly used in Markov chain Monte Carlo simulation algorithms, the so-called hybrid chains. We prove that under certain conditions, a hybrid chain will "inherit" the geometric ergodicity of its constituent parts.

We consider the ergodic control of a Markov chain on a countable state space with a compact action space in presence of finitely many (say, m) ergodic constraints. Under a condition on the cost functions that penalizes instability, the existence of an optimal stable stationary strategy randomized at a maximum of m states is established using convex analytic arguments.

Application problems are investigated for the Markov chains with quasitoeplitz transition matrix. Generating functions of transient and steady state probabilities, first zero hitting probabilities and mean times are found for various particular cases, corresponding to some known patterns of feedback ( “warm-up,” “switch at threshold” etc.), Level depending dams and queue-depending queueing systems of both M/G/1 and MI/G/1 types with arbitrary random sizes of arriving and departing groups are studied.

A probability density {pk} on the positive integers is of phase type, if it is the probability density of the time till absorption in an (m + l)-state Markov chain with one absorbing state m + 1, and m transient states all of which lead to the absorbing state. If the service times in a discrete time queue have densities of phase type, several transient and stationary probability distributions of interest may be computed by highly efficient algorithms, which are presented in the paper.

A quasi-reversible queue can be associated with certain type of transactions of a Markov chain. It is shown that if Markov chains are coupled in a certain way, then to the resulting chain be associated a queuing network which is itself quasi-reversible and the stationary distribution of the chain takes the product form. The product form for mixed networks is derived from the result for open networks.

A general notion of positive dependence among successive observations in a finite-state stationary process is studied, with particular attention to the case of a stationary ergodic Markov chain. This dependence condition can be expressed as a positivity condition on the joint probability matrices of pairs of observations. Some useful conditions equivalent to positive dependence are obtained for reversible chains, but shown not to be equivalent for nonreversible chains.

We consider iterative methods for the minimal nonnegative solution of the matrix equation G = Σ i =0 A i G , where the matrice A , are nonnegative and Σ i =0 A 1 is stochastic. Convergence theory for an inversion free algorithm is established. The convergence rate of this algorithm is shown to be comparable with that of the fastest iteration among three fixed point iterations.

Quantitative geometric rates of convergence for reversible Markov chains are closely related to the spectral gap of the corresponding operator, which is hard to calculate for general state spaces. This article describes a geometric argumen t to give different types of bounds for spectral gaps of Markov chains on bounded subsets of R n and to compare the rates of convergence of different Markov chains.

We study the properties of finite ergodic Markov Chains whose transition probability matrix P is singular. The results establish bounds on the convergence time of Pm to a matrix where all the rows are equal to the stationary distribution of P. The results suggest a simple rule for identifying the singular matrices which do not have a finite convergence time. We next study finite convergence to the stationary distribution independent of the initial distribution. The results establish the connection between the convergence time and the order of the minimal polynomial of the transition probability matrix. A queuing problem and a maintenance Markovian decision problem which possess the property of rapid convergence are presented.

In this paper circuit chains of superior order are defined as multiple Markov chains for which transition probabilities are expressed in terms of the weights of a finite class of circuits in a finite set, in connection with kinetic properties along the circuits. Conversely, it is proved that if we join any finite doubly infinite strictly stationary Markov chain of order r for which transitions hold cyclically with a second chain with the same transitions for the inverse time-sense, then they may be represented as circuit chains of order r.