Description
Sign-up Link : piazza.com/isibang.ac.in/spring2021/m2rwg
General Information
Start Date : Jan 25th, 2021. End Date : May 4/6, 2021.
RECOMMENDED READING -
1.) Finite Markov chains : Chapter 1 of the book of Levine, Peres and Wilmer ("Markov Chains and Mixing Times") OR Chapter 9 of Panchenko's "Lecture Notes on Probability Theory"
2.) Basic Probability Tools : Chapters 1-7 of Manjunath Krishnapur's "Probability Theory - Part 2" notes OR Sections 2.1-2.3 and 2.5 of Panchenko's "Lecture Notes on Probability Theory".
Graphs and weighted graphs (Examples and Geometric Properties). Laplacian and Random walks. Dirichlet problem.
Green functions. Harmonic functions. Dirichlet or energy form. Convergence to equilibrium. Spectral properties of the Laplacian and mixing time. Examples. Cheeger's inequality.
Connection between random walks and electrical networks.
PART II
Harnack inequalities. Liouville property. Stability under rough isometries.
Isoperimetric inequality, Faber-Krahn inequality, Nash inequality, Poincare inequality and applications.
Heat-kernel bounds. Carne-Varapoulous bounds.
Continuous time random walks.
2.) A. Grigoryan - Analysis on Graphs.
3.) L. Levine, Y. Peres and E. Wilmer - Markov Chains and Mixing Times.
4.) R. Lyons and Y. Peres: Probability on Trees and Networks. http://mypage.iu.edu/rdlyons/~prbtree/prbtree.html
5.) N. Berestycki - Mixing times of Markov chains. https://www.math.ubc.ca/~jhermon/Mixing/mixing3.pdf
6.) Andras Telcs: Art of Random walk
7.) T. Kumagai : Random Walks on Disordered Media and their
Scaling Limits.
2.) Rajat Hazra's course- https://sites.google.com/site/rshazra/home/teaching/rwen
3.) D. Aldous and J. A. Fill- Reversible Markov chains and random walk on graphs. http://www.stat.berkeley.edu/~aldous/RWG/book.html.
4.) L. Saloff-Coste: Lectures on finite Markov chains. www. math.cornell.edu/~lsc/math778-only/stf.pdf
5.) J. Hermon's course : https://www.math.ubc.ca/~jhermon/Mixing/mc.html
6.) T. Hutchcroft's Notes : Available at https://www.statslab.cam.ac.uk/~th361/
7.) R. Montenegro and P. Tetali. Mathematical Aspects of Mixing Times in Markov Chains. http://faculty.uml.edu/rmontenegro/research/TCS008-journal.pdf
8.) R. van Handel. Probability in High Dimensions. https://web.math.princeton.edu/~rvan/APC550.pdf
9.) Piyush Srivastava's Course : Markov Chains and Random Walks.
https://www.tifr.res.in/~piyush.srivastava/teaching/win-2020-markov/
Also has links to some other related courses.
Presentation : 15
Report on presentations by others : 5.
Assignments (30) : 40
+ Piazza (10)
+ Class participation (10)
Announcements
Suvadip's presentation will be on May 15th (Saturday) at 4.30 PM. Details are below.
Title - Renewal theory and applications to queueing.
ZOOM LINK :
Join Zoom Meeting
https://us02web.zoom.us/j/81400351526?pwd=T25GU1BsNi8zT1J2cmhCNjBPUThTZz09
Meeting ID: 814 0035 1526
Passcode: Harnack
This Friday April 23rd, 2021 we shall have two student talks in TAS
Abhiti Mishra 11:30-12:15pm
Title: Markov Chains in Biology (Moran Model)
References: Section 5.1 Markov Chains by J.R. Norris
Ritvik Radhakrishnan 12:30-1:15pm
Title: Bounded Harmonic Functions and Liouville Property
References: Aspects of Markov Chains Slides, Yuval Peres (Theorem 4.4)
https://services.math.duke.edu/~rtd/CPSS2009/peres6.pdf
Here is the schedule of Class Presentations in the RWG course. The students can post their presentation slides / notes before their lecture in reply to the post. The zoom link is the usual one but posted below for convenience.
1). APRIL 22nd - 6.25- 7.15 PM : Jhanvi Garg - Markov Chain Monte Carlo : Metropolis-Hastings Algorithm and Gibbs Sampler/Glauber Dynamics. (Chapter 3 of LPW)
6) TO BE SCHEDULED LATER : Suvadip Sana - Renewal theory and applications to queueing.
ZOOM LINK :
Join Zoom Meeting
https://us02web.zoom.us/j/81400351526?pwd=T25GU1BsNi8zT1J2cmhCNjBPUThTZz09
Meeting ID: 814 0035 1526
Passcode: Harnack
Dear All,
We shall have two talks this friday.
I) Sree Akshaya will give her talk from 11:30am:12:15pm
Topic: Expected hitting time of a pattern from a finite Alphabet set
Based on Section 3.3 from Martingale Theory and Applications by Nic Freeman [April 29, 2015]
https://nicfreeman.staff.shef.ac.uk/teaching_old/martingales%20notes%201.pdf
and
II) Shaibal Karmakar will give his talk from 12:30-1:15pm
Topic: Mixing time of the random walk on n-cycle
Based on Section 5.3.2 in Markov Chains and Mixing Times David A. Levin, Yuval Peres, and Elizabeth L. Wilmer
Join Zoom Meeting https://us02web.zoom.us/j/89430982848?pwd=MHhtRUk0UmE1QkI0SHJpdFVwd1o5dz09
Meeting ID: 894 3098 2848
Passcode: 304571
best wishes
Siva
Dear All,
If I may indulge in a small point of philosophy. Please disregard if it does not feel important.
One thing Yogesh and I consciously have tried during this effort of teaching a "joint"-but separate class for both M.Math and B.Math (Hons.) III year is the following:-
-- RWG will build on key mathematical concepts that lead to current frontiers in the field.
-- TAS will build on the same with key concrete examples.
Given this I would encourage everyone taking RWG to look at TAS assignments that are being given. Sarvesh has been writing solutions for many of the problems and they will be updated by this weekend. In case you have not tried any of them and would like to try them before the solutions are put up then please do so.
Thanks.
Siva
This week we shall start with student classes in TAS :
April 9th, 12:30-13:15 Jainam Khakra (Hypothesis tests and threshold crossing probabilities in random walks)
References: 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.
In case you missed it and are interested then last weeks student classes are archived at the course website:
https://www.isibang.ac.in/~athreya/Teaching/tas/
Best wishes,
Siva
This week we shall start with student classes in TAS:-
April 2nd, 11:30-12:15 Aritra Bhattacharya (Large Deviation for Simple Random Walk)
References: Frank Den Hollander Large Deviations-- Theorem 1.3 and Theorem 1.4 https://books.google.co.in/books/about/Large_Deviations.html?id=arxAjD_yl4oC&redir_esc=y
April 2nd, 12:30-1:15 Nitya Gadhiwala (Survival Probability in a Poisson field of moving traps)
References :Survival Probability of a Random Walk Among a Poisson System of Moving Traps
https://arxiv.org/abs/1010.3958 (Lemma 2.2)
If you wish to join in then please follow the TAS class link.
best wishes
Siva
Dear All,
At TAS, also there will be class presentations. The below is the tentative topics to be done by those crediting the class:
Abhiti-- Examples of Markov Chains in Biology
Akshaya- Time for "ABRACABADABRA" to appear -- using Martingales.
Aritra-- Large Deviations for Simple Random Walk on Z
Jainam- Neyman Pearson Lemma and threshold Probability for the random Walk
Nitya- Survival of Random Walk in Moving Traps.
Ritvik--Liouville Property on Euclidean lattice
Shaibal- Mixing time for the Random walk on n-cycle
Each topic will be delivered as 45-50 min class. There will be notes 6-7 pages posted on the course website and there will be 1 Homework Problem from the lecture as well. The plan is to hold the class presentations during the second week of April onwards (or in early April if anyone is ready).
Last but not least, thanks to the students for bailing out the instructor by agreeing to explain the above topics to their fellow classmates (and to instructor).
best wishes
Siva
| Name | Office Hours | |
|---|---|---|
Yogeshwaran | When? Where? | |
Siva Athreya | When? Where? | |
Sarvesh Iyer | When? Where? |