definition theorem example

A quasi-Borel space (Heunen, Kammar, Staton & Yang, Definition 7) is a set together with a set of random elements such that

  • whenever and is measurable (reparametrising the randomness);
  • every constant is in (deterministic values are random elements);
  • if with each Borel and , then with for is in (gluing along a countable Borel partition).

A morphism (Definition 11) is a function with for every : it takes random elements to random elements. These form the category . Where measure theory starts from the measurable sets of , a quasi-Borel space starts from the random variables into , all defined on one sample space ; the choice of does not matter, any uncountable standard Borel space gives the same notion (remark after Example 8).

Sources: Heunen, Kammar, Staton & Yang arXiv:1701.02547 (notes) Proposition 6, Definitions 7, 10, 11, Example 8, Propositions 15–18, Theorem 21, Proposition 22, §VI, Theorem 29; Karwowski, Nielsen & Staton arXiv:2610.17886 (notes) Definition 33, Theorem 4.

Why not measurable spaces: no space of functions

Proposition 6 (Aumann). is not cartesian closed: no -algebra on makes evaluation measurable.

So a measurable space of functions does not exist, and a probabilistic program that samples a function (a prior over regression curves, a random neural network, a stochastic process passed as an argument) has no measure-theoretic type. repairs this:

  • Function spaces (Proposition 18): with iff . Evaluation is a morphism, so is cartesian closed (Cartesian Closed Category). Products and coproducts exist too (Propositions 16–17).
  • Measurable spaces sit inside (Example 8, Proposition 15): every measurable space is a quasi-Borel space with its random variables . This gives an Adjunction between and , and is full and faithful on standard Borel spaces: for the spaces of ordinary statistics nothing changes.

Probability measures and the monad

A probability measure on (Definition 10) is a pair of a random element and a probability measure on : a law on the sample space, pushed forward along a random element. Pairs with the same pushforward are identified, giving .

Theorem 21. is a strong monad on . Proposition 22: it is commutative, its functorial action is , and the forgetful extends to a faithful functor from its Kleisli Category to that of the Giry Monad.

Commutativity is what makes a Markov Category: independent samples can be reordered, as in the Giry monad. The new thing is that can now be a function space. §VI of the paper gives Bayesian linear regression: the prior is a probability measure on , the random line with , and the posterior is obtained by observe statements, all as morphisms of . De Finetti’s theorem holds for quasi-Borel spaces in a weak form (Theorem 29).

Relatives

settingspaces of functionsprobability monadused for
no (Proposition 6)Giry Monadfirst-order programs,
yes (Proposition 18) (Theorem 21)higher-order probabilistic programs
diffeological spacesyes—higher-order differentiable programs
DQBS (diffeological quasi-Borel spaces)yes (Karwowski et al., Theorem 4)open problem (their Remark 16)programs that are both; Information Geometry of Probabilistic Programs

A DQBS (Karwowski et al., Definition 33) carries a diffeology and a quasi-Borel structure on the same set, compatibly; the category is complete, cocomplete and cartesian closed (their Theorem 4), which is what lets the information geometry of probabilistic programs reach continuous random variables.

Docs: Julia manual: functions and closures — a probability measure is a random element (a closure over the sample) plus a base law.

# A probability measure on a quasi-Borel space is (α, μ): a random element α : Ω → X and a law μ
# on Ω (Definition 10). Ω is a stream of uniforms (any uncountable standard Borel space will do),
# and splitting it in two is the Borel isomorphism Ω ≅ Ω × Ω that bind needs.
using Random
struct QMeasure{F}; α::F; end                      # μ is fixed: i.i.d. uniforms
sample(m::QMeasure, ω) = m.α(ω)
halves(ω) = (ω[1:2:end], ω[2:2:end])
ret(x) = QMeasure(ω -> x)                          # η: a constant random element
bind(m::QMeasure, k) = QMeasure(ω -> ((ω1, ω2) = halves(ω); sample(k(sample(m, ω1)), ω2)))
normal(μ, σ) = QMeasure(ω -> μ + σ * sqrt(-2log(ω[1])) * cos(2π * ω[2]))   # Box–Muller
 
# §VI: a prior on the FUNCTION SPACE ℝ^ℝ, the random line x ↦ s·x + b, s, b ~ N(0, 3²)
prior = bind(normal(0, 3), s -> bind(normal(0, 3), b -> ret(x -> s * x + b)))
rng = MersenneTwister(1)
lines = [sample(prior, rand(rng, 64)) for _ in 1:100_000]   # each draw is a function
var_at_2 = sum(f(2.0)^2 for f in lines) / length(lines)     # Var[2s + b] = 4·9 + 9 = 45
isapprox(var_at_2, 45; rtol = 0.02)                         # true
f = lines[1]; f(1.0) - f(0.0) ≈ f(3.0) - f(2.0)             # a line: true
import Mathlib
 
