« Home

Menu

List of Publications
Blog
Problems that haunt me

Definition Coinflip Markov Category [efr-VTCS]

November 27, 2025
Eigil Fjeldgren Rischel

A coinflip Markov category is a Markov category which admits a coinflip structure.

Context

Midpoint algebras and Coinflips [efr-AHFX]

November 8, 2025
Eigil Fjeldgren Rischel

We will not have any hope of giving a universal property for $\mathsf {BorelStoch}$ , or any interesting Markov category, without some property that forces certain maps to be nondeterministic. We now give such a structure. As mentioned, our basic idea will be to impose the existence of a "unbiased binary random choice". In a general Markov category, this choice forms a morphism $A \otimes A \to A$ . The axioms that such a choice must satisfy are essentially the axioms described by Escardo and Simpson in Reference [escardo-simpson-universal-interval-2001], which they termed midpoint algebras. The main theorem of their paper is a characterization of the interval $[0,1]$ as the free iterable (Definition [efr-JP37]) midpoint algebra on two points—this will play a central role in this paper.

Definition Midpoint algebra [efr-6W7X]

October 23, 2025
Eigil Fjeldgren Rischel

Let $\mathcal {C}$ be a Cartesian category. Then a midpoint algebra is an object $A$ equipped with $m: A \times A \to A$ , so that: $m(a,a) = a$ $m(a,b) = m(b,a)$ $m(m(a,b),m(c,d)) = m(m(a,c), m(b,d))$

We will call a homomorphism of midpoint algebras (a morphism satisfying $m(f(a),f(a')) = f(m(a,a'))$ ) a midpoint homomorphism

Definition Internal midpoint algebra [efr-1XB5]

November 5, 2025
Eigil Fjeldgren Rischel

Let $\mathcal {C}$ be any category. An internal midpoint algebra structure on an object $A \in \mathcal {C}$ is a family of midpoint algebra structures on each $\mathcal {C}(X,A)$ , so that precomposition is a midpoint homomorphism for every $f: Y \to X$ .

Note that if $\mathcal {C}$ is Cartesian this agrees with the above definition.

Definition Coinflip structure [efr-QBVU]

October 23, 2025
Eigil Fjeldgren Rischel

Let $\mathcal {C}$ be a Markov category. A coinflip structure is a internal midpoint algebra structure on each $A \in \mathcal {C}$ , which is natural in $A$ . In other words, it is a midpoint algebra structure on each homset $\mathcal {C}(X,Y)$ so that both pre- and postcomposition are midpoint homomorphisms.

Proposition [efr-OX26]

October 31, 2025
Eigil Fjeldgren Rischel

Let $\mathcal {C}$ be a Markov category. Then every coinflip structure on $\mathcal {C}$ is equal.

Proof

October 31, 2025
Eigil Fjeldgren Rischel

Let $m_1,m_2$ denote two coinflip structures. Let $\mu _1 = m_1(\pi _1, \pi _2) : A \otimes A \to A$ , analogously $\mu _2$ (we condense the notation by writing $\mu _1,\mu _2$ regardless of the object in question). Note $m_1(a,b) = \mu _1\langle a,b \rangle$ , where $\langle a,b \rangle$ is any pairing of $a,b$ , by naturality.

First consider $m_1(m_2(a,b),m_2(c,d))$ . By the above this is $\mu _1 \langle \mu _2 \langle a,b \rangle , \mu _2 \langle c,d \rangle \rangle$ . Applying naturality to the morphism $\mu _2$ , we can also rewrite this as $\mu _2 \circ (m_1(\langle a,c \rangle ,\langle b,d \rangle ))$

