University of Twente Student Theses


Monotonicity in Markov chains

Spel, Jip (2018) Monotonicity in Markov chains.

[img] PDF
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:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page