Minimum Description Length - MDL Notation

MDL Notation

Central to MDL theory is the one-to-one correspondence between code length functions and probability distributions. (This follows from the Kraft-McMillan inequality.) For any probability distribution, it is possible to construct a code such that the length (in bits) of is equal to ; this code minimizes the expected code length. Vice versa, given a code, one can construct a probability distribution such that the same holds. (Rounding issues are ignored here.) In other words, searching for an efficient code reduces to searching for a good probability distribution, and vice versa.