M2RWG | Class Profile

Course Information
Staff
Resources

Description

The course will review interactions between geometric properties of graphs, and the behaviour of random walks, transition densities, and harmonic functions. Depending on the audience, the course will take an analytic or probabilistic flavour.

Sign-up Link : piazza.com/isibang.ac.in/spring2021/m2rwg

General Information

AUDIENCE

This is a course for M.Math 2nd year students. Some of the first part of the course will be common for students (B.Math 3rd year and M.Math 2nd year) doing "Topics in Applied Stochastic Processes". For details on the latter course, see https://www.isibang.ac.in/~athreya/Teaching/tas/

TIMINGS

Monday and Thursday : 5.30 - 7.00 PM. (Tentative)

Start Date : Jan 25th, 2021. End Date : May 4/6, 2021.

VENUE

Classes will be conducted over zoom. The zoom links will be posted on Piazza page.

PRE-REQUISITES

Measure-theoretic probability - See Chapter 1 of Panchenko's "Lecture Notes on Probability Theory" OR Chapters 1-2 of Lanchier's "Stochastic Modelling" book.

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".

SYLLABUS

PART I :
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.

REFERENCES

1.) M. T. Barlow - Random walk and heat kernel on Graphs.

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.

MORE REFERENCES

1.) Siva Athreya's previous course - https://www.isibang.ac.in/~adean/infsys/database/MMath/RWG.html

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.

GRADING SCHEME

End-Semester : 40
Presentation : 15
Report on presentations by others : 5.
Assignments (30) : 40
+ Piazza (10)
+ Class participation (10)

Sarvesh Ravichandran Iyer

Announcements

Suvadip's presentation

5/12/21 9:11 PM

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

View More · View on Piazza

Student class in TAS

4/22/21 6:24 PM

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

View More · View on Piazza

RWG Class Presentation

4/19/21 7:20 PM

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)

2) APRIL 29th - 5.30 - 6.20 PM - Adhip Jadhav - Simulated Annealing. (Chapter 9 of Haggstrom)

3) APRIL 29th - 6.25 - 7.15 PM Pablo Bhowmik - Diaconis-Shahshahani Lemma (Chapter 6 of Berestycki)

4,5) MAY 3rd - 5.30 - 7.15 PM : Akshay Hegde and Rahul Kanekar - Transport-entropy inequalities

and curvature in discrete-space Markov chains. (based on paper by Eldan, Lee & Lehec - https://arxiv.org/abs/1604.06859 )

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

View More · View on Piazza

Class presentation in TAS

4/15/21 11:16 AM

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

View More · View on Piazza

Homework in TAS

4/07/21 9:52 AM

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

View More · View on Piazza

Student Class in TAS

4/07/21 9:44 AM

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

View More · View on Piazza

Student Class in TAS

3/31/21 11:29 PM

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

View More · View on Piazza

Class Presentations in TAS

2/26/21 11:01 PM

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

View More · View on Piazza