Author Archives: Michael Mislove

Probabilistic Programming and a Domain Theoretic Approach to Skorohod’s Theorem

Skorohod’s Theorem is a fundamental result from stochastic process theory. It makes two assertions:

  1. Any Borel probability measure \mu on a Polish space P can be realized as \mu = X_*\,\lambda for some random variable X\colon [0,1]\to P, where \lambda denotes Lebesgue measure and X_*\, \lambda is the “law of X,” the push forward of \lambda under X.
  2. Moreover, if \mu_n \to_w \mu is a weakly convergent sequence of probability measures on P, then the associated random variables X_n\to_{a.s} X converge almost surely wrt \lambda.

Recently, the author devised a domain-theoretic proof of Skorohod’s Theorem. Since domain theory is a mainstay of denotational semantics, and since Probabilistic Programming concerns modeling probability measures and stochastic processes, it’s reasonable to look for connections between the domain-theoretic proof of Skorohod’s Theorem and the semantics of Probabilistic Programming languages. But there is a difference in how computability is realized in the domain-theoretic approach used to prove Skorohod’s Theorem, versus the standard approach to computable metric spaces and their probability measures:

  • The domain-theoretic model used in the proof of Skorohod’s Theorem is built from topological subsets of the Polish space P. For example, in the case of locally compact spaces, the domain is the family of compact subsets ordered by reverse inclusion. Computability is “implicit” in the domain model, but can be instantiated by an enumeration of a countable basis of the domain, i.e., of a countable neighborhood basis of P that forms a basis for the domain model.
  • In the standard approach, a computable metric space (P,{\mathcal S},d) consists of a Polish space (P,d), a countable subset {\mathcal S}\subseteq P, with the assumption that d\colon {\mathcal S}\times {\mathcal S}\to {\mathbb R}_+ is computable. The computable structure is then lifted to \textsf{Prob}(P) via simple measures with rational coefficients that are concentrated on finite subsets of {\mathcal S}.

This difference can be seen in how computable simple measures are represented. In contrast to the standard approach to computable metric spaces where computable simple measures are concentrated on finite subsets of {\mathcal S}, in the domain-theroetic model, each point mass arising in a computable simple measure has for its mass a subset of the Polish space. Devising an application of the domain-theoretic proof of Skorohod’s Theorem to Probabilistic Programming first requires an understanding of how the computable structure on P and one on the domain model built from appropriate topological susbsets of P are related.

Extended Abstract:

Probabilistic Programming and a Domain Theoretic Approach to Skorohod’s Theorem

Posted in Uncategorized | Leave a comment