Three Problems in Computable Probability Theory
summary
Proves that an exchangeable sequence with a computable law yields a computable mixing measure via effective moment approximations and uniform procedures; shows the two‑dimensional Aldous–Hoover generalization can fail: some exchangeable arrays are not almost everywhere computable though they remain samplable, and under mild assumptions the representing function is only computably measurable; constructs joint distributions whose disintegration encodes the halting problem, so conditioning can be non‑computable even for absolutely continuous joints.
AI-written summary · about
chapters (6)
- 0:00Introduction to the topic
- 1:41De Finetti's theorem
- 15:50Computability notions
- 29:11Higher dimensional arrays
- 39:24Conditional distributions
- 46:16Q&A and concluding remarks
related talks
29mA Pre-Expectation Calculus for Probabilistic Sensitivity
20mWhat do posterior distributions of probabilistic programs look like?
24mHigher order programming with probabilistic effects: A model of stochastic memo...
47mUnprovability and Other Impossibility Results in Machine Learning
01h 12mLearning probability distributions; what can, what can't be done
11mProbabilistic Programming Meets Automata Theory: Exact Inference using Weighted Automata
18mCompositional imprecise probability: a solution from graded monads and Markov categories
20mInference of Probabilistic Programs with Moment-Matching Gaussian Mixtures