Now take $c = b, d = a$ . By symmetry for $m_2$ we can rewrite the left-hand side as $m_1(m_2(a,b),m_2(a,b))$ . By idempotency this is simply $m_2(a,b)$ . The other expression now becomes $\mu _2 \circ (m_1(\langle a,b \rangle ,\langle b,a \rangle ))$ . Now consider the first projection of the map $m_1(\langle a,b \rangle ,\langle b,a \rangle )$ . By naturality it is equal to $m_1(a,b)$ . By symmetry, so is the second projection. Hence this is a pairing of $m_1(a,b)$ with itself. Hence the composite is equal to $m_2(m_1(a,b),m_1(a,b)) = m_1(a,b)$ . This concludes the proof.

Definition Coinflip Markov Category [efr-VTCS]

November 27, 2025
Eigil Fjeldgren Rischel

A coinflip Markov category is a Markov category which admits a coinflip structure.

Note that any coinflip structure is determined by the family of maps $m(\pi _0,\pi _1) : A \otimes A \to A$ . To define a coinflip structure, such a family $\mu _A$ must satisfy the equations of a midpoint algebra, be natural in $A$ , and have the further property that $\mu _A f = \mu _A (\pi _0 f, \pi _1 f)$ (that is, the composite depends only on the projections of $f$ ).

Coinflip structures are not preserved by all Markov functors, since $F(\mu _A)$ only has to enjoy the above property with respect to maps in the image of $F$ . However, as we now show, this is true in the distributive case.

Definition Coinflip in a Markov category [efr-0XH9]

October 28, 2025
Eigil Fjeldgren Rischel

Let $\mathcal {C}$ be a Markov category with finite coproducts. A coinflip in $\mathcal {C}$ is a morphism $f: I \to I + I$ obeying the following equations:

Symmetry: $\tau _{I,I} f = f$ , where $\tau _{A,B} :A + B \to B + A$ is the canonical isomorphism.
Interchange: $(f + f)f = (I + \tau _{I,I} + I)(f + f)f$

Given a coinflip in a distributive Markov category, there is a canonical induced natural transformation $A \otimes A \to A$ , which makes every $A \in \mathcal {C}$ into a midpoint algebra.

Proposition [efr-V3JG]

October 29, 2025
Eigil Fjeldgren Rischel

Let $\mathcal {C}$ be a distributive Markov category. Any two coinflips in $\mathcal {C}$ coincide. In particular, any Markov functor $\mathcal {C} \to \mathcal {D}$ which preserves these finite coproducts also preserves the coinflip.

Proof

October 29, 2025
Eigil Fjeldgren Rischel

Let $f$ be a coinflip. Consider the map $2 \xrightarrow {\oplus f} 2$ given by flipping the coin, applying $\neg : 2 \to 2$ in one branch and doing nothing in the other. We claim this is equal to deletion followed by the coinflip. This can be checked on each summand (since $2$ is a coproduct), where it follows by symmetry.

Now let $f_1, f_2$ be two coinflips and consider the operation given by $1 \xrightarrow {f_1 \otimes f_2} 2 \otimes 2 \xrightarrow {\oplus }$ . This is easily seen to be equal both to $f_1 ; (\oplus f_2)$ and $f_2 ; (\oplus f_1)$ . But these are equal to $f_2$ and $f_1$ respectively by the above.

Note that any coinflip $I \to I + I$ in a distributive Markov category induces a coinflip structure, and vice versa. Since both notions are unique, this is obviously a 1-1 correspondence. From this we easily derive the following:

Corollary [efr-7QV9]

November 5, 2025
Eigil Fjeldgren Rischel

Let $\mathcal {C}, \mathcal {D}$ be distributive coinflip Markov categories, and suppose $F: \mathcal {C} \to \mathcal {D}$ is a Markov functor which preserves coproducts and the monoidal unit. Then $F$ also preserves the coinflip structure.

The terminology "midpoint algebra" is from Reference [escardo-simpson-universal-interval-2001]. In that paper, Escardo and Simpson provide a characterization of the interval as the free midpoint algebra satisfying certain properties generated by two points. The key property is the following:

Escardo and Simpson introduced the following notion:

