INCREASING CONVEX MONOTONE MARKOV CHAINS: THEORY ALGORITHM AND APPLICATIONS

Marin Mersenne

Description

Niveau: Supérieur, Doctorat, Bac+8
INCREASING CONVEX MONOTONE MARKOV CHAINS: THEORY, ALGORITHM AND APPLICATIONS? MOUAD BEN MAMOUN†‡ , ANA BUSˇIC† , JEAN-MICHEL FOURNEAU†, AND NIHAL PEKERGIN† Abstract. We develop theoretical and algorithmic aspects of discrete-time Markov chain com- parison with the increasing convex order. This order is based on the variability of the process and it is expected that one can get more accurate bounds with such an order although the monotonicity property is more complex. We give a characterization for finite state space to obtain an algebraic de- scription which is suitable for an algorithmic framework. We develop an algorithm and we introduce some applications related to the worst case stochastic analysis when some high level information is known, but not the complete structure of the chain. Key words. Markov chains, stochastic bounds AMS subject classifications. 60E15, 60J22, 15A51 1. Introduction. Comparison techniques have gained an increasing popularity in the study of stochastic processes [23]. These techniques may be related to various mathematical theory (stochastic ordering, polyhedral theory, Markov chain decision process, stochastic recurrence equation). In the context of numerical analysis of Markov chains, the first idea was to analyze systems which are too difficult for numerical analysis. One can compare a chain of the model with another one which is simpler to solve. A recent survey [16] presents several solutions that we can group into two key ideas: reduction of the state space or using an ad hoc structure, the numerical analysis of which is simpler.

• increasing convex monotone


• order


• however


• icx


• all increasing


• con- tinuous time


• markov chains

Sujets

• United States
• Fourneau
• Marin Mersenne
• However
• Markov chain

Informations

• Publié par: profil-zyak-2012
• Nombre de lectures: 20
• Langue: English

Extrait

INCREASING CONVEX MONOTONE MARKOV CHAINS: THEORY, ALGORITHM AND APPLICATIONS ∗ MOUAD BEN MAMOUN † ‡ A,CS ˇ´ IANUB † , JEAN-MICHEL FOURNEAU † , AND NIHAL PEKERGIN † §

Abstract.We develop theoretical and algorithmic aspects of discrete-time Markov chain com- parison with the increasing convex order. This order is based on the variability of the process and it is expected that one can get more accurate bounds with such an order although the monotonicity property is more complex. We give a characterization for finite state space to obtain an algebraic de- scription which is suitable for an algorithmic framework. We develop an algorithm and we introduce some applications related to the worst case stochastic analysis when some high level information is known, but not the complete structure of the chain.

Key words.Markov chains, stochastic bounds

AMS subject classifications.60E15, 60J22, 15A51

1. Introduction.Comparison techniques have gained an increasing popularity in the study of stochastic processes [23]. These techniques may be related to various mathematical theory (stochastic ordering, polyhedral theory, Markov chain decision process, stochastic recurrence equation). In the context of numerical analysis of Markov chains, the first idea was to analyze systems which are too difficult for numerical analysis. One can compare a chain of the model with another one which is simpler to solve. A recent survey [16] presents several solutions that we can group into two key ideas: reduction of the state space or using an ad hoc structure, the numerical analysis of which is simpler. The first approach was shown to be very efficient [25]. The stochastic approach was developed using projection or functions of Markov chains [13] and an algorithmic derivation of smaller chains based on strong or weak lumpability [28, 21, 15] was proposed. Other algorithms to obtain upper Hessenberg or single input macro state chains were also proposed in [16, 8]. A tool providing all these algorithms was also demonstrated [14]. However all these approaches are based on the strong stochastic ordering ( st - ordering) among random variables. This order is quite natural because it is associated with sample-paths and coupling. Nevertheless, many other stochastic orders have been studied. For instance, the variability orders ( icx and icv ) have been used to compare different queueing models when we change the variability of arrival or service distributions. To the best of our knowledge, very little was done to construct bounding Markov chains with these orders. Vincent’s pioneering work [1] was the only reference we could find. Note that the lack of algorithms for the increasing convex order ( icx ) has precluded to compare the accuracy of these orderings when we bound Markov chains. However, icx -ordering provides more accurate bounds when we compare random variables, as st -comparison implies icx -comparison. Another completely different application of bounds was recently proposed by P. Buchholz [7]. The main assumption is that the modelers do not know the real transi-

