MA/STAT 532: Elements of Stochastic Processes
Spring 2019, Purdue University
http://www.math.purdue.edu/~yip/532
Course Description:

(i) Markov chains,
(ii) Poisson processes,
(iii) Renewal processes,
(iv) Continuous time Markov chains,
(v) Random Walks,
(vi) Applications:
queueing theory,
biology,
physical modeling, simulations
Instructor:
 Aaron Nung Kwan
Yip
 Department of
Mathematics
 Purdue University
Contact Information:
 Office: MATH 432
 Email:
click here
Lecture Time and Place:
 T, Th 10:30am  11:45am, UNIV 217
Office Hours:

Tue: 2:003:00pm, Wed: 5:006:00pm, or by appointment
Textbook:

(All of the following are either available online or on reserve in
the math library.)
Main Text:
[D] Essentials of Stochastic Processes (Third Edition),
by Richard Durrett
(Available online through Purdue Library subscription.)
References:
[HPS] Introduction to Stochastic Processes,
by Hoel, Port and Stone
[F1, F2] An Introduction to Probability Theory and Its Applications,
Volume 1 and 2,
by William Feller
(Free electronic files of the above can be easily found online.)
Course Outline:
 The course will cover most of [D] Chapters 14
which also correspond roughly to [HPS] Chapters 13
and [F1] Chapters XIII  XVII.
(Additional topics might be covered based on time and interests.)
Prerequisites:

Good "working" knowledge of:
probability (e.g. MA 416, 519),
linear algebra (e.g. MA 265, 351, 511),
and mathematical analysis (e.g. MA 341, 440, 504).
Homework:

Homeworks will be assigned roughly biweekly.
They will be gradually assigned as the course progresses.
Please refer to the course announcement below.
 Steps must be shown to explain your answers.
No credit will be given for just writing down the answers, even
if it is correct.
 Please staple all loose sheets of your homework to prevent
5% penalty.
 Please resolve any error in the grading (hws and tests)
WINTHIN ONE WEEK after the return of each homework and exam.
 No late homeworks are accepted (in principle).
 You are encouraged to discuss the homework problems with
your classmates but all your handedin homeworks must be your
own work.
Examinations:
 Midterm Test: Date to be determined
 Final Exam: During Final Exam Week
Grading Policy:
 Homeworks (50%)
 Midterm Test (20%)
 Final Exam (30%)
You are expected to observe academic honesty
to the highest standard. Any form of cheating will automatically
lead to an F grade, plus any other disciplinary action,
deemed appropriate.
Accommodations for Students with Disabilities and
Academic Adjustment:
 University policy and procedures will be followed.
