IEOR 4106. Stochastic Models

Fall, 2018. Tuesdays and Thursdays 4:10PM--5:25PM in Room: 501 Schermerhorn Hall

Instructor: Professor Karl Sigman
Department of Industrial Engineering and Operations Research

Phone: (212) 854-3556
FAX: (212) 854-8103

Office hours: Wednesdays 11:00AM--12:00PM, 310 S.W. Mudd Building

COURSE WEB SITE:

Email: jc4823@columbia.edu

Email: yc3107@columbia.edu

Email: lz2573@columbia.edu

Weekly Homework Assignments (HOMEWORK DOES NOT COUNT TOWARDS YOUR GRADE AND IS NOT TO BE TURNED IN: SOLUTIONS ARE POSTED BELOW. (Try to start new homeworks on Thursdays of each week)

1. Homework 1
2. Homework 2
3. Homework 3
4. Homework 4
5. Homework 5
6. Homework 6
7. Homework 7 (Revised on November 20, 2018)
8. Homework 8

Homework Solutions

1. Homework 1
2. Homework 2
3. Homework 3
4. Homework 4
5. Homework 5
6. Homework 6
7. Homework 7
8. Homework 8

Lecture Notes (Written by Professor Sigman)

1. Gambler's Ruin Problem and simple random walks
2. Introduction to Markov Chains
3. More on Markov Chains: Communication classes and irreducibility; transience and recurrence, positive recurrence, limiting distributions.
4. Expected number of visits to transient states in a finite state Markov chain
5. Stopping times. Strong Markov property for Markov chains. Wald's equation
6. The Binomial Lattice Model for risky assets; introduction to option pricing
7. Review of the exponential distribution
8. The Poisson process, point processes, renewal processes, the Elementary Renewal Theorem
9. Continuous-Time Markov Chains
10. Little's Law (l= λ w )
11. Renewal Reward Theorem
12. Renewal Theory (forwards, backwards recurrence times, spread, equilibrium distribution, inspection paradox).
13. Introduction to random number generators
14. Introduction to Brownian Motion

Lectures from the Class (iPad)

1. Simple random walks. Gambler's Ruin Problem
2. More on the Gambler's Ruin Problem; hitting time probabilities for the simple random walk. Definition of a Markov chain.
3. Definition of a Markov chain. Examples; Markov chains as recursions
4. Inverse transform method for simulating from given distributions applied to Markov chain recursions. Examples; n-step transition probabilities; Chapman-Kolmogorov Equations. Examples.
5. More examples of Markov chains; Reservoir model and the single-server FIFO queueing model. Binomial Lattice Model for risky assets. Recurrence and transience of states, communication between states.
6. Communication classes, null versus positive recurrence, transience. Relationship between positive recurrence and the existence of a limiting/stationary probability distribution π.
7. More on irreducible positive recurrence and limiting/stationary probability distribution π=π P, rate in equals rate out interpretation.
8. Stopping times. Strong Markov property of Markov chains. Wald's equation
9. Expected number of visits to transient states in a finite state Markov chain. (Binomial Lattice Model and option pricing; see Lecture Notes 6 above)
10. This was a video lecture day (from the Video Library in CANVAS); covering a review of the exponential distribution; renewal point processes, the Elementary Renewal Theorem, introduction to the Poisson process.
11. More on Poisson processes. Partitioning theorems, and order statistics
12. Applications of Partitioning theorems, and order statistics. M/G/ ∞ queue
13. Examples/Exercises involving Poisson processes
14. Continuous-time Markov chains, Birth and Death processes, rate equations
15. More on Birth and Death processes, Global Balance Equations, Birth and Death Balance Equations. M/M/c Queueing loss models
16. More on Global Balance Equations, Birth and Death Balance Equations, and rates. Little's Law (l= λ w )
17. More on Little's Law (l= λ w ). Forwards and backwards recurrence time for renewal processes; the equilibrium distribution, the inspection paradox
18. The Renewal Reward Theorem with applications.
19. More on the inspection paradox, more on The Renewal Reward Theorem. Introduction to random number generators (see Lecture Notes above on this topic). Simulating normal random variables (the Polar Method); simulating Poisson random variables
20. More on simulation. Simulating a Reservoir model; connection with a single-server queue. Introduction to Brownian Motion; Brownian motion with drift.
21. More on Brownian motion; some computations, hitting probabilities, geometric Brownian motion.
22. More on Brownian motion; Maximum and minumum, More on geometric Brownian motion.

EXAMS: PLEASE MAKE NOTE OF THESE DATES, NO CHANGES ALLOWED. Missing an exam will lead to a "F" or "UW" letter grade in the course

Midterm Exam Information

• Date and Time: Tuesday, Tuesday October 23, 2018. In-Class: 1 hour, 15 minutes. Open notes, CLOSED BOOK. (but you can bring anything printed out from this class website). No electronics of any kind allowed (not even calculators: you will not need them). Practice Midterm Exam will be posted, solutions will be posted too.
• Information about the Midterm Exam
• Practice Midterm Exam.
• SOLUTIONS TO Practice Midterm Exam.

Final Exam Information

• Date and Time: Tuesday, December 18. 4:10PM--7:00PM, 501 Schermerhorn Hall. 2 hours and 50 minutes. Open notes, CLOSED BOOK. (but you can bring anything printed out from this class website). No electronics of any kind allowed (not even calculators: you will not need them).
• Final Exam Details.
• Practice Final Exam.
• SOLUTIONS TO Practice Final Exam.