University of Twente Student Theses
Monotonicity in Markov chains
Spel, Jip (2018) Monotonicity in Markov chains.
|
PDF
1MB |
| Abstract: | Markov chains (MCs) are an excellent formalism to capture systems that are governed by randomized behaviour. They are used in computer science, engineering, mathematics, and biology. MCs require fixed distributions, but often these probabilities are not precisely known. Parametric MCs (pMCs) allow for changing specific sets of distributions in the MC. One way to find the values for parameters is parameter synthesis. Based on the pMC and the specification, the parameter values for which the system meets these requirements are needed to be calculated. We investigate the effect of changing the parameter values. In particular, we observe that parameters often have a monotone effect on the probability that a given system state is reached. We want to exploit this monotone effect to improve the analysis on the behaviour of systems. To that end, we provide a formal framework to verify efficiently whether these systems are monotone. The framework consists of two layers: the foundation, and the top layer. In the foundation we define a set of monotone pMCs through the composition of predefined building blocks. In the top layer, we show that structures in high level descriptions of systems naturally map to the building blocks of the foundation. |
| Item Type: | Essay (Master) |
| Faculty: | EEMCS: Electrical Engineering, Mathematics and Computer Science |
| Subject: | 54 computer science |
| Programme: | Computer Science MSc (60300) |
| Link to this item: | https://purl.utwente.nl/essays/74981 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page