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:00-3:00pm, Wed: 5:00-6: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 1-4
which also correspond roughly to [HPS] Chapters 1-3 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 bi-weekly. 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 handed-in 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.1-1.2][HPS, 1.1-1.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.2-1.3][HPS, 1.1-1.6]
    transition probabilities, classification of states

    NOTE: Transition probabilities

    Homework 1, due Thursday, Jan. 24, in class.


    WEEK 3: Jan 22, 24

    [D, 1.2-1.3][HPS, 1.1-1.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]
    (One-step) transition probability matrix Q (from transient states to transient states),
    existence of (I-Q)^(-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] Birth-and-death 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: two-state-MC, web-page surfing and ranking
    How Does Google Google (David Gleich)
    PageRank Beyong the Web (David Gleich)

    Birth-and-death 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
    Grinstead-Snell, Introduction to Probability, Chapter 11 Markov Chain
    Perron-Frobenious 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, Watson-Galton)

    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 inter-jump 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: First-Step-Analysis: computation of absorption probabilities and expected absorption times
    NOTE: Solution of Gambler's Ruin Problems (using first-step-analysis)
    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 1-3 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 8x11-two-sided 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),
    Chapman-Kolmogorov 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] two-state 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: Chapman-Kolmogorov 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, 1pm-3pm, SMTH 118

    Materials covered:
    All lecture materials (including random walks), homeworks and relevant sections of [D, HPS].
    You can bring one 8x11-two-sided 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:30-5:30, Tuesday 4:30-6

    Solution of final exam