Kursernas Hemsidor

273023 Markovkedjor 5 sp - Markov Chains 5 cr

The course on Markov Chains treats the basics of Markov chains in discrete time: Chapman-Kolmogorov equations, transition probability matrices, classification of states, asymptotic behavior and stationary distributions as well as absorption problems and time reversibility, Markov Chain Monte Carlo methods, branching processes and other applications.

The course is lectured by PhD Daniel Aalto, e-mail address daaalto at åbo fi. The lectures are given in English. There will be theoretical and numerical exercises and assignments.

The course starts at 1 p.m. on Monday, 7 January 2013. Class hours are Mondays 13-15, Tuesdays 13-15 and Fridays 10-12. The venue is Hilbertrummet, ASA B329. Exercises are usually on Tuesdays. The course ends with a written examination on Friday 15 March at the last lecture. The final exam can be substituted by a written assignment which is presented in the class. The topic for the assignment has to be chosen during January and the oral presentation given before the exam. There will be a winter break on the course from 18 Feb to 24 Feb. The first exercise session is on Tuesday 15 Jan; the exercises can be downloaded on the page one week before the exercise session.

Literature: Sheldon M. Ross: Introduction to Probability Models 9th ed., Academic Press 2007; in particular Chapter 4. A small number of books are available at the student library in the ASA building. The lectures will follow first the book written by D. A. Levin, Y. Peres, and E. L. Wilmer: "Markov Chains and Mixing Times". The book can be downloaded here .

Additional material may also be used. All material will be available in room B310.

Prerequisites: Analysis (Calculus), probability theory and a course on linear algebra or matrix calculus. Basic programming ability using a major mathematical programming package such as Mathematica, Matlab, or Maple is necessary.

Evaluation: There are three component in the course: Exercises, Presentation, and Exam. Each component has equal value and is graded on the scale from 0 (failed) to 5 (best). The final grade for the course is the average of the two best components. The components are valid until 15 March 2013.

Exercises:There are eight exercise sessions and two short assignments to be handed in (first one is now published and should be handed in by 19 Feb). To pass this part, at least half of the exercises has to be prepared before the exercise sessions, and both short assignments have to be completed. The assignments give together as many points as all the exercises together.

Presentation:An oral presentation (15 min) and a written report on the main points of the talk (max. 2 pages) based on a research article where Markov Chains play a major role (to be done in small groups of max. 2 people). More information on the presentations at the lecture on 21 Jan. Presenatations can be held on 4 and 8 March. Choose a topic by 4 February by sending email to the lecturer to receive a confirmation. Please attach an electronic copy of (or link to) the research article that you will use for the presenatation.

Exam:Final exam (2 hours) is available for only those students who have completed succesfully at least the Exercises or the Presentation (including the written report).

After 15 March 2013: The course can be passed by a usual 4 hour exam. No extra points based on exercises and the presentation can be carried over to the future exams.

Course log:

Mon 7 Jan: Lecture 1. Introduction, Definition of a Markov chain, Transition probability matrix, Frog example.

Tue 8 Jan: No meeting.

Fri 11 Jan: Lecture 2. Random walks on graphs. Irreducibility, aperiodicity, stationary distributions. Definition of a hitting time.

Mon 14 Jan: Lecture 3. Classification of states. Time reversals and reversibility.

Tue 15 Jan: Exercise session 1.

Fri 16 Jan: Lecture 4. Existence and uniqueness of stationary distributions.

Mon 21 Jan: Lecture 5. Gambler's ruin, coupon collecting, Ehrenfest model, Projection of a chain.

Tue 22 Jan: Exercise session 2.

Fri 25 Jan: Lecture 6. Random walk on integers, reflection principle.

Mon 26 Jan: Lecture 7. Random walk on a group. Simulation of a random variable (Appendix B of the book).

Tue 29 Jan: Exercise session 3. The Home assignment 1 is available. See the book of C. M. Grinstead and J. L. Snell, Introduction to Probability, Chapter 11, pp. 417-418, for the solution of Exercise 3.3.

Fri 1 Feb: Lecture 8. Total variation norm, convergence theorem, coupling (See sections 4.1, 4.2, and 4.3 of the book).

Mon 4 Feb: Lecture 9. Mixing times (See sections 4.4 and 4.5) and eigenvalues (see sections 12.1 and 12.2).

Tue 5 Feb: Exercise session 4.

Fri 8 Feb: Lecture 10. Markov Chain Monte Carlo (see section 3.2).

Mon 11 Feb: Lecture 11. Glauber dynamics (see section 3.3).

Tue 12 Feb: Exercise session 5.

Fri 15 Feb: Lecture 12. Positive recurrence and convergence (see sections 21.1 and 21.3).

Mon 18 Feb - Fri 22 Feb: Winter break.

Mon 25 Feb: Lecture 13. Null recurrence and Hidden Markov Models (see section 21.4).

Tue 26 Feb: Exercise session 6. The Home assignment 2 is available.

Fri 1 March: Lecture 14. Viterbi algorithm and Hidden Markov Models applied to computational linguistics (see Runeberg.nb).

Mon 4 March: Students' talks I. Wessberg, Lönnfors, Salonen and Svartström.

Tue 5 March: Exercise session 7.

Fri 8 March: Students' talks II. Gama, Edman and Wanamo, Anckar.

Mon 11 March: Question hour for exam preparation.

Tue 12 March: Exercise session 8.

Fri 15 March: Final exam for course participants.

Senast uppdaterad: 2.1.2013