Monad Structures on Topological Spaces Comprising Mislove's Random Variables

Technical Summary: Monad Structures on Topological Spaces Comprising Mislove's Random Variables

Problem Statement
The paper addresses the challenge of defining random variables within Domain theory to form monads over categories of topological spaces, specifically targeting non-Hausdorff spaces such as $T_0$ spaces, $d$-spaces, and sober spaces. Previous work by Mislove, Goubault, and Varacca established frameworks for random variables on bounded complete domains but encountered difficulties in forming a monad structure for continuous random variables in certain contexts. Specifically, while Mislove [22] successfully constructed a monad for continuous random variables over bounded complete domains, the resulting structures did not form a monad over the broader category of $T_0$ spaces without additional constraints. The authors aim to resolve Mislove's question regarding the existence of a monad structure for random variables over $T_0$ spaces and to extend these results to $d$-spaces and sober spaces, providing a topological foundation for probabilistic programming semantics.

Methodology
The authors adopt a topological perspective on Mislove's definition of random variables. Their methodology involves the following key steps:

1. Definition of $\sqrt{}$-max Random Variables:
   The authors define a continuous random variable on a $T_0$ space $X$ as a pair $(\mu, f)$, where $\mu$ is a continuous valuation on Mislove's Cantor tree $M$ (a modified Cantor tree including maximal finite elements ending in a token $\sqrt{}$) and $f$ is a partially continuous map from the support of $\mu$ to $X$. Crucially, they impose a $\sqrt{}$-max property on the support of $\mu$: a lower subset $F \subseteq M$ is $\sqrt{}$-max if for every $x\sqrt{} \in F$, $x$ is maximal in $F \cap C$ (where $C$ is the standard Cantor tree). This property is identified as essential for preserving the specialization order under the monad's Kleisli lift.

2. Topological Construction:
   A topology is constructed for the space of $\sqrt{}$-max continuous random variables, denoted $CV^{\sqrt{}}_X$. The topology is generated by a subbase of sets $\langle \uparrow z, r, V \rangle$, where $z \in K(M)$ (compact elements of $M$), $r \in [0, 1)$, and $V \in O_X$. A random variable $(\mu, f)$ belongs to this set if $\mu(\uparrow z) > r$ and $f(z) \in V$. The subspace of normalized $\sqrt{}$-max simple random variables (where $\mu$ has finite support) is denoted $SV^{\sqrt{}}_X$.

3. Monad Construction via Kleisli Triples:
   The authors construct monads using Kleisli triples $(T, e, \star)$ over the categories of $T_0$ spaces ($TOP_0$) and $d$-spaces ($DS$).

   • Unit ($e$): Maps a point $x \in X$ to a simple random variable $(\delta_{\sqrt{}}, \chi_x)$, where $\chi_x$ maps the empty string and $\sqrt{}$ to $x$.
   • Kleisli Lift ($\star$): Defined for simple variables ($\dagger$) and extended to continuous variables ($\ddagger$) via approximation. The lift involves sequential composition of processes modeled as coin-flipping machines. If a process outputs a sequence ending in $\sqrt{}$, a subsequent process can erase the $\sqrt{}$ and continue; otherwise, it halts. The $\sqrt{}$-max property ensures that the resulting support remains well-behaved under this composition.

4. Approximation and Completion:
   The paper establishes that normalized $\sqrt{}$-max continuous random variables can be approximated by normalized $\sqrt{}$-max simple random variables. This is achieved through a chain of projection maps $P^n_X$ that truncate the support of valuations to finite prefixes of the Cantor tree.

Key Contributions and Results

• Monad over $TOP_0$: The space of normalized $\sqrt{}$-max simple random variables, $SV^{\sqrt{}}_1 X$, forms a monad over the category of $T_0$ spaces.
• Monad over $DS$: The space of normalized $\sqrt{}$-max continuous random variables, $CV^{\sqrt{}}_1 X$, forms a monad over the category of $d$-spaces.
• Sobrification and D-completion:
  • If $X$ is a sober space, $CV^{\sqrt{}}_X$ is the sobrification of $SV^{\sqrt{}}_X$. Consequently, $CV^{\sqrt{}}_1 X$ is the sobrification of $SV^{\sqrt{}}_1 X$.
  • If $X$ is a $d$-space, $CV^{\sqrt{}}_X$ is the D-completion of $SV^{\sqrt{}}_X$.
  • The paper proves that $X$ is sober if and only if $CV^{\sqrt{}}_X$ (or $CV^{\sqrt{}}_1 X$) is sober.
• Domain Structure: For a bounded complete domain $L$, the space $CV^{\sqrt{}}_1 \Sigma L$ is itself a bounded complete domain, and its topology coincides with the Scott topology.
• Non-Commutativity: The authors demonstrate that the constructed monads are not commutative. They explicitly calculate the left and right strengths and show that the condition $s^\star \circ t = t^\star \circ s$ does not hold, distinguishing these structures from commutative monads often used in probabilistic semantics.

Significance and Claims
The paper claims to provide a solution to Mislove's question regarding the formation of a monad of continuous random variables over $T_0$ spaces. By introducing the $\sqrt{}$-max property, the authors successfully construct monads over categories of non-Hausdorff spaces, which are viewed as extensions of posets and domains.

The work distinguishes itself from previous approaches (such as Gianantonio and Edalat [2]) by:

1. Interpreting random variables as processes manipulated by a "coin-flipping machine" rather than just push-forwards.
2. Utilizing Mislove's Cantor tree as the sample space, which covers all measures on the Cantor space, rather than fixed finite sample spaces.
3. Including simple random variables as a foundational component that approximates continuous ones, rather than focusing solely on continuous variables.

The authors conclude that their results establish models for stochastic processes and probabilistic automata in a topological setting. They note that while they have not yet established full semantics for these monads, the structural results (particularly the non-commutativity and the completion properties) lay the groundwork for future investigations into distributive laws with non-determinism and core-compactness properties.