Show The Graduate Center Menu

Introduction to Stochastic Processes & Computer Simulation

 
 

Introduction to Stochastic Processes & Computer Simulation

Instructor: Professor Felisa Vazquez-Abad

Learning Objectives

The ability to model systems under uncertainty is an important skill. The ubiquitous nature of Markov Chain applications makes it very important in a diverse range of subjects, such as bioinformatics, industrial engineering, telecommunications, strategic planning and manufacturing. This course addresses that need by studying fundamental results of Markov chain processes. The focus is on modeling and many examples will be covered. In real problems, often analytical solutions are impossible to obtain, mainly (but not only) due to large state spaces. Simulation is a versatile and popular tool that can provide numerical approximations. This course covers topics of computer simulation and modeling that emphasize statistical design and interpretation of results.


Course Description

This course covers probability models, with emphasis on Markov chains. Theoretical results will be stated, and focus is on modeling. The last part of the course is devoted to techniques and methods of simulation, with emphasis on statistical design and interpretation of results. Students will work in team projects with a programing component. The students who succeed this course will:

  • understand and apply probability models to describe real problems,

  • be capable of designing computer simulations for Markov chains,

  • understand how to interpret and present the statistical results from simulations,

  • understand the analysis techniques for studying Markov chains.


Lectures

The course consists of an equivalent of 15 two-hour lectures with assigned reading.


Syllabus

  • Week 1: Concepts of probability: random variables, probability distributions, expectations. Stopping times and examples.

  • Week 2: Concepts of probability: conditional probability, conditional expectations.

  • Week 3: Generation of random variables and introduction to simulation.

  • Week 4: Markov chains introduction, classi cation of states and properties.

  • Week 5: Simulation models: tick-based and discrete event-based methods.

  • Week 6: Simulation models: standard clock method and reduced models. examples: Petri nets, aggregated models.

  • Week 7: Analysis of absorbing Markov chains, examples. Branching processes and time to extinction.

  • Week 8: Analysis of stationary Markov chains, examples. Reversible chains.

  • Week 9: Statistical analysis of simulation output. Con fidence intervals, stopping tests.

  • Week 10: Statistical analysis of simulation output for stationary problems. Con fidence intervals, stopping tests.

  • Week 11: Continuous time Markov chains, birth and death processes, reversibility. Renewal processes and examples.

  • Week 12: Simulation efficiency and variance reduction methods.

  • Week 13: Optional topics (see below) or work on the projects.

  • Week 14: Student presentations.

  • Week 15: Final exam.


Optional Topics

Depending on the interests of students, several topics may be covered either with formal lectures or with reading of scholarly papers on the subjects. Example topics include the following:

  • Markov Chain Monte Carlo methods and Simulated Annealing.

  • Markov Decision Processes and Dynamic Programming.

  • Simulation-based Optimization Techniques.

  • Reliability theory, Inventory Models, and Queueing Systems.


Prerequisites

Undergraduate course in statistics, programming knowledge.


Recommended textbooks

  • Ross, Introduction to probability models, 2003, Academic Press.

  • Ross, Simulation, 4th Edition, 2006 Academic Press.

  • Taylor and Karlin, An Introduction to stochastic modeling, 1998, Academic Press.

  • Cassandras and Lafortune, Introduction to Discrete Event Systems, 1999, Springer.


Assessment

Research projects will be assigned to teams of 2 to 3 students. These projects will involve modeling and statement of a research question, application of theoretical results and experimental design for computer simulations. The students will program the simulations and analyze the results. There will be student presentations of research projects, and three homework assignments.

  • Project 40%

  • Homework assignments 35%

  • Exams 25%

Threshold: in order to pass the subject, a minimum of 55/100 in the exams is required.