The Mean Value of the Maximum

Henrik Bohnenkamp; Boudewijn Haverkort

doi:10.1007/3-540-45605-8_4

The Mean Value of the Maximum

Henrik Bohnenkamp, Boudewijn Haverkort

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

5 Citations (Scopus)

Abstract

This paper treats a practical problem that arises in the area of stochastic process algebras. The problem is the efficient computation of the mean value of the maximum of phase-type distributed random variables. The maximum of phase-type distributed random variables is again phase-type distributed, however, its representation grows exponentially in the number of considered random variables. Although an efficient representation in terms of Kronecker sums is straightforward, the computation of the mean value requires still exponential time, if carried out by traditional means. In this paper, we describe an approximation method to compute the mean value in only polynomial time in the number of considered random variables and the size of the respective representations. We discuss complexity, numerical stability and convergence of the approach.

Original language	English
Title of host publication	Process Algebra and Probabilistic Methods: Performance Modeling and Verification
Subtitle of host publication	Second Joint International Workshop PAPM-PROBMIV 2002, Copenhagen, Denmark, July 25-26, 2002 Proceedings
Editors	Holger Hermanns, Roberto Segala
Place of Publication	Berlin, Heidelberg
Publisher	Springer
Pages	37-56
ISBN (Electronic)	978-3-540-45605-6
ISBN (Print)	978-3-540-43913-4
DOIs	https://doi.org/10.1007/3-540-45605-8_4
Publication status	Published - 2002
Event	2nd International Workshop on Process Algebra and Probabilistic Methods & Probabilistic Methods in Verification, PAPM-PROBMIV 2002 - Copenhagen, Denmark Duration: 25 Jul 2002 → 26 Jul 2002 Conference number: 2

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	2399
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Workshop

Workshop	2nd International Workshop on Process Algebra and Probabilistic Methods & Probabilistic Methods in Verification, PAPM-PROBMIV 2002
Abbreviated title	PAPM-PROBMIV
Country/Territory	Denmark
City	Copenhagen
Period	25/07/02 → 26/07/02

Keywords

n/a OA procedure

Access to Document

10.1007/3-540-45605-8_4

Cite this

Bohnenkamp, H., & Haverkort, B. (2002). The Mean Value of the Maximum. In H. Hermanns, & R. Segala (Eds.), Process Algebra and Probabilistic Methods: Performance Modeling and Verification: Second Joint International Workshop PAPM-PROBMIV 2002, Copenhagen, Denmark, July 25-26, 2002 Proceedings (pp. 37-56). (Lecture Notes in Computer Science; Vol. 2399). Springer. https://doi.org/10.1007/3-540-45605-8_4

Bohnenkamp, Henrik ; Haverkort, Boudewijn. / The Mean Value of the Maximum. Process Algebra and Probabilistic Methods: Performance Modeling and Verification: Second Joint International Workshop PAPM-PROBMIV 2002, Copenhagen, Denmark, July 25-26, 2002 Proceedings. editor / Holger Hermanns ; Roberto Segala. Berlin, Heidelberg : Springer, 2002. pp. 37-56 (Lecture Notes in Computer Science).

@inproceedings{4df50e31568c41c5b7401685c99cde07,

title = "The Mean Value of the Maximum",

abstract = "This paper treats a practical problem that arises in the area of stochastic process algebras. The problem is the efficient computation of the mean value of the maximum of phase-type distributed random variables. The maximum of phase-type distributed random variables is again phase-type distributed, however, its representation grows exponentially in the number of considered random variables. Although an efficient representation in terms of Kronecker sums is straightforward, the computation of the mean value requires still exponential time, if carried out by traditional means. In this paper, we describe an approximation method to compute the mean value in only polynomial time in the number of considered random variables and the size of the respective representations. We discuss complexity, numerical stability and convergence of the approach.",

keywords = "n/a OA procedure",

author = "Henrik Bohnenkamp and Boudewijn Haverkort",

year = "2002",

doi = "10.1007/3-540-45605-8_4",

language = "English",

isbn = "978-3-540-43913-4",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "37--56",

editor = "Holger Hermanns and Roberto Segala",

booktitle = "Process Algebra and Probabilistic Methods: Performance Modeling and Verification",

address = "Germany",

note = "2nd International Workshop on Process Algebra and Probabilistic Methods & Probabilistic Methods in Verification, PAPM-PROBMIV 2002 , PAPM-PROBMIV ; Conference date: 25-07-2002 Through 26-07-2002",

}

