CSL860: Special Topics in Parallel Computation
Some stochastic processes on graphs
I semester: 2010-11
Amitabha Bagchi
Class Timings: 2PM to 3:30PM, Monday and Thursday.
Room: Bharti Building 204.
Topics
This class provides an introduction to the area of
probability on graphs with special emphasis on the kinds of stochastic
processes that might be used to study the evolution of certain kinds
of spreading behavior on a network. Specifically we will provide a
brief introduction to Markov chains and Martingales, Random walk on
graphs, Branching processes, Percolation, Contact processes and
Interacting particle systems.
Tentative lecture schedule
- Week 1.
- Intro to the class and Model #1 Percolation.
- Model #2 Oriented Percolation, Model #3 Branching processes.
- Week 2.
- Model #4 Random walks on graphs, Model #5 Contact processes.
- Introduction to probability : sigma fields, Kolmogorov’s 0-1 laws.
- Week 3.
- Tools: Coupling and FKG inequality.
- BK inequality.
- Week 4.
- Percolation.
- Percolation continued.
- Week 5.
- Intro to Martingales.
- Galton Watson Branching Processes.
- Week 6.
- Galton Watson Branching Processes continued.
- Markov Branching Processes.
- Week 7-13.
To be announced.
Exams and homework assignments
Instructions
- Please save the template in a latex file called
"minor<minor number>-your-name.tex".
- Fill in your answers and your name at the
appropriate places indicated, and, when you are done, printout the pdf
made from this latex file.
- Bring it with you to class on the due date.
- If for some reason you cannot come to class that
day, please drop the exam in my box before the beginning of
class on the due date.
- If you cannot access the local server because you live off campus,
email me and I will send you the tex template.
Scribing
- Please download the template file and the
latex class file that will be needed.
- Here are some general
guidelines which may help you with scribing class notes. Please
read them before you begin typing.
- Also the tex source for lecture
1 and lecture
4 of the class on Percolation Theory (2007-08) are available for
your reference (local access only.)
- Some latex tips here.
Amitabha
Bagchi