CMI Silver Jubilee Lecture
Jaikumar Radhakrishnan, Tata Institute of Fundamental Research, Mumbai
Mutual Information in One-Shot
Wednesday, November 12, 2014
Using two examples, we will describe information theoretic quantities such as Shannon Entropy, Relative Entropy and Mutual Information.
Example 1: We have a pair of random variables (X,Y) taking values in S x T. One party (the Sender) is given a value x in S chosen according to the distribution of X and needs to ensure that the other party (he Receiver) gets a value y in T so that (x,y) have the same distribution as (X,Y). How many bits on average must the Sender send the Receiver?
Example 2: There is one Sender and there two Receivers talking over a noisy channel: the sender feeds a letter into the channel and the two receivers receive something in response. How efficiently can the Sender communicate with the receivers?
In Example 1, we will obtain an operational one-shot meaning for Shannon's Mutual Information. In Example 2, we will obtain a one-shot version of Marton's bound.
We will assume no prior background in information theory.
(Based on joint work with David McAllester, Prahladh Harsha, Rahul Jain, Pranab Sen and Naqueeb Warsi.)