Thomas Stieltjes Institute for Mathematics

1. Renewal theory and regenarative processes: the renewal function; the renewal theorem; asymptotics; ergodicity; the compound Poisson process.
2. Markov chains: discrete and continuous time processes; state classification; the equilibrium distribution; flow-in-flow-out technique; uniformization method.

1. Introduction with examples;
2. For discounted, undiscounted and sensitive optimality criteria: the optimality equation; the policy improvement method, the linear programmering method and the method of successive approximations.
3. Applications: casino models; optimal stopping; replacement models; multi-armed bandit problems.

• Part a: H.C. Tijms, "Stochastic models - an algorithmic approach", John Wiley and Sons, New York, 1994 (ISBN 0-471-95123-4). The prize of this book is approximately Dfl. 75,-. The LNMB will give a discount of Dfl. 25,- for Ph.D. students who attend this course. If you will use this offer, please send an e-mail message to the secretary before September
• Part b: Lecture notes will be provided (free of charge).

• Part a: Queueing models; birth-and-death processes; Little's formula; M/G//1-queue; PASTA.
  
• Part b: generating functions; Laplace-Stieltjes transform; detailed analysis M/G/1-queue; polling systems; product form networks; a machine repair model; the Erlang loss model; optimization in networks of queues; applications.

• Complexity theory: 'easy' (polynomial time solvable) problems and 'hard' (NP-hard) combinatorial problems; consequences of this classification for the solution strategy of combinatorial problems.
• Optimization algorithms: optimization algorithms for NP-hard problems apply some kind of implicit enumaration (dynamic programming; branch-and-bound); special attention is paid on the computation of bounds (state relaxation; Lagrange relaxation; LP relaxation with cuts).
• Approximation algorithms: approximation algorithms for NP-hard problems provide often quickly a good, but not necessary optimal, solution. Methods are discussed which provide a performance guarantee for the quality of the approximate solution. Also local search methods are considered.
• Probabilistic analysis of algorithms: introduction; the partition problem; the multi-knapsack problem and the traveling salesman problem.

In the course we will show convergence to the Euler limit under some simplifying conditions.

The Euler limits will then be used for understanding (exponential) stability and transience of the walk by the construction of suitable Lyapunov functions based on the Euler limits. In the case of transience, from the Euler limit it also follows ``how'' the walk becomes unstable.

To explicitly calculate the Euler limit, is in general a complicated problem. We will study simple conditions under which the Euler limits for particular models in the field of queueing and neural networks can be calculated and we will study properties of the associated dynamical systems. For the studied queueing models we will connect the construction of the Euler limit to the so-called oblique reflection mapping.

The amount of workload is approximately 80 hours in case of active participation.