Semiconvergence of extrapolated iterative methods for singular linear systems

In this paper, we discuss convergence of the extrapolated iterative methods for solving singular linear systems. A general principle of extrapolation is presented. The semiconvergence of an extrapolated method induced by a regular splitting and a nonnegative splitting is proved whenever the coefficient matrix A is a singular M-matrix with ‘property c’ and an irreducible singular M-matrix, respectively. Since the (generalized, block) JOR and AOR methods are respectively the extrapolated methods of the (generalized, block) Jacobi and SOR methods, so the semiconvergence of the (generalized, block) JOR and AOR methods for solving general singular systems are proved. Furthermore, the semiconvergence of the extrapolated power method, the (block) JOR, AOR and SOR methods for solving Markov chains are discussed.     

Wide-sense regeneration for Harris recurrent Markov processes: an open problem

Harris recurrence is a widely used tool in the analysis of queueing systems. For discrete-time Harris chains, such systems automatically exhibit wide-sense regenerative structure, so that renewal theory can be applied to questions related to convergence of the transition probabilities to the equilibrium distribution. By contrast, in continuous time, the question of whether all Harris recurrent Markov processes are automatically wide-sense regenerative is an open problem. This paper reviews the key structural results related to regeneration for discrete-time chains and continuous time Markov processes, and describes the key remaining open problem in this subject area.     

Asymptotic Properties of Parabolic Systems for Null-Recurrent Switching Diffusions

This work is concerned with the asymptotic behavior of systems of parabolic equations arising fromnull-recurrent switching diffusions,which are diffusion processes modulated by continuous-time Markov chains.A sufficient condition for null recurrence is presented.Moreover,convergence rate of the solutions of systems ofhomogeneous parabolic equations under suitable conditions is established.Then a case study on verifying one ofthe conditions proposed is provided with the use of a two-state Markov chain.To verify the condition,boundaryvalue problems (BVPs) for parabolic systems are treated,which are not the usual two-point BVP type.Anextra condition in the interior is needed resulting in jump discontinuity of the derivative of the correspondingsolution.     

The Successive Over Relaxation Method (SOR) and Markov Chains

In the sixties SOR has been the working horse for the numerical solution of elliptic boundary problems; classical results for chosing the relaxation parameter have been derived by D. Young and R.S. Varga. In the last fifteen years SOR has been examined for the computation of the stationary distribution of Markov chains. In the paper there are pointed out similarities and differences compared with the application of SOR for elliptic boundary problems.     

Sojourn time problems in feedback queues

A brief survey of the literature on sojourn time problems in single node feedback queueing systems is presented. The derivation of the distribution and moments of the sojourn time of a typical customer in a Markov renewal queue with state dependent feedback is considered in depth. The techniques used relate to the derivation of a first passage time distribution in a particular Markov renewal process. These results are applied to birth-death queues with state dependent feedback. For such models an alternative approach using the theory of Markov chains in continuous time is also examined.     

The cyclic reduction algorithm: from Poisson equation to stochastic processes and beyond

Cyclic reduction is an algorithm invented by G. H. Golub and R. W. Hockney in the mid 1960s for solving linear systems related to the finite differences discretization of the Poisson equation over a rectangle. Among the algorithms of Gene Golub, it is one of the most versatile and powerful ever created. Recently, it has been applied to solve different problems from different applicative areas. In this paper we survey the main features of cyclic reduction, relate it to properties of analytic functions, recall its extension to solving more general finite and infinite linear systems, and different kinds of nonlinear matrix equations, including algebraic Riccati equations, with applications to Markov chains, queueing models and transport theory. Some new results concerning the convergence properties of cyclic reduction and its applicability are proved under very weak assumptions. New formulae for overcoming breakdown are provided.     

Hoeffding's inequality for Markov processes via solution of Poisson's equation

We investigate Hoeffding's inequality for both discrete-time Markov chains and continuous-time Markov processes on a general state space. Our results relax the usual aperiodicity restriction in the literature, and the explicit upper bounds in the inequalities are obtained via the solution of Poisson's equation. The results are further illustrated with applications to queueing theory and reective diffusion processes.     

A new numerical approach for solving a class of singular two-point boundary value problems

In this paper, we consider the following class of singular two-point boundary value problem posed on the interval x ?? (0, 1]

