PROJEKTY @

Stochastic Bounds for Markov Chains and how to use them for performance evaluation - Key-note speach by prof. Jean Michel Fourneau

Jean Michel Fourneau

Professor at the Université de Versailles

Slides

The key-note slides in pdf format

Abstract

We survey several algortihms and applications of stochastic comparison of Discrete Time Markov Chains. These techniques lead to an important reduction on  time and memory complexity when one is able to compare the initial rewards with rewards on smaller chains.  We also show that stochastic comparison and stochastic monotonicity can provide intervals for rewards when models are not completly known (some parameters are missing). Finally we can prove some qualitative properties due to the  stochastic monotonicity or the level crossing ordering or Markov Chains.

In this lecture we present some applications of stochastic comparison of Discrete Time Markov Chains. The approach differs from  sample path techniques and coupling theorem applied to models  as we only consider Markov chains and algorithms on stochastic  matrices. These algorithms build stochastic matrices which finally provide bounds on the rewards. We consider DTMC but we also show how we can apply the method to Continuous Time Markov Chains. We consider three typical problems we have to deal with when the consider a Markovian models.

The most known problem is the size of the state space. Even if the tensor representation provides an efficient manner to store the non zero entries of the transition rate matrix, it is still difficult to solve the model. We are interested in performance measures defined as reward functions on the steady-state or transient distribution or by first passage time (for instance to a faulty state in dependability modeling). Thus the numerical computation of the analysis is mainly the computation of the steady-state or transient distributions  or the fundamental matrix. This is in general difficult because of the memory space and time requirements. Sometimes it is even impossible to store a vector of states. We also have a problem related to the parametrization of the model. Finding realistic parameters for a Markovian model may be a very difficult task. Sometimes we know that some transition exist but we do not know their probabilities. Instead we can find an interval of probability for all the transitions. Thus the model is associated to a set of Markov chains. Some models are also described by a set of distributions rather than a single one. Finally, we sometimes need qualitative properties rather than numerical results. For instance we may want to prove that the reward we analyze is non decreasing with a parameter. Numerical analysis does not help here.

We show in that tutorial that stochastic comparison of Markov chains may lead to an efficient solution for these three problems. While modeling high speed networks or dependable systems, it is often sufficient  to satisfy the requirements for the Quality of Service we expect. Exact values of the performance measures are not necessary in this case and bounding some reward functions is often sufficient. So, we advocate the use of stochastic comparison to prove that  QoS requirements are satisfied. We can derive bounds for a family of stochastic matrices. Thus we are able to give an interval for rewards on models which are not completely specified. The stochastic monotonicity and the level crossing ordering of Markov chains allow to prove some qualitative properties of the models.

About the speaker

Jean-Michel Fourneau is Professor of Computer Science at the University of Versailles St Quentin, France. He was formerly with Ecole Nationale des Telecommunications, Paris and University of Paris XI Orsay as an Assistant Professor. He graduated in Statistics and Economy from Ecole Nationale de la Statistique et de l'Administation Economique, Paris and he obtained is PHD and his habilitation in Computer Science at Paris XI Orsay in 87 and 91 respectively. He is an elected member of IFIP WG7.3 the IFIP working group on performance evaluation.

He is the Head of the Performance Evaluation team within PRiSM laboratory at Versailles University and his recent research interests are algorithmic performance evaluation, Stochastic Automata Networks, G-networks, stochastic bounds, and application to high speed networks, and all optical networks.

---