Course home page (this page): http://pi.math.cornell.edu/~levine/4740
For many years this course was taught by longtime Cornellian Rick Durrett (now at Duke Univeristy) who also wrote our textbook. This year's course is modeled on the one taught last year by Nate Eldredge.
New: practice problems for the final
The final is on Thursday May 16 from 9-11:30 in Malott 406.
New: Office hours during exam period:
Section numbers on the right refer to the (online only) 2nd edition of Durrett.
date | due | topic | reference |
Jan 21 | Random walk, central limit theorem. Why randomness? | (Durrett 2nd ed.) | |
Jan 23 | Markov property. Multi-step transition probabilities. Examples | 1.1-1.2 | |
Jan 25 | Recurrence and transience | 1.3, worksheet 1 | |
Jan 28 | Strong Markov property. Expected number of visits E_x N(y) | 1.3 | |
Jan 30 | Closed and irreducible sets. Criteria for recurrence | 1.3 | |
Feb 1 | pset 1 | Coin flipping example. Intro to stationary distribution. | 1.4, worksheet 2 |
Feb 4 | Stationary distribution: 2x2 case, and what can go wrong with convergence | 1.4, Sage | |
Feb 6 | Doubly stochastic chains. Detailed balance, random walk on a graph | 1.6 | |
Feb 8 | pset 2 | Existence of stationary distribution; expected return time | 1.5, worksheet 3 |
Feb 11 | Irreducibility, uniqueness of stationary distribution | 1.5 | |
Feb 13 | Aperiodicity, convergence to equilibrium | 1.5 | |
Feb 15 | pset 3 | English language as a Markov chain | worksheet 4 |
Feb 18 | Proof of the convergence theorem | 1.7 | |
Feb 20 | Ergodic theorem. Exit distributions | 1.7(Thm 1.23), 1.8 | |
Feb 22 | pset 4 | Exit times | 1.9, worksheet 5 |
Feb 25 | Infinite state space | 1.10 | |
Feb 27 | Branching processes | 1.10(Ex 1.52) | |
Mar 1 | ***Prelim*** covering finite Markov chains (all topics through Feb 22) | 1.1-1.9 | |
Mar 4 | Pagerank | papers | |
Mar 6 | Markov chain Monte Carlo (MCMC) | MCMT chapter 3 | |
Mar 8 | pset 5 | Exponential distribution, lack of memory | 2.1 |
Mar 11 | Poisson distribution, Poisson process | 2.2 | |
Mar 13 | Poisson approximation to the binomial | 2.2 | |
Mar 15 | pset 6 | Compound Poisson processes | 2.3, worksheet 6 |
Mar 18-22 | ***spring break*** | ||
Mar 25 | Sums with a random number of terms | 2.3 | |
Mar 27 | Thinning and conditioning | 2.4 | |
Mar 29 | pset 7 | Higher dimensional Poisson processes | references |
Apr 1 | Point processes. Intro to continuous time Markov chains | 4.1 | |
Apr 3 | Yule process. Constructing a chain from its jump rates | 4.1 | |
Apr 5 | pset 8 | Kolmogorov differential equation | 4.2, worksheet 7 |
Apr 8 | Stationary distribution solves pi Q = 0 | 4.3 | |
Apr 10 | Detailed balance, continuous time random walk | 4.3, worksheet 8 | |
Apr 12 | project | Convergence theorem. Hitting and exit distributions | 4.4 |
Apr 15 | Conditional expectation | 5.1 | |
Apr 17 | Martingales | 5.2 | |
Apr 19 | pset 9 | You can't beat an unfavorable game | 5.3 |
Apr 22 | Optional stopping | 5.3,worksheet 9 | |
Apr 24 | Applications of optional stopping. Uncorrelated increments | 5.4,worksheet 10 | |
Apr 26 | project | Martingale convergence theorem | 5.5 |
Apr 29 | Martingales in prediction markets | paper | |
May 1 | Brownian motion: definition, construction, reflection principle | 1st ed. 6.1-6.3 | |
May 3 | pset 10 | Brownian motion: distribution of the maximum, dimension of the zero set | BM book |
Prerequisite: An introductory probability course such as MATH 4710, BTRY 4080, ORIE 3600, ECON 3190. General proficiency in calculus and linear algebra. If unsure about your preparation, please discuss it with me.
Essentials of Stochastic Processes, by Durrett.
The first edition, made out of dead trees, is available at the Cornell store, and a copy is on reserve at the Mathematics Library (4th floor Malott Hall).
Here is a list of known typos in the first edition.
And here is the second edition, made out of electrons. We are compiling a list of typos in the 2nd edition.
If Durrett crimps your style, take a look at these books which cover roughly the same material:
For the extra topics, we may dip into a couple more advanced books:
Problem Set 1, due Friday, February 1.
Problem Set 2, due Friday, February 8. Solutions
Problem Set 3, due Friday, February 15. Solutions
Problem Set 4, due Friday, February 22. Solutions
Problem Set 5, due Friday, March 8. Solutions
Problem Set 6, due Friday, March 15. Solutions
Problem Set 7, due Friday, March 29. Solutions
Problem Set 8, due Friday, April 5. Solutions
Problem Set 9, due Friday, April 19. Solutions
Problem Set 10, due Friday, May 3. Solutions
Please check out the problem set guidelines for how to write a good solution.
You are strongly encouraged to type your problem sets using LaTeX (or LyX). LaTeX is very versatile and widely used for writing technical documents of all kinds. It will serve you well if you go on in math or another technical field. Besides, you will need it for your project! Neatly handwritten problem sets are also acceptable.
New: Here is a sample LaTeX file and the pdf output it generates.
Here is a video tutorial to get you started with LaTeX. Another good resource is the LaTeX wikibook. The Cornell math support center can help you get LaTeX up and running. (Ask for a math major tutor!)
Two times during the semester, you may have an automatic 72-hour extension on a problem set. This does not require prior approval, just hand it in at the beginning of the next class with a note saying you are using an extension. Otherwise, late homework will not be accepted except in an emergency (in which case you must inform me as soon as possible).
Group work policy: Working together with other students to solve the problems is encouraged. However, you must understand the solution yourself and write it up entirely in your own words. Discussing your solution with others is fine, but do not share your written solution with another student. If you work in a group, list the group members at the top of your problem set.
One in-class prelim on Friday, March 1. Final exam on Thursday, May 16. The exams are closed book.
If a conflict prevents you from completing the exams on these dates, please let me know immediately.
Practice problems for the prelim.
Solutions to the prelim. The mean was 42 out of 60 and the standard deviation was 9. Approximate grade ranges: A (47-57), B (31-46), C (22-30).
The course project allows you to explore a topic of your choice in depth. You will choose a peer-reviewed journal article that uses stochastic processes to model some real world phenomenon, and write a critical summary of the article analyzing the strengths and weaknesses of the model it proposes.
Check out the project guidelines for details.
Graduate students: If you are taking the course for credit, you will need to complete all the regular coursework (homework, exams and project), and will be assigned a grade like any other student. If you are taking the course S/U, you still need to do the coursework; I will compute a letter grade as usual and then assign you an S if the letter grade is at least C-. If you are not interested in doing the coursework, you are welcome to audit the course instead.
The Cornell disability policy is as follows. If you have a disability‐related need for reasonable academic adjustments in this course, provide me with an accommodation letter from Student Disability Services. Students are expected to give two weeks notice of the need for accommodations. If you need immediate accommodations, please arrange to meet with me within the first two class meetings.
Please read carefully the group work policy for problem sets. I, your classmates, and the entire Cornell community expect you to complete this course based on your own work, to abide by relevant rules for coursework and exams, and to clearly attribute any use of the work of others. The Cornell Academic Integrity Policy spells out the nasty details of what happens otherwise.