Kolmogorov Extension, Martingale Convergence, and Compositionality of Processes
| Title | Kolmogorov Extension, Martingale Convergence, and Compositionality of Processes |
| Publication Type | Conference Paper |
| Year of Publication | 2016 |
| Authors | Kozen, Dexter |
| Conference Name | Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science |
| Publisher | ACM |
| Conference Location | New York, NY, USA |
| ISBN Number | 978-1-4503-4391-6 |
| Keywords | composability, compositionality, Computing Theory, Kolmogorov extension, Markov processes, martingale convergence, probabilistic computation, pubcrawl |
| Abstract | We show that the Kolmogorov extension theorem and the Doob martingale convergence theorem are two aspects of a common generalization, namely a colimit-like construction in a category of Radon spaces and reversible Markov kernels. The construction provides a compositional denotational semantics for lossless iteration in probabilistic programming languages, even in the absence of a natural partial order. |
| URL | http://doi.acm.org/10.1145/2933575.2933610 |
| DOI | 10.1145/2933575.2933610 |
| Citation Key | kozen_kolmogorov_2016 |