Markov chains

MATH-332

This file is part of the content downloaded from Markov chains.
Course summary

General news and announcements

The course follows reasonably closely the first three chapters of Norris. 
Some proofs are different.
The grade will be based on exercises and a midterm but mostly on the final exam.
The formula is as follows Variable B is calculated as 1/2(E+M).  (E is for exercises, M is for midterm,
both are between 0 and 1.  ) The grade is given by F + B(1 - (F/6)^(3/4)).  Here the variable
F is the note from the final exam (between 1 and 6).

The midterm will be in class on April 7.

The exercise will be the best three of four tests on exercises given at the start of the exercise sessions.
The first test will be in week 4, that is wednesday 12 march.

This week we reviewed basic elements of probability, in particular conditional probability and conditional

independence.  We also recalled useful distributions:

binomial, geometric, exponential and Poisson.

We introduced probability vectors and transition matrices.  We defined a (lambda, P ) Markov chain and established basic equivalences before the most important result:

conditional on X_m being equal to state i, the future is a (\delta_i, P) markov chain independent of the vector

(X_0,X_1, . . ._m).   We then defined communicating classes and irreducible Markov chains.

We discuss communicating classes and the notion of irreducibility and why it is important.

We then discuss various hitting probability questions, giving the recursive

equations for hitting probabilities and the abstract result that the hittinng probabilities are

the minimal solutions to these equations.

We introduce the strong Markov property.  We then introduce notion of transience and recurrence and use the Strong Markov property to give
equivalent formulations. 
In the companion recordings we gain a necessary and sufficient condition for an irreducible Birth and Death chain to be transient and
show that random walks in 1 & 2 dimensions are recurrent but in higher dimensions the random walk is transient.

THIS WEEK IS FIRST EXERCISE TEST ON WEDNESDAY

17 march-23 march

We continue studying transience and recurrence.  We sho
recurrence is a class property.  We consider trasience of random walks and birth and death processes
We define stationary distributions


Probably the most important week of the course.

24 March-30'th March

In this lecture we consider invariant (or stationary) distributions
and the link  with positive recurrence.

THIS WEEK IS THE SECOND EXERCISE TEST (AGAIN IN THE EXERCISE SESSION)

7'th April-14'th April

THIS IS THE MIDTERM

We finish chapter one and begin continuous time processes.  The exercises will be week 7 with expoenetial r.v. questions.

21'st April-27'th April

We finish off discrete time Markov chain theory and begin continuous time chains.

We first describe a continuous time chain and discuss why holding time smust be Exponential.  We start with Poisson processes

28'th April-4'th May

We examine the Poisson propcess and prove 3 equivalent conditions and
the censoring theorem

may 5-may 11

  We show that transition matrics P+t are equal to e^{Qt}
for finite state space.  We then discuss continuous Markov chains on infinite state spaces and the possibility of "explosions".  We then show
that the minimal semigroup is a solution fo the backward equations.

12'th May- 18'th May

We discuss explosions and give criteria for there to be no explosions.  We discuss trasience recurrence for Markov chains

26'th May-31'st May

We end by discussing invaraince and positive recurrence.  

Then we discuss two Markov processes "on" countable state spaces

that are not Markov chains in our sense.

We complete the proofs of the results stated in the previous lecture and then give the (simple) proof of the convergence to equilibrium result for positive recurrent irreducible Markov chains .   For the exercises ignore the last two questions which depend on renewal theory which is not in the course this year.  For the same reason for the practice exam, question 3 need not be attempted as it deals with renewal theory.

We give the solutions to the practice exam posted in the last week.  We do not treat
question 3 as it examines renewal theory which is not given in this year's course.


Disclaimer.  The choice of subjects and emphasis need not be the same as for this exam.