MS&E 321

Stochastic Systems

| General Info | Announcements | Course Topics | Handouts | Assignments | References | Links |

The Big Picture

The great majority of models formulated within the management science/engineering/operations research/economics communities are formulated as Markov chains and Markov processes, in part because such models permit known "physics" to be easily incorporated. So, most of what we are covering this quarter relates to tools for the analysis of Markovian models.

The key ideas are most easily discussed in the setting of discrete-time Markov models (i.e. Markov chains). In this setting, computing "transient performance measures" is straightforward, whether in discrete state space or continuous state space. Computing the n-step transition probabilities amounts to computing n-1 fold sums or integrals, as does computing n-step expected rewards or n-step probability distributions (with very little additional complication arising if the transition probabilities are non-stationaty or not). A variety of performance measures can be computed by using first step/first transition analysis. In general, the linear systems take the form u = f + Gu, with f and G non-negative; such linear systems can have multiple solutions. The probabilistically meaningful solution is invariably the minimal non-negative solution (which could be infinity-valued). In this setting, there are two (related) methods for bounding solutions to such linear systems:

Method 1: Using weighted vector/function norms and related weighted matrix/operator norms (which can also establish that the operator I - G is invertible as an operator)
Method 2 (more general): Using a non-negative Lyapunov function g for which Gg <= g - f

We then turned to the steady-state theory for Markov chains. The key idea here is the use of "regeneration". When a stochastic process is regenerative, it inherits many of the properties that are known for iid sequences: the LLN, the CLT, exponential limit laws for hitting times of rare sets, etc. The idea is straightforward to apply in the presence of discrete state space; in continuous state space, use of regeneration requires a randomization trick (involving coin-flipping, based on representing the transition probabilities as a mixture distribution). The associated class of Markov chains that can be handled as regenerative processes are known as Harris chains. Verifying that a Markov chain is a Harris chain requires constructing a suitable Lyapunov function on the complement of some compact set, and then showing that the m-step transition probabilities are suitably bounded below on the compact set.

When a Markov chain is Harris recurrent, one can use renewal theory to analyze the convergence of the n-step transition probabilities, because such probabilities/expectations satisfy a class of equations known as renewal equations. The limiting behavior of the solution of a renewal equation can be analyzed via the renewal theorem. A method known as "coupling" can be used to prove the renewal theorem, and can even be used to construct bounds on rates of convergence (in both the renewal theorem and for Markov chains), via the "coupling inequality". Such rates of convergence are of central interest in applications areas such as Markov chain Monte Carlo.

A key theoretical device in the analysis of Markov chains and processes is martingale theory. Martingales form a generalization of a sum of independent mean-zero rvs; supermartingales generalize "negative drift" random walks, while submartingales generalize "positive drift" random walks. As a generalization of a sum of independent mean-zero rvs, the mean and variance of a martingale is easily computable, and there are martingale analogs to the LLN and CLT. In addition, the Wald identity for random walks generalizes to martingales, in an extension known as the "optional sampling formula". Martingales also offer another mechanism for deriving the linear systems associated with first step/first transition analysis, and supermartingales/submartingales provide a means of bounding the solutions to such linear systems (and are closely related to the Lyapunov methods discussed earlier in the course). One advantage of using this martingale approach to derive and bound these linear systems is that they generalize nicely to continuous time Markov processes (whereas first step/first transition analysis is difficult to rigorously extend to continuous time).

Martingales also play a fundamental role in the discussion of stochastic control and optimal stopping for Markov chains and processes, as well as in statistical inference and "change-of-measure" for Markov chains and processes.

Course Topics

Discrete-time Markov Chains (DTMCs):

Definition, examples, and review of basic theory in finite state space
Connection to stochastic recursions
Matrix analysis
Recurrence and positive recurrence
Steady-state theory
Martingale structure for DTMCs
Poisson's equation
Markov chains with non-stationary transition probabilities
Statistical analysis for DTMCs
Stochastic control for DTMCs

Continuous-time Markov chains (CTMCs):

Definition, examples, and review of basic theory
Martingale structure
Birth-death processes

Stability for General State Space Markov Chains:

Definition of Harris recurrent Markov chains and examples
Lyapunov functions
Renewal theory
The coupling method

Diffusion Approximations and Brownian motion:

Definition of Brownian motion
Brownian motion as a limit of random walk
Reflection principle
Reflected Brownian motion as a limit of queues in heavy traffic

Analysis of Algorithms:

Monte Carlo method

| Management Science & Engineering Dept | Stanford University |