Introduction to stochastic processes
program LNMB and MasterMath , Fall 2011
[Announcements] [General
information] [Course outline] [Archive] [Some further reading]
22.12.2011 The grades of the
resit on Friday December 2 are known, and can be found here. If you have any questions or
comments, please let us know.
28.11.2011 The location of the
resit on Friday December 2, 13.45-16.45, here at the University of
Twente is: room CR 1A in the Carré building. A route description and a campus map can
be found on http://www.utwente.nl/en/contact
(under ‘related links’).
04.11.2011 There will be a Resit
(second exam possibility) for this course on Friday December 2, 13.45-16.45,
at the University of Twente. Precise location will follow, but take
into account the travel time to Twente (approx. two hours from Utrecht CS).
11.10.2011 As soon as the exam is
graded (probably this week) you may find the grades
here. In case of questions please contact Nelly Litvak, as Werner
Scheinhardt will be absent until October 24.
23.09.2011 Please be on time
for the exam on Monday in room BBL 201, and please bring your (ordinary)
scientific calculator (no graphic calculator allowed)
12.09.2011 Course outline below has been
updated till September 13.
05.09.2011 Course outline below has been
updated till September 6.
01.09.2011 Dear students, welcome to the course Introduction to
Stochastic Processes!
Back to the top
Meetings: Two lectures each day, always from
10.15-12.00 and 13.00-14.45, on
September 5, 6, 12 and 13.
Location: Always in Buys Ballot Lab, University of Utrecht, but room
varies:
Monday
September 5: Buys Ballot Lab 061
Tuesday
September 6: Buys Ballot Lab 065
Monday September
12: Buys Ballot Lab 061
Tuesday
September 13: Buys Ballot Lab 023
Instructors: Nelly Litvak and Werner Scheinhardt
Course description at MasterMath
Examination: Written exam. September
26th 2011 from 13:00-16:00 h., in the Buys Ballot Lab., room 201 in Utrecht.
Text: Introduction to Probability Models Academic Press, 10th
ed., 2010 Sheldon M. Ross (9th edition can also be used; brackets [..] below
indicate 9th edition)
Back to the top
Course outline (brackets [..] below indicate 9th edition)
|
September
5, a.m.
Topics:
Material:
Exercises:
|
Markov Chains: definition, Chapman-Kolmogorov equations, classification of
states,
Sections 4.1 - 4.3, except example 4.19 [4.16]. sheets
Ross chapter 4: exercises 1,2,3,10,14,15
|
|
September
5, p.m.
Topics:
Material:
Exercises:
|
Markov Chains: limiting probabilities, applications, time spent in transient
states,
Sections 4.4, 4.5.1, 4.5.2 (to study by yourself), 4.6 except examples
4.23, 4.26 [4.20, 4.22] sheets
Ross chapter 4: exercises 20,25,29,30,57,63 (solutions for chapter 4) problems 10 and 13 from the list (solutions)
|
|
September
6, a.m.
Topics:
Material:
Exercises:
|
Generating Functions and Laplace-Stieltjes Transforms; branching processes;
exponential distribution
Some pages from Cooper on PGFs and LSTs; Ross sections 4.7 and 5.2. sheets
Cooper, exercise 4 (page 30), exercises 4,5 (page 199); Ross, chapter
4: exercises 64, 66; chapter 5: exercises 3,14,18
link to the book by Cooper: http://www.cse.fau.edu/%7Ebob/publications/IntroToQueueingTheory_Cooper.pdf
|
|
September
6, p.m.
Topics:
Material:
Exercises:
|
Poisson
process.
Section 5.3 until example 5.19, but without examples 5.9 and 5.17. Sheets are
here, here and here
Ross
chapter 5: exercises 35, 37, 38, 40, 41, 42, 43, 60, 61, 63 (Solutions
September 6, classes 3-4)
|
|
September
12, a.m.
Topics:
Material:
Exercises:
|
Continuous time Markov Chains: introduction, birth/death process, transition
probabilities
Sections 6.1 - 6.4 until example 6.8.
Ross chapter 6: 1,3, 6ab, 9, 10 (but don't verify forward and backward eqns),
20ab (solutions)
|
|
September
12, p.m.
Topics:
Material:
Exercises:
|
CTMC: Kolmogorov's equations, limiting distribution, uniformization (Sheets
September 12, classes 5-6)
Sections 6.4 (rest), 6.5, 6.7
Ross chapter 6: exercises 12, 13, 15, 17, 18, 20c, 21, 22, 23 (solutions)
|
|
September
13, a.m.
Topics:
Material:
Exercises:
|
Renewal theory: renewal process and limit theorems
Section 7.1, 7.2, 7.3. sheets with some typos.
Ross chapter 7: exercises 2,4,5,10,11,12,15,19
|
|
September
13, p.m.
Topics:
Material:
Exercises:
|
Renewal reward process, regeneration process
Sections 7.4,7.5. sheets with some typos.
Ross, chapter 7: exercises 21,22,26,32,37,41,44,45,51 (solutions
for chapter 7)
|
Back to the top
Exam 2006 (Solutions)
Exam 2005 (Solutions)
Back to the top
Books
- Sheldon M. Ross. Introduction to
probability models. Academic Press, New
York, 2003
The course is based on this book. The book also contains most of the
homework problems.
- Rick Durrett. Essentials of stochastic
processes. Springer 1999
Elegant rigorous treatment of most of the topics
- James R. Norris. Markov Chains. Cambridge University Press, 1997.
Classical reference on Markov chains
- David Aldous and James A. Fill. Reversible
Markov Chains and Random Walks on Graphs. Available here .
Advanced book on Markov chains. Highly recommended, in particular, if
you've got a feeling that this all is too easy!
- Sheldon M. Ross. Stochastic processes.
Wiley, New York,
1996..
Very good book on stochastic processes, covering most of the material,
slightly more advanced than `Introduction to Probability Models'
- William J. Stewart (1994) An
Introduction to the Numerical Solution of Markov Chains. Princeton
University Press
The classical reference if you need to find a stationary distribution
of a large Markov Chain by using numerical methods
Articles
- Gely P. Basharin, Amy N. Langville, and
Valeriy A. Naumov (2004) The Life and Work of A. A. Markov. Linear Algebra
and its Applications. Vol. 386:3-26 pdf
Very well written biography of A.A. Markov including some results from
his work on chains. Enjoyable and useful reading!
- Sergey Brin and Lawrence Page (1998) The
anatomy of a large-scale hypertextual web search engine. In The Seventh
International World Wide Web Conference WWW1998 pdf
In this paper Google is presented for the first time to the Computer
Science community. The PageRank concept is introduced as well. The paper
has got 1689 citations!
- Amy N. Langville and Carl D. Meyer (2005)
Deeper Inside PageRank. Internet Mathematics Vol. 1(3):335-380 pdf
A solid and well written survey on PageRank. Also useful if you want to
know more about the linear algebra framework and numerical methods for
Markov chains
Back to the top