For more detail information, please click
ADA Information
Course Progress and Announcement:
 (You should consult this section regularly,
for homework assignments, additional materials and announcements.)
WEEK 1: Jan 8, 10
[D, 1.11.2][HPS, 1.11.3]
introduction, examples
Five
great applications of Markov Chains
Use of
Markov Chain by Markov himself to analyze syllabus in a language (Russian)  "first application" of Markov Chain
Use of
linear algebra and Markov Chain in search engines
(HITS and PageRank)
NOTE: Introduction to
Markov Chain
WEEK 2: Jan 15, 17
[D, 1.21.3][HPS, 1.11.6]
transition probabilities,
classification of states
NOTE:
Transition probabilities
Homework 1, due Thursday, Jan. 24, in class.
WEEK 3: Jan 22, 24
[D, 1.21.3][HPS, 1.11.6]
first return time, kth return time,
recurrent vs transient states,
communication between states,
close and irreducible sets
[D Theorem 1.8, p. 18][HPS Theorem 4, p. 24]
NOTE:
Classification of States
[HPS 1.6.1][D 1.9, 1.10]
Absorption probability, exit distribution and exit times;
Gambler's ruin problem, probability of winning and losing.
WEEK 4: Jan 29, 31
[HPS 1.6.1][D 1.9, 1.10]
(Onestep) transition probability matrix Q (from transient states
to transient states),
existence of (IQ)^(1) (when the number of transient states is
finite);
Gambler's ruin problem, expected duration of the game.
Markov chain with infinite state space.
[HPS 1.7] Birthanddeath chain,
criterior of transient and recurrence.
Recurrence and transience of
birth and death chain (from HPS)
recurrence of 1D simple random walk.
Recurrence
of simple random walk in 1D and 2D but transience in 3D
(from Durrett, Probability, Theory and Examples)
Homework 2,
due Tuesday, Feb. 12, in class.
WEEK 5: Feb 5, 7
[HPS Chapter 2][D 1.6]
Stationary distribution, interpretation, long time behavior of MC,
Examples: twostateMC, webpage surfing and ranking
How Does Google Google
(David Gleich)
PageRank Beyong
the Web (David Gleich)
Birthanddeath chain,
criterior of existence of stationary distribution
Stationary distribution
of birth and death chain (from HPS)
Interpretation of stationary distribution using
number of returns and return times to a state.
WEEK 6: Feb 12, 14
[HPS Chapter 2][D 1.6, 1.8, 1.11]
Existence and Uniqueness of and Convergence
to stationary distribution.
NOTE:
Proof in the finitely many state, ergodic and regular case
GrinsteadSnell,
Introduction to Probability, Chapter 11 Markov Chain
PerronFrobenious Theory
of Nonnegative Matrices (Meyer, Matrix Analysis, Chapter 8)
WEEK 7: Feb 19, 21
[HPS Chapter 2][D 1.6, 1.8, 1.11] (countably infinite case)
transient, null recurrent and positively recurrent states
for irreducible Markov chain,
a unique stationary distribution exists if and only
if the chain is positively recurrent
NOTE:
Existence and Uniqueness of stationary distribution
[D Sec 1,6, 1.8, Theorem 1.19]
period of a state,
convergence to stationary distribution (irreducible and aperiodic)
[D Theorem 1.22]
ergodic theorem: time average equals ensemble average.
Homework 3,
due Thursday, Feb. 28, in class.
WEEK 8: Feb 26, 28
[HPS, 1.8, 1.9] Branching processes
[F1, XII] Compound processes
survival of family names
(Extinction of Families, WatsonGalton)
NOTE: Branching Processes
[F1, XII]
Branching Processes
Privault,
Understanding Markov Chains, Branching Processes
WEEK 9: Mar 5, 7
[D Chapter 2, 4][HPS Chapter 3] Markov pure jump processes
transition rate, jump rate, and transition probabilities,
(i) exponentially distributed interjump times;
(ii) transition probability of jumping locations;
(i) (when) and (ii) (where) are independent.
memoryless property of exponential random variables
NOTE:
description of pure jump processes
[D Chapter 2][HPS Chapter 3] Poisson processes
exponential random variables, Poisson random variables
convergence of
(i) binomial to Poisson;
(ii) geometric to Exponential;
(iii) negative binomial to Gamma, and
(iv) infinitely many iid coin tossing to Poisson processes
NOTE: Poisson process
(WEEK 10: Spring Break)
WEEK 11: Mar 19, 21
NOTE:
FirstStepAnalysis: computation of absorption probabilities
and expected absorption times
NOTE:
Solution of Gambler's Ruin Problems (using firststepanalysis)
Homeworks 1, 2, 3 selected
solutions
A Past Test
Midterm Solution
Midterm on Thursday, Mar 21, in class
Materials covered: discrete space, discrete time Markov chains
All lecture materials, Homeworks 13 and relevant sections of [D, HPS].
(Poisson processes will not be covered. But you do need to know the basic
properties of Poisson random variables.)
You can bring one 8x11twosided formula sheet.
No electronic devices.
WEEK 12: Mar 26, 28
[D Chapter 2][HPS Chapter 3] Poisson processes
Definition (1): using transition rate;
Definition (2): as a spatial point process;
convergence of Binomial to Poisson process,
[D Section 2.4] properties of Poisson process:
superposition, thinning, conditioning
(order statistics, Binomial distribution)
NOTE:
Properties of Poisson Processes
Definition of Poisson Processes
(Ross, First Course in Probability)
Definition of Poisson Processes
(Ross, Stochastic Processes)
[D Chapter 4][HPS Chapter 3]
Transition probability (in continuous time),
ChapmanKolmogorov equations,
Kolmogorov backward and forward equations
Homework 4,
due Thursday, Apr. 4, in class.
WEEK 13: Apr 2, 4
[D Chapter 4][HPS Chapter 3]
Some analytical techniques of solving differential equations:
matrix exponential and integrating factor
(variation of parameters)
Solution of Kolmogorov forward equations:
[D p. 155][HPS p. 92] twostate Markov process,
[D p. 154][HPS p. 94] Poisson process
General birth and death processes and their applications:
branching processes (with immigration),
Yule process (pure birth with linear growth),
M/M/(infinty/s/1) queues.
NOTE:
ChapmanKolmogorov Equations and
Kolmogorov backward and forward equations
WEEK 14: Apr 9, 11
[D Chapter 4][HPS Chapter 3]
Integration of Kolmogorov F/B equations, integrating factor
Stationary distribution of CTMC, exit distribution, exit time,
Stationary distribution of birth and death chain, M/M/s queue
NOTE:
Stationary distribution of CTMC
Homework 5,
due Thursday, Apr. 18, in class.
WEEK 15: Apr 16, 18
[F1 Chapter 3] One dimensional simple symmetric Random Walk
computation of probabilities, reflection principle,
(1) probability of equalization;
(2) return time distribution (null recurrence);
(3) distribution of maximum;
(4) distribution of first passage time.
Feller, Volume 1, Chapter 3:
1D Random Walks
WEEK 16: Apr 23
[F1 Chapter 3] Further properties of one dimensional simple symmetric
Random Walk:
(5) distribution of last visits;
(6) distribution of time intervals above/below 0;
(7) distribution of crossings.
NOTE:
Computation of probabilities of trajectories of random walk
Final Exam: Wed, 05/01, 1pm3pm, SMTH 118
Materials covered:
All lecture materials (including random walks),
homeworks and relevant sections of [D, HPS].
You can bring one 8x11twosided formula sheet but no electronic devices.
A past final
Solution of Hw 4
Solution of Hw 5
Some commonly asked questions
Feller, Volume 1, Chapter 17:
Jump processes
Little's original paper 1961
Little's Law: applications
Little's Law: 50th Anniversary
Office hours during exam week:
Monday 3:305:30, Tuesday 4:306
Solution of final exam