Statistics 650  Applied Stochastic Processes

After Spring Break, starting March 30, 2020, this course will be delivered only in an online format, through ELMS/Canvas and Zoom tools. Major announcements related to homework assignments will continue to be posted on this website as well as on ELMS. However, essential course materials including lecture materials, tests, discussion boards, and online office hours will be accessible only through your student accounts on ELMS, into which you log in with University credentials at https://elms.umd.edu/.

This web-page for STAT 650 is adapted from one last used in Spring 2018. The main difference is that in Spring 2020 the required textbook is the Serfozo book listed below, which is available free as an e-book through the University of Maryland Library catalog. The texts listed below other than Karlin and Taylor -- including the Durrett book required in Spring 2018 -- are also available as free e-books and are still Recommended Texts for Spring 2020.

A directory containing old final exams and sample exam problems, and also a list of topics we emphasized in the Spring 2018 term's course, can be found here.

Instructor: Eric Slud, Statistics Program, Math. Dept.

Office:    MTH (Kirwan Hall) 2314, x5-5469, email slud@umd.edu

Office hours:    M11am-12noon, W1-2pm or by appointment.

Required Course Text:
R. Serfozo, Basics of Applied Stochastic Processes, 2009 Springer.

This book is somewhat more formal about theorems and proofs than Durrett, and uses some real-analysis language and the notation of "sigma-algebras", but is presented at the level of a slightly strengthened version of undergraduate Probability (STAT 410) and does not require any knowledge of measure theory.

Recommended Texts:
Karlin, S. and Taylor, H., A First Course in Stochastic Processes, 2nd ed. 1975, Academic Press.

This is an excellent standard book, with thorough treatment of all important topics and lots of applications. However, its problems are (much) too hard.

Additional Recommended Course Texts (used in Spring 2016 and 2018):
R. Durrett, Essentials of Stochastic processes, 1999, 2nd ed. 2010, 3rd ed. 2016, Springer.

This is a good, readable book, with intuitive explanations and many interesting problems. The beta 2nd edition is available free online and also here.

M. Lefebvre, Applied Stochastic Processes, 2007 Springer.

This book is definitely easier than the others; it is radable at a more basic level and is a source for easier problems and more straightforward applications.

The Serfozo and Lefebvre books can be freely downloaded as e-books (through the University of Maryland libraries) by currently registered University of Maryland College Park students, who can also purchase hard-copies for $25.00. (Inquire at the EPSL (STEM) Library for details.)

Current HW Assignment         Updated HW Solutions         Info about Mid-term Test         Info about Final Examination         Sample Final-Exam Problems

Course Coverage: The core material of the course consists of Chapters 1-4 in the Serfozo book, with considerable skipping of more advanced topics, and Chapters 3, 5, and 6 in the Lefebvre book: the primary topics are Discrete Time Markov Chains, Poisson Processes, Continuous Time Markov Chains, and Renewal Processes. See detailed Course Outline below. The primary applications are population and queueing processes, but many other special applied examples occur in both books.

Overview:    This course is about Stochastic Processes, or time-evolving collections of random variables, primarily about the discrete-state continuous time Markov chains which arise in applications in a variety of disciplines. For the first part of the course, both the random variables and the time index-set are discrete: in this setting, our object of study is discrete-time discrete-state Markov chains. Examples of "states" which arise in applications include the size of a population or a waiting-line, or the state ("in control" versus "out of control") of a manufacturing process, or other indicators such as "married" or "employed" etc. for an individual. "Markov chains" are time-evolving systems whose future trajectory does not depend on their past history, given their current state. But many of the most interesting applications involve the generalization of the same ideas to continuous time.

Probability theory material needed throughout this course includes joint probability laws, probability mass functions and densities, conditional expectations, moment generating functions, and an understanding of the various kinds of probabilistic convergence, including the Law of Large Numbers.

Various technical tools developed in the course and used in an essential way include: Laplace transforms and moment generating functions, methods of solving recursions and systems of difference equations, ergodic and renewal theorems for Markov chains, and (discrete-time) martingales.

Prerequisite:   Stat 410 plus additional background in mathematical analysis and proofs, or Math 410 plus one semester of probability theory.

Course requirements and Grading: there will be 6 or 7 graded homework sets (one every 1½ to 2 weeks) which together will count 50% of the course grade. In all homework problems, your solution will be graded correct only if you fully justify your reasoning. There will also be an in-class test and a final examination, which will respectively count 20% and 30% toward the overall course grade.
NOTE As of March 30: There will be 6 HW's in all. The Midterm will be an online 60 minute Quiz administered through ELMS. The Final will be Take-Home. The weights used in computing the final grade will be changed to: HW 60%, Midterm 15%, Final 25%. Details of these course changes, the revised Syllabus, and the mode of delivery of Lectures, Office Hours and Discussions can be found in the ELMS Pages and Files and here.

