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:
“Legends of prediction are common throughout the whole Household of Man. Gods speak, spirits speak, computers speak. Oracular ambiguity or statistical probability provides loopholes, and discrepancies are expunged by Faith.”
—Ursula K. Le Guin (b. 1929)
“The parents who wish to lead a quiet life I would say: Tell your children that they are very naughty—much naughtier than most children; point to the young people of some acquaintances as models of perfection, and impress your own children with a deep sense of their own inferiority. You carry so many more guns than they do that they cannot fight you. This is called moral influence and it will enable you to bounce them as much as you please.”
—Samuel Butler (1835–1902)
“It is difficult even to choose the adjective
For this blank cold, this sadness without cause.
The great structure has become a minor house.
No turban walks across the lessened floors.
The greenhouse never so badly needed paint.”
—Wallace Stevens (1879–1955)
“Uses are always much broader than functions, and usually far less contentious. The word function carries overtones of purpose and propriety, of concern with why something was developed rather than with how it has actually been found useful. The function of automobiles is to transport people and objects, but they are used for a variety of other purposes—as homes, offices, bedrooms, henhouses, jetties, breakwaters, even offensive weapons.”
—Frank Smith (b. 1928)