Topics in Applied Stochastic Processes
Basic Information
Instructor
:
Siva Athreya
.
Email
: athreya@isibang.ac.in
Classes Post February 15th 2021
: Tuesday 08:55am-10:30am and Friday 11:55-1:30pm
January 25th-February 12th Classes:
Monday and Thursday : 5:30pm--7:00pm
The classes will be held jointly with
Topics: Random Walks on Graphs
Course Syllabus:
PART I (From): Our initial goal will be to cover the following specific topics:
Graphs and weighted graphs (Examples and Geometric Properties)
Random walks
Transition densities and the Laplacian
Dirichlet or Energy form
Green functions, Harmonic functions, Harnack inequalities
PART II (From):-
Discrete parameter martingales
Markov models for epidemics
Pre-requisite:
Topics in Random Walk on Graphs will be:
Measure Theoretic Probability.
Topics in Applied Stochastic process will be:
Probabilty III.
References
Random Walk of Graphs
M.T. Barlow's Lecture Notes (Lectures given at RIMS, 2005)
T. Kumagai's notes (St.Flour summer school 2010)
Random Walks by Luca Avena, Markus Heydenreich, Frank den Hollander, Evgeny Verbitskiy, Willem van Zuijlen
Markov Chains
Markov Chains
by James Norris.
Reversible Markov Chains and Random Walks on Graphs
by David Aldous and Jim Fill.
Markov Chains and Mixing Times
by David A. Levin, Yuval Peres, and Elizabeth L. Wilmer.
Basic Probability
Probability and Statistics with Examples using R
Discrete Parameter Martingales and Markov Models for Epidemics
Probability: Theory and Examples
by Rick Durrett.
Discrete Stochastic Processes (Draft of 2nd Edition)
by Robert Gallager.
Markov Chains (Cambridge Series in Statistical and Probabilistic Mathematics)
by James Norris.
Homework:
There will be regular homework assignments during the semester. A selection of which will be required to be turned in.
Scoring:
Final Exam 40%, In-class presentation 25%, Quiz 20%, Homework 15%.
Class-Notes:
The consolidated notes of the class can be found
here (125MB).
The notes are also archived as the topics were covered every below.
Week 1 - Week3: January 25th to February 12th.
Notes:
Lecture 6
Lecture 5
Lecture 4
Lecture 3
Lecture 2
Lecture 1
Homework 1
Topics Covered
Weighted Graphs, Product Graphs
Stochastic Matrix : Eigenvalues, Eigenfunctions
Laplacian
Harmonic Functions
Poincare Inequality
Dirichlet Problem
Maximum Principle
Review of Discrete time Markov Chains
Week 4 : February 16th, and February 19th, 2021.
Homework 2
,
[Solutions to Selected Problems]
Notes:
February 16th
February 19th
Video:
February 16th
February 19th-Part 1
February 19th-Part 2
Topics Covered
Review of Discrete time Markov Chains
Example: Reflected Random walk on m vertices, on m-cycle
Result on Convergence to Stationarity;Rate of convergence;Mixing time
Example: Gambler's ruin chain
Results on Hitting times; Properties: Harmonic and Solution to Dirichlet Problem
Week 5 : February 23rd, and February 25th, 2021.
Homework 3
,
[Solutions to Selected Problems]
Notes:
February 23rd
February 26th
Video:
February 23rd-Part 1
February 23rd-Part 2
February 26th
Topics Covered
Sufficient criteria for Recurrence on weighted graphs
Examples of graphs with Exponential volume growth
Simple Random walk on ${\mathbb Z}^d$.
Foster's Criteria/Lyapunov Function
Queue Chain
Week 6 : March 2nd and March 5th, 2021.
Homework 4
Notes:
March 2nd
March 5th
Video:
March 2nd
March 5th
March 5th
Topics Covered
Simple Random walk of finite length $N$: Construction and Properties
Observable events and Filtration
Stopping times
Zero expected profit
Reflection Principle
Week 7 : March 9th and March 12th, 2021.
Homework 5
,
Solution.
Quiz 3 Solution.
Notes:
March 9th
March 12th
Video:
March 9th
March 12th
Topics Covered
Last visit to origin
Hitting distribution.
Infinite time horizon Walk
Discrete time Martingale
Conditional Expectation
Week 8 : March 16th and March 19th, 2021.
Homework 6
Notes:
March 16th
March 19th
Video:
March 16th
March 19th
Topics Covered
Tower Property
Conditioning Martingale on its past.
Exponential Martingale
Conditional Expectation for discrete random Variables
Conditional Expectation with respect to Observable events/-filtration.
Stopping times and Stopped Processes
Week 9 : March 23rd and March 26th, 2021.
Homework 7
,
Solution
Notes:
March 23rd
March 26th
Video:
March 23rd
March 26th
Topics Covered
Optional Stopping Theorem
Sub-Martingale
Kolmogorov Maximal Inequalities
Week 10 : March 30th, and April 2nd 2021.
Homework 8
March 30th
Notes
Video
April 2nd, 2021, Student Classes:
Aritra Bhattacharya
Notes
Class-Talk Notes
Video
Nitya Gadhiwala
Notes
Class-Talk Notes
Video
Topics Covered
Kolmogorov Maximal Inequality
Martingale Convegence Theorem
Lemma 2.2 in
Survival Probability of a Random Walk Among a Poisson System of Moving Traps
by Alexander Drewitz, Jürgen Gärtner, Alejandro F. Ramirez, and Rongfeng Sun
Theorem 1.3 and Theorem 1.4 in
Large Deviations
by Frank den Hollander
Week 11 : April 6th, 2021 and April 9th, 2021.
Homework 9
April 6th
Notes
Video
April 9th
Notes
Video
Jainam Khakhra
Notes
Class-Talk Notes
Video
Topics Covered
Martingale Convegence Theorem
Wald's Identity
Chernoff Bounds
Error Bounds for MAP Test and Sequential Test.(Section 7.5.5-7.5.6 in
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-262-discrete-stochastic-processes-spring-2011/course-notes/MIT6_262S11_chap07.pdf
Discrete Stochastic Processes by Robert Gallager.
Week 12 : April 13th, 2021 and April 16th, 2021.
April 13th
Notes
Video
Homework 10
April 16th, 2021, Student Classes:
Sree Akshaya
Notes
Class-Talk Notes
Video
Shaibal Karmakar
Notes
Class-Talk Notes
Video
Topics Covered
Martingale Convergence Theorem (non-negative)
Expected hitting time of a finite pattern
Mixing time of Simple random walk on the $n$-cycle.
Week 13 : April 20th, 2021 and April 23rd, 2021.
Homework 11
April 20th
Notes
Video
April 23rd, 2021, Student Classes:
Abhiti Mishra
Notes
Class-Talk Notes
Video
Ritvik Radhakrishnan
Notes
Class-Talk Notes
Video
Topics Covered
Chernoff Bounds Re-visited
Galton-Watson Process
Moran Model
Liouville Property for Harmonic functions on $\Z^d$.
Week 14 : April 27th, 2021 and April 30th, 2021
April 27th
Notes
Video
April 30th- No class
Topics Covered
Binomial Model for Option Pricing
Harnack Inequality Statement
Strong Liouville Property
Last Modified: April 30th, 2021.
Courses Page
Teaching Page