STAT 650 SYLLABUS / COURSE OUTLINE    Revised 3/13/2020 syllabus here

Homework

HW Assignment 1 (due in class Monday, Feb. 10):
Read Serfozo Ch.6 (Review) Sec.1.22, Secs. 6.1 and 6.6--6.9, plus Ch.1, Sections 1.1-1.6.
Problems to Hand in from Serfozo Ch.1, pp.84-98: #8, 13, 17, 26.
Problems in Lefebvre book, pp.145-6: #12, 15.
Additional Problems to Hand in:
(I) For two independent random variables   X ~ Uniform[0,2]   and   Y ~ Expon(1),   find   (a)   E(Y-X | Y > X) ,   and   (b)   the joint probability distribution of   (min(X,Y), Y - min(X,Y)).   Note that the second component random variable in this pair has a probability atom at 0, i.e. a positive probability of being equal to 0.
(II) In the game of craps when the "shooter's point is 4", the player's objective is to throw a sum of 4 dots showing with two [independent, fair] dice before a sum of 7 dots appears, in repeated tosses of the two dice. Calculate in three different ways the probability x that he succeeds:   
(i) Consider the outcome of the first roll of the dice, to conclude that    x = 3/36 + (27/36) x    and solve.
(ii) Let   A_k   be the event that the sum is   k   and justify why    x = P(A₄) / P( A₄ ∪ A₇).
(iii) Calculate directly and then sum up over k the probabilities that 4 occurs before 7 and that this happens on the   k'th trial.

HW Assignment 2 (due in class Monday, Feb. 24):
Read Serfozo Ch.1 Sections 1.5-1.13 and 1.20-1.22.
Problems to hand in:
Problems in Serfozo book, pp.89-92: # 25, 36, 37, 44.
Problems in Lefebvre book, pp.145-149: # 11, 18, 20, 21.

HW Assignment 3 (due in class Wednesday, March 11):
Read Serfozo Ch.1 Sections 1.8, 1.12, 1.13,, 1.17, 1.18, 1.20-1.21, Ch. 2 through Sec.2.2.
Problems to hand in:
Problems in Serfozo book, pp.89-92: # 27, 39, 50.
Problems in Lefebvre book, pp.153-155: # 38, 41.
3 Additional Problems to Hand in:
(A) Establish the complete set of values a,b for which the Markov Chain with states 0,1,2 and transition matrix defined by
p_0,1 = p_1,0 = p_1,1 = p_1,2 = p_2,1 = 1/3,       p_0,2 = a ,     p_2,0 = b,       is reversible.
(B) Suppose that (X_k,    k=0,1,2, ...) is a temporally homogeneous Markov chain on state-space   S   equal to the nonnegative integers. Suppose that   p(i,j)=0   whenever   j > i+20,   that   p(i,i+1)>0   for all   i,   and that for all   n ≥ 10,   p(n,0) ≥ 1/n^1/2.   Prove from these assumptions that
(a) for all initial states   i,     Pr(min({k ≥ 1:   X_k ∈ {0,1,...,9}}) < ∞)   |   X₀=i) = 1,   and that therefore
(b) the Markov chain is irreducible and recurrent.
(C) Let {X_n: n=0,1,2,...} be a branching process for which X₀=1 and the offspring prob. mass function is    p_Z(0)=0.1,   p_Z(1)=0.6, and   p_Z(2)=0.3.
(a) Find the extinction probability   q = P(X_n=0 for some n>0 | X₀=1).
(b) Find the expected value and variance of X₄.
(c) Find E(X₄ | X₃>1).

HW Assignment 4, six (6) problems due April 13 (by 11:59pm) in Assignments on ELMS.
Read Serfozo Ch.2 Sections 2.1-2.2, Ch.3 through Sec.3.3, Lefebvre Ch.5 Sec.5.1 through p.247.
Problems to hand in:
Problems in Serfozo book: Ch.3 #15 on p.228, and Ch.2 # 53 on p.167.
Problems in Lefebvre book: Ch.3 #17, 60 pp.147-160, and Ch.5 #10 pp.290-292.
1 Additional Problem to Hand in:
(A) Calculate the variance of X defined in Example (c) at the end of 3/30 Lecture part A.

