Information-theoretic de Finetti-style theorems

We review information-theoretic approaches to obtaining simple probabilistic representations for sequences of exchangeable random variables. Specifically, we examine information-theoretic proofs of finite versions of de Finetti’s celebrated representation theorem. Such results state, in a quantitative manner, that the joint distribution of the first k of n > k exchangeable random variables is close to a mixture of product distributions. Closeness is measured in terms of the relative entropy and explicit bounds are typically provided. First we review a recent information-theoretic proof a finite de Finetti theorem for binary random variables, and then we give a different, new proof for the case of arbitrary finite alphabets. This second proof is nicely motivated by the Gibbs conditioning principle in connection with statistical mechanics, and it follows along an appealing sequence of steps. The technical estimates required for these steps are obtained via the method of types.A full version of this paper is available online as [23].