Brian Van Koten
Assistant Professor
Email: vankoten(at)math.umass.edu
Office: LGRT 1428
Website: See my personal website
here.
If you have questions or concerns, talk to me during my office hours or make an appointment. My office hours are listed on my math department directory page.
I may change my office hours during the course of the semester. Any such changes will be announced in advance in class.
Lectures will be held MW from 2:30-3:45pm in LGRT 1334.
Week 1: Definition of homogeneous Markov chain, Brémaud Section 2.1.1 or Norris Section 1.1. Matrix formulas for the distribution of a homogeneous Markov chain, Section 2.1.2 in Brémaud or Theorems 1.1.1 and 1.1.3 in Norris. Sequential Bayes Rule, Section 1.2.2 in Brémaud.
Week 2: Conditional independence of events and random variables, Section 1.2.3 in Brémaud. Restatement of Markov property in terms of conditional independence, Theorem 1.1.2 in Norris. Hitting times and hitting probabilities, Section 1.3 in Norris. Deriving a linear system for hitting probabilities via first-step analysis, Theorem 1.3.2 in Norris and Section 2.3 in Brémaud. Stopping times and the strong Markov property, Section 1.4 in Norris.
Week 3: Recurrence and transience, Section 1.5 in Norris. Communicating classes, Section 1.2 in Norris or Section 2.4.1 in Brémaud.
Week 4: Recurrence and transience of random walks, Section 1.6 in Norris. Invariant distributions, Section 1.7 in Norris.
Week 5: Invariant distributions, Section 1.7 in Norris. Convergence to equilibrium, Section 1.8 in Norris. Ergodic theorem, Section 1.10 in Norris.
Week 6: Ergodic theorem, Section 1.10 in Norris. Generating functions, Section 1.5.1 in Brémaud. Characterization of continuous time Markov chains in terms of jump chain and holding times, Chapter 2 in Norris. Strong Markov property for continuous time chains, Theorem 2.8.1 in Norris, statement but not proof. Infinitesimal and master equation characterization of continuous time chains, Theorem 2.8.2 in Norris.
Week 7: Explosion, Theorem 2.3.2 and 2.5.2 in Norris on explosion of birth processes, Theorem 2.7.1 on general criteria prohibiting explosion. Poisson distribution and law of rare events, Section 1.3.3. in Brémaud.
Week 8: A more flexible version of the law of rare events, Theorem 3.6.1 in Durrett, statement but not proof. Poisson process, Theorem 2.4.3 in Norris, alternative proof based on law of rare events. Superposition of Poisson processes, Theorem 2.4.4 in Norris. Uniform distribution of jump times for a Poisson process, Theorem 2.4.6 in Norris.
Week 9: Technicalities related to the master equation for a continuous time Markov chain when the state space is infinite, digest of Theorems 2.8.3, 2.8.4, 2.8.6 in Norris, statements but not proofs. Explanation of why master equation may have multiple solutions when the state space is infinite. Class structure of continuous time chains, Theorem 3.2.1 in Norris.
Week 10: Recurrence and transience of continuous time chains, Theorem 3.4.2 in Norris. The skeleton chain and its relation to recurrence, Theorem 3.4.3 in Norris. Invariant distributions of continuous time chains, Theorems 3.5.1 and 3.5.2 in Norris. Positive recurrence and the existence of invariant distributions, Theorem 3.5.3 in Norris. Convergence to equilibrium for continuous time chains, Theorem 3.6.2 in Norris, sketch of proof using the skeleton chain. Ergodicity of continuous time chains, Theorem 3.8.1 in Norris, statement but not proof.
Homework will be assigned after every class. All assigments will be posted below. Problems assigned during each week will be due the following week on Thursday.
No late homework will be accepted. Instead, when the total course grade is computed, the lowest homework score will be dropped.
I encourage you to discuss the homework with your classmates and to come to my office hours with your questions.
Assignments due 1/30: HW1
Assignments due 2/8: HW2.1 and HW2.2
Assignments due 2/13: HW3
Assignments due 2/20: HW4
Assignment due 2/27: HW5
Assignment due 3/6: HW6
Assignment due 3/27: HW7
Assignment due 4/10: HW8
Assignment due 4/17: HW9
Assignment due 5/1: HW10
Here is the midterm. The exam is due March 29 by 3:00pm in my mailbox or email.
Please do not discuss the problems on the midterm with anyone. You may consult any of the recommended texts, but please do not search the web for solutions.
The final exam will be designed to resemble the Ph.D. program's qualifying exam in probability.
If for any reason you will not be able to take either exam at the specified time, let me know as soon as possible.
If you suspect that a mistake has been made in the grading of your work, please point it out to me no more than two weeks after the work was returned. I will not consider complaints if more than two weeks have passed. Please do not ask the grader to change homework grades; come to me with any disputes.
Pierre Brémaud, Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues. (ISBN 978-0-387-98509-1)
Other Useful TextsJ. R. Norris, Markov Chains. The first chapter is available for free here.
Brémaud's book is excellent, but perhaps a bit unconventional and digressive. This book gives a more concise and straightforward account of the basic theorems. The first weeks of the course will probably follow this text more closely than Brémaud.
Rick Durrett, Probability: Theory and Examples. Available for free here.
This excellent book covers Markov processes on a continuous state space, Brownian motion and the Brownian bridge, and many other essential aspects of stochastic processes beyond the scope of Stat 697U.
David A. Levin, Yuval Peres, and Elizabeth L. Wilmer, Markov Chains and Mixing Times. Available for free here.
This specialized text focuses on estimates of the rate of convergence of Markov chains to equilibrium. I may present a digest of this book as part of our discussion of discrete time Markov chains.
David Aldous and James Allen Fill, Reversible Markov Chains and Random Walks on Graphs. Available for free here.
A wonderful compendium of interesting examples, applications, and theorems. If you decide you like stochastic processes, it's worth browsing through this book.
Discrete time Markov chains.
Poisson process, continuous time Markov chains, queues.
Monte Carlo methods, including Markov chain Monte Carlo.
Concentration inequalities, large deviations, Gartner--Ellis theorem, connections with Monte Carlo methods.
Applications to population genetics, image reconstruction, or other fields selected based on the interests of the students and expertise of the instructor.
Introductory courses in probability and analysis. No knowledge of measure theory will be assumed.
The total course score will be computed according to the following formula: 34% Homework + 33% Midterm + 33% Final.
If your score is in the top third, you will receive an A. If your score is in the middle third, you will receive at least a B, but possibly a higher grade. If I am convinced that all students understand the basic principles of the course, I will not give any C's, D's, or F's. I will make the distribution of scores on the midterm and the final exam known.