HW Assignment 5, six (6) problems due Monday April 27 (by 11:59pm) in Assignments on ELMS.
Read Lefebvre 3.3.2-3.3.5 (Continuous-time MC's) and Sec. 5.2 (Nohomogeneous Poisson),
and also Serfozo Ch.4 through 4.5 plus Sec. 4.7.
Problems to hand in:
Problems in Serfozo book: Ch.3 #27 and #30 on p.231, and Ch.4 #20 on p.328.
Problems in Lefebvre book: Ch.3 #75 p.164, #81, #82 pp.166-167.

HW Assignment 6, six (6) problems due Wednesday May 13 (by 11:59pm) in Assignments on ELMS.
Read Serfozo Sec. 1.8 (MCMC), Durrett Example 1.35 and Chapter 5, and Serfozo Sections 5.5-5.6.
4 Problems to hand in from Serfozo:
Serfozo text, Ch.1 #55, p.95; Ch.4 #14 p.326, #19 p.328; and #24 pp.329-330.
2 Additional Problems to hand in:
(A)(a) Show that the continuous-time Birth-Death Process with   λ_n = μ_n = n λ , with   λ > 0,
is a martingale, and use this to show that E₁(X(t)) = 1.
(b) Argue that the birth-death process X(t) in (a) starting at X(0)=m, is equal in distribution
to the algebraic sum of m independent processes X_j(t) of the same Birth-Death type but
starting at X_j(0)=1. Use this to obtain the formula for   P_m(X(t) = 0).
(B) Suppose that N_rc are independent Poisson(λ p_r q_c)   random variables, for r=1,...,R and c=1,...,C,
where   (p₁,p₂,...,p_R)   and   (q₁,q₂,...,q_C)   are probability vectors.
Find the generalized Hypergeometric joint probability mass function for these random
variables N_rc conditionally given   Σ_c=1^C N_rc= m_r   and   Σ_r=1^R N_rc= n_c. This joint probability
mass function should depend on the row and column marginal sums   m_r   and   n_c   but turn
out not to depend on the values   p_r   and   q_c.

Handouts

(1). Handout on a non-Markovian example constructed by lumping 2 of the states in a 3-state Homogeneous Markov Chain.

(2). Handout of 5 pages from Durrett's "Essentials of Stochastic Processes" book containing proofs for equivalent conditions to positive-recurrence, for aperiodic irreducible HMC's.

(3). Handout clarifying two loose ends from recent classes: (1) the condition for existence of a stationary probability distribution for recurrent Birth-Death chains, and (2) the notational verification as in Durrett that the "cycle trick" provides a stationary distribution for an irreducible positive-recurrent HMC.

(4). Handout on existence of invariant vectors for countable-state irreducible transient Homogeneous Markov Chains.

(5). Handout on the uniqueness of solutions of the Kolmogorov forward and backward equations when the rates q_i of leaving states are uniformly bounded.

(6). A Sample Test containing short-answer problems like the ones to appear on the March 30 in-class test can be found here. Note that this sample test does not have Poisson process problems, although they are in scope for the mid-term.

(7). Handout on the main limit theorems of renewal theory, taken from 2 pages of the Grimmett and Stirzaker book, "Probability and Random Processes".

(8). Handout on Introduction to Markov Chain Monte Carlo. This is a statistical computing topic based on a strong theoretical foundation involving Markov Chains in discrete-time on discrete or continuous state spaces. This is unit 7 on my STAT 705 web-page, for which you can find lecture notes on Metropolis-Hastings and the Gibbs Sampler here. In addition, you can find lectures from a mini-course pair of lectures I gave on the topic in this folder.

In light of the campus closure and online course format from March 30 through April 10, a mid-term test will be given on-line to be taken through ELMS between April 8 and 10, 2020. It will be easier than the HW problems, consisting of short-answer questions emphasizing definitions and the application of results of Theorems, plus a true-false component. Sample problems can be found here.

Sample problems and information about specific coverage of the test can be found here.

You can find sample final-exam problems here. By all means try them and ask questions about them.

• First Class: Monday, January 27
• Spring Break: March 15-22.
• Extra week off due to Coronavirus
• Mid-Term Exam:   Will now be given in an online assessment format TBD after April 6, 2020.
• Last day of class: Monday, May 11
• Review session for Final:   Friday, May 15, 4:30 - 6pm.
• Final Exam:  Monday, 5/18/20: 4-6pm if campus re-opens. Otherwise, final will be take-home over May 15-18, due on the 18th.  
  IN-CLASS FINAL EXAM: NOTE 4pm instead of 5pm.

The UMCP Math Department home page.

The University of Maryland home page.

My home page.

© Eric V Slud, May 11, 2020.