$$\begin{array}{@{}rcl@{}} (g(x)y^{\prime})^{\prime}=g(x)f(x,y),\\ y^{\prime}(0)=0,\mu y(1)+\sigma y^{\prime}(1)=B. \end{array} $$

A recursive scheme is developed, and its convergence properties are studied. Further, the error estimation of the method is discussed. The proposed scheme is based on the integral equation formalism and optimal homotopy analysis method in which a recursive scheme is established without any undetermined coefficients. The original differential equation is transformed into an equivalent integral equation to remove the singularity. The integral equation is then made free of undetermined coefficients by imposing the boundary conditions on it. Finally, the integral equation without any undetermined coefficients is efficiently treated by using optimal homotopy analysis method for finding the numerical solution. The optimal control-convergence parameter involved in the components of the series solution is obtained by minimizing the squared residual error equation. The present method is applied to obtain numerical solution of singular boundary value problems arising in various physical models, and numerical results show the advantages of our method over the existing methods.     

Equivalence of conditions for convergence of iterative methods for singular equations

Equivalence is shown between different conditions for convergence of iterative methods for consistent singular systems of linear equations on Banach spaces. These systems appear in many applications, such as Markov chains and Markov processes. The conditions considered relate the range and null spaces of different operators.     

Moderate deviations for time-varying dynamic systems driven by non-homogeneous Markov chains with Two-time Scales

Motivated by problems arising in time-dependent queues and dynamic systems with random environment, this work develops moderate deviations principles for dynamic systems driven by a fast-varying non-homogeneous Markov chain in continuous time. A distinct feature is that the Markov chain is time dependent or inhomogeneous, so are the dynamic systems. Under irreducibility of the non-homogeneous Markov chain, moderate deviations of a non-homogeneous functional are established first. With the help of a martingale problem formulation and a functional central limit theorem for the two timescale system, both upper and lower bounds of moderate deviations are obtained for the rapidly fluctuating Markovian systems. Then applications to queueing systems and dynamic systems modulated by a fast-varying Markov chain are examined.     

Block Two-stage Methods for Singular Systems and Markov Chains

The use of block two-stage methods for the iterative solution of consistent singular linear systems is studied. In these methods, suitable for parallel computations, different blocks, i.e., smaller linear systems, can be solved concurrently by different processors. Each of these smaller systems are solved by an (inner) iterative method. Hypotheses are provided for the convergence of non-stationary methods, i.e., when the number of inner iterations may vary from block to block and from one outer iteration to another. It is shown that the iteration matrix corresponding to one step of the block method is convergent, i.e., that its powers converge to a limit matrix. A theorem on the convergence of the infinite product of matrices with the same eigenspace corresponding to the eigenvalue 1 is proved, and later used as a tool in the convergence analysis of the block method. The methods studied can be used to solve any consistent singular system, including discretizations of certain differential equations. They can also be used to find stationary probability distribution of Markov chains. This last application is considered in detail.     

Two classes of time-inhomogeneous Markov chains: Analysis of the periodic case

We consider the M/G/1 and GI/M/1 types of Markov chains for which their one step transitions depend on the times of the transitions. These types of Markov chains are encountered in several stochastic models, including queueing systems, dams, inventory systems, insurance risk models, etc. We show that for the cases when the time parameters are periodic the systems can be analyzed using some extensions of known results in the matrix-analytic methods literature. We have limited our examples to those relating to queueing systems to allow us a focus. An example application of the model to a real life problem is presented.     

Implementation of Markovian Queueing Network Model with Multiple Closed Chains

Mathematical strategy portrays the performance evaluation of computer and communication system and it deals with the stochastic properties of the multiclass Markovian queueing system with class-dependent and server-dependent service times. An algorithm is designed where the job transitions are characterized by more than one closed Markov chain. Generating functions are implemented to derive closed form of solutions and product form solution with the parameters such as stability, normalizations constant and marginal distributions. For such a system with N servers and L chains, the solutions are considerably more complicated than those for the systems with one sub-chain only. In Multi-class queueing network, a job moves from a queue to another queue with some probability after getting a service. A multiple class of customer could be open or closed where each class has its own set of queueing parameters. These parameters are obtained by analyzing each station in isolation under the assumption that the arrival process of each class is a state-dependent Markovian process along with different service time distributions. An algorithmic approach is implemented from the generating function representation for the general class of Networks. Based on the algorithmic approach it is proved that how open and closed sub-chain interact with each other in such system. Specifically, computation techniques are provided for the calculation of the Markovian model for multiple chains and it is shown that these algorithms converge exponentially fast.     