Bohnenkamp, H & Haverkort, B 2002, The Mean Value of the Maximum. in H Hermanns & R Segala (eds), Process Algebra and Probabilistic Methods: Performance Modeling and Verification: Second Joint International Workshop PAPM-PROBMIV 2002, Copenhagen, Denmark, July 25-26, 2002 Proceedings. Lecture Notes in Computer Science, vol. 2399, Springer, Berlin, Heidelberg, pp. 37-56, 2nd International Workshop on Process Algebra and Probabilistic Methods & Probabilistic Methods in Verification, PAPM-PROBMIV 2002 , Copenhagen, Denmark, 25/07/02. https://doi.org/10.1007/3-540-45605-8_4

The Mean Value of the Maximum. / Bohnenkamp, Henrik; Haverkort, Boudewijn.
Process Algebra and Probabilistic Methods: Performance Modeling and Verification: Second Joint International Workshop PAPM-PROBMIV 2002, Copenhagen, Denmark, July 25-26, 2002 Proceedings. ed. / Holger Hermanns; Roberto Segala. Berlin, Heidelberg: Springer, 2002. p. 37-56 (Lecture Notes in Computer Science; Vol. 2399).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - The Mean Value of the Maximum

AU - Bohnenkamp, Henrik

AU - Haverkort, Boudewijn

N1 - Conference code: 2

PY - 2002

Y1 - 2002

N2 - This paper treats a practical problem that arises in the area of stochastic process algebras. The problem is the efficient computation of the mean value of the maximum of phase-type distributed random variables. The maximum of phase-type distributed random variables is again phase-type distributed, however, its representation grows exponentially in the number of considered random variables. Although an efficient representation in terms of Kronecker sums is straightforward, the computation of the mean value requires still exponential time, if carried out by traditional means. In this paper, we describe an approximation method to compute the mean value in only polynomial time in the number of considered random variables and the size of the respective representations. We discuss complexity, numerical stability and convergence of the approach.

AB - This paper treats a practical problem that arises in the area of stochastic process algebras. The problem is the efficient computation of the mean value of the maximum of phase-type distributed random variables. The maximum of phase-type distributed random variables is again phase-type distributed, however, its representation grows exponentially in the number of considered random variables. Although an efficient representation in terms of Kronecker sums is straightforward, the computation of the mean value requires still exponential time, if carried out by traditional means. In this paper, we describe an approximation method to compute the mean value in only polynomial time in the number of considered random variables and the size of the respective representations. We discuss complexity, numerical stability and convergence of the approach.

KW - n/a OA procedure

U2 - 10.1007/3-540-45605-8_4

DO - 10.1007/3-540-45605-8_4

M3 - Conference contribution

SN - 978-3-540-43913-4

T3 - Lecture Notes in Computer Science

SP - 37

EP - 56

BT - Process Algebra and Probabilistic Methods: Performance Modeling and Verification

A2 - Hermanns, Holger

A2 - Segala, Roberto

PB - Springer

CY - Berlin, Heidelberg

T2 - 2nd International Workshop on Process Algebra and Probabilistic Methods & Probabilistic Methods in Verification, PAPM-PROBMIV 2002

Y2 - 25 July 2002 through 26 July 2002

ER -

Bohnenkamp H, Haverkort B. The Mean Value of the Maximum. In Hermanns H, Segala R, editors, Process Algebra and Probabilistic Methods: Performance Modeling and Verification: Second Joint International Workshop PAPM-PROBMIV 2002, Copenhagen, Denmark, July 25-26, 2002 Proceedings. Berlin, Heidelberg: Springer. 2002. p. 37-56. (Lecture Notes in Computer Science). doi: 10.1007/3-540-45605-8_4

The Mean Value of the Maximum

Abstract

Publication series

Workshop

Keywords

Access to Document

Fingerprint

Cite this