Dagstuhl Seminar Proceedings, Volume 7461



Publication Details

  • published at: 2008-04-07
  • Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Access Numbers

Documents

No documents found matching your filter selection.
Document
07461 Abstracts Collection – Numerical Methods for Structured Markov Chains

Authors: Dario A. Bini, Beatrice Meini, Vaidyanathan Ramaswami, Marie-Ange Remiche, and Peter Taylor


Abstract
From 11.11. to 14.11.07, the Dagstuhl Seminar 07461 ``Numerical Methods for Structured Markov Chains'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.

Cite as

Dario A. Bini, Beatrice Meini, Vaidyanathan Ramaswami, Marie-Ange Remiche, and Peter Taylor. 07461 Abstracts Collection – Numerical Methods for Structured Markov Chains. In Numerical Methods for Structured Markov Chains. Dagstuhl Seminar Proceedings, Volume 7461, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{bini_et_al:DagSemProc.07461.1,
  author =	{Bini, Dario A. and Meini, Beatrice and Ramaswami, Vaidyanathan and Remiche, Marie-Ange and Taylor, Peter},
  title =	{{07461 Abstracts Collection – Numerical Methods for Structured Markov Chains}},
  booktitle =	{Numerical Methods for Structured Markov Chains},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7461},
  editor =	{Dario Bini and Beatrice Meini and Vaidyanathan Ramaswami and Marie-Ange Remiche and Peter Taylor},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07461.1},
  URN =		{urn:nbn:de:0030-drops-14046},
  doi =		{10.4230/DagSemProc.07461.1},
  annote =	{Keywords: Matrix analytic methods, markov processes, queuing theory, numerical methods, structured matrices, telecommunication modeling, performance evaluation}
}
Document
07461 Executive Summary – Numerical Methods for Structured Markov Chains

Authors: Dario A. Bini, Beatrice Meini, Vaidyanathan Ramaswami, Marie-Ange Remiche, and Peter Taylor


Abstract
This Dagstuhl seminar has brought together leaders and young researchers in the fields of analysis of numerical algorithms, applied stochastic modeling and statistical inference, with the result of stimulating exchange of methodologies and experiences and generating synergetic collaborations. This has favored a better communication between these worlds where problems from the applications feed the theoretical research and where advanced numerical tools can be utilized in applications with reciprocal advantages.

Cite as

Dario A. Bini, Beatrice Meini, Vaidyanathan Ramaswami, Marie-Ange Remiche, and Peter Taylor. 07461 Executive Summary – Numerical Methods for Structured Markov Chains. In Numerical Methods for Structured Markov Chains. Dagstuhl Seminar Proceedings, Volume 7461, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{bini_et_al:DagSemProc.07461.2,
  author =	{Bini, Dario A. and Meini, Beatrice and Ramaswami, Vaidyanathan and Remiche, Marie-Ange and Taylor, Peter},
  title =	{{07461 Executive Summary – Numerical Methods for Structured Markov Chains}},
  booktitle =	{Numerical Methods for Structured Markov Chains},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7461},
  editor =	{Dario Bini and Beatrice Meini and Vaidyanathan Ramaswami and Marie-Ange Remiche and Peter Taylor},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07461.2},
  URN =		{urn:nbn:de:0030-drops-14006},
  doi =		{10.4230/DagSemProc.07461.2},
  annote =	{Keywords: Matrix analytic methods, Markov processes, queuing theory, numerical methods, structured matrices, telecommunication modeling, performance evaluation.}
}
Document
A policy iteration algorithm for Markov decision processes skip-free in one direction

Authors: Joke Lambert, Benny van Houdt, and Chris Blondia


Abstract
In this paper we present a new algorithm for policy iteration for Markov decision processes (MDP) skip-free in one direction. This algorithm, which is based on matrix analytic methods, is in the same spirit as the algorithm of White (Stochastic Models, 21:785-797, 2005) which was limited to matrices that are skip-free in both directions. Optimization problems that can be solved using Markov decision processes arise in the domain of optical buffers, when trying to improve loss rates of fibre delay line (FDL) buffers. Based on the analysis of such an FDL buffer we present a comparative study between the different techniques available to solve an MDP. The results illustrate that the exploitation of the structure of the transition matrices places us in a position to deal with larger systems, while reducing the computation times.

Cite as

