06CS665 - Stochastic Models And Applications |
PART – A |
UNIT 1 |
INTRODUCTION: Machine perception, an example; Stochastic Models And Applications
System; The Design Cycle; Learning and Adaptation. |
UNIT 2 |
INTRODUCTION - 2: 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: 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: 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: 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: Martingales: Definitions and examples; The martingale
stopping theorem; The Hoeffding-Azuma inequality; Sub-martingales. |
UNIT 7 |
POISSON PROCESSES, QUEUING THEORY - 1: 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: 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. |
REFERENCE |
TEXT BOOKS: |
1. Probability Models for Computer Science – Sheldon M. Ross:,
Elsevier, 2002.
|
Reference Books |
1. Stochastic Models Analysis and Applications – B. R. Bhat:, New
Age International, 2000.
2. Probability and Random Processes with Applications to Signal
Processing and Communications – Scott L. Miller, Donald G.
Childers:, Elsevier, 2004. |