Axioms of probability; Conditional probability and independence; Random variables; Expected value and variance; Moment-Generating Functions and Laplace Transforms; conditional expectation; Exponential random variables.
Limit theorems; Examples: A random graph; The Quicksort and Find algorithms; A self-organizing list model; Random permutations.
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.
Introduction; Chapman-Kologorov Equations; Classification of states; Limiting and stationary probabilities; Some applications; Time-Reversible Markov Chains; Markov Chain Monte Carlo methods.
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.
Martingales: Definitions and examples; The martingale stopping theorem; The Hoeffding-Azuma inequality; Sub-martingales.
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.
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.