Joke Lambert, Benny van Houdt, and Chris Blondia. A policy iteration algorithm for Markov decision processes skip-free in one direction. In Numerical Methods for Structured Markov Chains. Dagstuhl Seminar Proceedings, Volume 7461, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{lambert_et_al:DagSemProc.07461.3,
  author =	{Lambert, Joke and van Houdt, Benny and Blondia, Chris},
  title =	{{A policy iteration algorithm for Markov decision processes skip-free in one direction}},
  booktitle =	{Numerical Methods for Structured Markov Chains},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7461},
  editor =	{Dario Bini and Beatrice Meini and Vaidyanathan Ramaswami and Marie-Ange Remiche and Peter Taylor},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07461.3},
  URN =		{urn:nbn:de:0030-drops-14032},
  doi =		{10.4230/DagSemProc.07461.3},
  annote =	{Keywords: Markov Decision Process, Policy Evaluation, Skip-Free, Optical buffers, Fibre Delay Lines}
}
Document
Characterizing Coxian Distributions of Algebraic Degree q and Triangular Order p

Authors: Mark Fackrell


Abstract
In this research note we present a procedure to characterize the set of all Coxian distributions of algebraic degree q that have Coxian representations of order p where p > q.

Cite as

Mark Fackrell. Characterizing Coxian Distributions of Algebraic Degree q and Triangular Order p. In Numerical Methods for Structured Markov Chains. Dagstuhl Seminar Proceedings, Volume 7461, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{fackrell:DagSemProc.07461.4,
  author =	{Fackrell, Mark},
  title =	{{Characterizing Coxian Distributions of Algebraic Degree q and Triangular Order p}},
  booktitle =	{Numerical Methods for Structured Markov Chains},
  pages =	{1--10},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7461},
  editor =	{Dario Bini and Beatrice Meini and Vaidyanathan Ramaswami and Marie-Ange Remiche and Peter Taylor},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07461.4},
  URN =		{urn:nbn:de:0030-drops-13916},
  doi =		{10.4230/DagSemProc.07461.4},
  annote =	{Keywords: Phase-type distribution, Coxian distribution, algebraic degree, triangular order, rational Laplace-Stieltjes transform}
}
Document
Current results and open questions on PH and MAP characterization

Authors: Levente Bodrog, Armin Heindl, Gábor Horváth, Miklós Telek, and András Horváth


Abstract
Stochastic processes with matrix exponential kernels have a wide range of applications due to the availability of efficient matrix analytic methods. The characterization of these processes is in progress in recent years. Basic questions like the flexibility, the degree of freedom, the most efficient (canonical) representation of these models are under study. The presentation collects a set of available results and related open questions.

Cite as

Levente Bodrog, Armin Heindl, Gábor Horváth, Miklós Telek, and András Horváth. Current results and open questions on PH and MAP characterization. In Numerical Methods for Structured Markov Chains. Dagstuhl Seminar Proceedings, Volume 7461, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{bodrog_et_al:DagSemProc.07461.5,
  author =	{Bodrog, Levente and Heindl, Armin and Horv\'{a}th, G\'{a}bor and Telek, Mikl\'{o}s and Horv\'{a}th, Andr\'{a}s},
  title =	{{Current results and open questions on PH and MAP characterization}},
  booktitle =	{Numerical Methods for Structured Markov Chains},
  pages =	{1--6},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7461},
  editor =	{Dario Bini and Beatrice Meini and Vaidyanathan Ramaswami and Marie-Ange Remiche and Peter Taylor},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07461.5},
  URN =		{urn:nbn:de:0030-drops-14010},
  doi =		{10.4230/DagSemProc.07461.5},
  annote =	{Keywords: PH distribution, ME distribution, MAP, MEP}
}
Document
Erlangian Approximation to Finite Time Ruin Probabilities in Perturbed Risk Models

Authors: Kaiqi Yu, David A. Stanford, and Jiandong Ren


Abstract
In this work-in-progress, we consider perturbed risk processes that have an underlying Markovian structure, including Markovian risk processes, and Sparre-Andersen risk processes when both inter claim times and claim sizes are phase-type. We apply the Erlangization method to this risk process in order to obtain an accurate approximation of the finite time ruin probability. In addition, we recognize a repeating structure in the probability matrices we work with. This is the key element in developing more efficent algorithms for the computation of the ruin probabilities. Several numerical examples are present to illustrate the model.

