A short introduction to information theory and Bayesian Model Averaging
Olivier Catoni · 2012
1. Information theory and lossless codes 1.1. Binary codes. Let us consider a finite alphabet A and a random sequence (Xn) ∞ n=1 taking its values in A. (The alphabet can be any finite set here.) Let {0, 1} ∗ = ⋃ ∞ n=1 {0, 1}n be the set of finite binary sequences. Definition 1.1 Given some block length n, a binary code c is an injective map from A n to {0, 1} n. The mean length of c is E { ℓ [ c(X n)]}, where the expectation is taken with respect to the distribution of the sequence n def X = (X1,..., Xn) and where the length function ℓ is defined as ℓ(w) = k for any w ∈ {0, 1} k. Minimizing the mean code length under various assumptions on the source and the set of authorized codes is the main subject of lossless coding theory. 1.2. Optimal code length for a known source. In the case when PXn (the distribution of Xn = (X1,..., Xn)) is known and c is arbitrary, minimizing the code length is achieved by sorting An in order of decreasing probabilities. More precisely, let us write An = {bi, i = 1,..., dn}, where d = |A | is the size of the alphabet and where the blocks of n letters are indexed by order of decreasing probabilities: PX n(bi) ≤ PX n(bi−1), i = 2,..., d n. Let us sort {0, 1} ∗ by order of increasing lengths, writing {0, 1} ∗ = { w(j), j ∈ N \\ {0} },