Definition Iterable midpoint algebra [efr-JP37]

November 5, 2025
Eigil Fjeldgren Rischel

A midpoint algebra $(A,m)$ in $\mathcal {C}$ is iterable if, for each $s: X \to X \times A \in \mathcal {C}$ , there is a unique $u : X \to A$ so that the diagram

If $A$ is an internal midpoint algebra in a category $\mathcal {C}$ , a priori, the only version of Definition [efr-JP37] we can impose is that all the midpoint algebras $\mathcal {C}(X,A)$ are iterable (in $\mathsf {Set}$ ). However, if $\mathcal {C}$ is Markov, we can alternatively demand the following (which is just Definition [efr-JP37] with tensor products instead of products):

Definition Internally iterable [efr-87W1]

November 5, 2025
Eigil Fjeldgren Rischel

Let $\mathcal {C}$ be a Markov category, let $A$ be an object, and let $m$ be a midpoint algebra on $A$ , i.e a midpoint algebra structure on each $\mathcal {C}(X,A)$ , natural in $X$ . Then $A$ is internally iterable if, for each $X \to X \otimes A \in \mathcal {C}$ , there exists a unique map $u: X \to A$ satisfying $u = m(u \pi _X, \pi _A)s$

In this case we might call $u$ an iteration operator for $s$ .

Definition [efr-Z9IU]

October 29, 2025
Eigil Fjeldgren Rischel

Let $\mathcal {C}$ be a coinflip Markov category. Then it is called externally iterable if the midpoint algebras $\mathcal {C}(X,Y)$ are all iterable in $\mathsf {Set}$ . It is said to be internally iterable if they are all internally iterable.

Escardo and Simpson's theorem is that the set $[0,1]$ is the free iterable, cancellative (i.e satisfying $m(a,b) = m(a,c) \Rightarrow b = c$ ) midpoint algebra on two generators. We now strengthen their theorem by proving that it is free among merely iterable midpoint algebras (since it cancellative, this implies their statement).

Lemma [efr-CZUI]

October 29, 2025
Eigil Fjeldgren Rischel

In $\mathsf {Set}$ , the free iterable midpoint algebra on two generators $0,1$ is $[0,1]$ . That is, given an iterable midpoint algebra $A$ and two points $a_0, a_1$ , there exists a unique midpoint homomorphism $f: [0,1] \to A$ so that $f(0)=a_0, f(1)=a_1$ .

Proof

October 29, 2025
Eigil Fjeldgren Rischel

Let $A$ be an iterable midpoint algebra. Note that any map $f: [0,1] \to A$ must be a homomorphism for the infinitary midpoint operator $M$ . Hence given $a_0,a_1 \in A$ , the unique $f$ so that $f(0) = a_0, f(1) = a_1$ is given by $f(0.b_1b_2 \dots ) = M(a_{b_1}, \dots )$ . This is straightforwardly seen to be well-defined and a midpoint homomorphism.

Lemma [efr-JB06]

October 29, 2025
Eigil Fjeldgren Rischel

Let $X$ be a possibly infinite set. Then the infinitary simplex $\bar {\Delta }(X) = \{ (a_x \geq 0)_{x \in X} \mid \sum a_x = 1 \}$ is the free iterable midpoint algebra on $X$ .

Proof

October 29, 2025
Eigil Fjeldgren Rischel

We identify the elements of $\bar {\Delta }(X)$ with countably supported probability measures on $X$ . Observe that $\bar {\Delta } X$ is an iterable midpoint algebra (with the infinitary choice operation given by the sum $M((a_i)) = \sum _i 1/2^i a_i$ ). By the preceding, every finitely supported measure can be obtained by iterating $M$ , and every countably supported measure can be obtained by applying $M$ to a sequence of these (half of the probability measure must be concentrated in some finite subset, then $1/4$ of the remainder again in some finite subset, and so on). Hence there is at most one midpoint homomorphism $\bar {\Delta }X \to Y$ extending any given function $f: X \to Y$ , for any iterable midpoint algebra $Y$ .

