Markov Chains

COURSE OBJECTIVE 

• The student is able to check whether a given stochastic process is a Discrete/Continuous-time Markov chain.
• The student is able to compute the transient probabilities of a Markov chain in discrete time in terms of the eigenvalues of the transition matrix.
• The student is able to determine open and closed classes of a Markov chain.
• The student is able to classify the states of a Markov chain into transient and recurrent.
• The student is able to characterize the hitting probabilities and expected hitting times for a given transition matrix; and be able to compute these for chains with a small number of states and/or a transition matrix with a special structure (in particular birth-death processes).
• The student is able to characterize the distribution of hitting times for a given transition matrix in terms of its generating function; and be able to compute these for chains with a small number of states and/or a transition matrix with a special structure (in particular birth-death processes).
• The student is able to characterize (i.e. verify) stationary distributions for a Markov chain with given transition matrix; and be able to compute these for chains with a small number of states and/or a transition matrix with a special structure (in particular birth-death processes).
• The student is able to prove convergence to a stationary distribution for an irreducible, positive recurrent Markov chain.
• The student is able to verify reversibility of a Markov chain using detailed balance conditions and use these to compute stationary distributions for these chains.
• The student is able to formulate the connection between a continuous-time Markov chain on a discrete state space with its embedded jump-chain, and use this to conclude on all the aforementioned items for continuous time Markov processes.
• The student is able to prove the equivalence of three definitions of a Poisson process.
• The student is able to prove the splitting and merging properties of (independent) Poisson processes.
• The student is able to determine the stationary queue-length and waiting-time distributions in several basic queueing models using embedded Markov chains.

COURSE CONTENT

The first part of the course is an introduction to discrete-time Markov chains in which we treat class structure, hitting times, absorption probabilities, strong Markov property, random walks, invariant distributions, convergence to equilibrium, and reversibility.

The second part of the course deals with continuous-time Markov chains, the Poisson process, and embedded discrete-time Markov chains, among other things. Also, we consider applications of Markov chains, such as branching processes and queueing theory.

TEACHING METHODS 

Weekly lectures and tutorials

TYPE OF ASSESSMENT 

A written midterm exam and a written final exam, each counting for 50% of the grade. There is a one single resit exam that covers the entire course material.