Statistics 650  Applied Stochastic Processes

Spring 2018                                      MW 5-6:15pm , Mth 0409

This course web page will be updated in mid-January for the Spring 2018 STAT 650 course. The texts previously used in 2016 are still avalable free to UMCP students through the Library, as e-books. This spring, the main text will be Durrett, Essentials of Stochastic Processes, in the beta 2nd edition available free online and also here.


Please go to the web-page CourseEvalUM by Wednesday, May 11, 2017, to fill out a course evaluation on this course, on me, the books, and the level of the problems and tests. Thank you.


For a copy of two pages in the Grimmett and Stirzaker "Probability and Random Processes" book summarizing the main Renewal Theory Limit Theorems, click here or go to Handout (6) below.

                                      Information about Mid-term Test

                                      Information about Final Examination

                                      Sample Final-Exam Problems

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

Office:    Mth 2314, x5-5469, email evs@math.umd.edu

Office hours:    M11, W1:30 or by appointment.

Course Texts:
       R. Serfozo, Basics of Applied Stochastic Processes, 2009 Springer.
       M. Lefebvre, Applied Stochastic Processes, 2007 Springer.

Both of these books can be freely downloaded (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 Library for details.)

Both of these two books are well-written mathematical treatments of our subject, but the first book is written with slightly more advanced prerequisite, assuming measure-theoretic probability. We will generally cover material in the Lefebvre book first, amplifying as needed from Serfozo. I will try to keep the problems at the level of the Lefebvre book.

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.

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 a broad selection of applications. However, its problems are (much) too hard.

R. Durrett, Essentials of Stochastic processes, 1999, Springer-Verlag.

Slightly less formal problem-oriented text, which explains things well, and has lots of simple examples and problems.

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 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, or Math 410 plus one semester of probability theory.

Course requirements and Grading: there will be 8 graded homework sets (one every 1 weeks) which together will count 50% of the course grade. There will also be an in-class test and a final examination, which will respectively count 20% and 30% toward the overall course grade.


Homework

Homeworks are to be handed in in-class on the indicated due-dates. With advance notice from you, I will accept electronically submitted papers. Generally I will post solutions or sketches of solutions on or shortly after the due date. Late papers will lose at least 15% credit (the more the later they are).
Assignments, including any changes and hints, will continually be posted here. The directory in which you can find old homework assignments and selected problem solutions is Homework.

In all homework problems, your solution will be graded correct only if you fully justify your reasoning.

The reading for the first Homework consists of the Review Chapter (Chapter 1 of Lefebvre) along with review of STAT 410 level material from any other books.

Homework 1 (due Friday Feb. 5 in class, 8 problems in all): Do problems 4, 6, 15, 19, 30, 33, 43, pp. 35-43 in Lefebvre. Also do the same problem as #26 but with the N(μ, σ2) distribution replaced by the Gamma(α,β) distribution (which has density of the form    C xα-1 exp(-βx)    for x>0).

Homework 2 (due Monday Feb.22 in class, 8 problems): Do problems 11, 15, 20, 21, 23, 29, 31, 38 (using a different 4x4 transition matrix that I will give you to replace the one in #38). pp. 134-159 in Lefebvre (Sec.3.4).
For problem number 38, use the 4x4 transition matrix    P     on the state-space   S    {0,1,2,3}   given by

         |   0.5    0.5     0       0   |
         | 0.25    0.25   0.5    0    |
         |     0     0.5     0     0.5  |
         |     0     0        1       0   |

NOTE that as a result of snow and student requests, the due date for HW2 was changed to Monday, February 22. I also sent a course-mail message to everybody (2/17) about HW2 Problem #15. That message is reproduced in full here.

Homework 3 (due Wednesday March 2 in class, 8 problems in all): Do problems 33, 43, 49, 51, 61, 67 from pp. 152-162 in Lefebvre. In addition, do the following two problems.
         (I). Look at the statement of Proposition 3.2.2, p.86 in Lefebvre. This assertion (which the book says is "easy to show") is actually wrong. Give a concrete example of a finite-state homogeneous-transition Markov Chain for which it fails.
         (II). Consider the process X_n = Z_{n-1}+Z_{n-2} where Z_{k} are the binary {0,1} outcomes of Bernoulli(1/2) trials, for n > 2. Using the definitions, show that Y_n = (Z_n, Z_{n-1}) is a HMC, but that X_n is not a Markov Chain.

Homework 4 (extended due-date Wednesday March 23 in class, 8 problems in all): Do problem 53 in Lefebvre, problems 39, 43
and 47 in Serfozo (Chapter 1, pp.91-93). But note that there are a couple of misprints in Serfozo's Problem 47:
first, the definition of the waiting time τ should be   τ = inf{ n ≥ 0: Xn = 101}. Also, the equation for G1(s) that you
are supposed to verify should be:    G1(s) = s (p G1(s) + q G2(s)).

In addition, as part of the same HW4 set, do the problems:

(I). Let {Xn: n=0,1,2,...} be a branching process for which X0=1 and the offspring distribution is
pZ(k) = 0.1 for k=0, =0.6 for k=1, and = 0.3 for k=2.
      (a) Find the extinction probability   q = P(Xn=0 for some t>0 | X0=1).
      (b) Find the expected value and variance of X4.
      (c) Find E(X4 | X3>1).

(II).(a) Let Mn denote the size at time n of a population governed by a pure-death Markov-chain with M0=100 and transition probabilities  P_k,k-1 = min(0.5, .01*k) = 1-Pk,k for k=0,1,2,... Find the expectation and variance of the time T0 until the population dies out.   (b) Suppose we modify the chain so that all transitions P0,k = 0.01 for k=1,...,100 (leaving all other transitions Pk,j for k>0 just as in part (a)). Find the stationary distribution for the chain.

(III).(a) In problem #50 in Lefebvre, find   E(T0 | X0=0).
      (b) In problem #43 in Lefebvre, find   E(T5 | X0=4). Hint: use first-step analysis.

(IV) Let X(n) be a birth-death Markov chain with μk = Pk,k+1 = p if k is odd and r if k is even, k=1,2,... where both p, r are between 0 and 1, and where λk = Pk,k-1= 1-Pk,k+1 for positive k, and P0,1=1. Give a necessary and sufficient condition on p,r for the chain to be recurrent, and a necessary and sufficient condition for the chain to be positive-recurrent.

Homework 5 (due Wednesday March 30 in class, 6 problems will be on continuous-time Markov chain definitions and basic properties.): Do problems # 18, 72 and 87 in Lefebvre. In addition:

(I). Define a continuous time chain with state-space S={0,1,2,3,4} from the discrete-time transition matrix   P   with p0,1 = p4,3=1 and for k=1,2,3,    pk,k+1 = p = 1- pk,k-1, letting the rates   λk   of transition away from each state k ∈ S be 1.
      (a) Find   E1(T0)   for this continuous-time chain.
      (b) Show that the stationary distribution   π   for the discrete-time chain also has the property that if   P(X0=j) = πj, then for all t>0,    P(Xt=j) = πj.

(II). Give and solve an ordinary differential equation satisfied by   Pij(t)   for the continuous-time chain with discrete transitions on {0,1,2,3} governed by the transition matrix with   p3,2 = 1 = p0,1, p1,0 = p1,2 = p2,1 = p2,3 = ½ and all rates   λj = 1.

(III). For the chain in problem (II), find   E0(X1)  and   E0(T0) .


Reading for the next segment of the course is: Lefebvre Chapter 3 Secs. 3.3.2-3.3.5 (pp.121-142) and Serfozo Ch.4 (pp.241-255, through Sec.4.5) on continuous-time Markov chains, and Lefebvre Ch.5 pp. 231-247 on Poisson processes. Course-Outline topics that we are covering now and for the next 5 or 6 lectures are: 3(a) long-time limit theory and explicit solutions in continuous-times chains, and 6(a),(c),(d) on Poisson processes and birth-death processes, with some queueing examples (Sec.7(a)).

Homework 6 (due Monday April 18 in class, 7 problems): Do problems #77, 79, 92 in Lefebvre Ch.3, pp. 165-170, and problems #1, 8, 16 in Serfozo Ch.4, on pp. 323-327.

In addition: do

(I). Find the explicit solution for the transition probability functions   P1,k(t) for k=1,2,3,4,5, in the continuous-time homogeneous Markov chain with transition rates λj,k (for j,k=1,...,5) equal to 1 for |j-k| equal to 1 or 2, equal to 0 for |j-k| > 2, and equal respectivly to -2,-3,-4,-3,-2 when j=k is respectively equal to 1,2,3,4,5. Give the value of the limiting probabilities   P1,k(∞) = πk, and the dominant terms   ck exp(-β t)   of the differences P1,k(t) - πk   when t is large.


For the next portion of the course and the next HW read: Serfozo Section 1.11 especially Proposition 69 about "Cycles and Costs", and Serfozo Chapter 2 on Renewal and Regenerative processes, through section 2.6; also read Section 5.6 in Lefebvre on Renewal ideas.

Homework 7 (due Friday April 29 in class, 7 problems): Do problems #22 (p.161) in Serfozo Chapter 2, and #5,13, 19 (pp.226-229) in Serfozo Chapter 3. Also do Problems #9,13,25 in Lefebvre Chapter 5, pp.292-295.

For the final portion of the course and the next HW, read: Lefebvre pp.101-104 on martingales (and Serfozo Section 5.5 if you can); Lefebvre Sections 5.2-5.3 on nonhomogeneous and compound Poisson processes, and Serfozo Sec.3.5 on Poisson processes on more general spaces like Rk.

Homework 8 (due Wednesday May 11 at the review session, 7 problems): Do problems #29(c) and 36 in Ch.5 in Lefebvre (pp.296,298) and #17 in Chapter 3 (p.229) of Serfozo. In addition: do

(I). Suppose that N(t) is a nonhomogeneous Poisson process with rate-function 2t2 for t ≥ 0. Show that for any bounded function a(s),   Z(t) = ∫0t a(s) dN(s)   is a Compound Poisson random variable of the form   ∑i=1ν Xi for a Poisson random variable ν and independent iid random variables Xi; give the parameter of ν and the distribution of Xi, and interpret the meaning of Z(t) in a setting where N(t) is counting failure events.

(II). Suppose that N(E) is a homogeneous Poisson(λ) process on the positive quadrant in the plane, with t1 ≥ 0,   t2 ≥ 0. Show that the processes   M1(t) = N({(t1, t2):   0 ≤ t1 ≤ t2 ≤ t})   and   M2(t) = N({(t1, t2):   0 ≤ t1 ≤ t,   0 ≤ t2 ≤ 1})   are (possibly nonhomogeneous) Poisson processes, and give their rate functions.

(III). Suppose that Y(t) = ∑k=1N(t) Xk   is a compound Poisson process, where Xk   are i.i.d. with probability mass function p(0)=.2, p(1)=.5, p(2)=.3. Find a number r ≠ 1 such that   rY(t)   is a martingale with mean 1. (This number r should not depend on the rate λ of the Poisson process N(t).)

(IV). A gambling game is conducted by giving a player an initial stake of $10, doing a series of Bernoulli(0.4) trials each of which adds $1 to his fortune with probability 0.4 and subtracts $1 from it with the remaining probability 1/6. The game ends the first time that the player's fortune hits $15 or $0, whichever comes first. What is the expected fortune at the end ?



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 disatribution 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 Kolmogoroff forward and backward equations when the rates q_i of leaving states are uniformly bounded.

(5). A Sample Test containing short-answer problems like the ones to appear on the April 1 in-class test can be found here. Note also that a correction has been made to the statements of HW5 Problems II,III saying that the rates   λj   are 1.

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


Mid-Term Test

A mid-term test will be given in-class on Friday, April 1, 2016. It will be easier than the HW problems, consisting of short-answer questions emphasizing definitions and the application of results of Theorems. Sample problems can be found here. On the test, you will not be permitted to use your books, but you are allowed to bring up to two notebook sheets of notes for reference.

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


Sample Final Exam

You can find sample final-exam problems here. By all means try them and ask questions about them, either in class or in the Review Session to be held Wednesday, May 11, in our classroom from 9--11am.


Final Examination

The Final Examination will be held from 8 to 10am on Monday, May 16, 2016 in the regular classroom. It will have 5 or 6 problems. The coverage is cumulative of all material from the Lefebvre book assigned and covered in class throughout the semester. Also, you will be allowed 2 2-sided notebook sheets of reference material for the exam. But the exam will otherwise be closed-book.

There will be a review session on Wednesday, May 11, 9-11am, for the Final Exam.


STAT 650 SYLLABUS / COURSE OUTLINE

0. Probability Review.     ( Lefebvre, Chapter 1; Serfozo, Sec.1.22 & Ch.6.)     3 Lectures
                Probability spaces, countable additivity.
                Conditional expectation, change-of-variable and transforms of r.v.'s

1. General Definitions and Properties of Stochastic Processes     ( Lefebvre, Chapter 2.)     1 Lecture
                Spaces of trajectories (infinite sequences of states).
                Independent increments, stationarity and wide-sense stationarity, Markov property, ergodicity

2. Discrete-time Discrete-State Markov Chains.     ( Lefebvre, Ch. 3, Secs.3.-3.2, Serfozo, Ch. 1 through Sec. 1.10)     5 Lectures
                (a) Markov property. Examples of Markov & non-Markov random sequences.
                (b) Multistep transition probabilities. Chapman-Kolmogorov equation.
                (c) "First-step analysis"
                (d) Classification of states.
                (e) Notions of limiting behavior. Reducibility. Recurrence. Steady state.
                (f) Time reversibility & regeneration.

3. Recurrence and Ergodicity.     ( Lefebvre, Sec.3.2.3; Serfozo Secs. 1.12, 1.13, 1.21)     2 Lectures
                (a) Criteria for recurrence and positive recurrence.
                    Random-walk & birth-death examples.
                (b) Empirical averages. Ergodic Theorem (Law of Large Numbers).
                    Renewal reward theorem.

4. Asymptotic Behavior. Equilibrium & Renewal theory.     ( Lefebvre, Secs.3.2.3, 3.2.4 and
                    Serfozo, Secs. 1.11, 1.20 & Ch.2 through Sec. 2.9
)        4 Lectures
                (a) Proof of equilibrium. Coupling method of proof.
                (b) Renewal theory. Regenerative processes.
                (c) Analysis of Absorption (in transient examples).

5. Martingales & Applications.
        3 Lectures
                (a) Definitions and Optional Sampling Theorem.
                (b) Expectation calculations in examples.
                (c) Random-walk, branching-process and other examples.

6. Poisson Processes & Continuous-time Chains.     ( Lefebvre, Chapter 5 & Sec.3.3.)         6 Lectures
                (a) Poisson process def'ns and characterizations
                (b) Relation to Discrete-time chains. Embedding.
                (c) Transition probabilities. Recurrence. Limiting behavior.
                (d) Birth-death process examples.

7. Queueing & Other Applications     ( Lefebvre, Chapter 6; Serfozo)         6 Lectures
                (a) Queueing examples.
                (b) Reversibility. Applications in Queueing & Markov Chain Monte Carlo.

Important Dates


The UMCP Math Department home page.

The University of Maryland home page.

My home page.

Eric V Slud, December 13, 2017.