Fuzzy Markov Chains and Decision-Making

Decision-making in an environment of uncertainty and imprecision for real-world problems is a complex task. In this paper it is introduced general finite state fuzzy Markov chains that have a finite convergence to a stationary (may be periodic) solution. The Cesaro average and the -potential for fuzzy Markov chains are defined, then it is shown that the relationship between them corresponds to the Blackwell formula in the classical theory of Markov decision processes. Furthermore, it is pointed out that recurrency does not necessarily imply ergodicity. However, if a fuzzy Markov chain is ergodic, then the rows of its ergodic projection equal the greatest eigen fuzzy set of the transition matrix. Then, the fuzzy Markov chain is shown to be a robust system with respect to small perturbations of the transition matrix, which is not the case for the classical probabilistic Markov chains. Fuzzy Markov decision processes are finally introduced and discussed.     

Rounding Error Analysis in Solving M-Matrix Linear Systems of Block Hessenberg Form

The problem of solving large M-matrix linear systems with sparse coefficient matrix in block Hessenberg form is here addressed. In previous work of the authors a divide-and-conquer strategy was proposed and a backward error analysis of the resulting algorithm was presented showing its effectiveness for the solution of computational problems of queueing theory and Markov chains. In particular, it was shown that for block Hessenberg M-matrices the algorithm is weakly backward stable in the sense that the computed solution is the exact solution of a nearby linear system, where the norm of the perturbation is proportional to the condition number of the coefficient matrix. In this note a better error estimate is given by showing that for block Hessenberg M-matrices the algorithm is even backward stable.     

Solving matrix polynomial equations arising in queueing problems

The matrix equation ∑_i=0ⁿA_iXⁱ=0, where the A_i's are m×m matrices, is encountered in the numerical solution of Markov chains which model queueing problems. We provide here a unifying framework in terms of Möbius' mapping to relate different resolution algorithms having a quadratic convergence. This allows us to compare algorithms like logarithmic reduction (LR) and cyclic reduction (CR), which extend Graeffe's iteration to matrix polynomials, and the invariant subspace (IS) approach, which extends Cardinal's algorithm. We devise new iterative techniques having quadratic convergence and present numerical experiments.     

Local mean-field Markov processes: An application to message-switching networks

Summary Local mean-field Markov processes are constructed from local mean-field dynamical semigroups of Markov transition operators. This provides a general scheme for the convergence of empirical measure processes for tagged particles in the thermodynamic limit of classical interacting particle systems. As an application the Poissonian approximation for message-switching queueing networks is investigated.     

On perturbation bounds for continuous-time Markov chains

We suggest an approach to obtaining general estimates of stability in terms of special “weighted” norms related to total variation. Two important classes of continuous-time Markov chains are considered for which it is possible to obtain exact convergence rate estimates (and hence, guarantee exact stability estimates): birth–death–catastrophes processes, and queueing models with batch arrivals and group services.     

New convergence results on functional iteration techniques for the numerical solution of M/G/1 type Markov chains

Summary. By performing an accurate analysis of the convergence, we give a complete theoretical explanation of the experimental behaviour of functional iteration techniques for the computation of the minimal nonnegative solution of the matrix equation , arising in the numerical solution of M/G/1 type Markov chains (here the 's are nonnegative matrices such that the matrix is column stochastic). Moreover, we introduce a general class of functional iteration methods, which includes the standard methods, and we give an optimality convergence result in this class. Received September 1, 1995 / Revised version received September 9, 1996     

Stationary Analysis of a Fluid Queue Driven by Some Countable State Space Markov Chain

Motivated by queueing systems playing a key role in the performance evaluation of telecommunication networks, we analyze in this paper the stationary behavior of a fluid queue, when the instantaneous input rate is driven by a continuous-time Markov chain with finite or infinite state space. In the case of an infinite state space and for particular classes of Markov chains with a countable state space, such as quasi birth and death processes or Markov chains of the G/M/1 type, we develop an algorithm to compute the stationary probability distribution function of the buffer level in the fluid queue. This algorithm relies on simple recurrence relations satisfied by key characteristics of an auxiliary queueing system with normalized input rates.