/-- Heunen–Kammar–Staton–Yang, Definition 7: a quasi-Borel space on `X`. -/
structure QBS (X : Type*) where
  M : Set (ℝ → X)
  comp_mem : ∀ α ∈ M, ∀ f : ℝ → ℝ, Measurable f → α ∘ f ∈ M
  const_mem : ∀ x : X, (fun _ => x) ∈ M
  glue_mem : ∀ (S : ℕ → Set ℝ) (α : ℕ → ℝ → X), (∀ i, MeasurableSet (S i)) →
    Pairwise (Function.onFun Disjoint S) → (⋃ i, S i) = Set.univ → (∀ i, α i ∈ M) →
    ∀ β : ℝ → X, (∀ i, ∀ r ∈ S i, β r = α i r) → β ∈ M
 
/-- Definition 11: a morphism takes random elements to random elements. -/
def QBS.IsHom {X Y : Type*} (A : QBS X) (B : QBS Y) (f : X → Y) : Prop :=
  ∀ α ∈ A.M, f ∘ α ∈ B.M
 
/-- Example 8: a measurable space is a quasi-Borel space whose random elements are its
random variables. -/
def QBS.ofMeasurableSpace (X : Type*) [MeasurableSpace X] : QBS X where
  M := {α | Measurable α}
  comp_mem := fun _ hα _ hf => hα.comp hf
  const_mem := fun _ => measurable_const
  glue_mem := by
    intro S α hS _ hcov hα β hβ t ht
    have h : β ⁻¹' t = ⋃ i, S i ∩ α i ⁻¹' t := by
      ext r
      simp only [Set.mem_preimage, Set.mem_iUnion, Set.mem_inter_iff]
      constructor
      · intro hr
        obtain ⟨i, hi⟩ := Set.mem_iUnion.1 (hcov ▸ Set.mem_univ r)
        exact ⟨i, hi, by rwa [← hβ i r hi]⟩
      · rintro ⟨i, hi, hr⟩
        rwa [hβ i r hi]
    rw [h]
    exact MeasurableSet.iUnion fun i => (hS i).inter (hα i ht)
 
/-- Proposition 15(1) in one direction: a measurable map is a morphism. -/
theorem QBS.isHom_of_measurable {X Y : Type*} [MeasurableSpace X] [MeasurableSpace Y]
    {f : X → Y} (hf : Measurable f) :
    (QBS.ofMeasurableSpace X).IsHom (QBS.ofMeasurableSpace Y) f :=
  fun _ hα => hf.comp hα
-- Probability measures on quasi-Borel spaces as random elements of one sample space
-- (Definition 10); bind splits the sample space, Ω ≅ Ω × Ω. Functions are ordinary values.
data Omega = Omega Double Omega                  -- an infinite stream of uniforms
 
newtype P x = P { runP :: Omega -> x }
 
splitO :: Omega -> (Omega, Omega)
splitO (Omega a (Omega b rest)) = let (l, r) = splitO rest in (Omega a l, Omega b r)
 
instance Functor P where fmap f (P a) = P (f . a)              -- [α, μ] ↦ [f ∘ α, μ]
instance Applicative P where
  pure x = P (const x)
  pf <*> px = pf >>= \f -> fmap f px
instance Monad P where
  P a >>= k = P (\w -> let (w1, w2) = splitO w in runP (k (a w1)) w2)
 
uniform :: P Double
uniform = P (\(Omega u _) -> u)
 
normal :: Double -> Double -> P Double                         -- Box–Muller
normal m s = do
  u <- uniform
  v <- uniform
  return (m + s * sqrt (-2 * log u) * cos (2 * pi * v))
 
prior :: P (Double -> Double)                                  -- §VI: a measure on ℝ^ℝ
prior = do
  s <- normal 0 3
  b <- normal 0 3
  return (\x -> s * x + b)
 
-- a deterministic stream of pseudo-uniforms, to run it without a random library
stream :: Int -> Omega
stream seed = go seed
  where go k = let k' = (1103515245 * k + 12345) `mod` 2147483648
               in Omega ((fromIntegral k' + 0.5) / 2147483648) (go k')
 
main :: IO ()
main = do
  let fs = [ runP prior (stream k) | k <- [1 .. 20000] ]
  print (sum [ f 2 ^ 2 | f <- fs ] / 20000)                   -- ≈ 45 = Var[2s + b]