Columbia  University   in the City of New York        |     New York, N.Y.  10027

DEPARTMENT OF STATISTICS                                                                        618  Mathematics Building
                                                                                                                                                  2990 Broadway
                                                                                                                                   Phone: (212) 854-3652/3
                                                                                                                                          Fax: (212) 663-2454

W 6501:  STOCHASTIC PROCESSES
Fall Semester 2003
Professor Ioannis Karatzas

COURSE SYLLABUS

 Review of Conditional Distributions and Expectations. 
The simple Random Walk and its properties; gambler’s ruin problem. Markov Chains in discrete time; notions of commun-icating classes, stopping times, recurrence, transience, harmonic functions, invariant mea-sures; ergodic properties. 
Markov Chains in continuous time: birth-and-death processes, Poisson process, pure-birth processes, queueing processes. Branching processes and their properties. 
Martingales in discrete time: invariance under transforms, Doob decomposition, optional sampling theorem, applications, upcrossings, convergence. Brownian motion: construction, basic properties, sample paths, reflection principle, hitting times, quadratic variation. 
Elementary introduction to stochastic integration and its connection with martingale transforms, Ito’s rule, applications, connections with the heat equation. Martingales in continuous time. Elementary introduction to stochastic differential equations and diffusions.

 Required Text:
G. LAWLER: "Introduction to Stochastic Processes". Chapman & Hall (1995).
 
Recommended Texts:
J.R. NORRIS: "Markov Chains". Cambridge University Press (1997).
B. OKSENDAL: "Stochastic Differential Equations". 3rd Edition, Springer-Verlag (1992). 
R.B. ASH: "Basic Probability Theory". J. Wiley & Sons (1972). 

A  DETAILED  SYLLABUS  FOLLOWS

. Lecture #1: Tuesday, 2 September
Overview of the topics in the course: Simple Random Walk. Random Walk. Processes with Independent Increments. MARKOV property. Martingale property. BROWNian motion.
 
. Lecture #2: Thursday, 4 September
Elementary approach to the simple random walk: Gambler’s ruin problem, absorption probabilities, expected duration of games. Notions of Recurrence and Transience.
 
. Lecture #3: Tuesday, 9 September
Combinatorial approach to the simple random walk.  Distribution of the first-return-time to the origin.
Assignment # 1:  Read R. Ash’s Chapter on the Combinatorial Approach to the Simple Random Walk.  Problems 1 – 8, from Ash, pp. 190-191.      Due on  Thu. 18 September.
 
. Lecture #4: Thursday, 11 September
The MARKOV property. MARKOV Chains. Initial distributions, transition probabilities (for one and several days). Notions of communication, equivalence classes, irredu-cibility.
 
. Lecture #5: Tuesday, 16  September
First hitting times and their elementary properties. Notion of stopping time. The Strong MARKOV property.
 
. Lecture #6: Thursday, 18 September
Equivalent formulations of the MARKOV property. Conditional Independence. Statement and proof of the Strong MARKOV property. Applications: generating functions and distributions for first-passage-times, and for first-return-times,        based on the Strong MARKOV property.
Assignment # 2:  Not to be handed in. 
1.	Read sections 1.1 – 1.7 in Norris. 
2.	Norris, Problems (Pbs.) # 1.1.2 – 1.1.4, 1.2.1, 1.5.1, 1.5.3. 
3.	Lawler, Problems (Pbs.) # 1.2, 1.5(a,b), 2.4. 
 
. Lecture #7: Tuesday, 23 September
Recurrence and Transience for MARKOV Chains: definitions and basic properties. Application to the simple random walk in two and three dimensions.
 
. Lecture #8: Thursday, 25 September
Invariant measures and invariant distributions for a MARKOV Chain. Examples. Doubly-stochastic matrices. Positive- and null-recurrence. Existence of invariant distributions. Ergodic theorem for MARKOV Chains.
Assignment # 3:  Lawler, Problems # 1.9 - 1.11, 1.13, 2.2 – 2.5.  Due on Tue. 7 October.
 
. Lecture #9: Tuesday, 30 September
Periodicity for a MARKOV Chain. The "convergence to equilibrium" theorem for irredu-cible, aperiodic chains, via the coupling method. Time-reversal, the detailed-balance equations.
 
. Lecture #10: Thursday, 2 October
Definition and properties of conditional expectations. Conditional expectation as  least-squares predictor. Definition and basic properties of Martingales.  The DOOB decomposition.
 
