Induction: from Kolmogorov and Solomonoff to de Finetti and back to Kolmogorov.

*(English)*Zbl 1089.60006Summary: This paper compares the solutions to “the induction problem” by Kolmogorov, de Finetti, and Solomonoff. Brief sketches of the intellectual history of de Finetti and Kolmogorov are also composed. Kolmogorov’s contributions to information theory culminated in his notion of algorithmic complexity. The development of algorithmic complexity was inspired by information theory and randomness. Kolmogorov’s best-known contribution was the axiomatization of probability in 1933. Its influence on probability and statistics was swift, dramatic, and fundamental. However, Kolmogorov was not satisfied by his treatment of the frequency aspect of his creation. This in time gave rise to Kolmogorov complexity.

De Finetti, on the other hand, had a profound vision early in his life which was encapsulated in his exchangeability theorem. This insight simultaneously resolved a fundamental philosophical conundrum – Hume’s problem, and provided the bricks and mortar for de Finetti’s constructive probabilistic theory. Most of his subsequent research involved extensions of his representation theorem. De Finetti was against determinism and celebrated quantum theory, while Kolmogorov was convinced that in every seemingly indeterministic manifestation there lurked a hidden deterministic mechanism. Solomonoff introduced algorithmic complexity independently of Kolmogorov and Chaitin. Solomonoff’s motivation was firmly focused on induction. His interest in induction was to a marked extent sparked by Keynes’ 1921 seminal book. This interest in induction has never faltered, remaining prominent in his most recent research.

The decisive connection between de Finetti and Kolmogorov was their lifelong interest in the frequency aspect of induction. Kolmogorov’s solution to the problem was algorithmic complexity. De Finetti’s solution to his frequency problem occurred early in his career with the discovery of the representation theorem. In this paper, we try to explain these solutions and mention related topics which captured the interest of these giants.

De Finetti, on the other hand, had a profound vision early in his life which was encapsulated in his exchangeability theorem. This insight simultaneously resolved a fundamental philosophical conundrum – Hume’s problem, and provided the bricks and mortar for de Finetti’s constructive probabilistic theory. Most of his subsequent research involved extensions of his representation theorem. De Finetti was against determinism and celebrated quantum theory, while Kolmogorov was convinced that in every seemingly indeterministic manifestation there lurked a hidden deterministic mechanism. Solomonoff introduced algorithmic complexity independently of Kolmogorov and Chaitin. Solomonoff’s motivation was firmly focused on induction. His interest in induction was to a marked extent sparked by Keynes’ 1921 seminal book. This interest in induction has never faltered, remaining prominent in his most recent research.

The decisive connection between de Finetti and Kolmogorov was their lifelong interest in the frequency aspect of induction. Kolmogorov’s solution to the problem was algorithmic complexity. De Finetti’s solution to his frequency problem occurred early in his career with the discovery of the representation theorem. In this paper, we try to explain these solutions and mention related topics which captured the interest of these giants.

##### MSC:

60-03 | History of probability theory |

68Q30 | Algorithmic information theory (Kolmogorov complexity, etc.) |

60A05 | Axioms; other general questions in probability |

01A60 | History of mathematics in the 20th century |

PDF
BibTeX
XML
Cite

\textit{J. J. McCall}, Metroeconomica 55, No. 2--3, 195--218 (2004; Zbl 1089.60006)

Full Text:
DOI

##### References:

[1] | Aldous D. J., American Math Monthly 93 pp 333– (1986) |

[2] | E. S. Andersen (1953 ): ’On the fluctuations of sums of random variables, 1 and 2 ’, Mathematika Scandinavia, 1 , 263 -85 ; 1 , 263 -85 . · Zbl 0053.09701 |

[3] | Baxter G., Zeitschrift fur Wahvscheinlich keits theorie 1 pp 263– (1963) |

[4] | Bernardo J. M., Bayesian Theory (1994) · doi:10.1002/9780470316870 |

[5] | Blackwell D., Annals of Statistics 1 pp 353– (1973) |

[6] | Bollobas B., Probabilistic Combinatorics and Its Applications (1991) · doi:10.1090/psapm/044 |

[7] | Breiman L., Probability (1968) |

[8] | Bremaud P., Markov Chains (1999) · Zbl 0949.60009 · doi:10.1007/978-1-4757-3124-8 |

[9] | Cover T. M., Annals of Probability 17 pp 840– (1989) |

[10] | Dawid A. P., Bayesian Statistics 4 (1992) |

[11] | Diaconis P., Annals of Probability 8 pp 115– (1980) |

[12] | Dobrushin R. L., Russian Mathematical Surveys 43 pp 157– (1988) |

