Search

# Stochastic Processes in Information Systems

This course is designed for science and engineering students who want to build solid mathematical foundations for probabilistic systems that evolve in time through random changes that occur at discrete fixed or random intervals. Instead of rigorous proofs of pure mathematics, such as using or developing measure theory, the course focuses on the mathematical principles and the intuition required to design, analyze, and comprehend insightful models, as well as how to select and apply the best models to real-world applications. The course has four parts: (1) point processes, which cover the Bernoulli process, laws of large numbers, convergence of sequences of random variables, Poisson process, and merging/splitting Poisson processes; (2) Markov chains and renewal processes, which cover finite-state Markov chains, Markov eigenvalues and eigenvectors, Markov rewards, dynamic programming, renewals, the strong law of large numbers, renewal rewards, stopping trials, Wald's equality, Little, M/G/1, and ensemble averages; (3) Markov processes, which cover countable state Markov chains and processes, the Kolmogorov differential equations, birth-death processes, reversibility, and semi-Markov processes; and (4) random walks, large deviations, and martingales.

3

## Learning Objective:

• Understand the mathematical principles of stochastic processes
• Acquire and the intuition necessary to create, analyze, and understand insightful models for a broad range of discrete and continuous stochastic processes
• Learn how to choose and apply the best possible models to real-world situations in engineering, operations research, physics, biology, economics, finance, statistics, etc.

## Topics Covered:

Lecture Topic
1 Course overview, Review of probability models and random variables
2 Expectation, Sums of I.I.D. random variables, Sample averages, the Bernoulli process
3 Laws of large numbers, Convergence, Central limit theorem, Markov/Chebyshev inequalities
4 Poisson process, Memoryless property, Stationary increment, Independent increments
5 Combining and splitting Poisson process
6 Order statistics, Conditional arrival epoches, From Poisson to Markov
7 Finite-state Markov chains, the matrix approach
8 Markov eigenvalues and eigenvectors, Chapmann-Kolmogorov equation, Perron-Frobenius theory
9 Markov rewards and dynamic programming, Expected first passage time
10 Renewal process, Strong law of large numbers (SLLN), Time averages vs. ensemble averages
11 Renewal rewards, Stopping times, Wald's equality, Elementary renewal theory
12 Blackwell's theorem, Renewal process and Markov chains, Residual life, age, duration
13 Renewal reward processes, Time-average, ensemble-average renewal reward theorems
14 Key renewal theorem, Distribution of residual life
15 Queuing theory, Little's theorem, Time average waiting times
16 Markov chains with countable state space, Recurrence classes, Recurrence times
17 Countable-state Markov processes, Kolmogorov differential equations
18 Birth-death chains, Reversibility
19 Burke's theorem for M/M/1 queues, Semi-Markov processes
20 Markov processes and random walks
21 Hypothesis testing and random walks, Threshold crossing bounds, Large deviations theory
22 Random walks and thresholds
23 Martingales (plain, sub and super)
24 Martingales: stopping, Kolmogorov (sub)martingale inequality
25 Martingales: converging
26 Conclusion

## Prerequisites:

ECE 60000, Random Variables and Signals

Comprehensive knowledge of elementary probability at the level of ECE 60000, Random Variables and Signals, which uses the text Probability, Random Variables, and Stochastic Processes, Papoulis & Pillai, 4th edition, McGraw Hill, 2022

## Textbooks:

### Required:

1. Stochastic Processes, 2nd Edition, Ross, Sheldon, Wiley, 1996, ISBN No. 978-0471120629
2. Stochastic Processes: Theory for Applications, Gallagher, Robert G., Cambridge University Press, 2013, ISBN No. 978-1107039759

### Recommended:

1. Adventures in Stochastic Processes with Illustrations, Sidney Resnick, Springer Scientific+Business Media 2002
2. An Introduction to Probability Theory, 2nd Edition, D. Bertsekas and J. Tsitsiklis, Athena Scientific, 2008
3. An Introduction to Probability Theory and Its Applications, Vol 1, 3rd Edition, William Feller, Wiley, 1968
4. An Introduction to Probability Theory and Its Applications, Vol 2, William Feller, Wiley, 1971