Instructor: Shubhanshu Shekhar (shubhan2 at andrew dot cmu dot edu)

Location: BH 232M

Time: Tuesday, Thursday 11:00 am to 12:20 pm

Office hours: by appointment

Information theory is an area of applied probability that was developed to model and analyze engineering systems for storing and transmitting data. Since then, information-theoretic ideas have also played an important role in several topics within statistics, most notably in showing the optimality of statistical procedures. However, the role of information theory is not limited only to proving impossibility results. In this course, we will develop the tools to study some such modern and classical topics involving the interplay of information theory and statistics.

We will begin the course by introducing the main information measures (entropy, relative entropy, and mutual information) and rigorously establish their key properties. Next, we will study the fundamental task of (lossless) data compression, and in particular, see how the above information measures naturally arise as quantities with specific operational meaning. Next, we will study the (perhaps surprising) links between compression, and the optimal growth rate of the wealth in gambling. Finally, we will show how this connection can be exploited to design powerful methods for sequential inference. We will also introduce the notion of information projection, and study its connections to the error exponents in hypothesis testing.

Lecture notes will be posted here.

There will be two homework assignments.

- Homework 1 (due 09/21/2023).
- Homework 2 (due 10/19/2023).

- 08/29: Information measures for discrete distributions.
- 08/31: Properties of Information measures (chain rules, convexity/concavity, DPI, Fano's inequality).
- 09/05: Information measures for continuous/general distributions.
- 09/07: Variational Definitions, f-divergences, applications.
- 09/12: Data Compression.
- 09/14: Gambling and Portfolio Optimization.
- 09/19: Universal Compression.
- 09/21: Universal Portfolios.
- 09/26: Coin betting and OCO.
- 09/28: Sequential Hypothesis Testing.
- 10/03: Sequential Hypothesis Testing.
- 10/05: Sequential Hypothesis Testing.
- 10/10: Confidence Sequences.
- 10/12: Confidence Sequences.