654-Spring-2024

Stochastic Processes, Spring 2024

Instructor: Pierre C. Bellec
pcb71@stat.rutgers.edu

TA: Takuya Koriyama tk691@stat.rutgers.edu

Classroom: Hill Center 552:

• Stochastic Processes, Spring 2024
• Exam dates
• Zoom link for some lectures
• Office hours
• Grading:
• Book(s)
  • Prerequisites on Probability Theory
• Tentative syllabus, subject to change
• Handwritten notes from class, notebooks and zoom recordings
  • Notability links:
  • Notebooks used during lectures
  • Zoom recordings and lecture summaries after
  • Tentative lecture summaries with approximate dates from last year
• Some pictures from previous years
• Some previous exams

Exam dates

• First midterm: Monday Feb 26 (class time)
• Second midterm: Monday April 1 (class time)
• Final: Early may (TBD)

Zoom link for some lectures

https://rutgers.zoom.us/j/96103220554?pwd=bzNSN0dKZkNMZ1lWclAyTXIrQ1RjZz09

Caution! The zoom link used for lectures is not the same as the one used for office hours.

Office hours

With instructor: Tuesdays 9.20-11am using the link https://rutgers.zoom.us/j/92284023210?pwd=RzhuK09NNmloeHc2a3EyTFpaNWRoQT09

With TA: Mondays 1pm-3pm, Takuya Koriyama (tk691@stat.rutgers.edu). The first few office hours (prior to Feb 6) will be zoom-only and will be in-person afterwards (after Feb 6). Takuya will send an announcement with a Zoom link.

Grading:

• Final: 40 percent
• Best Midterm: 25
• Worst Midterm: 15
• Homework and other take-home assignments: 20 (not all homework will be graded, but solutions will be provided for each)

Book(s)

1. For Markov chains, mixing times and martingales: the book by DA Levin, Y Peres, and EL Wilmer. It is available at http://pages.uoregon.edu/dlevin/MARKOV/mcmt2e.pdf. Make sure to download the PDF from this URL, as this URL contains an updated book with some typos/errors fixed.

2. For Poisson processes and renewal theory: TBA

Prerequisites on Probability Theory

For prerequisites on probability, you may also look at Appendix 1 in DA Levin, Y Peres, and EL Wilmer. You may look at Chapter 1 in Ross.

Tentative syllabus, subject to change

• From the DA Levin, Y Peres, and EL Wilmer book: Chapters 1, 2, 3, 4, 5.
• Poisson Processes and renewal theory: latex lecture notes will be provided

Handwritten notes from class, notebooks and zoom recordings

Notability links:

• Chapter 1: https://notability.com/n/1wLAs0KqG6ifUt~vB6oXs6
• Chapter 2: https://notability.com/n/0ChKeGqrh8gcOrH9Oq4xpu
• Chapter 3: https://notability.com/n/0mSBHC3pS3Qf~YRVyH3kbV
• Chapter 4: https://notability.com/n/2w0_PXaw_3VeudM9FRtBis
• Chapter 5: https://notability.com/n/VhC40K5tDnAbrADvLJNUY
• Chapter 12 and reversible chains: https://notability.com/n/2dT4gzloO5zN8Ci8ia6QI5
• Poisson Point Processes: https://notability.com/n/2Mh4ZE_pC46vHl5przI7Kg - see also the lecture notes in a canvas announcement

Notebooks used during lectures

• Metropolis chain for Poisson target distribution and a mixture of 3 Poisson distributions html - notebook ipynb - python
• Glauber dynamics on 4-colorings html - notebook ipynb - python
• Metropolis on 4-colorings on 4-colorings html - notebook ipynb python
• Optimal coupling, independent coupling, reflection coupling (with illustrations!) html with page breaks - notebook ipynb - python
• Lazy random walk on the hypercube and coupons collecting html - notebook ipynb - python
• Lazy random walk on the cycle and Gambler’s ruin html - notebook ipynb - python

Zoom recordings and lecture summaries after

• Wed Jan 17: Section 1.1, 1.2 https://rutgers.zoom.us/rec/share/RfdL_ntks61Sa3glHY5tRRGHoNNBGWB-5dANjBLgzwWhE72gU-fWJDSYZDKWRjkF.lWcg79Uto3MfwdG- Password: Q3E9A#qh
• Mon Jan 22: Sections 1.2, 1.3, proof of Lemma 1.6 https://rutgers.zoom.us/rec/share/OAaBczaWWyeAPxutIRrJ814OQQQDQ2woGMQ1-VfN6R3hnm1s0NrBEgbDbYnwaq87.r4upiCEs797Devea password wJ+myJ7*
• Wed Jan 24: Proof of Proposition 1.7 Section 1.4 and Example 1.12 (no zoom recording)
• Mon Jan 29: Section 1.7, proof of Lemma 1.13, proof of uniqueness of stationary distributions (sec 1.5.4). https://rutgers.zoom.us/rec/share/JjxchJPGUzAtPwMMc6BBBv7A-5ZOy84hqck7rqS1ciOFKOceqUybcOOm7qq51gHm.2b_JmeBsND7nwJUy Password: DZ4@ja.2
• See https://mathoverflow.net/a/451868/141760 for a proof of uniqueness of the stationary distribution that extends to countable state spaces
• Wed Jan 31: Existence of stationary distributions (Proposition 1.14). Reversible Markov Chains in section 1.6 of the book and the proofs of that section. Discussion section 1.7 without proofs.

