On 10/19/2012 10:54 AM, Stephen P. King wrote:
Hi,I was looking up a definition and found the following: http://en.wikipedia.org/wiki/Minimum_description_length"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."Is this true? Would it be an approach to the measure problem of COMP?
Although the display math didn't show up above, I looked at the site. I'm not clear on what x refers to in P(x) and C(x). Is it the data being fitted, so in the coin tossing example x is a sequence, e.g. x={HHTTHHTHTT} and P(x) is the probability of various possible sequences, i.e. ignoring order but not length, it's the binomial distribution? Then C(x) would be the length of the code to produce/describe a particular sequence x? So a sequence {HHHHHHHHHHH} would have a shorter code than {TTHHTHTHTHTHH} - but ex hypothesi they both have the same probability? What am I missing?
Brent -- You received this message because you are subscribed to the Google Groups "Everything List" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/everything-list?hl=en.
