Rice University

*This course covers the theory of some of the stochastic processes used
**most frequently**in application:
discrete and continuous time Markov chains, Poisson and renewal processes,
and Brownian motion*

Test 2 due last day of class

Solution 9 available

Last update Dec 1. 2006

**Instructor**

Dr. Rudolf Riedi

Duncan Hall 2082, 713 / 348 3020,

Email for appointments

Alireza Keshavarz-Haddad

TR 09:25AM - 10:40AM HZ 119 (Hermann Brown)

see also Time (official Rice page)

Location (Rice map)

Monday 1-2 pm pm (DH 2082), or by appointment

**Outline and suggested topics**

- Preliminaries (incl. probability generating functions, simple random walks and branching processes, stopping times, Wald equality)
- QUIZ (allowed: one sheet = two pages of personal notes)
- Discrete-time Markov chains (joint distributions, transition probability, irreducibility, absorbing, transient and recurrent states, invariant measures, stationarity and equilibrium, ergodicity (time averages, mixing))
- Poisson Processes (including thinned and marked Poisson processes)
- Midterm EXAM (open-notes, closed-books)
- Renewal Processes (more on Poisson processes, Renewal theorem)
- Continuous-time Markov chains (Holding times, Chapman-Kolmogorov and Consistency, backward and forward equations)
- Brownian motion (construction via mid-points, self-similarity and scaling, Brownian bridges)
- Second EXAM (open-notes)

**Textbook**

Further suggested reading

S. Resnick, `Adventures in Stochastic Processes'.

The course will closely follow this book; it is available at the campus bookstore.

Also, Amazon quotes currently (4/2005) a prize reduction by 14%

- Ross, `Introduction to Probability Models'
- A. Papoulis, `Probability, Random Variables, and Stochastic Processes'
- W. Davenport, `Probability and Random Processes'
- W. Feller, `An Introduction to Probability Theory and Its Applications'
- P. Billingsley, `Probability and Measure'

**Grading**

15% QUIZ

30% Midterm EXAM

30% Last EXAM

25% Homework

[Outline] [Textbooks] [Grading] [Reading assignment] [Homework problems and solutions] [Tests][Knowledge Milestones]

**Classes and Reading assignments**

This doubles as a calendar for the course.See also the course schedule from Fall 2005

2006 |
Covered material | Reading: Resnick (Edition 2002) |

August 29 |
Orientation | |

August 31 |
Probability generating function (pgf), | 1-17, |

September 5 | Pgf cont., Simple Branching process, | 18-20, 21-26, |

September 7 |
Extinction, Simple random walk |
33-34 |

September 12 | First Hit at 1, stopping times, Wald's
identity
Up to here : material for QUIZ |
34-39, 44-45, 47-48 |

September 14 | Markov Chains basics, Chapman-Kolmogorov, Accessible States, Classes, Closed sets | 60-79 |

September 19 | REVIEW random walk, MC | |

September 21 | Quiz hand out. Take home, Due Friday Sept 22 Transience, Recurrence, Periodicity |
85-90 |

September 26 | Canonical Decomposition | 91-99 |

September 28 | Finite closed classes | 100-116 |

October 3 |
Stationary Distributions for recurrent chains | 116-122 |

October 5 |
Time averages |
123-132 |

October 10 | Limiting distributions | |

October 12 | Renewal processes: basics, Convolution | 174-176, 176-184 |

October 17 | Recess | |

October 19 | Renewal function, Renewal equation | 186-187, 197-205 |

Start to here | Material for Test 1 | |

October 24 |
exponential inter-arrival times, Poisson process on the line | 211,182 |

October 26 |
Limiting theorems | 189-191,212-217,224-227, 237 |

October 31 |
Review MC, discussion HW 6 | |

November 2 |
Hand-out 1st Exam | due Nov 10 noon |

November 2 | HW 6; Elementary renewal thm, Stationarity | |

November 7 | Stationary renewal sequences, Blackwell | 214-215,224-229 |

November 9 | Poisson processes: basics, transformation. | 300-318 |

November 14 | Discussion Test 1; Poisson processes: marking, queuing |
316-320; 333-336 |

November 16 | Poisson processes: thinning; Laplace functional | 337-346 |

November 21 |
general construction, order statistics and records; Compound Poisson | 346-349; 330-331 |

November 23 | Thanksgiving | |

November 28 |
Hand-out test 2. Material = from Recess to here | due last day of class 11:59 |

November 28 | General Markov processes: def, cond. probabilities, marginals and consistency, Poisson Point Process on line | Rao (Probab. Th.), pp 114-135 |

November 30 | Review Renewal processes, Poisson Point Processes | |

December 5 | Ex Markov: Poisson Renewal Process, Brownian motion | 367-376 |

December 7 | Continuous time Markov chains, Birth-Death process | 382-391 |

December 8 |
Last day of class, test 2 due |

[Outline] [Textbooks] [Grading] [Reading assignment] [Homework problems and solutions] [Tests][Knowledge Milestones]

**Homework**

(tex-source and solutions restricted to Rice University)

This
file is needed to latex the source.

Homework sheet | Due date (in class) | Solutions |

Problem Set 1 [ps] [pdf] [tex] | Sept 7, 2006 | posted Sept 12 [ps] [pdf] [tex] |

Problem Set 2 [ps] [pdf] [tex] | Sept 14, 2006 | posted Sept 21 [ps] [pdf] [tex] |

Problem Set 3 [ps] [pdf] [tex] | Oct 3, 2006 | posted Oct 3 [ps] [pdf] [tex] |

