Course Objectives:
To introduce the power of probability theory and randomization techniques in computer science, with particular emphasis on analyzing algorithms that employ randomization.
Course contents:
Introduction – Events, probability spaces, random variables, expectation, conditional expectation, tail bounds including Markov’s inequality, Chebyshev’s inequality, Chernoff bounds. Sample applications include Karger’s min-cut algorithm, randomized quicksort, and permutation routing on the hypercube.
Common Probability Distributions – Bernoulli and binomial random variables, geometric distribution, coupon collector’s problem, Poisson distribution, normal
distribution, power law distributions.
Hashing with Applications – Balls into bins, chain hashing, Bloom filters, pairwise
independence, Chebyshev’s inequality for pairwise independent variables, universal
hash functions, perfect hashing, the count-min sketch, the power of two choices, cuckoo hashing.
Probabilistic Method – The counting argument, the expectation argument, sample and
modify, the second moment method, the conditional expectation inequality, the Lovasz local lemma.
Markov Chains and Random Walks – Basic definitions, stationary distribution,
variation distance and mixing time and their relation to graph spectrum, random walks on undirected graphs, the Monte Carlo method, the Metropolis algorithm, coupling.
Martingales – Basic definitions, stopping time, Wald’s equation, Azuma-Hoeffding
inequality.
Text Books:
Probability and Computing: Randomized Algorithms and Probabilistic Analysis,
by Mitzenmacher and Upfal, Cambridge University Press, 2005.
References
- Randomized Algorithms, by Motwani and Raghavan, Cambridge University Press,
1995.
- Concentration of Measure for the Analysis of Randomized Algorithms, by
Dubhashi and Panconesi, Cambridge University Press, 2009.
- The Probabilistic method, by Alon and Spencer, 3rd edition, Wiley, 2008.
