Probability Models and The Kolmogorov Structure Function
For every computable probability distribution P it can be proved that . For example, if P is the uniform distribution on the set S of strings of length n, then each has probability . In the general case of computable probability mass functions we incur a logarithmic additive error term. Kolmogorov's structure function becomes
where x is a binary string of length n with where P is a contemplated model (computable probability of n-length strings) for x, is the Kolmogorov complexity of P and is an integer value bounding the complexity of the contemplated P's. Clearly, this function is nonincreasing and reaches for where c is the required number of bits to change x into and is the Kolmogorov complexity of x. Then . For every complexity level the function is the Kolmogorov complexity version of the maximum likelihood (ML).
Read more about this topic: Kolmogorov Structure Function
Famous quotes containing the words probability, models, structure and/or function:
“The probability of learning something unusual from a newspaper is far greater than that of experiencing it; in other words, it is in the realm of the abstract that the more important things happen in these times, and it is the unimportant that happens in real life.”
—Robert Musil (1880–1942)
“... your problem is your role models were models.”
—Jane Wagner (b. 1935)
“The structure was designed by an old sea captain who believed that the world would end in a flood. He built a home in the traditional shape of the Ark, inverted, with the roof forming the hull of the proposed vessel. The builder expected that the deluge would cause the house to topple and then reverse itself, floating away on its roof until it should land on some new Ararat.”
—For the State of New Jersey, U.S. public relief program (1935-1943)
“The information links are like nerves that pervade and help to animate the human organism. The sensors and monitors are analogous to the human senses that put us in touch with the world. Data bases correspond to memory; the information processors perform the function of human reasoning and comprehension. Once the postmodern infrastructure is reasonably integrated, it will greatly exceed human intelligence in reach, acuity, capacity, and precision.”
—Albert Borgman, U.S. educator, author. Crossing the Postmodern Divide, ch. 4, University of Chicago Press (1992)