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:
“Only in Britain could it be thought a defect to be “too clever by half.” The probability is that too many people are too stupid by three-quarters.”
—John Major (b. 1943)
“Today it is not the classroom nor the classics which are the repositories of models of eloquence, but the ad agencies.”
—Marshall McLuhan (1911–1980)
“Man is more disposed to domination than freedom; and a structure of dominion not only gladdens the eye of the master who rears and protects it, but even its servants are uplifted by the thought that they are members of a whole, which rises high above the life and strength of single generations.”
—Karl Wilhelm Von Humboldt (1767–1835)
“Of all the inhabitants of the inferno, none but Lucifer knows that hell is hell, and the secret function of purgatory is to make of heaven an effective reality.”
—Arnold Bennett (1867–1931)