## MS&E 321 |
## Stochastic Systems |

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

**The Big Picture**

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

Reversibility

**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 |