Uniformization: Basics, extensions and applications

N. M. van Dijk (Corresponding Author), Samuel Pieter Josephus van Brummelen, Richard Boucherie

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
1 Downloads (Pure)

Abstract

Uniformization, also referred to as randomization, is a well-known performance evaluation technique to model and analyse continuous-time Markov chains via an easier to performance measures via iteration of the one-step transition matrix of the discrete-time Markov chain. The number of iterations has a Poisson distribution with rate dominating the maximum exit rate from the states of the continuous-time Markov chain. This paper contains an expository presentation of uniformization techniques to increase awareness and to provide a formal and intuitive justification of several exact and approximate extensions, including:
•exact uniformization for reward models,
•exact uniformization for time-inhomogeneous rates,
•a numerical comparison with simple time-discretization,
•approximate uniformization for unbounded transition rates, and
•exact uniformization for continuous state variables for non-exponential networks.
Furthermore, several of these results are numerically illustrated for a processor sharing web server tandem model of practical interest.
Original languageEnglish
Pages (from-to)8-32
Number of pages25
JournalPerformance evaluation
Volume118
Early online date16 Oct 2017
DOIs
Publication statusPublished - 1 Feb 2018

Fingerprint

Uniformization
Markov processes
Poisson distribution
Continuous-time Markov Chain
Servers
Processor Sharing
Iteration
Transition Matrix
Web Server
Numerical Comparisons
Time Discretization
Randomisation
Reward
Justification
Performance Measures
Performance Evaluation
Intuitive
Markov chain
Discrete-time
Model

Keywords

  • Uniformization
  • Randomization
  • Time discretization
  • Time inhomogeneous
  • Cumulative reward model
  • Web server tandem model

Cite this

van Dijk, N. M. ; van Brummelen, Samuel Pieter Josephus ; Boucherie, Richard. / Uniformization : Basics, extensions and applications. In: Performance evaluation. 2018 ; Vol. 118. pp. 8-32.
@article{1217a4f9e69043d0a6bc8ac6a1b7616d,
title = "Uniformization: Basics, extensions and applications",
abstract = "Uniformization, also referred to as randomization, is a well-known performance evaluation technique to model and analyse continuous-time Markov chains via an easier to performance measures via iteration of the one-step transition matrix of the discrete-time Markov chain. The number of iterations has a Poisson distribution with rate dominating the maximum exit rate from the states of the continuous-time Markov chain. This paper contains an expository presentation of uniformization techniques to increase awareness and to provide a formal and intuitive justification of several exact and approximate extensions, including:•exact uniformization for reward models,•exact uniformization for time-inhomogeneous rates,•a numerical comparison with simple time-discretization,•approximate uniformization for unbounded transition rates, and•exact uniformization for continuous state variables for non-exponential networks.Furthermore, several of these results are numerically illustrated for a processor sharing web server tandem model of practical interest.",
keywords = "Uniformization, Randomization, Time discretization, Time inhomogeneous, Cumulative reward model, Web server tandem model",
author = "{van Dijk}, {N. M.} and {van Brummelen}, {Samuel Pieter Josephus} and Richard Boucherie",
year = "2018",
month = "2",
day = "1",
doi = "10.1016/j.peva.2017.09.008",
language = "English",
volume = "118",
pages = "8--32",
journal = "Performance evaluation",
issn = "0166-5316",
publisher = "Elsevier",

}

Uniformization : Basics, extensions and applications. / van Dijk, N. M. (Corresponding Author); van Brummelen, Samuel Pieter Josephus; Boucherie, Richard.

In: Performance evaluation, Vol. 118, 01.02.2018, p. 8-32.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Uniformization

T2 - Basics, extensions and applications

AU - van Dijk, N. M.

AU - van Brummelen, Samuel Pieter Josephus

AU - Boucherie, Richard

PY - 2018/2/1

Y1 - 2018/2/1

N2 - Uniformization, also referred to as randomization, is a well-known performance evaluation technique to model and analyse continuous-time Markov chains via an easier to performance measures via iteration of the one-step transition matrix of the discrete-time Markov chain. The number of iterations has a Poisson distribution with rate dominating the maximum exit rate from the states of the continuous-time Markov chain. This paper contains an expository presentation of uniformization techniques to increase awareness and to provide a formal and intuitive justification of several exact and approximate extensions, including:•exact uniformization for reward models,•exact uniformization for time-inhomogeneous rates,•a numerical comparison with simple time-discretization,•approximate uniformization for unbounded transition rates, and•exact uniformization for continuous state variables for non-exponential networks.Furthermore, several of these results are numerically illustrated for a processor sharing web server tandem model of practical interest.

AB - Uniformization, also referred to as randomization, is a well-known performance evaluation technique to model and analyse continuous-time Markov chains via an easier to performance measures via iteration of the one-step transition matrix of the discrete-time Markov chain. The number of iterations has a Poisson distribution with rate dominating the maximum exit rate from the states of the continuous-time Markov chain. This paper contains an expository presentation of uniformization techniques to increase awareness and to provide a formal and intuitive justification of several exact and approximate extensions, including:•exact uniformization for reward models,•exact uniformization for time-inhomogeneous rates,•a numerical comparison with simple time-discretization,•approximate uniformization for unbounded transition rates, and•exact uniformization for continuous state variables for non-exponential networks.Furthermore, several of these results are numerically illustrated for a processor sharing web server tandem model of practical interest.

KW - Uniformization

KW - Randomization

KW - Time discretization

KW - Time inhomogeneous

KW - Cumulative reward model

KW - Web server tandem model

U2 - 10.1016/j.peva.2017.09.008

DO - 10.1016/j.peva.2017.09.008

M3 - Article

VL - 118

SP - 8

EP - 32

JO - Performance evaluation

JF - Performance evaluation

SN - 0166-5316

ER -