Now we must show that one exists. By a finitary dyadic measure, we mean one which is finitely supported and where each weight $a_x$ has the form $k/2^n$ . Note that these are exactly those that can be written using just the binary choice operator $m(x,y)$ . Also note that any two such terms are equal in a generic midpoint algebra if and only if they represent the same such measure. Hence given $f: X \to Y$ , there is a unique and well-defined $f(a)$ defined on the finitary dyadic measures, which is a midpoint homomorphism.

Now for any probability measure $\mu$ , we can write it as $\mu = M(a_1,\dots )$ , where each $a_i$ is a finitary dyadic measure. We define our operation as $f(\mu ) = M(f(a_1), \dots )$ , with $f(a_i)$ defined as above. It suffices to show that this is well-defined, since $f(m(\mu ^1,\mu ^2)) = f(m(M(a_1^1,\dots ),M(a_1^2,\dots ))) =$ $f(M(m(a^1_1,a^2_1), \dots )) = M(m(f(a_1^1),f(a_1^2)),\dots ) = m(f(\mu ^1),f(\mu ^2))$

Now let $M(a_1,\dots ) = M(b_1,\dots ) = \mu$ be two representations in this form of the same measure. Then there exists some smallest $N$ so that there exists a finitary dyadic probability measure $c_1 = \sum _i \frac {k_i}{2^N} \delta _{x_i}$ so that $k_i/2^N < 2 \mu (x_i)$ whenever this is positive - that is, so that $c/2$ is strictly less than $\mu$ everywhere on the support.

Now in the sum $\sum _i 1/2^i a_i$ must exceed $c/2$ by some finite partial sum, say $M$ . Then $\sum ^M_{i=1} 1/2^i a_i$ is a finitary dyadic measure. Hence a finite manipulation using the properties of midpoint algebras can rewrite the term $M(a_1,\dots )$ into $M(c_1,a_2',\dots ,a_M',a_{M+1})$ . Iterating this we build $c_2,\dots$ so that $M(a_1,\dots ) = M(c_1,\dots )$ . Since these only depended on the measure $\mu$ , we similarly find $M(b_1,\dots ) = M(c_1,\dots )$ . Since this argument used only the axioms of an iterable midpoint algebra, it follows that $f$ is well-defined.

Corollary [efr-REOY]

October 31, 2025
Eigil Fjeldgren Rischel

Any iterable midpoint algebra carries the structure of an algebra of $\bar {\Delta }$ . Moreover any midpoint homomorphism between iterable midpoint algebras is a $\bar {\Delta }$ -homomorphism. In particular, if $\mathcal {C}$ is an externally iterable coinflip Markov category, each homset $\mathcal {C}(X,Y)$ is a $\bar {\Delta }$ -algebra, and composition is biconvex (i.e convex in each variable separately). If $\mathcal {C} \to \mathcal {D}$ is a functor between externally iterable coinflip Markov categories which preserves the coinflip (eg if $\mathcal {C}, \mathcal {D}$ are distributive), it automatically preserves this structure.

The situation with coinflip Markov categories is similar to the situation of preadditive categories, known for example from the study of homological algebra. Under mild conditions on a category (admitting finite products and coproducts is sufficient), an enrichment over commutative monoids is unique if it exists.

Proposition [efr-E4WU]

November 3, 2025
Eigil Fjeldgren Rischel

Let $\mathcal {C}$ be a coinflip Markov category. If it is externally iterable, then it is internally iterable.

Proof

November 3, 2025
Eigil Fjeldgren Rischel