Cite as

Kaiqi Yu, David A. Stanford, and Jiandong Ren. Erlangian Approximation to Finite Time Ruin Probabilities in Perturbed Risk Models. In Numerical Methods for Structured Markov Chains. Dagstuhl Seminar Proceedings, Volume 7461, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{yu_et_al:DagSemProc.07461.6,
  author =	{Yu, Kaiqi and Stanford, David A. and Ren, Jiandong},
  title =	{{Erlangian Approximation to Finite Time Ruin Probabilities in Perturbed Risk Models}},
  booktitle =	{Numerical Methods for Structured Markov Chains},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7461},
  editor =	{Dario Bini and Beatrice Meini and Vaidyanathan Ramaswami and Marie-Ange Remiche and Peter Taylor},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07461.6},
  URN =		{urn:nbn:de:0030-drops-13999},
  doi =		{10.4230/DagSemProc.07461.6},
  annote =	{Keywords: Perturbed risk processes, finite-time ruin probability, phase-type distribution, fluid flow models, Erlangization}
}
Document
From Algebraic Riccati equations to unilateral quadratic matrix equations: old and new algorithms

Authors: Dario A. Bini, Beatrice Meini, and Federico Poloni


Abstract
The problem of reducing an algebraic Riccati equation $XCX-AX-XD+B=0$ to a unilateral quadratic matrix equation (UQME) of the kind $PX^2+QX+R$ is analyzed. New reductions are introduced which enable one to prove some theoretical and computational properties. In particular we show that the structure preserving doubling algorithm of B.D.O. Anderson [Internat. J. Control, 1978] is nothing else but the cyclic reduction algorithm applied to a suitable UQME. A new algorithm obtained by complementing our reductions with the shrink-and-shift tech- nique of Ramaswami is presented. Finally, faster algorithms which require some non-singularity conditions, are designed. The non-singularity re- striction is relaxed by introducing a suitable similarity transformation of the Hamiltonian.

Cite as

Dario A. Bini, Beatrice Meini, and Federico Poloni. From Algebraic Riccati equations to unilateral quadratic matrix equations: old and new algorithms. In Numerical Methods for Structured Markov Chains. Dagstuhl Seminar Proceedings, Volume 7461, pp. 1-28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{bini_et_al:DagSemProc.07461.7,
  author =	{Bini, Dario A. and Meini, Beatrice and Poloni, Federico},
  title =	{{From Algebraic Riccati equations to unilateral quadratic matrix equations: old and new algorithms}},
  booktitle =	{Numerical Methods for Structured Markov Chains},
  pages =	{1--28},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7461},
  editor =	{Dario Bini and Beatrice Meini and Vaidyanathan Ramaswami and Marie-Ange Remiche and Peter Taylor},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07461.7},
  URN =		{urn:nbn:de:0030-drops-13987},
  doi =		{10.4230/DagSemProc.07461.7},
  annote =	{Keywords: Algebraic Riccati Equation, Matrix Equation, Cyclic Reduction, Structured doubling algorithm}
}
Document
Interarrival Times Characterization and Fitting for Markovian Traffic Analysis

Authors: Giuliano Casale, Eddy Z. Zhang, and Evgenia Smirni


Abstract
We propose a traffic fitting algorithm for Markovian Arrival Processes (MAPs) that can capture statistics of any order of interarrival times. By studying real traffic traces, we show that matching higher order properties, in addition to first and second order descriptors, results in increased queueing prediction accuracy with respect to other algorithms that only match the mean, coefficient of variation, and autocorrelations. The result promotes the idea of modeling traffic traces using the interarrival time process instead of the counting process that is more frequently employed in previous work, but for which higher order moments are difficult to manipulate. We proceed by first characterizing the general properties of MAPs using a spectral approach. Based on this characterization, we show how different MAP processes can be combined together using Kronecker products to define a larger MAP with predefined properties of interarrival times. We then devise an algorithm that is based on this Kronecker composition and can accurately fit traffic traces. The algorithm employs nonlinear optimization programs that can be customized to fit an arbitrary number of moments and to meet the desired cost-accuracy tradeoff. Numerical results of the fitting algorithm on real HTTP and TCP traffic data, such as the Bellcore Aug89 trace, indicate that the proposed fitting methods achieve increased prediction accuracy with respect to other state-of-the-art fitting methods.

