On Markov Chains with Uncertain Data

Research output: Working paperDiscussion paperOther research output

387 Downloads (Pure)

Abstract

In this paper, a general method is described to determine uncertainty intervals for performance measures of Markov chains given an uncertainty region for the parameters of the Markov chains. We investigate the effects of uncertainties in the transition probabilities on the limiting distributions, on the state probabilities after n steps, on mean sojourn times in transient states, and on absorption probabilities for absorbing states. We show that the uncertainty effects can be calculated by solving linear programming problems in the case of interval uncertainty for the transition probabilities, and by second order cone optimization in the case of ellipsoidal uncertainty. Many examples are given, especially Markovian queueing examples, to illustrate the theory.
Original languageEnglish
Place of PublicationTilburg
PublisherOperations research
Number of pages20
Volume2008-50
Publication statusPublished - 2008

Publication series

NameCentER Discussion Paper
Volume2008-50

Fingerprint

Uncertain Data
Markov chain
Uncertainty
Transition Probability
Second-order Cone
Interval
Sojourn Time
Transient State
Queueing
Limiting Distribution
Absorbing
Performance Measures
Linear programming
Absorption
Optimization

Keywords

  • Markov chain
  • Interval uncertainty
  • Ellipsoidal uncertainty
  • Linear Programming
  • Second Order Cone Optimization

Cite this

Blanc, J. P. C., & den Hertog, D. (2008). On Markov Chains with Uncertain Data. (CentER Discussion Paper; Vol. 2008-50). Tilburg: Operations research.
Blanc, J.P.C. ; den Hertog, D. / On Markov Chains with Uncertain Data. Tilburg : Operations research, 2008. (CentER Discussion Paper).
@techreport{b44dfb0a16764ce38d16f16f29714ca4,
title = "On Markov Chains with Uncertain Data",
abstract = "In this paper, a general method is described to determine uncertainty intervals for performance measures of Markov chains given an uncertainty region for the parameters of the Markov chains. We investigate the effects of uncertainties in the transition probabilities on the limiting distributions, on the state probabilities after n steps, on mean sojourn times in transient states, and on absorption probabilities for absorbing states. We show that the uncertainty effects can be calculated by solving linear programming problems in the case of interval uncertainty for the transition probabilities, and by second order cone optimization in the case of ellipsoidal uncertainty. Many examples are given, especially Markovian queueing examples, to illustrate the theory.",
keywords = "Markov chain, Interval uncertainty, Ellipsoidal uncertainty, Linear Programming, Second Order Cone Optimization",
author = "J.P.C. Blanc and {den Hertog}, D.",
note = "Pagination: 20",
year = "2008",
language = "English",
volume = "2008-50",
series = "CentER Discussion Paper",
publisher = "Operations research",
type = "WorkingPaper",
institution = "Operations research",

}

Blanc, JPC & den Hertog, D 2008 'On Markov Chains with Uncertain Data' CentER Discussion Paper, vol. 2008-50, Operations research, Tilburg.

On Markov Chains with Uncertain Data. / Blanc, J.P.C.; den Hertog, D.

Tilburg : Operations research, 2008. (CentER Discussion Paper; Vol. 2008-50).

Research output: Working paperDiscussion paperOther research output

TY - UNPB

T1 - On Markov Chains with Uncertain Data

AU - Blanc, J.P.C.

AU - den Hertog, D.

N1 - Pagination: 20

PY - 2008

Y1 - 2008

N2 - In this paper, a general method is described to determine uncertainty intervals for performance measures of Markov chains given an uncertainty region for the parameters of the Markov chains. We investigate the effects of uncertainties in the transition probabilities on the limiting distributions, on the state probabilities after n steps, on mean sojourn times in transient states, and on absorption probabilities for absorbing states. We show that the uncertainty effects can be calculated by solving linear programming problems in the case of interval uncertainty for the transition probabilities, and by second order cone optimization in the case of ellipsoidal uncertainty. Many examples are given, especially Markovian queueing examples, to illustrate the theory.

AB - In this paper, a general method is described to determine uncertainty intervals for performance measures of Markov chains given an uncertainty region for the parameters of the Markov chains. We investigate the effects of uncertainties in the transition probabilities on the limiting distributions, on the state probabilities after n steps, on mean sojourn times in transient states, and on absorption probabilities for absorbing states. We show that the uncertainty effects can be calculated by solving linear programming problems in the case of interval uncertainty for the transition probabilities, and by second order cone optimization in the case of ellipsoidal uncertainty. Many examples are given, especially Markovian queueing examples, to illustrate the theory.

KW - Markov chain

KW - Interval uncertainty

KW - Ellipsoidal uncertainty

KW - Linear Programming

KW - Second Order Cone Optimization

M3 - Discussion paper

VL - 2008-50

T3 - CentER Discussion Paper

BT - On Markov Chains with Uncertain Data

PB - Operations research

CY - Tilburg

ER -

Blanc JPC, den Hertog D. On Markov Chains with Uncertain Data. Tilburg: Operations research. 2008. (CentER Discussion Paper).