Management Science and Engineering 221
Stochastic Modeling

Mondays and Wednesdays, 1:00 PM-2:15 PM
Building 200, Room 202
3 units

Instructor:

Ramesh Johari
Assistant Professor
Management Science and Engineering
Terman Engineering Center, Room 319
E-mail: ramesh.johari@stanford.edu
Office hours: Monday, 5:00-6:30 PM; Thursday, 5:15-6:45 PM

Course assistant:

Chin Liu
E-mail: chinliu@stanford.edu
Office hours: TBA

Note: Additional lectures will be held on Friday 2/10/06 (midterm review), and Friday 2/24/06.

Course webpage:

The course webpage will be accessible through http://coursework.stanford.edu.

Course description:

A more detailed title for this course might be ``Stochastic Modeling of Time-Dependent Systems.'' We will be focusing almost entirely on dynamic models of random phenomena, and in particular, the most well-studied class of such models: Markov chains. The tentative list of topics (not necessarily in order of presentation):

1. Markov models in discrete time
   1. Basic definitions, calculating transition probabilities
   2. Classification of states; recurrence and transience
   3. Absorption probabilities and hitting times
   4. Invariant distributions
   5. Convergence to equilibrium
   6. Strong Markov property
   7. Regeneration and LLN for Markov chains
   8. Reversibility
2. Markov models in continuous time
   1. The exponential distribution and the Poisson process
   2. Generators
   3. Forward and backward equations
   4. The jump chain
   5. Analogs of discrete time results
3. Applications
   1. Queueing
   2. Markov decision theory
   3. Simulation

The focus of the course will be on modeling and applications of the theory. Students seeking a more pure mathematical treatment of the subject should consider taking Stat 217.

Grading

The grade will be based on the following:

• 25% problem sets
• 25% midterm (to be held February 13, 2006)
• 50% final exam

Please familiarize yourself with the Stanford Honor Code; violations will be prosecuted to the fullest extent of the (Stanford) law.

Matlab

One of the most valuable features of Markov chain theory in practice is that it has deep connections to linear algebra and matrix analysis. To numerically explore this connection, at least one assignment in the course will make use of Matlab, a widely used software package for linear algebra (among other things). Matlab is available on the Sweet Hall cluster machines, and a short Matlab tutorial is available online. More details on accessing the Sweet Hall Linux/Unix machines can be found here:

http://www.stanford.edu/services/cluster/environs/sweet/

Once you login, type ``matlab'' at any prompt to begin.

A useful means of using X Windows programs such as Matlab remotely on Macs (Apple X11) and PCs (VNC Client) is described here:

http://www.stanford.edu/services/unix/moreX.html

Matlab review: A Matlab review session will be scheduled, TBA.

Prerequisites

This course is intended for master's students and first year Ph.D. students, and is particularly targeted at students who wish to use Markov chains for applied work in operations and management. The main prerequisite for the course is probability at the level of MS&E 220; an acceptable substitute is Stat 116. Note that this is a hard constraint; we will not be reviewing any of the material from these courses in class. Students without this prerequisite can only enroll with permission of the instructor. The other primary prerequisite for the class is some familiarity with linear algebra and matrices, at the level of Math 51.

If you have taken probability elsewhere and would like to know if you satisfy the prerequisite, contact Prof. Johari via e-mail prior to registering for the course.

Textbook

The textbook is Introduction to Probability Models (Eighth Edition), by Sheldon Ross. The book can be found at the Stanford Bookstore. A few other books to consider, for an alternate perspective (presented in increasing order of difficulty):

• Bertsekas and Tsitsiklis, Introduction to Probability. This is an excellent introduction to basic probability, at the advanced undergraduate level. It contains two chapters on random processes and (finite state) Markov chains.
• Norris, Markov Chains. This is a slightly more mathematical treatment of the subject, but one of the most clearly presented versions of the material available.
• Durrett, Essentials of Stochastic Processes. This book is also more mathematical than Ross' book; it is a good place for an introduction to martingales that is not very technical.
• Grimmett and Stirzaker, Probability and Random Processes. This book is a comprehensive treatment of basic probability and Markov chains, at a more rigorous pace than the books above.