thinkBS 309 Markov Chains and Its Applications

  • Level: Upper
  • Status: Ready
  • Offered by: Debreceni Egyetem

Course Form

Academic Institution offering the course Debreceni Egyetem
Mode of Delivery
(in class / online / blended)
Prerequsites by Topic Linear Algebra
Language of Instruction English
Course Objectives To obtain an advanced understanding on linear algebraic and numerical methods in the theory of Markov chains, with a wide variety of applications in Mathematics, Physics, Engineering, Economics and Computer Science.
Course Contents Advancved methods in linear algebra, graph theory, Markov chains. Ergodic and absorbing Markov chains, stationary distribution, recurrence, absorption, reversibility, mixing time.
Learning Outcomes of the Course Unit 1. To model and solve problems in engineering using linear algebraic techniques.
2. To utilize numerical methods and other algorithms.
3. To study real-life problems in an abstract framework, in a systematic way.
Planned Learning Activities and Teaching Methods 2 hours lecture and 2 hours seminar per week, homework assigment regularly


Week Subjects
1 Linear algebraic background. Eigenvalues, eigenvectors. Jordan- and Frobenius normal form. Matrix multiplication, exponentiation.
2 Effective deterministic and non-deterministic numerical methods (significantly faster than Gaussian elimination) to matrix product, exponentiation, rank, inverse, normal forms, and to the solution of systems of linear equations.
3 Graphs, adjacency matrices, spectra. Cauchy interlacing theorem. Graph properties determined by the spectrum.
4 Perron-Frobenius theorem, Gershgorin circles, numerical methods.
5 Finite Markov chains as digraphs, transition matrix. Basic notions: irreducibility, regularity, absorption, ergodicity, recurrence. Some applications.
6 Irreducible and regular Markov chains. Stationary distribution and its computation, examples.
7 Frequency of recurrence, law of large numbers and central limit theorem in irreducible Markov chains.
8 Absorbing Markov chains. Basic formulas: probability of absorption in each state, expected value and higher moments of the time to absorption.
9 Reversible chains. Kolmogorov criterion. Related algorithms and numerical approximations.
10 Mixing time. Random walks on simple, undirected graphs. Expanders. Pseudo-randomness. Applications, examples.
11 Nondeterministic decision-making and other evolutionary processes. Applications in computer science.
12 Countably infinite Markov chains.