. Lecture #11: Tuesday, 7 October
The optional sampling theorem, application to simple random walk and to the gambler’s ruin problem. Martingales associated with MARKOV Chains, harmonic functions; connections with recurrence and transience.
Assignment # 4:  Lawler, Problems # 5.3 – 5.7, 5.9, 5.10.   Due on Tue, 14 October.
 
. Lecture #12: Thursday, 9 October
Basic facts about martingale transforms. Upcrossings inequality, the convergence theorem for martingales.
 
. Lecture #13: Tuesday, 14 October
Martingale transforms; invariance of martingales under stopping. Optional sampling theorem: for bounded stopping times, for bounded martingales, other sufficient conditions. Application of optional sampling to the simple random walk.
 
. Lecture #14: Thursday, 16 October.
Definition and properties of the BROWNian motion. Martingale and MARKOV  properties. Distribution of the first-hitting-time to a certain level; null recurrence. Computation of the probability of zero-crossing during a given time-interval.

. Lecture #15: Tuesday, 21 October.  MID-TERM EXAMINATION.
 
 . Lecture #16: Thursday, 23 October
Gambler’s ruin problem for BROWNian motion; martingale methods. Strong MARKOV property. Quadratic variation of the BROWNian path; variations of all other orders.
Assignment # 5:  Read Chapter 8 in Lawler. Problems # 8.4 – 8.10.   Not to be handed in.
  
. Lecture #17: Tuesday, 28 October
Stochastic integral for simple processes; elementary properties, connections with martingale transforms.
 
. Lecture #18: Thursday, 30 October
Stochastic integral for general adapted processes. Properties. ITO’s change-of-variable rule. Elementary computations for stochastic integrals.
Assignment # 6:  Due on Tue, 11 November.
1.	Read Chapter 9 in Lawler, do Problems # 9.1, 9.2. 
2.	Oksendal, Problems # 3.2, 3.4, 3.5 (p.29); # 4.2, 4.3, 4.6, 4.7 (pp. 38-40); 5.1, 5.2, 5.10(I)          (pp. 54-57). 

. Lecture #19: Tuesday, 4 November.         UNIVERSITY HOLIDAY
 
. Lecture #20: Thursday, 6 November
Variants of the ITO formula. Applications. Argument for the proof. The heat equation; fundamental solution, solution of a general CAUCHY problem. Interpretation in terms of BROWNian motion.
 
. Lecture #21: Tuesday, 11 November
Variants of the heat equation (cooling, heat-transfer), interpretation of solutions in terms of BROWNian motion. FEYNMAN-KAC formula, the arc-sine law. DIRICHLET problem; computation of the expected exit-time for multi-dimensional BROWNian motion in a ball. 
 
. Lecture #22: Thursday, 13 November
Definition and properties of the POISSON process. Generalizations: pure-birth process, birth-and-death process. Examples: M/M/1, M/M/k, and M/M/infinity queues.    Exponential distribution of the interarrival times. Some basic properties of the exponential distribution.
Assignment # 7:  Read Chapter 3 in Lawler. Problems 3.1 – 3.5, 3.7 –3.12. Not to be handed in.
 
. Lecture #23: Tuesday, 18 November
MARKOV Chains in continuous-time. Independence and exponential distribution of jump-times, transition mechanism. Transition probabilities, Chapman-Kolmogorov equations, invariant measures.
 
. Lecture #24: Thursday, 20 November
Optimal Stopping for discrete-parameter Markov Chains, and for Brownian motion (notes from Dynkin & Yushkevich).
Assignment # 8:  Read Chapter 4 in Lawler. Problems 4.1, 4.2, 4.6, 5.14.   Due Tue. 2 December. 

. Lecture #25: Tuesday, 25 November
Discrete-time Markov Chain embedded in a Continuous-time Markov Chain, discussion of recurrence and transience. Birth-and-death processes; criteria for positive and for null recurrence.  Examples: invariant measures for the M/M/1, M/M/k, and M/M/infinity queues.

. Lecture #26: Thursday, 27 November.               THANKSGIVING HOLIDAY
  
. Lecture #27: Tuesday, 2 December
Stochastic Differential Equations, the basic existence and uniqueness theorem of ITO. Explicit solutions for linear SDE’s. Examples. Notion and computation of infinitesimal generator.
 
 . Lecture #28: Thursday, 4 December
GIRSANOV’s Theorem: Motivation and proof.

 . Lecture #29: Tuesday, 9 December
GIRSANOV’s Theorem: application to Brownian motion with drift, computation of the distribution of first-passage-times.  
 
. Lecture #30: Thursday, 11 December.                    FINAL EXAMINATION