Linkage

In lieu of serious posting, which will resume in the new year, a few links:

• Several videos of David Blackwell, over at The Inherent Uncertainty
• The (in)famous Witsenhausen counterexample in decentralized control theory now has its own Wikipedia entry (and I think I know who is behind it).
• Emmanuel Abbe, guest-blogging at Combinatorics and More, presents his perspective on Erdal Arikan’s polar codes. Much of what he says makes me think of Terence Tao‘s work on structure and randomness in “large” combinatorial objects.
• Markov decision processes make a surprising appearance in a paper on subexponential lower bounds for certain randomized pivot rules for the simplex algorithm.
• Computation and Control: a new blog by Jerome Le Ny.
• And, last but not least, exorcising Laplace’s demon.

Value of information, Bayes risks, and rate-distortion theory

In the previous post we have seen that access to additional information is not always helpful in decision-making. On the other hand, extra information can never hurt, assuming one is precise about the quantitative meaning of “extra information.” In this post, I will show how Shannon’s information theory can be used to speak meaningfully about the value of information for decision-making. This particular approach was developed in the 1960s and 1970s by Ruslan Stratonovich (of the Stratonovich integral fame, among other things) and described in his book on information theory, which was published in Russian in 1975. As far as I know, it was never translated into English, which is a shame, since Stratonovich was an extremely original thinker, and the book contains a deep treatment of the three fundamental problems of information theory (lossless source coding, noisy channel coding, lossy source coding) from the viewpoint of statistical physics.