[13] | O. Dubois, R. Monasson, B. Selman, and R. Zecchina (eds) (2001 ): Theoretical Computer Science, 265 , 1 , pp. 1 -75 . |

[14] | Dynkin E. B., Annals of Probability 6 pp 705– (1978) |

[15] | Dynkin E. B., Annals of Probability 17 pp 822– (1989) |

[16] | de Finetti B., Probability, Induction and Statistics: the Art of Guessing (1972) · Zbl 0275.60001 |

[17] | de Finetti B., Theory of Probability 1 (1974) · Zbl 0328.60002 |

[18] | DOI: 10.1006/tpbi.1999.1421 · Zbl 0928.92019 · doi:10.1006/tpbi.1999.1421 |

[19] | Gacs P., Soviet Mathematic Dokl. ady 15 pp 1477– (1974) |

[20] | Galavotti M. C., Erkenntnis 31 pp 238– (1989) |

[21] | Galavotti M. C., Theoria 62 (3) pp 239– (1989) |

[22] | Geweke J., Econometrica 57 pp 1317– (1989) |

[23] | Geweke J., Econometric Reviews 18 pp 1– (1999) · Zbl 0930.62105 |

[24] | Gillman L., American Mathematics Monthly 99 pp 3– (1992) |

[25] | Hill B. M., Aspects of Uncertainty (1994) |

[26] | Kallenberg O., Zeitshrift fur Wahrscheinlichkeitstheorie verwendte Gebiete 27 pp 23– (1973) |

[27] | Kelly F. P., Reversibility and Stochastic Networks (1979) |

[28] | Kingman J. F. C., Annals of Probability 6 pp 183– (1978) |

[29] | DOI: 10.1016/0020-0190(92)90040-3 · Zbl 0742.68035 · doi:10.1016/0020-0190(92)90040-3 |

[30] | A. N. Kolmogorov (1933 ): Foundations of the Theory of Probability; reprinted Chelsea, 1950. · Zbl 0074.12202 |

[31] | Kolmogorov A. N., Sankhya 25 pp 369– (1963) |

[32] | Kolmogorov A. N., Mathematics: Its Content, Methods, and Meaning 2 (1963) |

[33] | Kolmogorov A. N., Russian Mathematical Surveys 38 pp 27– (1983) |

[34] | Kolmogorov A. N., Theory of Probability and its Applications 32 pp 389– (1987) |

[35] | Kreps D. M., Notes on the Theory of Choice (1988) |

[36] | Lad F., Operational Subjective Statistical Methods (1996) · Zbl 0862.62005 |

[37] | Lad F., Statistica 1 pp 19– (1990) |

[38] | Li M., An Introduction to Kolmogorov Complexity and Its Applications (1997) · Zbl 0866.68051 · doi:10.1007/978-1-4757-2606-0 |

[39] | Mengersen K. L., Bayesian Statistics 6 pp 415– (1999) |

[40] | DOI: 10.1016/S0304-3975(01)00153-0 · Zbl 0983.68076 · doi:10.1016/S0304-3975(01)00153-0 |

[41] | DOI: 10.1016/S0304-4149(99)00119-2 · Zbl 1045.62006 · doi:10.1016/S0304-4149(99)00119-2 |

[42] | von Plato J., Creating Modern Probability (1994) · doi:10.1017/CBO9780511609107 |

[43] | Poirier D. J., Journal of Economic Perspectives 2 pp 121– (1988) · doi:10.1257/jep.2.1.121 |

[44] | Port S. C., Journal of Mathematical Analysis and Applications 6 pp 109– (1963) |

[45] | Ramsey F. P., Studies in Subjective Probability (1980) |

[46] | Ryll-Nardzewski, Coll. Math. 4 pp 149– (1955) |

[47] | Schwartz E. S., Real Options and Investment Under Uncertainty (2001) |

[48] | Shiryaev A. N., Annals of Probability 17 pp 866– (1989) |

[49] | Sinai Y. G., Annals of Probability 17 pp 833– (1989) |

[50] | Solomonoff R. J., Information and Control 7 pp 1– (1964) |

[51] | Takacs L., Combinatorial Methods in the Theory of Stochastic Processes (1967) · Zbl 0162.21303 |

[52] | Velupillai K., Computable Economics (2000) · Zbl 1007.91001 · doi:10.1093/0198295278.001.0001 |

[53] | S. G. Walker, P. Damien, P. W. Laud, and A. F. Smith (1999 ): ’Bayesian nonparametric inference for random distributions and related functions ’, Journal of the Royal Statistical Society B, Part 3, pp. 485 -27 . · Zbl 0983.62027 |

[54] | Young J. Z., Philosophy and the Brain (1988) |

[55] | Zellner A., American Statistician 42 pp 278– (1988) |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.