Cite as

Giuliano Casale, Eddy Z. Zhang, and Evgenia Smirni. Interarrival Times Characterization and Fitting for Markovian Traffic Analysis. In Numerical Methods for Structured Markov Chains. Dagstuhl Seminar Proceedings, Volume 7461, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{casale_et_al:DagSemProc.07461.8,
  author =	{Casale, Giuliano and Zhang, Eddy Z. and Smirni, Evgenia},
  title =	{{Interarrival Times Characterization and Fitting for Markovian Traffic Analysis}},
  booktitle =	{Numerical Methods for Structured Markov Chains},
  pages =	{1--8},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7461},
  editor =	{Dario Bini and Beatrice Meini and Vaidyanathan Ramaswami and Marie-Ange Remiche and Peter Taylor},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07461.8},
  URN =		{urn:nbn:de:0030-drops-13908},
  doi =		{10.4230/DagSemProc.07461.8},
  annote =	{Keywords: MAP fitting, interarrival time process, higher-order moments}
}
Document
Matrix Analytic Methods in Branching processes

Authors: Sophie Hautphenne, Guy Latouche, and Marie-Ange Remiche


Abstract
We examine the question of solving the extinction probability of a particular class of continuous-time multi-type branching processes, named Markovian binary trees (MBT). The extinction probability is the minimal nonnegative solution of a fixed point equation that turns out to be quadratic, which makes its resolution particularly clear. We analyze first two linear algorithms to compute the extinction probability of an MBT, of which one is new, and, we propose a quadratic algorithm arising from Newton's iteration method for fixed-point equations. Finally, we add a catastrophe process to the initial MBT, and we analyze the resulting system. The extinction probability turns out to be much more difficult to compute; we use a $G/M/1$-type Markovian process approach to approximate this probability.

Cite as

Sophie Hautphenne, Guy Latouche, and Marie-Ange Remiche. Matrix Analytic Methods in Branching processes. In Numerical Methods for Structured Markov Chains. Dagstuhl Seminar Proceedings, Volume 7461, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{hautphenne_et_al:DagSemProc.07461.9,
  author =	{Hautphenne, Sophie and Latouche, Guy and Remiche, Marie-Ange},
  title =	{{Matrix Analytic Methods in Branching processes}},
  booktitle =	{Numerical Methods for Structured Markov Chains},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7461},
  editor =	{Dario Bini and Beatrice Meini and Vaidyanathan Ramaswami and Marie-Ange Remiche and Peter Taylor},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07461.9},
  URN =		{urn:nbn:de:0030-drops-13935},
  doi =		{10.4230/DagSemProc.07461.9},
  annote =	{Keywords: Branching Processes, Matrix Analytic Methods, Extinction Probability, Catastrophe Process}
}
Document
Multivariate matrix-exponential distributions

Authors: Mogens Bladt and Bo Friis Nielsen


Abstract
We review what is currently known about one-dimensional distributions on the non-negative reals with rational Laplace transform, also known as matrix-exponential distributions. In particular we discuss a flow interpreation which enables one to mimic certain probabilisticly inspired arguments which are known from the theory of phase-type distributions. We then move on to present ongoing research for higher dimensions. We discuss a characterization result, some closure properties, and a number of examples. Finally we present open problems and future perspectives.

Cite as

Mogens Bladt and Bo Friis Nielsen. Multivariate matrix-exponential distributions. In Numerical Methods for Structured Markov Chains. Dagstuhl Seminar Proceedings, Volume 7461, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{bladt_et_al:DagSemProc.07461.10,
  author =	{Bladt, Mogens and Nielsen, Bo Friis},
  title =	{{Multivariate matrix-exponential distributions}},
  booktitle =	{Numerical Methods for Structured Markov Chains},
  pages =	{1--13},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7461},
  editor =	{Dario Bini and Beatrice Meini and Vaidyanathan Ramaswami and Marie-Ange Remiche and Peter Taylor},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07461.10},
  URN =		{urn:nbn:de:0030-drops-13975},
  doi =		{10.4230/DagSemProc.07461.10},
  annote =	{Keywords: Multivariate matrix-exponential distributions, multivariate phase-type distributions, rational Laplace transform}
}
Document
Nonsymmetric algebraic Riccati equations associated with an M-matrix: recent advances and algorithms