∗ ssawkrowdetroppuisThowtefokr´eitdEanO-URInNGhtfsorAmIC´ScerubyprojectSure-Pa excellence. † Av5,,4esinelYvn-e-nitneuQ-tniaSsilleersaedeVsit´vire,MnURPSi8035Ver--snUsi7,d.setEta sailles, France. Email:{mobe, abusic, jmf, nih}[e-mail].u ‡ V,B.mmed4,RaP101aMorab,tcsrevinUahoMe´ti § tnereC75013Paris,FranceriMaernMnnseUne,revi´tisraPe,1si 189

190

ˇ ´ M. BEN MAMOUN, A. BUSIC, J.-M. FOURNEAU, AND N. PEKERGIN

tion probabilities. Thus, one wants to model a system by a family of Markov chains where the transition probabilities belong to an interval of probabilities. One has to derive the worst case (or the best case) for all the matrices in the set. The theoretical arguments rely on Courtois’s polyhedral approach. The algorithms are very accurate as the bounds can be reached by a matrix in the set. Unfortunately the complexity is quite high. Very recently a similar problem was solved independently by Haddad and Moreaux [18]. Again, one has to find a bound for a set of matrices. However, Haddad and Moreaux’s approach is quite different and relies on stochastic compari- son with st  Noteorder. The set is given through componentwise extremal matrices. that these matrices are useless for a direct computation as they are not stochastic. The authors derive an algorithm to find an upper bounding monotone matrix for all elements in the set according to the st  algorithm is very simple and itsorder. This complexity is relatively small (less than quadratic). However the method seems to be less accurate than Buchholz’s method. Note that to the best of our knowledge there is no comparison between these two new methods. The techniques we use in this paper are quite different. Here we improve the theory of icx  order is known This-ordering for finite discrete time Markov chains. for a long time but very little was known in the context of Markov chains. Unlike the st order, this stochastic order imposes difficult constraints for the monotonicity property and, until recently, it was an open problem to build icx -monotone bound- ing matrices. In [4] an algorithm has been designed to construct icx -monotone bounding matrices that belong to a class of matrices denoted as classC. However the algorithm relies on the specific monotonicity characterization of classCMarkov chains. Here we develop a general algorithm to obtain an icx -monotone upper bound for a given stochastic matrix. We also show that the icx order is more accurate than the st order when we derive some worst case stochastic process for which only the expected value and a pattern of nonzero transitions are known. This problem is some- how related to the problem considered by Buchholz, Haddad and Moreaux. We do not assume that the set of Markov chains we must bound is defined by intervals on the elements, but we know the pattern of nonzero transitions and the average, and we build the processes which provides extremal distributions. The remaining of the paper is organized as follows. In Section 2 we present a brief overview of the comparison of random variables and Markov chains under some stochastic order when the state space is endowed with a total order. We also stress that the stochastic comparison approach is much more versatile than the polyhedral technique developed by Courtois [10, 11] even if it is often less accurate. Then we de- velop in Section 3 the theory to compare finite discrete time Markov chains (DTMCs) with the icx order. Section 4 is devoted to an algorithm to build an icx -monotone upper bound of a Markov chain. Finally in Section 5 we present two applications of our approach. The first application consists in deriving the worst case of a family of Markov chains where the transitions are defined by their expectation and a pattern for nonzero transitions. The second one is related to the absorption time of a DTMC with one absorbing state and can be used to bound a phase type (PH) distribution modeling a general service time. By doing so, the complexity in two level modeling formalisms can be significantly reduced.

2. A brief presentation.Here we state some basic definitions and results on the stochastic comparison approach. We refer to [24, 26] for further details. First we give the definition of stochastic comparison of two random variables taking values on a totally ordered spaceE. LetF st denote the class of all increasing real functions on