Let $s: X \to A \otimes X$ be a map, and suppose $u_1,u_2$ both satisfy the equation $u_i = m(\pi _A s, u_i \pi _X s)$ . Let $a_n : X \to A$ denote the map defined inductively by $a_1 = \pi _A s$ , $a_{n+1} = a_n \pi _X s$ . Let $b_i^{n}$ be defined inductively by $b_i^1 = u_i$ , $b_i^{n+1} = b_i^n \pi _X s$ . Then we see that $b_i^n = m(a_n, b_i^{n+1})$ for both $i=1,2$ . Therefore they must agree, and in particular $u_1 = u_2$ . This concludes the proof.

Proposition [efr-60YW]

November 3, 2025
Eigil Fjeldgren Rischel

Let $\mathcal {C}$ be a coinflip Markov category which is countably distributive. If $\mathcal {C}$ is internally iterable, then it is externally iterable.

Proof

November 3, 2025
Eigil Fjeldgren Rischel

By Reference [escardo-simpson-universal-interval-2001], a midpoint algebra $(A,m)$ in $\mathsf {Set}$ is iterable if and only if is satisfies these conditions:

There exists an operator $M: A^\omega \to A$ so that $M(a_1,a_2, \dots ) = m(a_1, M(a_2, a_3, \dots ))$
Given two sequences $a_i, b_i$ so that $b_i = m(a_i, b_{i+1})$ for all $i$ , then $b_1 = M(a_1, a_2, \dots )$

Let a countable family $f_i : A \to B$ be given. Consider the operation $\sum ^\omega _{i=0} A \to B \times \sum ^\omega A$ given by the copairing of all the $f_i$ paired with the map $\sum ^\omega _{i=0} A \to \sum ^\omega _{i=0} A$ which maps each summand to the next one (i.e $(i,a) \mapsto (i+1,a)$ ). Now an iteration of this map $u: \sum _i A \to B$ is equivalently a sequence of maps $g_i$ so that $g_i = m(f_i,g_{i+1})$ . Hence the existence and uniqueness of such an operator precisely corresponds to points 1 and 2 above.

If the Markov category under consideration has at least countable coproducts, we may therefore simply speak of an iterable coinflip Markov category.

Backlinks

Proposition [efr-AFCK]

December 8, 2025
Eigil Fjeldgren Rischel

Let $\mathcal {C}$ be a Markov category which is countably extensive, Boolean, coinflip, and admits countable Kolmogorov products. Then there is an essentially unique (strong) Markov functor $i: \mathsf {Borel} \to \mathcal {C}$ which preserves pullbacks along monomorphisms and countable Kolmogorov products.

Proof

December 8, 2025
Eigil Fjeldgren Rischel

Since $\mathsf {Borel}$ is Cartesian, any such Markov functor must factor over $\mathcal {C}_\mathrm {det}$ . $\mathcal {C}_\mathrm {det}$ has countable limits (it has countable products by Lemma [efr-OH6B] and pullbacks along monomorphisms, which along with finite products suffices to build equalizers) and is countably extensive and Boolean by assumption. The assumptions on $i$ are equivalent to the factorization $\mathsf {Borel} \to \mathcal {C}_\mathrm {det}$ preserving countable limits and countable coproducts. Hence this uniqueness is exactly Reference [chen-universal-stdborel-2019] theorem 1.1

Theorem [efr-FTTL]

October 30, 2025
Eigil Fjeldgren Rischel

Let $\kappa$ be a regular cardinal. Let $\mathsf {Set}_{\bar {\Delta }}^{< \kappa }$ denote the subcategory of $\mathsf {Set}_{\bar {\Delta }}$ consisting of the sets of cardinality less than $\kappa$ . Then $\mathsf {Set}_{\bar {\Delta }}^{< \kappa }$ is the initial $\kappa$ -distributive, externally iterable, coinflip Markov category. In particular, $\mathsf {FinStoch}$ is the initial distributive, externally iterable, coinflip Markov category, and $\mathsf {Set}_{\bar {\Delta }}$ is the initial small-distributive, externally iterable, coinflip Markov category.