Authors: Dario A. Bini, Bruno Iannazzo, Beatrice Meini, and Federico Poloni


Abstract
We survey on theoretical properties and algorithms concerning the problem of solving a nonsymmetric algebraic Riccati equation, and we report on some known methods and new algorithmic advances. In particular, some results on the number of positive solutions are proved and a careful convergence analysis of Newton's iteration is carried out in the cases of interest where some singularity conditions are encountered. From this analysis we determine initial approximations which still guarantee the quadratic convergence.

Cite as

Dario A. Bini, Bruno Iannazzo, Beatrice Meini, and Federico Poloni. Nonsymmetric algebraic Riccati equations associated with an M-matrix: recent advances and algorithms. In Numerical Methods for Structured Markov Chains. Dagstuhl Seminar Proceedings, Volume 7461, pp. 1-31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{bini_et_al:DagSemProc.07461.11,
  author =	{Bini, Dario A. and Iannazzo, Bruno and Meini, Beatrice and Poloni, Federico},
  title =	{{Nonsymmetric algebraic Riccati equations associated with an M-matrix: recent advances and algorithms}},
  booktitle =	{Numerical Methods for Structured Markov Chains},
  pages =	{1--31},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7461},
  editor =	{Dario Bini and Beatrice Meini and Vaidyanathan Ramaswami and Marie-Ange Remiche and Peter Taylor},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07461.11},
  URN =		{urn:nbn:de:0030-drops-13958},
  doi =		{10.4230/DagSemProc.07461.11},
  annote =	{Keywords: Nonsymmetric algebraic Riccati equations, matrix equation, M-matrices, Newton method, quadratically convergent algorithms, cyclic reduction, doubling}
}
Document
On the Properties of Moments of Matrix Exponential Distributions and Matrix Exponential Processes

Authors: Levente Bodrog, András Horváth, and Miklós Telek


Abstract
In this paper we provide properties of moments of matrix exponential distributions and joint moments of matrix exponential processes. Based on the provided properties, an algorithm is presented to compute any finite dimensional moments of these processes based on a set of required (low order) moments. This algorithm does not require the computation of any representation of the given process. We present some related examples to demonstrate the potential use of the properties of moments.

Cite as

Levente Bodrog, András Horváth, and Miklós Telek. On the Properties of Moments of Matrix Exponential Distributions and Matrix Exponential Processes. In Numerical Methods for Structured Markov Chains. Dagstuhl Seminar Proceedings, Volume 7461, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{bodrog_et_al:DagSemProc.07461.12,
  author =	{Bodrog, Levente and Horv\'{a}th, Andr\'{a}s and Telek, Mikl\'{o}s},
  title =	{{On the Properties of Moments of Matrix Exponential Distributions and Matrix Exponential Processes}},
  booktitle =	{Numerical Methods for Structured Markov Chains},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7461},
  editor =	{Dario Bini and Beatrice Meini and Vaidyanathan Ramaswami and Marie-Ange Remiche and Peter Taylor},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07461.12},
  URN =		{urn:nbn:de:0030-drops-13943},
  doi =		{10.4230/DagSemProc.07461.12},
  annote =	{Keywords: Matrix exponential process, Markov arrival process, Matrix exponential distribution, phase type distribution}
}
Document
On the tail decay of M/G/1-type Markov renewal processes

Authors: Dario A. Bini, Beatrice Meini, and Vaidyanathan Ramaswami


Abstract
The tail decay of M/G/1-type Markov renewal processes is studied. The Markov renewal process is transformed into a Markov chain so that the problem of tail decay is reformulated in terms of the decay of the coefficients of a suitable power series. The latter problem is reduced to analyze the analyticity domain of the power series.

Cite as

