Course Instructor: Arnab Sen
Office: 238 Vincent Hall
Email: arnab@math.umn.edu
Class time and Location: TThu 10:10 -12:05 PM
Vincent Hall 6 (Lec 001), TThu 4:40 -6:35 PM Tate Hall B65 (Lec 002).
Office hours: TuTh 12:10 pm - 1:30 pm (for both Lec 001 & Lec
002) or by appointment. (location Vincent Hall 238)
Textbook:
Essentials of Stochastic Processes, 3rd ed. by Richard Durrett. An e-copy
is available from library.
References: Stochastic Processes, 2nd ed. by Sheldon Ross
Adventures in Stochastic Processes by Sidney Resnick
Introduction to Stochastic Processes by Ehran Cinlar (library has an
e-copy)
Topics: We will mainly cover the first four chapters of the text (i.e., Markov chains, Poisson processes, renewal theory, continuous-time Markov chains). If time permits, we might include other related topics (briefly).
Grading: Homework 20%, 1st Midterm 20%, 2nd Midterm 20%, Final 40%.
Exam Schedule:
Midterm 1: Oct 12 (in class) (tentative)
Midterm 2: Nov 16 (in class) (tentative)
Final Exam: Lec 001 (morning section) 1:30-3:30pm, Saturday, December 16 at Vincent 6,
Lec 002 (evening section) 4:40 - 6:40pm Tuesday, December 19 (Lec 002) at Ford Hall 115 (note classroom change).
There will be no make-up midterms. If you miss a midterm due to a
medical emergency, the grade for a
missed midterm exam will be prorated from the final exam. Missing the
final exam would result an automatic F.
All exams will be closed book and closed class notes. The use of
calculator, smartphone or similar electronic devices are not permitted using the
exams.
For midterm 1 and 2, you are allowed to bring a single sheet of A4
paper (both sides) with notes written by yourself. For Final, you are allowed to bring two sheets of A4 paper
(you can use both sides) with notes written by yourself. The final exam will be cumulative.
Announcements:
(10/5) The midterm 1 covers all materials covered in class till Oct
5. This includes all of chapter 1 of Durrett, except Kolmogorov cycle
condition (Durrett 1.5.3), proof of the convergence theorem (Durrett
1.8) and branching process (part of Durrett 1.11).
(10/10) Extra office hour: 10/11 (Wed) 11:30-12:30pm.
(11/7) The midterm 2 will be based on all materials that have been/
will be covered in class till Nov 9
after midterm 1. The materials include branching processes and
Metropolis-Hasting algorithm (from Markov chain), Poisson Process
(except inhomogeneous Poisson process) and
the part of renewal processes (sec 3.1, 3.3).
(12/12) [On final exam ] The final exam will be closed
book and closed class note. No calculator will be allowed in the
exam. You are allowed to bring two sheets of A4 paper (you
can use both sides) with notes written by yourself. The final exam
will be cumulative. It will be based on the materials of Chapter 1-4
of Durrett except
Kolmogorov's cycle condition (Durrett 1.5.3), proof of the convergence theorem (Durrett
1.8), inhomogeneous Poisson process (Durrett 2.2.2),
Pollaczek-Khintchine formula (Theorem 3.9) and queueing networks
(Durrett 4.6).
(12/12) Arnab's office hour on 12/12 (Tuesday) has been
rescheduled to 3-4pm on the same day.
Homework Assignments: There will be weekly homework assignments. Homework are due on the corresponding deadlines in class. Late homework will not be accepted. The lowest homework score will be dropped. You are encoraged to discuss homework solutions with your friends. However, you have to write your own solutions. To get full credit, be neat and answer with reasons.
| Homework 1 (due Sep 14 (Thur) in class) | Page 78 of Durrett (3rd E): 1.1, 1.2, 1.3, 1.7 and this problem. |
| Homework 2 (due Sep 21 (Thur) in class) | Page 79 of Durrett: 1.8(a), 1.8(d), 1.8(e) (for each of these three problems also draw the transition diagrams) and these problems. |
| Homework 3 (due Sep 28 (Thur) in class) | Page 78-80 of Durrett: 1.6, 1.9(a), 1.13(a)(b) and these problems. |
| Homework 4 (due Oct 5 (Thur) in class) | Page 80, 84, 85 of Durrett: 1.14(a)(b)(d), 1.37, 1.38 and these problems. |
| Homework 5 (due Oct 17 (Tue) in class) | Page 87, 89, 91, 92 of Durrett: 1.47, 1.53, 1.62, 1.67 and this problem. |
| Homework 6 (due Oct 26 (Thur) in class) | Page 88, 94 of Durrett: 1.51, 1.77 and these problem. |
| Homework 7 (due Nov 2 (Thur) in class) | Page 117-118 of Durrett: 2.5, 2.6, 2.15, 2.16, 2.17 |
| Homework 8 (due Nov 9 (Thur) in class) | Page 119-124 of Durrett: 2.20, 2.32, 2.36, 2.43, 2.61 |
| Homework 9 (due Nov 21 (Tue) in class) | Page 142-145 of Durrett: 3.3, 3.5, 3.18, 3.21 and this problem. |
| Homework 10 (due Nov 30 (Thur) in class) | Page 192-193 of Durrett: 4.1, 4.2, 4.7 and these problems. |
| Homework 11 (due Dec 7 (Thur) in class) | Page 193-197 of Durrett : 4.8, 4.11, 4.15, 4.17, 4.26 |
Moodle: You can keep track of your grades in moodle. Also, the course materials such as practice problems for exams or solutions to selected homework problems will be posted in moodle.
Weekly Lecture Schedule:
| Sep 5, Sep 7 | Markov chains - definition and examples. Transition probability. Durrett 1.1, 1.2 |
| Sep 12, Sep 14 | Strong Markov property. Classification of states - recurrence and transience. Durrett 1.3 |
| Sep 19, Sep 21 | recurrence/transience of SRW on Z^d (see notes in moodle), stationary distribution, positive and null recurrence Durrett 1.4, 1.11 (part) |
| Sep 26, Sep 28 | limit theory of Markov chains, doubly stochastic chain, detailed balance condition. Durrett 1.6, 1.7, 1.4.1, 1.5 |
| Oct 3, Oct 5 | reversibility, hitting probabilities and hitting times, Metropolis-Hastings Algorithm. Durrett 1.5.1, 1.9, 1.10, 1.5.2 |
| Oct 10, Oct 12 | review (Oct 10), midterm 1 (Oct 12) |
| Oct 17, Oct 19 | applications of Metropolis-Hastings algorithm: two dimensional Ising model (Durrett example 1.33), knapsack problem (non-examinable), branching process (Durrett example 1.55) |
| Oct 24, Oct 26 | properties of exponential distribution, basic properties of Poisson process: Durrett 2.1 and 2.2 (part). |
| Oct 31, Nov 2 | Properties of Poisson process (contd.), compound Poisson process, thinning, superposition and conditioning of Poisson process : Durrett 2.2, 2.3, 2.4 |
| Nov 7, Nov 9 | renewal processes and its basic properties, renewal reward process, alternating renewal process, residual life and current age : Durrett 3.1, 3.3 |
| Nov 14, Nov 16 | review (Nov 14), midterm 2 (Nov 16) |
| Nov 21 | continuous time Markov chain - definition, construction. Transition probability. Durrett 4.1, 4.2 |
| Nov 28, Nov 30 | Yule process, stationary distribution, Limiting behavior, detailed balance, hitting probabilities and hitting time, Durrett 4.2, 4.3, 4.4 |
| Dec 5, Dec 7 | Queueing theory: different types of queues, Markovian queues, Little's law, PASTA principle, Durrett 3.2, 4.5 |
| Dec 12 | Review problems |