Introduction to stochastic processes

Announcements:  

  • The Final Exam will be on April 20, 12:00-2:30pm in CIRS 1250.  It is covers all of the material from class.  I will have an office hour on April 18, 12:30-2:20.  It will be a chance for students to ask questions about any of the material from class.
  • Here are solutions for Midterm 2.
  • I had to cancel OH on March 26, but will replace with with OH on March 29 at 2pm (in my office).
  • The average for Midterm 2 (Section 201) was 18.67, standard deviation 6.98.  Here is a histogram of scores.
  • Midterm 2 is on March 21.  It covers every topic after branching processes and through Poisson processes.  (Lectures 14-20.)
    Note: A Poisson process is a kind of CTMC.  While it will not be required, you may use the material we learn about general CTMCs on the midterm.
  • Here are the solutions for Midterm 1 (aside from the transition matrix in Problem 1).
  • Midterm 1 is on February 14.  It covers every topic through branching processes.  (Lectures 1-13.)  You can see past exams here.

 

Instructor: Yaniv Plan
Office: 1219 Math Annex
Email:  yaniv (at) math (dot) ubc (dot) ca

Lectures: MWF 9:00 am – 10:00 am,  SWNG 121

Office hours: M 11:30 am – 12:30 pm, F 2:00 pm – 3:00 pm, MATX 1219

Outline: Here.

Piazza:  Sign up link here.

Textbook:  S. M. Ross, “Introduction to Probability Models”, 11th edition, Academic Press. Earlier editions are indistinguishable for our purposes apart from possible changes to page and problem numbers. An optional more advanced reference: G.R. Grimmett and D.R. Stirzaker,“Probability and Random Processes”, 3rd edition, Oxford, (2001).

There are interesting resources at: http://www.math.uah.edu/stat/

Discussion board: We will use a Piazza discussion board this term. You can ask questions regarding the course there, and answer other students’ questions. Do not share solutions to assignments on Piazza before the due date.

Grading:  The final mark will be based on homework (10%), two midterm exams (20% each),
and final exam (50%). Term marks may be scaled for consistency in both sections of MATH 303.

Tests: There will be two 50-minute midterms during class.  Midterm I on Wednesday, February 14, and Midterm II on Wednesday, March 21.

Final Examination: will take place on April 20, 12:00 – 2:30pm.

Missed mid-terms and assignments will normally receive a zero grade. Exceptions may be
granted by prior consent from the instructor, or for a documented medical emergency. In
the latter case, the instructor must be notified within two working days of the missed test, and
presented with a doctor’s note immediately upon the student’s return to UBC. When an exception
is granted for a missed test, there is no make-up test, and the final exam mark will be used.

Lectures* (written on computer, handwriting may suffer).

Lecture 1: Basic definitions.  Warm-up 2-state Markov chain limiting behaviour.
Lecture 2: Chapman Kolmogorov equations.  Probability distribution after n-steps of a Markov Chain.
Lecture 3: Gambler’s ruin. (For some extra material on linear recurrence relations, see some brief notes here and the videos here.)
Lecture 4:  Classification of states.  Partition into communicating classes.  Periodicity, recurrence.
Lecture 5:  Properties of transience/recurrence.
Lecture 6:  Recurrence/transience of random walk on Z^d.
Lecture 7:  Limiting probabilities.
Lecture 8:  Time reversibility.
Lecture 9:  Time reversibility examples.
Lecture 10:  Time reversibility more examples (including on a graph).
Lecture 11:  Intro branching processes and generating function.
Lecture 12: More on branching processes, extinction probability.
Lecture 13:  Still more on branching processes, extinction probability.
Everything above here is on the first midterm.
Lecture 14:  Markov chain Monte Carlo (MCMC).  Just a taste.
Chapter 5 of the textbook starts below:
Lecture 15:  Exponential random variables (review).
Lecture 16:  Intuitive introduction to Poisson processes.
Lecture 17:  Poisson processes.
Lecture 18:  Poisson processes continued.
Lecture 19:  Poisson processes continued.
Lecture 20: Poisson processes application.
Chapter 6 of the textbook starts below:
Lecture 21:  Continuous time Markov chains,
Lecture 22.  Expected value of birth/death processes
Lecture 23:  P_i,j(t).  Chapman Kolmogorov equations, backward Kolmogorov equation.
Lecture 24: Solving backward Kolmogorov equation to find P_i,j(t) for birth death processes.
Lecture 25:  Limiting probabilities for CTMCs.
Lecture 26:  Calculating limiting probabilities for birth/death processes.  M/M/1 queue.
Some practice problems for the midterm.  This focuses on Poisson processes and memorylessness of exponential rv’s.  Other topics to study are MCMC and Poisson processes which split into different types at rates that depend on time (as in Lectures 19 and 20).
Lecture 27:  Relation  between stationary dist of MC and limiting probabilities of continuous time MC.
Lecture 28:  Reversible CTMC
Lecture 29:  Reversible CTMC continued
Lecture 30:  Calculating limiting probabilities for reversible CTMCs (examples)
We covered most of Chapter Sections 6.1-6.6

 

*Based on a set of lecture notes by Gordon Slade.

Reading ahead:  Here is a rough outline of material covered week by week, including book sections and other helpful learning materials.  This was compiled by Richard Balka, and is from a previous iteration of this class.  It will approximately, but not exactly, match our syllabus.

Homework: 9 weekly assignments will be given. These are due at the beginning of class on
the due date, almost each Wednesday. No later assignments will be accepted. The single lowest
assignment will be ignored.

Due January 17: Homework 1.   Solutions.
Due January 24: Homework 2.   Solutions.
Due January 31: Homework 3.    Solutions.
Due February 7: Homework 4.  Solutions.  Deadline extended to February 9!
Due February 28: Homework 5.  Solutions.  Deadline extended to March 2!
Due March 7: Homework 6.  Solutions.  Due on Wednesday!
Due March 14: Homework 7.  Solutions.
Due March 28: Homework 8. Solutions.
Due April 4: Homework 9.  Solutions.  Deadline extended to April 6!