Dario A. Bini, Beatrice Meini, and Vaidyanathan Ramaswami. On the tail decay of M/G/1-type Markov renewal processes. In Numerical Methods for Structured Markov Chains. Dagstuhl Seminar Proceedings, Volume 7461, pp. 1-7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{bini_et_al:DagSemProc.07461.13,
  author =	{Bini, Dario A. and Meini, Beatrice and Ramaswami, Vaidyanathan},
  title =	{{On the tail decay of M/G/1-type Markov renewal processes}},
  booktitle =	{Numerical Methods for Structured Markov Chains},
  pages =	{1--7},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7461},
  editor =	{Dario Bini and Beatrice Meini and Vaidyanathan Ramaswami and Marie-Ange Remiche and Peter Taylor},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07461.13},
  URN =		{urn:nbn:de:0030-drops-13966},
  doi =		{10.4230/DagSemProc.07461.13},
  annote =	{Keywords: Renewal processes, tail decay, M/G/1-type Markov chains}
}
Document
QBD processes and matrix orthogonal polynomilas: somw new explicit examples

Authors: Alberto F. Grünbaum


Abstract
In the case of birth-and-death processes there are a few exactly solvable situations where the n-step transition matrix can be written down using the Karlin-McGregor formula. A few of these come from group representation theory. I plan to show how this can be extended to some instances of QBD processes with an arbitrary finite number of phases. The group involved is the set of all unitary matrices of size N. For a fixed N one gets examples where the number of phases is a free parameter, and there are a few extra parameters to play with. By tunning these parameters one can exhibit examples where states are recurrent or transient. The rather surprising fact that for these examples one can compute everything explicitly raises the issue of finding a possible network application for this piece of mathematics that involves matrix valued orthogonal polynomials. I will give an ab-initio discussion of the examples starting with the case of one phase.

Cite as

Alberto F. Grünbaum. QBD processes and matrix orthogonal polynomilas: somw new explicit examples. In Numerical Methods for Structured Markov Chains. Dagstuhl Seminar Proceedings, Volume 7461, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{grunbaum:DagSemProc.07461.14,
  author =	{Gr\"{u}nbaum, Alberto F.},
  title =	{{QBD processes and matrix orthogonal polynomilas: somw new explicit examples}},
  booktitle =	{Numerical Methods for Structured Markov Chains},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7461},
  editor =	{Dario Bini and Beatrice Meini and Vaidyanathan Ramaswami and Marie-Ange Remiche and Peter Taylor},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07461.14},
  URN =		{urn:nbn:de:0030-drops-13922},
  doi =		{10.4230/DagSemProc.07461.14},
  annote =	{Keywords: QBD, orthogonal polynomials, Karlin-McGregor formula, representation theory}
}
Document
Structured Markov Chains Arising from Finite-Source Retrial Queues with Orital Search

Authors: Patrick Wüchner, János Sztrik, and Hermann de Meer


Abstract
We consider retrial queueing systems with a finite number of homogeneous sources of calls, a single reliable server, and the search for orbiting customers by the server after job completion. During this investigation, the infinitesimal generator of the underlying (finite) continuous-time Markov chain takes a (level-dependent) QBD-like form. After solving for the steady state probabilities using the MOSEL-2 tool, the results show a surprising maximum of the mean response time. This maximum was already discovered by other researchers dealing with finite-source retrial queues. However, to our best knowledge, no thorough investigation was done yet why this maximum exists and in which way it depends on the system parameters. In the talk, after introducing the backgrounds of finite-source retrial queues with orbital search, a generalized stochastic Petri net is used to derive the underlying continuous-time Markov chain and its generator. Finally, using the seminar, we can hopefully bring forward discussions how to make more general statements on the parameter-dependent behavior of the response time’s maximum.

Cite as

Patrick Wüchner, János Sztrik, and Hermann de Meer. Structured Markov Chains Arising from Finite-Source Retrial Queues with Orital Search. In Numerical Methods for Structured Markov Chains. Dagstuhl Seminar Proceedings, Volume 7461, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{wuchner_et_al:DagSemProc.07461.15,
  author =	{W\"{u}chner, Patrick and Sztrik, J\'{a}nos and de Meer, Hermann},
  title =	{{Structured Markov Chains Arising from Finite-Source Retrial Queues with Orital Search}},
  booktitle =	{Numerical Methods for Structured Markov Chains},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7461},
  editor =	{Dario Bini and Beatrice Meini and Vaidyanathan Ramaswami and Marie-Ange Remiche and Peter Taylor},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07461.15},
  URN =		{urn:nbn:de:0030-drops-13895},
  doi =		{10.4230/DagSemProc.07461.15},
  annote =	{Keywords: Structured Markov chain, finite source, retrial queues, orbital search, performance measures, performance tool}
}

Filters


Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail