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
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.
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: X_{n} = 101}. Also, the equation for G_{1}(s) that you
are supposed to verify should be: G_{1}(s) = s (p G_{1}(s) + q G_{2}(s)).
In addition, as part of the same HW4 set, do the problems:
(I). Let {X_{n}: n=0,1,2,...} be a branching process for which X_{0}=1 and the
offspring distribution is
p_{Z}(k) = 0.1 for k=0, =0.6 for k=1, and = 0.3 for k=2.
(a) Find the extinction probability q = P(X_{n}=0 for some t>0 |
X_{0}=1).
(b) Find the expected value and variance of X_{4}.
(c) Find E(X_{4} | X_{3}>1).
(II).(a) Let M_{n} denote the size at time n of a population governed by a pure-death Markov-chain with M_{0}=100
and transition probabilities P__{k,k-1} = min(0.5, .01*k) = 1-P_{k,k} for k=0,1,2,... Find the
expectation and variance of the time T_{0} until the population dies out. (b) Suppose we modify the chain
so that all transitions P_{0,k} = 0.01 for k=1,...,100 (leaving all other transitions P_{k,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(T_{0} | X_{0}=0).
(b) In problem #43 in Lefebvre, find E(T_{5} | X_{0}=4).
Hint: use first-step analysis.
(IV) Let X(n) be a birth-death Markov chain with μ_{k} = P_{k,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} = P_{k,k-1}=
1-P_{k,k+1} for positive k, and P_{0,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 p_{0,1} = p_{4,3}=1 and for k=1,2,3,
p_{k,k+1} = p = 1- p_{k,k-1}, letting the rates λ_{k} of
transition away from each state k ∈ S be 1.
(a) Find E_{1}(T_{0}) for this continuous-time
chain.
(b) Show that the stationary distribution π for the
discrete-time chain also has the property that if P(X_{0}=j) = π_{j}, then for all
t>0, P(X_{t}=j) = π_{j}.
(II). Give and solve an ordinary differential equation satisfied by P_{ij}(t) for the
continuous-time chain with discrete transitions on {0,1,2,3} governed by the transition matrix with
p_{3,2} = 1 = p_{0,1}, p_{1,0} = p_{1,2} = p_{2,1} = p_{2,3}
= ½ and all rates λ_{j} = 1.
(III). For the chain in problem (II), find E_{0}(X_{1}) and
E_{0}(T_{0}) .
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 P_{1,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
P_{1,k}(∞) = π_{k}, and the dominant terms c_{k} exp(-β t)
of the differences P_{1,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 R^{k}.
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 2t^{2} for t ≥ 0. Show that for any bounded function a(s), Z(t) = ∫_{0}^{t} a(s) dN(s) is a Compound Poisson random variable of the form ∑_{i=1}^{ν} X_{i} for a Poisson random variable ν and independent iid random variables X_{i}; give the parameter of ν and the distribution of X_{i}, 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 t_{1} ≥ 0,
t_{2} ≥ 0. Show that the processes M_{1}(t) = N({(t_{1}, t_{2}): 0 ≤ t_{1} ≤ t_{2} ≤ t}) and M_{2}(t) = N({(t_{1}, t_{2}): 0 ≤
t_{1} ≤ t, 0 ≤ t_{2} ≤ 1}) are (possibly nonhomogeneous) Poisson processes, and give their rate functions.
(III). Suppose that Y(t) = ∑_{k=1}^{N(t)} X_{k} is a compound Poisson process, where X_{k} are i.i.d. with probability mass function p(0)=.2, p(1)=.5, p(2)=.3. Find a number r ≠ 1 such that r^{Y(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 ?
(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.
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.
The UMCP Math Department home page.
The University of Maryland home page.
My home page.
© Eric V Slud, December 13, 2017.