Problem Set 4 [ps] [pdf] [tex] | Oct 10, 2006 | posted Oct 12 [ps] [pdf] [tex] |

Problem Set 5 [ps] [pdf] [tex] | Oct 19, 2006 | posted Oct 23 [ps] [pdf] [tex] |

Problem Set 6 [ps] [pdf] [tex] | voluntary, practice test | discussed in class |

Problem Set 7 [ps] [pdf] [tex] | Nov 16 | posted Nov 18 [ps] [pdf] [tex] |

Problem Set 8 [ps] [pdf] [tex] | Nov 21 | posted Nov 22 [ps] [pdf] [tex] |

Problem Set 9 [ps] [pdf] [tex] | voluntary, practice test | discussed in class [ps] [pdf] [tex] |

Homework is due at the beginning of class on the due date. After the due date, but before solutions are handed out, homework can be turned in for 50% credit. In this case, please slip your homework under the instructors's office door, or bring it to class. After solutions are handed out, 0% credit will be issued. You are encouraged to work in groups for homeworks but you will hand in your own solution which you are expected to understand.

[Outline] [Textbooks] [Grading] [Reading assignment] [Homework problems and solutions] [Tests][Knowledge Milestones]

Quiz (15% towards the grade) | Due Sept 22 | In class, 60 min, (open: only two hand-written pages ) |

Test 1 (30%) | Due Nov 10 noon |
Take home, 3 hours,
closed book, open notes open solution handouts |

Test 2 (30%) | Due last day of class | Take home, 3 hours, open everything
on Renewal and Point processes |

**Knowledge Milestones aquired in this course
**

- Probability generating functions (pgf)

- Definition, Radius of convergence, relation to mean and higher moments
- Compounding formula (with derivation)

- Simple random walk
- Definition
- first hit at 1, first return to 0
- be able to derive pgf
- Know and derive formula for mean

- Wald identity for stopping times (with proof)

- Branching processes
- definition, be able to compute extinction probability from pgf

- definition, be able to compute extinction probability from pgf
- Discrete-time Markov chains
- Definition, transition probability,

- know: def of stationary, time-homogenous, Chapman-Kolmogorov (with
proof)

- Def: accessible, commuting state; Class; Irreducibility; Closed set
of states.

- Formulate: Dissection Principle
- def: Absorbing, transient and recurrent (null / positive) states
- Equivalent conditions for recurrent and for transient in terms of n-step transitions
- def of Canonical representation and Solidarity properties

- Know:

- recurrent classes are closed;

- example of closed transient classes
- Finite, closed sets contain recurrent states
- Classification of states for Simple Random Walk and for
Branching Processes

- recurrent classes are closed;
- Invariant measures
- Definition of invariant measures and of stationary distributions
- Know criteria for existnence and/or for uniqueness of invariant measures and/or stat. distr.
- Know formula for stat distr in terms of mean return times for irred. pos recurrent MC

- Limiting distribution
- definition
- relation to stationary distribution
- computation of limiting distribution using invariance properties

- Time-averages for f(x) bounded, irreducible pos recurrent MC
- understand connection to LLN and Dissection Principle
- compute limits of time averages in terms of the stationary distribution

- Definition, transition probability,
- Poisson Point Processes

- Definition of a Point Process (PP)

- Notion of randomly scattered PP, special case of Poisson Point
Process (PRM)

- Transformation property

- formula for the transformed process (with proof)
- transform inhomogeneous PRM on the real line to a homogeneous
PRM

- Marked and Thinned Poisson processes

- proof that they are PRM (using the conditioning on the number of points)

- formula's for their intensity measures

- Solve simple queueing problems from Resnick/lecture notes
- Laplace functional for PRM
- formula in terms of the control measure (with proof)
- know construction of PRM via iid points conditioned on their number
- on positive line: know order statistics property of points conditioned on their number

- Compound Poisson Process: Laplace functional

- Definition of a Point Process (PP)
- Renewal Processes Nt with interarrival times Xn

- Definition, pure and delayed;

- pgf of Nt
- renewal equations (with derivation) for

- mean function
- distribution of life time
- distribution of residual life time

- state theorem on existence and uniqueness of solutions of renewal equations
- hom. Poisson process on the positive line: know formulas for

- mean function,

- interarrival times (expon)
- distrib. of residual life time (expon)

- renewal version SLLN (with proof using standard SLLN): Nt / t
-> 1/ E[ X1 ]

- State Renewal Theorem
- basic: E[Nt] / t -> 1 / E[ X1 ]
- Blackwell: E[ N(t+b) - Nt ] -> b / E[ X1 ]

- Stationary renewal sequence
- definition in terms of residual life

- equivalent condition: E[Nt] = t / E[ X1 ]
- equivalent condition: form of initial delay distribution

- definition in terms of residual life

- Definition, pure and delayed;
- Continuous-time Markov processes

- Definition
- explain and compute conditional probabilities in discrete and
continuous cases

- explain and compute Chapman-Kolmogorov discrete and continuous cases
- relate Chapman-Kolmogorov to Consistency (existence of contin-time MC)
- Examples (verify Markov property and Chapman-Kolmogorov)

- Poisson renewal process (independent increments)
- Wiener process / Brownian motion via Gaussian transition densities

- Continuous-time Markov Chains

- Definition, holding times
- Ex: Birth-Death process
- Definition, transition proba matrix, holding times
- understand the minimum of two independent exponential r.v.

Any student with a documented disability needing academic adjustments or accommodations is requested to speak with me during the first two weeks of class. All discussions will remain confidential. Students with disabilities should also contact Disabled Student Services in the Ley Student Center.

June 29, 2006