Abstract
We have explored a number of topics motivated by concrete applications. It is time to stitch together these ideas into a complete panorama. In addition, we provide some complements.Section 15.1 discusses the general question of inference: what can one deduce from observations? Section 15.2 explains the important notion of sufficient statistic: what is the relevant data in a set of observations? Section 15.3 presents the theory of Markov chains where the number of states is infinite. Section 15.4 explains the Poisson process. Section 15.5 discusses the boosting algorithm for choosing among experts. What drug should you further research; what noisy channel should one use? These are examples of multi-armed bandit problems. In such problems one faces the trade-off between exploiting known possibilities versus exploring potentially more rewarding but less well understood alternatives. Section 15.6 explains a key results for such multi-armed bandit problems. Information Theory studies the limits of communication systems: how fast can one transmit bits reliably over a noisy channel? How many bits should be transmitted to convey some information? Section 15.7 introduces some key concepts and results of Information Theory. When estimating the likelihood of errors or the reliability of some estimates, one usually has to calculate bounds on the probability that a random variable exceeds a given value. Section 15.8 discusses some useful probability bounds. Section 15.9 explains the main ideas of the theory of martingales and shows how it provides a proof of the law of large numbers.
Funding Information
  • University of California, Berkeley Foundation