Math/Stat 632 Introduction to Stochastic Processes
Spring 2018, Lecture 1
Meeting time: Monday, Wednesday, Friday 12:05 PM - 12:55PM
Meeting place: Van Vleck B239.
Instructor: David Anderson
Office: 617 Van Vleck
Instructor E-mail: firstname.lastname@example.org
This is the course homepage that also serves as the syllabus for the course. Here you will find our weekly schedule, and updates on scheduling matters. The Mathematics Department also has a general information page on this course.
Number of credits: 3. This course meets for 3 hours per week, and there is an expectation that students will work an additional 6 hours per week outside of class.
There are three different options for office hours. They are each drop-in, so no appointment is needed. Note that you have lots of options on Wednesdays. This is because your HW is due Friday.
Math 632 provides an introduction to stochastic processes, which describe the time evolution of a system in a random setting. We will work with basic stochastic processes and applications with an emphasis on problem solving. Topics will include discrete-time Markov chains, Poisson point processes, continuous-time Markov chains, and renewal processes.
A typical advanced math course follows a strict theorem-proof format. 632 is not of this type. Mathematical theory is discussed in a precise fashion but only some results can be rigorously proved in class. This is a consequence of time limitations and the desire to leave measure theory outside the scope of this course. Interested students can find the proofs in the textbook. For a thoroughly rigorous probability course students should sign up for the graduate probability sequence 733-734.
To go beyond Math 632 in probability you should consider taking Math 635 - Introduction to Brownian Motion and Stochastic Calculus.
Students will be able to model simple real life situations by means of discrete-space stochastic processes. Specifically they will study discrete-time Markov chains, continuous-time Markov chains, Poisson processes, branching processes, renewal processes, and models from queueing theory.
Students will be able to apply the theory associated with the previously mentioned processes. They will be able to apply definitions and derive certain important properties of the processes.
Students will be able to calculate the probabilities associated with different important events related to the processes. Moreover, they will be able to check for the existence of limiting/stationary distributions for the processes, and will learn how to interpret and use them in the real life situations being modeled.
Where are stochastic processes used?
Stochastic processes are a mathematical tool to model the time evolution of systems with random features. Hence, they are used ubiquitously throughout the sciences and industry. For example, in biology many cellular phenomena are now modeled as stochastic processes rather than as deterministic solutions of ODEs. As for industry, many models of interaction with customers or machine maintenance are probabilistic in nature, as we cannot determine customer choices or the time when a machine breaks deterministically. In informatics, a solid understanding of stochastic processes is extremely useful in designing computer algorithms that for example learn to play chess, or perform speech recognition.
The material is treated at a level that does not require measure theory. Consequently technical prerequisites needed for this course are not too heavy: calculus, linear algebra, and an introduction to probability (at the level of Math 431) are sufficient. However, the material is sophisticated, so a degree of intellectual maturity and a willingness to work hard are required. For this reason some 500-level work in mathematics is recommended for background, preferably in analysis (521).
Good knowledge of undergraduate probability at the level of UW-Madison Math 431 (or an equivalent course) is required. This means familiarity with basic probability models, random variables and their probability mass functions and distributions, expectations, joint distributions, independence, conditional probabilities, the law of large numbers and the central limit theorem. If you need a thorough review of basic probability, the textbook Introduction to Probability (on reserve in math library) by Anderson, Sepplinen, and Valko is recommended.
There will be two primary readings the course. First, I will provide you with lecture notes that contain almost everything that is covered in class. Second, the lecture notes are based on (and sometimes reference) the following book: Durrett: Essentials of Stochastic Processes, Springer, 2nd edition. This text is FREE and is available on Prof. Durrett’s website. Note that you do not need to purchase a book. However you need to download the pdf file, since you will be assigned exercises from it. Other textbooks which could be used for supplemental reading:
We will use the Canvas website of the course to post homework assignments and solutions. The lecture notes will also be posted there.
We will be using Piazza for class discussion. The system is catered to getting you help fast and efficiently from classmates and myself. Rather than emailing math questions to me, I encourage you to post your questions on Piazza. If you have any problems or feedback for the developers, email email@example.com.
Please note that students from the other section of Math 632 (taught by Prof. Cappelletti) will also be using the same Piazza page. Hence, make sure to mention which section you are in if the comment is specific to it.
Find our class Piazza page here.
Course grades will be based on homework (15%), two midterm exams (2x25%), and a comprehensive final exam (35%). Your lowest homework grade will be dropped.
No calculators, cell phones, or other gadgets will be permitted in exams, only pencils, pens and paper.
The final grades will be determined according to the following scale:
A: [100,90], AB: (90,86], B: (86,77], BC: (77,73], C: (73,64], D: (64,50], F: [50,0].
There will be no curving in the class, but the instructor reserves the right to modify the final grade lines.
How to succeed in this course
The midterm and final exams will contain problems which will be similar to the homework problems in difficulty. The best way to prepare for these is to do as many practice problems from the book as you can. This will also help you understand the theory a lot better! If you have trouble solving the homework (or practice) problems then come see me in my office hours (or set up an appointment).
Homework assignments will be posted here and on the Canvas website of the course. Weekly homework assignments are due on Fridays at 4pm. The first assignment is due Friday, February 2nd. The lowest homework grade will be dropped.
Instructions for homework
We will use the software Gradescope, which is already being succesfully tested in other courses here at UW-Madison. The advantages for you are the following:
Here is a guide on how you have to submit your homework. You can also watch the video “For students: submitting homework” here.
Here is a tentative weekly schedule, to be adjusted as we go. The numbers refer to sections in the textbook by Durrett.
|1||Review of basic concepts of probability,|
|1/23-1/26||Discrete Markov chains: definitions and examples, the transition probability matrix, multistep probabilities|
|2||Classification of states, strong Markov property, transience and recurrence, closed and irreducible sets.|
|1/29 - 2/2||Section 1.3|
|3||Monday and Wednesday will continue section 1.3. Friday will begin Stationary distributions.|
|2/5-2/9||Sections 1.3 and 1.4|
|4||More on stationary distributions. Periodicity, limit behavior.|
|2/12-2/16||Sections 1.4, 1.5|
|5||Stationary distributions, positive recurrence, asymptotic frequencies (M and W). Exit times and exit distributions (F).|
|2/19-2/23||Sections 1.5 (M/W), 1.8 (F), 1.9 (F), 1.10 (M/W)|
|6||Monday – Finish exit distributions, including the general solution to the gambler’s ruin problem,|
|Monday/Wednesday – Detailed balance condition and birth and death chains with infinite state space|
|Friday – begin branching processes.|
|2/26-3/2||Sections 1.9, 1.10|
|7||Branching processes, Gerrymandering, and the Metropolis-Hastings algorithm.|
|3/5-3/9||First midterm exam|
|8||Exponential distribution, Poisson process, Compound Poisson process, transformations of Poisson processes.|
|9||(M/W) Poisson processes. Renewal processes - LLN.|
|3/19-3/23||Sections 2.4, 3.1|
– Spring Break –
|Continuous time Markov chains, Markov property in continuous time, the embedded discrete time MC, infinitesimal rates.|
|4/2-4/6||Sections 3.1 and 4.1|
|11||Examples, the Poisson clock construction, Kolmogorov’s backward and forward equations.|
|12||Solving the Kolmogorov equations, stationary distribution, limiting behavior.|
|13||Stationary distribution, detailed balance.|
|4/23-4/27||Second midterm exam|
|14||Birth and death processes, exit times, Queueing Theory.|