https://rutgers.zoom.us/rec/share/wynRv-lFJ0TEOJ15Ng8VKRYjqkjLxfqzmcJPUpbBUkd0zF8VZdixQyWcHgoW6ibF.gEwnxPgP-7pds44b Password: d&+?HG9X

• Mon Feb 5: Another proof of existence of stationary distributions (Proposition 1.32). We will start Chapter 2 and study the chains in section 2.1 (Gambler’s ruin). Section 2.2: Expectation of geometric distributions, and expected time to collect all n coupons in the coupon collecting problem.
• Wed Feb 7: Chapter 2, 2.3: The Hypercube and the Ehrenfest Urn Model. 2.3.1: Projection of chains (without proof).
• Mon Feb 12: Chapter 3: Metropolis chain with symmetric and non-symmetric base chain, example with the simple random walk on on graph. Metropolis algorithm on hardcore configurations and proper 3-colorings. Glauber dynamics to construct as Markov Chain with given stationary distribution on functions defined on vertices of a graph, by updating only one component at a time. https://rutgers.zoom.us/rec/share/zbPJst53AZBTvkvJ6vrTGIcx_KV3oQtiKjcBGeGrilvqD2yBR2nd7M-PWAYZH2iC.1fzgtRL1Nkvc1rvB Password: 5nRoPy7*
• Wed Feb 14: Python notebooks on the metropolis algorithm (simple discrete pmg in 1-dimension), Metropolis and Glauber dynamics chains on proper 4-colorings (see above for notebook links). A conditional probability interpretation of the sampling in Glauber dynamics

https://rutgers.zoom.us/rec/share/Ut_1O0q7NxZRPTnRxRHUcP01eyOG-ZqA_Jw5fMEVMFssPbxGPXsRd8jN057CQ-fP.OiUue-bzp3YfCA6I Password: V1+C4p?e

• Mon Feb 19: Section 4.1: TV distance, characterizations. Couplings are relationship with TV distance (section 4.2). Zoom: https://rutgers.zoom.us/rec/share/ad0RpA0ZLD7hw8yL-hT6QY34m8ouYzG1tRI4FVA5_FXFSJGNCLIY6Z3fSLzJDBwe.nbgWY0V29iJ-iywN Password: &6xyS?XB
• Wed Feb 21: Construction of an optimal coupling for the TV distance. Section 4.4: distances d(t) and bar-d(t). By a coupling argument, the TV distance between μP and νP is always smaller than the TV distance between μ and ν. Zoom: https://rutgers.zoom.us/rec/share/kNbesYI23t-BDLDXcRYE2D_GIaZG4JdJ9fVZM0TV1duouMbl7Ka31zBqX1BhQz8o.ac_gxlTmt4buQChl Password: XLR3L$?*
• Mon Feb 26: first midterm exam
• Wed Feb 28: submultiplicativity of the distance bar-d, and why it implies the convergence theorem. Proof of Lemma 4.11.
• Mon March 4: Chapter 5: Couplings of Markov Chains, Markovian couplings, Theorem 5.4 and Corollary 5.5. Section 5.3.1: lazy random walk on the hypercube.
  Zoom: https://rutgers.zoom.us/rec/share/xhqDI4Xx050GCackcJc2TcMpCFoEmLmsL-hs6FlQAGAhU9PNI_9chZPelzT9zfEg.EKuJrt708wAmmKVK Password: Cn*.U6DN
• Wed March 6: Chapter 5: Faithfullness condition necessary to modify a coupling of Markov Chains so that they stay together after the first time they meet. Zoom: https://rutgers.zoom.us/rec/share/vmmlzVFqzbpAqulYTC5SasyEcweJgDGf6boo6DLjtfHB_RnbBIafEefsy8KHab-q.jwPwoNNsN5bGGBXa Password: b#raW49S
• Mon Marc 18: upper and lower bounds for the mixing time on the n-cycle.
  Zoom: https://rutgers.zoom.us/rec/share/BRg5yrcSrY7mkd_n35xLNq018vqJpRlMAUjdQ-iHzwAry468mPfP4Z89a_YoH8MK.Ykuqjb6b5M2fpZJv Password: WTh5%6f+
• Wed March 20: Coupling to bound the TV distance between the lazy chain at time t and at time t+1.
• Mon March 25: path coupling and bound in the mixing time of the Metropolis chain on proper q-colorings (Section 5.3)
  Zoom: <7HkPUITZTuo3M_Ps5pvqMufpYlmorqS_R2KWfKQemV8T89w2v9mQwXTNgSsyakLO.E8Z6pe35nVQupIO1> Password: Dm&@e4!c
