06CS665 STOCHASTIC MODELS AND APPLICATIONS syllabus for CS


Part A
Unit-1 INTRODUCTION 1 6 hours

Axioms of probability; Conditional probability and independence; Random variables; Expected value and variance; Moment-Generating Functions and Laplace Transforms; conditional expectation; Exponential random variables.

Unit-2 INTRODUCTION 2 6 hours

Limit theorems; Examples: A random graph; The Quicksort and Find algorithms; A self-organizing list model; Random permutations.

Unit-3 PROBABILITY BOUNDS, APPROXIMATIONS, AND COMPUTATIONS 7 hours

Tail probability inequalities; The second moment and conditional expectation inequality; probability bounds via the Importance sampling identity; Poisson random variables and the Poisson paradigm; Compound Poisson random variables.

Unit-4 MARKOV CHAINS 7 hours

Introduction; Chapman-Kologorov Equations; Classification of states; Limiting and stationary probabilities; Some applications; Time-Reversible Markov Chains; Markov Chain Monte Carlo methods.

Part B
Unit-5 THE PROBABILISTIC METHOD 6 hours

Introduction; Using probability to prove existence; Obtaining bounds from expectations; The maximum weighted independent set problem: A bound and a ranom algorithm; The set covering problem; Antichains; The Lovasz Local lemma; A random algorithm for finding the minimal cut in a graph.

Unit-6 MARTINGALES 6 hours

Martingales: Definitions and examples; The martingale stopping theorem; The Hoeffding-Azuma inequality; Sub-martingales.

Unit-7 POISSON PROCESSES, QUEUING THEORY 1 7 hours

The non-stationary Poisson process; The stationary Poisson process; Some Poisson process computations; Classifying the events of a non-stationary Poisson process; Conditional distribution of the arrival times. Queuing Theory: Introduction; Preliminaries; Exponential models.

Unit-8 QUEUING THEORY 2 7 hours

Birth-and-Death exponential queuing systems; The backwards approach in exponential queues; A closed queuing network; An open queuing network; The M/G/1 queue; Priority queues.

Last Updated: Tuesday, January 24, 2023