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)
“Grandparents can be role models about areas that may not be significant to young children directly but that can teach them about patience and courage when we are ill, or handicapped by problems of aging. Our attitudes toward retirement, marriage, recreation, even our feelings about death and dying may make much more of an impression than we realize.”
—Eda Le Shan (20th century)
“Women over fifty already form one of the largest groups in the population structure of the western world. As long as they like themselves, they will not be an oppressed minority. In order to like themselves they must reject trivialization by others of who and what they are. A grown woman should not have to masquerade as a girl in order to remain in the land of the living.”
—Germaine Greer (b. 1939)
“Literature does not exist in a vacuum. Writers as such have a definite social function exactly proportional to their ability as writers. This is their main use.”
—Ezra Pound (1885–1972)