• Wed March 27: convergence theorem using eigenvalue decomposition for aperiodic reversible Markov Chains: Spectral theorem for symmetric matrices, the symmetric matrix A associated with a transition matrix P, eigenvalues in [-1,1], aperiodicity and the -1 eigenvalue.
  Zoom: https://rutgers.zoom.us/rec/share/8pBaA_sF_YUqUrU_07oQBFqD2DqSVDgcpc45-7zNV9cDOrkR2gobuLMjR8l0XSo0.yKzVGxhYGFdDOFfO Password: 0XFSt@Gq
• Mon April 1: exam
• Wed April 3: exam comments and solutoins
• Mon April 8: the Ergodic Theorem
• Wed April 10: Poisson Processes, first lecture: properties of Poisson random variables, sum of independent Poisson random variables, countable sum of Poisson random variables and the Borel-Cantelli lemma, thinning a Poisson random variable.
• Mon April 15: Properties of exponential and Gamma random variables. Exponential races: independence of the argmin and the min.
  Zoom: https://rutgers.zoom.us/rec/share/ebHSCPmzxlTX66p57wPfIeEkbBM7aef-jMRTnc8upz2n_ZgZAj0KDPC10g4tAn24.-sI-bQ4Ehc5BDbIY Password: #M9KpcBZ

Tentative lecture summaries with approximate dates from last year

• Jan 18: Section 1.1, 1.2
• Jan 23: Sections 1.2, 1.3, proof of Lemma 1.6
• Jan 25: Proof of Proposition 1.7 Section 1.4 and Example 1.12, section 1.5
• Jan 30: We will finish the proof of Lemma 1.13, prove existence of stationary distributions (Prop 1.14) and study uniqueness of stationary distributions (section 1.5.4)
• Feb 1: We will go through reversible Markov Chains in section 1.6 of the book and the proofs of that section. I will also discuss section 1.7, but we will not do the proofs there.
• Feb 6: we will start Chapter 2 and study the chains in section 2.1 (Gambler’s ruin).
• Feb 8: 2.2 coupon collecting, and 2.3 random walk on the hypercube
• Feb 13: Erhenfest urn model (2.3) and Metropolis chains with symmetric base chain (Section 3.2.1).
  Metropolis chain notebook for Poisson and mixture of Poisson: https://bellecp.github.io/teaching/2023-Spring-654/metropolis.html
• Feb 15: Metropolis chains with non-symmetric base chain, Example 3.3 (transforming a random walk on a graph to obtain a chain that has uniform stationary distribution on the vertices), Section 3.3 Glauber Dynamics.
• Feb 20: We will explore proper colorings with some programming experiments. I will start with the notebook https://bellecp.github.io/teaching/2023-Spring-654/proper_colorings.html to explain how Markov chains with the uniform distribution on proper 4-colorings as stationary distributions can be used to approximately count the number of all such proper 4-colorings. Time permitting, we will move on to Chapter 4 and sections 4.1 and 4.2 (total variation distance).
• Feb 22: Section 4.1 (TV distance) and 4.2 on the relationship between couplings and TV distance.
• Feb 27: We will discuss the notebook html with some coupling illustrations, and discuss the convergence theorem in Section 4.3 (time permitting, we will provide a proof).
• March 1: Midterm
• March 6: The convergence theorem (section 4.3), standardizing distance from stationary (section 4.4) and mixing time (section 4.5). We will deduce the convergence theorem by proving the submultiplicativity property in Lemma 4.11.
• March 20: Chapter 5: Couplings of Markov Chains, Markovian couplings, Theorem 5.4 and Corollary 5.5. Section 5.3.1: lazy random walk on the hypercube.
• March 22: 5.3.1 random walk on the hypercube, 5.3.2 random walk on the cycle, 5.4.1 random colorings.
• March 27: 5.4: grand coupling on colorings
• March 29: Chapter 12, convergence theorem for reversible Markov Chains using the spectral theorem for symmetric matrices
• April 3: Poisson and exponential random variables, introduction to Poisson point processes
• April 17: Point processes
• April 19: Poisson Point Processes (definition, homogeneous process, sum of independent PPP, a PPP is simple)
• April 24: Construction of 1d homogeneous Poisson Point Process
• April 26:
• May 1: Some problems on Poisson Point Processes

Some pictures from previous years

https://bellecp.github.io/teaching/2019-Spring-Stochastic-Processes/#some-pictures

Some previous exams

• midterm: https://github.com/bellecp/CC-BY-SA-teaching-material/raw/master/stochastic_processes/midterm-sample-exam-1.pdf
• midterm: https://github.com/bellecp/CC-BY-SA-teaching-material/raw/master/stochastic_processes/midterm-sample-exam-2.pdf
• final: https://bellecp.github.io/teaching/2023-Spring-654/final.pdf