Joost Berkhout

Berkhout, Joost

Logistics & Operations Research

Dissertation title
Topics in Markov Chain Theory and Simulation Optimisation

and location
December 21, 2016 at 11:45 in the Aula of the Main Building of the Vrije Universiteit Amsterdam

Topics in Markov Chain Theory and Simulation Optimisation

Berkhout, JoostThis thesis addresses different topics from Markov chain theory and simulation optimisation. Each chapter is dedicated to a specific topic summarized in the following.
In Chapter 2 an easily computable new way of achieving a sufficient probability of correct selection for the nested partition hybrid algorithm from [169] for simulation optimisation is presented. The basic philosophy is that it is better to directly search for the most promising subregion of the partitioning than searching for the best design in a sample of designs (and thereby indirectly identifying the most promising subregion). In this chapter, we fill this gap by providing a mathematical proof that an approximate scheme for identifying the most promising region has higher probability of selecting the truly most promising region than the approximate scheme used in the nested partition algorithm. Numerical examples illustrate that on average a decrease of approximately 18% in computation time can be expected from the new approach.
Chapter 3 studies generalized Jackson networks which may have nodes with infinite supply of work, simultaneous breakdown of groups of nodes and group repair strategies. It is shown that the distribution of the failure regime and the steady state distribution of the queue length at stable nodes decouple in a product-form way, and closed form solutions are provided for the classical performance measures. Since productform queuing networks (PQN) maximize the entropy of the stationary queue length distribution, PQN are particularly useful in the planning and design phase, where - due to entropy maximization - PQN allow for a conservative planning. As in the planning and design phase the exact network specifications are not known, one arrives naturally at the question on how to incorporate this parameter insecurity into the model. This chapter presents an approach that allows to do this. The basic conceptual contribution is that we show how, building on the concise solutions obtained for key performance measures of PQN, the value at risk inflicted by parameter insecurity can be explicitly calculated. We believe that the combination of input distributions and PQN can prove fruitful for future research on integrating statistical models and queuing theory. In addition, the nested derivative approach used in the computation of the value at risk has potential of a much wider range of applications.
The study of the effect of perturbing a Markov transition matrix on its stationary distribution dates back to Schweitzer’s pioneering paper [166] in 1968 and since then has attracted much attention in the literature. Our analysis in Chapter 4 shows that the known perturbation bounds are rather limited in their range of applicability. Specifically, we show that the relative error of the known perturbation bounds fail to tend to zero as the size of the perturbation tends to zero. In this chapter we provide a new bound that overcomes this drawback. We illustrate our findings by means of a realistic application to a problem in queuing. Best to our knowledge this is the first research on perturbation bounds that provides numerical comparisons of various bounds for non-trivial cases. Based on these findings the chapter questions the usefulness of the theory of perturbation analysis of Markov chains. Furthermore, a new area of applications of these techniques is proposed. We believe that this analysis of mixtures of stable chains with unstable chains opens a door to a very interesting line of research.
Chapter 5 addresses the computation of the ergodic projector which contains information about the long-term behaviour of finite Markov multi-chains. The ergodic projector is, e.g., one of the key measures behind the acclaimed Google search engine. A new computation approach is presented that allows efficient direct approximation of the ergodic projector of multi-chains elaborated in the jump start power method, as the approximation allows a ‘jump’ towards the ergodic projector. The approximation is theoretically analysed and numerical experiments are presented to illustrate its applicability even in the case of the notorious nearly decomposable Markov chains.
The results from Chapter 5 are further elaborated into an approximation scheme for the deviation matrix in Chapter 6. The deviation matrix of Markov chains is the root of virtually all Markov chains concepts, such as, e.g., mean and variances of the first passage times and the Kemeny constant. Again the approximation is theoretically analysed and numerically supported by experiments. The results are exploited in an algorithm for decomposition of Markov chains which is also applicable to data clustering.
In Chapter 7 a new ranking methodology is developed for general networks. The proposed ranking approach allows for a more careful ranking of transient states compared to Google PageRank. Results from Chapters 5 and 6 are exploited to ensure efficient computation of the new ranking. A numerical experiment with real data illustrates that the proposed ranking can lead to a more intuitive ranking compared to Google PageRank.

Short Biography
Joost Berkhout (1990) obtained his BSc and MSc (Cum Laude) degrees in the field of Econometrics and Operations Research at the Vrije Universiteit Amsterdam (in 2011  and 2012, resp.). In 2012 he joined the Amsterdam Business Research Institute (ABRI) Junior Research Programme which allowed him to enter the three-year ABRI PhD program in 2013. During his PhD Joost was awarded with the Student Best Paper Award at the International Workshop on Discrete Event Systems (WODES) 2016 in Xi’an (China). In September 2016 Joost started as a post-doctoral researcher at the Centrum Wiskunde & Informatica (CWI).