Wouldn't life be nice in a world where every random variable is always equal to its expectation? In some special cases (e.g. sums of independent random variables) it is possible to use powerful concentration inequalities (i.e. Chernoff bounds) to prove that the random variables in question are with high probability not too far from their expectation. But quite often the world does not supply you with independent random variables, particularly when you are analyzing a randomized algorithm or some other type of process where random decisions in one step depend on other random decisions made in prior steps of the process.
Martingales, originally developed as a formalism for analyzing gambling systems, are a powerful tool to be applied in such situations. We'll review the basic definitions of martingale theory, and will introduce the most important techniques (Kolmogorov-Doob inequality, Azuma's inequality, the method of bounded differences, and Doob's convergence theorem). Along the way we'll learn:
1. Why is the chromatic number of a random graph likely to be near its expectation?
2. How do you prove that the growth rate of a population of bacteria is asymptotically exponential?
3. What is the preferential-attachment model for the web graph, and how does it explain the observation that the vertex degree distribution of this graph obeys a power law?