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)
“Friends broaden our horizons. They serve as new models with whom we can identify. They allow us to be ourselves—and accept us that way. They enhance our self-esteem because they think we’re okay, because we matter to them. And because they matter to us—for various reasons, at various levels of intensity—they enrich the quality of our emotional life.”
—Judith Viorst (20th century)
“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)
““... The state’s one function is to give.
The bud must bloom till blowsy blown
Its petals loosen and are strown;
And that’s a fate it can’t evade
Unless ‘twould rather wilt than fade.””
—Robert Frost (1874–1963)