2024/2025
Markov Chains
Type:
Optional course (faculty)
Delivered by:
Faculty of Mathematics
Where:
Faculty of Mathematics
When:
1, 2 module
Open to:
students of all HSE University campuses
Instructors:
Alexandra Skripchenko
Language:
English
ECTS credits:
3
Contact hours:
30
Course Syllabus
Abstract
The simplest random process is a sequence of independent events (experiments). The scope of such processes is limited, since in practice very often the events are not independent. Markov chains are the simplest random processes formed by sequences of dependent events: given an event, it is assumed that the next event depends only on the given one, but does not depend on the previous events. In other words, «the future depends only on the present, but does not depend on the past». Markov chains have deep and beautiful but rather simple mathematics. Due to their amazing efficiency in applications to problems from various fields — mathematics, physics, computer science, biology, economics, etc. — they are known as probably the most important class of random processes. The present course is an introduction to the theory of Markov chains. We will discuss their most important properties and some of their applications PREREQUISITES: Standard courses of linear algebra and analysis of the first year of education. A standard course of the probability theory is recommended but not required: all essential knowledge from the probability theory will be communicated.
Learning Objectives
- Learning the audience what are the Markov chains with finite number of states and the corresponding basic technique.
- Learning possible types of large-time behavior of the Markov chains with finite number of states.
- Learning some applications of the Markov chains technique to various examples arising in different areas.
Expected Learning Outcomes
- After the course the students are expected to understand what is a Markov chain with finite number of states, to know its basic properties, possible types of its large-time behavior and possible topological structure.
- The students are expected to be familiar with a number of examples of Markov chains with finite number of states and to be able to recognize if a given discrete stochastic system with finite number of states is a Markov chain or not and apply the Markov chain technique to study this system if the system forms a Markov chain.
Course Contents
- Markov chains with finite number of states
- Examples
- Stationary states and their existence
- Ergodic theorem for Markov chains with ergodic transition probability matrix
- Applications of the ergodic theorem. The law of large numbers for Markov chains. The Google’s Page Rank.
- Perron–Frobenius theorem
- Topological structure of Markov Chains
- Periodic Markov chains.
- Aperiodic Markov chains. Ergodic theorem for irreducible aperiodic Markov chains
Bibliography
Recommended Core Bibliography
- Gnedenko, B. V., & Ushakov, I. A. (1997). Theory of Probability (Vol. Sixth edition). Amsterdam, the Netherlands: Routledge. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=1835590
- Meyn, S. P., & Tweedie, R. L. (2009). Markov Chains and Stochastic Stability (Vol. 2nd ed). Cambridge: Cambridge University Press. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=313161
Recommended Additional Bibliography
- Ibe, O. C. (2013). Markov Processes for Stochastic Modeling (Vol. 2nd edition). Chennai: Elsevier. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=516132