# Algebraic Reduction of Hidden Markov Models

Tommaso Grigoletto and Francesco Ticozzi T. Grigoletto and F. Ticozzi are with
the Department of Information Engineering, University of Padova, Via Gradenigo
6, 35131 Padova, Italy. Emails<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

The problem of reducing a Hidden Markov Model (HMM) to a one of smaller
dimension that exactly reproduces the same marginals is tackled by using a
system-theoretic approach, adapted to HMMs by leveraging on a suitable
algebraic representation of probability spaces. We propose two algorithms that
return coarse-grained equivalent HMMs obtained by stochastic projection
operators: the first returns models that reproduce the single-time
distribution of a given output process, while in the second the full (multi-
time) distribution is preserved. The reduction method exploits not only the
structure of the observed output, but also its initial condition, whenever the
latter is known or belongs to a given subclass. Optimal algorithms are derived
for a class of HMM, namely observable ones. In the general case, we propose
algorithms that have produced minimal models for all the examples we analyzed,
and conjecture their optimality.

##  I Introduction

Hidden Markov processes are an ubiquitous class of stochastic models that has
extensive application in modeling and prediction for speech [1, 2], biological
systems [3, 4, 5, 6], information and communication systems [7, 8, 9] and
more.

In the development of the realization theory for HMMs, two related yet well
distinct problems emerged: constructing an HMM from data, and reducing an
existing model, when possible, to an equivalent one of smaller size. For an
analysis and review of the first one, see for example [10, 11], and more
recent results in [12]. In this paper, we shall focus on the reduction
problem. Beside its theoretical interest, methods for model reduction are
critical in effectively addressing problems in large-scale systems [13, 14,
15].

A characterization of equivalent HMMs, that is, models that produce the same
output marginals of a given one, is proposed in [16]. Their treatment of
equivalent HMMs is based on the definition of effective spaces, which specify
equivalence classes of HMMs, representing the HMM analogue of minimal
realizations spaces for linear systems. In the same paper, the authors pose
the problem of finding a minimal equivalent HMM. As a reduction to the
effective space does not guarantee to preserve the positivity of the model,
the problem has so far remained unsolved.

In this paper, we show how effective spaces can be extended so that the
reduced model remains an HMM. In fact, we propose a general approach to the
model reduction problem that is based on an algebraic description of
probability spaces. While this is done very frequently and almost implicitly,
we shall look deeper into the algebraic structures and the associated
representation of probabilistic concepts and tools, in particular minimal
algebraic models that represent a set of random variable (r.v) and conditional
expectations. This approach has been developed to generalize the classical
Kolmogorov description to the non-commutative case so that it suitably covers
quantum mechanics [17, 18, 19], but it has proven useful in many other areas,
from random matrix theory (see, e.g. the insightful introduction [20]) to
algebraic statistics [21]. In our setting, the algebraic framework and the
induced matrix representations allow for a direct translation of the concepts
of observability and reachability, that will be used in the characterization
of equivalent models, as well as a linear-algebraic algorithm that computes
the reduced model. As a consequence, our approach is deeply rooted in the
system-theoretic analysis of the dynamical model and can be seen as a way to
construct reduced stochastic realizations for a HMM.

In what follows, we deal with reductions of a given HMM that exactly reproduce
the marginals of the original systems. This allows us to clearly illustrate
the working and theoretical foundation of the method. The extension to
approximate reduction will be the focus of a forthcoming publication [22].

Similar problems have been studied from different perspectives: in particular,
the concept of lumpability of Markov processes [23], which induces coarse-
grained processes analogous to those presented here, has been employed to
characterize a class of exactly reducible HMMs (2-lumpable systems), see [24]
and references therein. Other works, [25] and references therein, reframe the
problem using cellular automata for hidden information sources, within this
abstract approach and obtain results on how to reduce Markov transition
kernels.

The differences between our approach and the existing results are manifold,
both in the tools used and the nature of results. In the framework we propose,
we introduce and solve two types of reduction problems: preserving only the
single-time marginal, or the full (multi-time) distribution on the outcomes.
We show that the former, which is of interest in model reduction of master
equations for statistical models or mixing processes and algorithms [26], can
lead to further reduction and smaller final models, as one might expect. In
addition, our reductions leverage not only the structure of the measured
process, but also by the particular initial distribution of the HMM. We show
that the initial conditions are indeed critical for obtaining minimal
reductions in many situations, in particular, when the original model is
initialized in an equilibrium density. Lastly, we make direct contact with
system-theoretic ideas in a linear algebraic framework, which allows for
effective, practically implementable algorithms for the reduction process.

The structure of the paper is as follows: In Section II we review the
fundamental facts underlying the algebraic probabilistic models. The approach
is directly borrowed from non-commutative probability [19, 27] and its use in
quantum theory, where the algebras used for embedding the probability space
need not be commutative (and are typically infinite-dimensional [18]), and can
then be used to model quantum systems [17]. In this work, we only use
commutative, finite-dimensional algebras, represented as ${\mathbb{R}}^{n}$
endowed with its element-wise product. Extension to more general cases will be
treated in [28]. Subsection II-B is in particular focused on conditional
expectations as linear maps on algebras, their duals, and their
representations, as they are key tools in development of our method.

Section III is devoted to introducing the notation and the problems of
interest, namely obtaining reduced models that reproduce either the single-
time marginals or the multi-time marginals of a given HMM, while Section IV
presents some preliminary results that extend [16] from an explicit system-
theoretic perspective. The key ideas we leverage to obtain a reduced HMMs are
described in V, where a class of reduction algorithm for the single-time
marginal problem is developed. Section VI then extends and adapts these ideas
to the multi-time marginal problem. A key point in our analysis is that, in
order to develop the algorithms, we must switch from the quotient spaces of
[16] to a representative effective subspace. The freedom in this choice has a
non-trivial effect on the reduction itself. The choices for this and other
parameters used in the algorithms are discussed in Section VII, where we
provide an optimal one for observable HMMs, and propose one for the general
case that proves to be optimal in all the examples we tested. Some
particularly instructive examples are given in Section VIII, and an outlook on
future developments is provided in Section IX.

##  II Algebraic approach to probability theory

The central idea is to represent all the key ingredients of a classical
probabilistic model - events, random variables - as elements of a suitable
algebra $\mathscr{A}$, endowed with a probability functional (or state) $p$.
In the following sections, we will start from a probability space
$(\Omega,\Sigma,{\mathbb{P}})$ and briefly review how to construct its
algebraic representation $(\mathscr{A},p)$. Correspondingly, any pair
$(\mathscr{A},p)$ admits a classical representation. This allows for a natural
probabilistic interpretation of the proposed reduction method.

###  II-A Events and random variables as vectors

Throughout the rest of this article we will consider finite-dimensional
probability spaces $(\Omega,\Sigma,{\mathbb{P}})$. Without loss of generality,
we can assume $\Omega=\\{1,\dots,n\\}$.

The first step in the construction entails the vector representation of
indicator functions, and hence of events. Since the probability space is
finite-dimensional, we can associate indicator functions to vectors in
${\mathbb{R}}^{n}$. In particular, each indicator of an elementary event
$\omega\in\Omega$ can be associated to its corresponding vector of the
standard basis, i.e. $\bm{e}_{\omega}\in{\mathbb{R}}^{n}$. Similarly, we can
define indicator vectors for any event $E\in\Sigma$ as
$\bm{f}_{E}=\sum_{\omega\in E}\bm{e}_{\omega}$. For these vectors,
$(\bm{f}_{E})_{\omega}=1$ if $\omega\in E$ and zero otherwise. Notice that
$\bm{f}_{\Omega}=\bm{1}$, the vector of all ones, and
$\bm{f}_{\emptyset}=\bm{0}$, the vector of all zeros.

Let us denote with $\mathcal{F}_{\Sigma}$ the set of indicator vectors of the
events of the $\sigma$-algebra $\Sigma.$ Let $\wedge$ denote the element-wise
product $(\bm{v}\wedge\bm{w})_{i}=\bm{v}_{i}\bm{w}_{i}$, $\vee$ denote the
modified sum operation defined as
$\bm{v}\vee\bm{w}=\bm{v}+\bm{w}-\bm{v}\wedge\bm{w}$ and $\neg$ denote the
negation operation defined as $\neg\bm{v}=\bm{1}-\bm{v}$. By construction, the
set $\mathcal{F}_{\Sigma}$ equipped with the operations $\wedge,\vee,\neg$ is
isomorphic to the $\sigma$-algebra $\Sigma$ with $\cap,\cup,\overline{\cdot}$.
In the following, we refer to $\mathcal{F}_{\Sigma}$ as a vector
$\sigma$-algebra, and we will drop the subscript when unnecessary.

A vector partition of $\Omega$ is a subset
$\mathcal{P}\subseteq\mathcal{F}\setminus\\{\bm{0}\\}$ such that
$\bm{f}_{i}\wedge\bm{f}_{j}=\bm{0}$, for all
$\bm{f}_{i},\bm{f}_{j}\in\mathcal{P}$, $i\neq j$ and
$\bm{1}=\vee_{\bm{f}_{j}\in\mathcal{P}}\bm{f}_{j}$. The finest resolution of
the identity in $\mathcal{F}$ is a partition ${\rm res}(\mathcal{F})$ such
that $\bm{f}=\vee_{\bm{f}_{j}\in{\rm res}(\mathcal{F})}c_{j}\bm{f}_{j}$ with
$c_{j}\in\\{0,1\\}$, for all $\bm{f}\in\mathcal{F}$.

Note that ${\rm res}(\mathcal{F})$ is not necessarily equal to the standard
basis of $\mathbb{R}^{n}$ since, in general, $\Sigma$ is contained but not
equal to the power set of $\Omega$. We shall also denote ${\rm res}(\Sigma)$
to indicate the finest resolution of a classical $\sigma$-algebra.

Random variables (r.v.) $X$ are defined as $\Sigma$-measurable functions
$X(\omega):\Omega\to\mathbb{A}\subset\mathbb{R}$, where
$\mathbb{A}=\\{x_{i}\\}$ is the finite set of outcomes of $X,$ called the
alphabet. Let $I_{E}(\omega)$ be the indicator function associated with the
event $E$ and $E_{i}=X^{-1}(x_{i})$. An r.v. $X$ can also be represented as
linear combination of indicator function
$X(\omega)=\sum_{i=0}^{|\mathbb{A}|}x_{i}I_{E_{i}}(\omega).$

Using the vector representation of indicator functions in the previous
equation, each $X$ can also be represented as a vector

$\bm{x}=\sum_{i=1}^{|\mathbb{A}|}x_{i}\bm{f}_{i}\in{\mathbb{R}}^{n}$

such that $\\{\bm{f}_{i}\\}\subset\mathcal{F}_{\Sigma}$ forms a partition of
$\Omega$. Notice that in the vector formalism, the notion of
$\mathcal{F}_{\Sigma}$-measurability is equivalent to the condition
$\bm{x}\in{\rm span}\\{\mathcal{F}_{\Sigma}\\}$. Here and elsewhere, the
boldface font $\bm{x}$ is used for r.v.s, while $x$ denotes the corresponding
outcome. As we show below, ${\rm span}\\{\mathcal{F}_{\Sigma}\\}$ has the
property of being an algebra, namely a vector space (or subspace) that is
closed under the element-wise product $\wedge$. An algebra is unital if it
contains $\bm{1}$. The whole ${\mathbb{R}}^{n}$ is then a unital algebra, and
we denote its subalgebras using the script font, e.g. $\mathscr{A}$. Given a
vector $\bm{x}\in\mathbb{R}^{n},$ we define its support as the vector space
${\rm supp}(\bm{x})={\rm span}\\{\bm{e}_{i}|\bm{e}_{i}^{T}\bm{x}\neq 0\\}$.
Given a vector space $\mathcal{V}\subseteq\mathbb{R}^{n}$ its support is the
vector space ${\rm supp}(\mathcal{V})={\rm
span}\\{\bm{e}_{i}|\exists\bm{x}\in\mathcal{V}\text{ s.t
}\bm{e}_{i}^{T}\bm{x}\neq 0\\}$. A non-unital algebra $\mathscr{A}$ still
contains the vector $\bm{1}_{\mathscr{A}},$ which has entries $1$ on the
support of $\mathscr{A}$ and $0$ otherwise and acts as the product identity.

The following proposition collects some known facts which clarifies the
relation between $\mathcal{F}_{\Sigma}$ and $\mathscr{A}={\rm
span}\\{\mathcal{F}_{\Sigma}\\}$ and proves that it is indeed an algebra.

######  Proposition 1.

Let $\mathcal{F}\subset\mathbb{R}^{n}$ be a vector $\sigma$-algebra, then
$\mathscr{A}={\rm span}\\{\mathcal{F}\\}$ is the smallest subalgebra in
$\mathbb{R}^{n}$ containing $\mathcal{F}$, and it is unital.

On the other hand, let $\mathscr{A}$ be any unital subalgebra in
$\mathbb{R}^{n}$ and let ${\rm
idem}(\mathscr{A}):=\\{\bm{f}\in\mathscr{A}|\bm{f}\wedge\bm{f}=\bm{f}\\}\subset\mathscr{A}$
be the set of idempotent vectors in $\mathscr{A}$. Then ${\rm
idem}(\mathscr{A})$ is the smallest $\sigma$-algebra such that every element
in $\mathscr{A}$ is $\mathcal{F}$-measurable and ${\rm res}({\rm
idem}(\mathscr{A}))$ forms an orthogonal basis for $\mathscr{A}$.

A proof of this proposition is reported in Appendix B for completeness. This
proposition shows that, not only does the space of
$\mathcal{F}_{\Sigma}$-measurable random variables form a unital subalgebra,
but, more importantly, given any unital subalgebra $\mathscr{A}$, it is
possible to find the vector $\sigma$-algebra that makes every random variable
in $\mathscr{A}$ measurable. More on that in the next remark. For convenience,
in the following, we refer to ${\rm res}({\rm idem}(\mathscr{A}))$ as ${\rm
res}(\mathscr{A})$.

Let now consider a probability measure ${\mathbb{P}}:\Omega\to[0,1]$. For any
probability measure ${\mathbb{P}}[\cdot]$ on $\Sigma$ we can define a vector
as follows

$\bm{p}:=\sum_{\omega\in\Omega}\frac{{\mathbb{P}}[\omega]}{\left<\bm{f}_{\omega},\bm{f}_{\omega}\right>}\bm{f}_{\omega}.$

Then, for any $\bm{f}_{E}\in\mathcal{F}_{\Sigma}$ it is immediate to verify
that ${\mathbb{P}}[E]=\left<\bm{p},\bm{f}_{E}\right>$. In particular, notice
that if we can write $\bm{p}:=\sum_{\bm{f}_{r}\in{\rm
res}(\mathscr{A})}p_{r}\bm{f}_{r},$ we find that $\bm{p}$ can be interpreted
as a random variable in the same algebra, $\bm{p}\in\mathscr{A}$.

In general, a vector $\bm{p}$ is said to be a probability vector if
$\bm{p}_{i}\geq 0$ for all $i$ and $\bm{1}^{T}\bm{p}$. The set of probability
vectors in $\mathscr{A}$ is defined as
$\mathcal{D}(\mathscr{A}):=\\{\bm{p}\in\mathscr{A}|\bm{p}_{i}\geq
0\quad\forall i,\quad\bm{1}^{T}\bm{p}=1\\}$. Note that
$\mathcal{D}(\mathscr{A})=\mathcal{D}({\mathbb{R}}^{n})\cap\mathscr{A}.$

Consider a r.v. $X$ and let us denote again with $\bm{f}_{i}$ the indicator
function associated to the outcome $x_{i}$. To describe the probability of an
outcome of a random variable, we can then use
${\mathbb{P}}[X=x_{i}]=\left<\bm{p},\bm{f}_{i}\right>$. Similarly, we can
compute the expectation of a random variable as
${\mathbb{E}}[\bm{x}]=\sum_{j}x_{j}{\mathbb{P}}[E_{i}]=\sum_{j}x_{j}\left<\bm{p},\bm{f}_{i}\right>=\left<\bm{p},\bm{x}\right>$.

######  Remark.

So far, we have shown that a unital subalgebra can subsume both the structure
of the $\sigma$-algebra and the space of measurable random variables of a
given probability space. Moreover, it is equivalent to a probability space
when paired with a positive linear functional defined as an inner product with
a probability vector. Conversely, given a pair $(\mathscr{A},\bm{p}),$ with
$\mathscr{A}\subseteq\mathbb{R}^{n}$ a unital subalgebra and $\bm{p}$ a
probability vector, we can always construct a (classical) probability space
associated with the pair. This can be done by choosing
$\Omega=\\{1,\dots,n\\}$ and, thanks to Proposition 1, we have that it is
always possible to find the underlying $\sigma$-algebra $\Sigma$ associated to
${\rm idem}(\mathscr{A}).$ Lastly, $\bm{p}$ represents the probability measure
associated with the functional
${\mathbb{P}}[E]=\left<\bm{p},\bm{f}_{E}\right>$.

###  II-B Stochastic maps and Conditional Expectations

Let us now focus on the maps between probability vectors.

Consider two unital subalgebras $\mathscr{F}$ and $\mathscr{G}$ of
${\mathbb{R}}^{n}$. A linear map between probability vectors
$P[\cdot]:\mathcal{D}(\mathscr{F})\to\mathcal{D}(\mathscr{G})$,
$\bm{p}\mapsto\bm{q}=P[\bm{p}]$ is called a stochastic map. Such a map can be
represented as a (column)-stochastic matrix $P\in\mathbb{R}^{m\times n}$, i.e.
a matrix such that $(P)_{i,j}\geq 0$ $\forall i,j$ and
$\bm{1}_{m}^{T}P=\bm{1}_{n}^{T}$.

In the following, the main task will be to find reduced descriptions of linear
dynamics associated to stochastic maps. In doing this, we exploit the
properties of a particular class of stochastic maps: the duals of conditional
expectations.

Recall that the conditional expectation of a r.v. given a $\sigma$-algebra
$\Sigma$ with finest resolution ${\rm res}(\Sigma)$ can be written as follows:

${\mathbb{E}}[X|\Sigma]=\sum_{E\in{\rm
res}(\Sigma)}\frac{{\mathbb{E}}[I_{E}X]}{{\mathbb{E}}[I_{E}]}I_{E}(\omega).$
(1)

Let consider a vector r.v. $\bm{x}\in\mathscr{F}\subseteq\mathbb{R}^{n}$, a
unital algebra $\mathscr{A}\subseteq\mathscr{F}$ with $\\{\bm{a}_{i}\\}={\rm
res}(\mathscr{A})$ and $d=\dim(\mathscr{A})<n$, and the underlying probability
measure $\bm{p}$. Following the previous definition, we can define the
conditional expectation for the vector r.v. with respect to an algebra
$\mathscr{A}$:

${\mathbb{E}}_{\bm{p}}[\bm{x}|\mathscr{A}]:=\sum_{j=1}^{d}\frac{\left<\bm{p},\bm{x}\wedge\bm{a}_{j}\right>}{\left<\bm{p},\bm{a}_{j}\right>}\bm{a}_{j}.$

Noticing that it is a linear operator acting on $\bm{x}$ we can represent it
as a matrix ${\mathbb{E}}_{|\mathscr{A},\bm{p}}\in\mathbb{R}^{n\times n}$,
namely:

${\mathbb{E}}_{|\mathscr{A},\bm{p}}=\sum_{j=1}^{d}\frac{\bm{a}_{j}(\bm{p}\wedge\bm{a}_{j})^{T}}{\left<\bm{p},\bm{a}_{j}\right>}.$
(2)

The dual of the conditional expectation is then a map on probability
distributions defined as:

$\displaystyle\left<\bm{q},{\mathbb{E}}_{|\mathscr{A},\bm{p}}\bm{x}\right>$
$\displaystyle=\left<{\mathbb{E}}_{|\mathscr{A},\bm{p}}^{T}\bm{q},\bm{x}\right>$

which gives in

${\mathbb{E}}_{|\mathscr{A},\bm{p}}^{T}=\sum_{j=1}^{d}\frac{(\bm{p}\wedge\bm{a}_{j})\bm{a}_{j}^{T}}{\left<\bm{p},\bm{a}_{j}\right>}.$
(3)

It is immediate to verify that ${\mathbb{E}}_{|\mathscr{A},\bm{p}}^{T}$ is
stochastic.

The conditional expectation and its adjoint are orthogonal projectors with
respect to a modified inner product. Notice that $\bm{p}\wedge\mathscr{A}={\rm
span}\\{\bm{p}\wedge\bm{a}_{i}\\}={\rm diag}(\bm{p})\mathscr{A}$.

######  Lemma 1.

Let consider the modified inner product
$\left<\bm{v},\bm{w}\right>_{\bm{p}}={\mathbb{E}}_{\bm{p}}[\bm{v}\wedge\bm{w}]$.
Then ${\mathbb{E}}_{|\mathscr{A},\bm{p}}$ is the orthogonal projector onto
$\mathscr{A}$ with respect to the inner product
$\left<\cdot,\cdot\right>_{\bm{p}}$ and
${\mathbb{E}}_{|\mathscr{A},\bm{p}}^{T}$ is the orthogonal projector onto
$\bm{p}\wedge\mathscr{A}$ with respect to the inner product
$\left<\cdot,\cdot\right>_{\bm{p}^{-1}}$.

The proof of this lemma is reported in Appendix B for completeness.

######  Remark.

Note that the above Lemma also implies that
${\mathbb{E}}_{|\mathscr{A},\bm{p}}$ acts as the identity on $\mathscr{A}$
while ${\mathbb{E}}_{|\mathscr{A},\bm{p}}^{T}$ acts as the identity on
$\bm{p}\wedge\mathscr{A}$. Furthermore, they are orthogonal projections for
the standard inner product $\left<\cdot,\cdot\right>$ if (and only if)
$\bm{p}\in\mathcal{D}(\mathscr{A})$ and is positive, namely
$\bm{p}=\sum_{j}\lambda_{j}\bm{a}_{j}\in\mathbb{R}^{n}$ with $\lambda_{j}>0$,
$\sum_{j}\lambda_{j}=1$. In this case, we have
${\mathbb{E}}_{|\mathscr{A},\bm{p}}={\mathbb{E}}_{|\mathscr{A},\bm{p}}^{T}.$

Consider the standard basis $\\{\bm{e}_{j}\\}$ for $\mathbb{R}^{d},$ where $d$
is the dimension of $\mathscr{A}.$ We can then construct a (full-rank)
stochastic factorization of ${\mathbb{E}}^{T}_{|\mathscr{A},\bm{p}}$.

######  Proposition 2.

Define

$J=\sum_{j=1}^{d}\frac{(\bm{p}\wedge\bm{a}_{j})\bm{e}_{j}^{T}}{\left<\bm{p},\bm{a}_{j}\right>}\in\mathbb{R}^{n\times
d},\quad R=\sum_{j=1}^{d}\bm{e}_{j}\bm{a}_{j}^{T}\in\mathbb{R}^{d\times n}.$
(4)

Then $J,R$ are stochastic matrices that satisfy
$JR={\mathbb{E}}_{|\mathscr{A},\bm{p}}^{T}$, $RJ=I_{d}$,
$\ker(R)=\mathscr{A}^{\perp}$ and
$\ker(J^{T})=(\bm{p}\wedge\mathscr{A})^{\perp}$.

###### Proof.

$J$ and $R$ are clearly positive since both $\\{\bm{a}_{j}\\}$ and
$\\{\bm{e}_{j}\\}$ are vectors of zeros and ones and $\bm{p}$ is positive. $J$
is clearly stochastic, $\bm{1}_{n}^{T}J=\bm{1}_{d}^{T}$ since
$\bm{1}_{n}^{T}(\bm{p}\wedge\bm{a}_{j})=\left<\bm{p},\bm{a}_{j}\right>$. On
the other hand, we have
$\bm{1}_{d}^{T}R=\sum_{j=1}^{d}\bm{a}_{j}^{T}=\bm{1}_{n}$, since $\mathscr{A}$
is unital.

We can then observe that
$\bm{a}_{j}^{T}(\bm{p}\wedge\bm{a}_{k})=\left<\bm{p},\bm{a}_{j}\wedge\bm{a}_{k}\right>=\left<\bm{p},\bm{a}_{j}\right>\delta_{j-k}$
to conclude that $RJ=I_{d}$. Finally, if we consider
$\bm{x}\in\mathscr{A}^{\perp}$, i.e. $\left<\bm{x},\bm{a}_{j}\right>=0$ for
all $j$ we obtain $R\bm{x}=\bm{0}$ and, similarly, if
$\bm{x}\in(\bm{p}\wedge\mathscr{A})^{\perp}$, i.e.
$\left<\bm{x},\bm{p}\wedge\bm{a}_{j}\right>=0$ for all $j$ we obtain
$J^{T}\bm{x}=\bm{0}$. ∎

This stochastic factorization induces a reduction in the probabilistic
description. In particular, for any random variable $\bm{x}\in\mathscr{A}$ we
have:

$\displaystyle\left<\bm{q},{\mathbb{E}}_{|\mathscr{A},\bm{p}}\bm{x}\right>$
$\displaystyle=\left<{\mathbb{E}}_{|\mathscr{A},\bm{p}}^{T}\bm{q},\bm{x}\right>=\left<JR\bm{q},\bm{x}\right>$
$\displaystyle=\left<R\bm{q},J^{T}{\bm{x}}\right>=\left<\widecheck{\bm{q}},\widecheck{\bm{x}}\right>$

where we defined the reduced distribution and random variable as
$\widecheck{\bm{q}}:=R\bm{q}\in\mathcal{D}(\mathbb{R}^{d})$ and
$\widecheck{\bm{x}}:=J^{T}\bm{x}\in\mathbb{R}^{d}$. This property shows that,
given a unital algebra $\mathscr{A}$, it is possible to reduce the
probabilistic description of the set of measurable events to the space
$\mathbb{R}^{d}$ with $d=\dim(\mathscr{A})$. For this reason, we name $R$ the
stochastic reduction and $J$ the stochastic injection.

In order to obtain smaller reduced models, it is useful to notice that even if
$\mathscr{A}$ is a non-unital subalgebra of ${\mathbb{R}}^{n}$, namely the
subalgebra has limited support, we can still use the reduction via
factorization. In particular, we can use definitions (2), (3) and (4) to
define orthogonal (to a modified product) projections on the algebra, their
dual, and their factorization. Although we use the notation
${\mathbb{E}}_{|\mathscr{A},\bm{p}}$, these operators are not associated to
conditional expectations, at least in a strict sense.

One of the main differences that will become important in the following is
highlighted in the following corollary.

######  Corollary 1.

Let $\mathscr{A}$ be a non-unital subalgebra and $\bm{p}$ be such that
$\bm{p}_{i}>0$ for all $i$, then ${\mathbb{E}}^{T}_{|\mathscr{A},\bm{p}}$
allows for a factorization ${\mathbb{E}}_{|\mathscr{A},\bm{p}}^{T}=JR$ with
$J$ and $R$ as defined above. Moreover, $J$ is stochastic while $R$ is
stochastic over the support of $\mathscr{A}$, i.e
$\bm{1}^{T}_{d}R=\bm{1}^{T}_{{\rm supp}(\mathscr{A})}$ and $\bm{1}^{T}_{{\rm
supp}(\mathscr{A})}J=\bm{1}^{T}_{d}$.

###### Proof.

The proof is the same as 2 with the only difference that
$\sum_{j=1}^{d}\bm{a}_{j}^{T}=\bm{1}_{{\rm supp}(\mathscr{A})}$ and
$\bm{1}_{\rm
supp}(\mathscr{A})^{T}(\bm{p}\wedge\bm{a}_{j})=\left<\bm{p},\bm{a}_{j}\right>$
holds, since $\mathscr{A}$ is not unital. ∎

##  III Problem definition

Throughout the rest of this work, we consider stochastic processes that can be
described as Markov processes or Hidden Markov processes (HMPs).

A stochastic process $\\{\bm{x}_{t}\\}$ is a collection of r.v.s taking values
in the finite alphabet $\mathbb{A}_{\bm{x}}$, indexed by time $t$. Without
loss of generality, we can assume $\mathbb{A}_{\bm{x}}=\\{1,2,\ldots,n\\}$. As
the alphabet is independent of time, we can choose a fixed resolution of
indicator vectors $\\{\bm{f}_{i}\\}$ with respect to which $\bm{x}_{t}$ is
measurable at all times, the standard basis for $\mathbb{R}^{n}$ being the
most compact one. With this choice, $\\{\bm{x}_{t}\\}$ is a sequence in
${\mathbb{R}}^{n}.$ In the following we thus denote by $\bm{x}_{0}^{k}$ a
stochastic process with $t=0,\dots,k$, with
$x_{0}^{k}\in\mathbb{A}_{\bm{x}}^{k+1}$ an ordered sequence of its outcomes,
i.e. $x_{0}^{k}=x_{0},x_{1},\dots,x_{k}$, where $x_{i}\in\mathbb{A}_{\bm{x}}$
for all $i$ and $|x_{0}^{k}|=k$. Then, the joint probability of a sequence of
outcomes can be written as
${\mathbb{P}}\left[\bm{x}_{0}=x_{0},\dots,\bm{x}_{k}=x_{k}\right]={\mathbb{P}}\left[\bm{x}_{0}^{k}=x_{0}^{k}\right]$.
A stochastic process $\\{\bm{x}_{t}\\}$ in $\mathbb{R}^{n}$ is a homogeneous
Markov process if

${\mathbb{P}}[\bm{x}_{t+1}=x_{t+1}|\bm{x}_{0}^{t}=x_{0}^{t}]={\mathbb{P}}[\bm{x}_{t+1}=x_{t+1}|\bm{x}_{t}=x_{t}]$

and such probability is independent of $t$ for all pairs $x_{t+1},x_{t}$.

In this case we have that there exist an initial probability vector
$\bm{p}_{0}\in\mathbb{R}^{n}$ and a stochastic matrix
$P\in{\mathbb{R}}^{n\times n}$ called the transition probability matrix such
that ${\mathbb{P}}[\bm{x}_{0}=x_{0}]=\left<\bm{p}_{0},\bm{f}_{x_{0}}\right>$
and
${\mathbb{P}}[\bm{x}_{t+1}=x_{t+1}|\bm{x}_{t}=x_{t}]=\bm{f}_{x_{t+1}}^{T}P\bm{f}_{x_{t}}$
where and $\bm{f}_{x_{t}}$ represents the elementary event associated with the
outcome $x_{t}$.

The main focus of this work are partially-observed HMPs, better known as HMPs.
The following definition adapts [10, Definitions 9.2 and 9.3] to our setting.

######  Definition 1 (Hidden Markov processes).

A stochastic process $\\{\bm{y}_{t}\\}$ in $\mathbb{R}^{m}$ taking values in
$\mathbb{A}_{\bm{y}}$ is an HMP if there exist a Markov process
$\\{\bm{x}_{t}\\}$ in $\mathbb{R}^{n}$ taking values in $\mathbb{A}_{\bm{x}}$
such that $\\{(\bm{y}_{t},\bm{x}_{t})\\}$ is jointly Markov and
${\mathbb{P}}[\bm{y}_{t}=y_{t},\bm{x}_{t}=x_{t}|\bm{y}_{t-1}=y_{t-1},\bm{x}_{t-1}=x_{t-1}]={\mathbb{P}}[\bm{y}_{t}=y_{t},\bm{x}_{t}=x_{t}|\bm{x}_{t-1}=x_{t-1}]$
for all t.

For HMPs, there exists an initial probability distribution $\bm{p}_{0}$ and
transition probability matrix $P\in\mathbb{R}^{n\times n}$ defined as before,
as well as a stochastic matrix $C\in\mathbb{R}^{m\times n},$ called emission
probability matrix, such that
${\mathbb{P}}[\bm{y}_{t}=y_{t}|\bm{x}_{t}=x_{t}]=\bm{e}_{y_{t}}^{T}C\bm{f}_{x_{t}}$,
where $\\{\bm{e}_{i}\\}$ is the standard basis for $\mathbb{R}^{m},$ and
$\bm{e}_{y_{t}}$ represents the elementary event associated to $y_{t}$.

######  Definition 2 (Hidden Markov models).

We define a Hidden Markov Model (HMM) as the couple $\theta=(P,C)$.

The HMM $\theta$ and the initial distribution $\bm{p}_{0}$ completely
characterize the evolution of the probability distributions, leaving $n,m$ and
the alphabets implicit. In fact, the marginal distribution evolution can be
modeled by

$\begin{cases}\bm{p}(t+1)=P\bm{p}(t)\\\ \bm{q}(t)=C\bm{p}(t)\end{cases}$ (5)

associated to $\theta$ and initial condition $\bm{p}(0)=\bm{p}_{0}$ and can
then be computed as

${\mathbb{P}}_{\theta,{\bm{p}_{0}}}[\bm{y}_{t}=y_{t}]=\bm{e}_{y_{t}}^{T}CP^{t}\bm{p}_{0}.$

Notice that we made the dependence on the HMM $\theta$ and initial
distribution $\bm{p}_{0}$ explicit whenever necessary to distinguish
distributions induced by different models.

We are ready to state the first of the problems we will address in the
following sections.

######  Problem 1 (Single-time marginals).

Given an HMM $\theta=(P,C)$ and a finite set of initial probability
distributions $\mathcal{S}\subset\mathcal{D}(\mathbb{R}^{n})$ find a reduced
HMM $\widecheck{\theta}=(\widecheck{P},\widecheck{C})$ of dimension $d\leq n$
and a linear map $\Phi[\cdot]:\mathcal{S}\to\mathcal{D}(\mathbb{R}^{d})$,
$\bm{p}_{0}\mapsto\widecheck{\bm{p}}_{0}$ such that

${\mathbb{P}}_{\theta,{\bm{p}_{0}}}[\bm{y}_{t}=y_{t}]={\mathbb{P}}_{\widecheck{\theta},{\Phi[\bm{p}_{0}]}}[\bm{y}_{t}=y_{t}]$

for all $t\geq 0$ and for any initial conditions $\bm{p}_{0}\in\mathcal{S}$.

Calculating the probability of a sequence of events is more involved: [16,
Lemma 1] provides a closed form for such a computation. We report it here for
completeness.

######  Lemma 2.

Given an HMM $\theta$ and an initial probability distribution $\bm{p}_{0}$,
the probability of a sequence of outcomes is given by

${\mathbb{P}}_{\theta,{\bm{p}_{0}}}[\bm{y}_{0}^{k}=y_{0}^{k}]=\bm{1}^{T}P_{C}^{y_{0}^{k}}\bm{p}_{0}$

where

$P_{C}^{y_{0}^{k}}=P_{C}^{y_{1}^{k}}{\rm diag}(\bm{e}_{y_{0}}^{T}C),$
$P_{C}^{y_{1}^{k}}=\prod_{i=k}^{1}P_{C}^{y_{i}},\quad P_{C}^{y_{i}}={\rm
diag}(\bm{e}_{y_{i}}^{T}C)P$

and ${\rm diag}(\cdot)$ is the operator that, given a vector $\bm{v}$ returns
a diagonal matrix with $[{\rm diag}(\bm{v})]_{i,i}=\bm{v}_{i}$.

In the above lemma, the multiplication by the diagonal matrices ${\rm
diag}(\bm{e}_{y_{t}}^{T}C)$ accounts for the conditioning of $\bm{p}_{t}$ on
the outcome $\bm{y}_{t}=y_{t}.$ Without the latter we obtain the formulas for
the single marginals.

In order to exploit a system-theoretic analysis, it is useful to write the
probability of a sequence of outcomes as the output of a dynamical model. Call
$\psi(t)=\mathbb{P}(\bm{y}_{0}^{t}=y_{0}^{t}).$ We can obtain its evolution as
the output of a discrete-time, autonomous, switching, linear system described
by

$\begin{cases}\bm{\phi}(t+1)=P_{C}^{y_{t}}\bm{\phi}(t)\\\
\psi(t)=\bm{1}^{T}\bm{\phi}(t)\end{cases}$ (6)

with initial condition $\bm{\phi}_{y_{0}}(1)={\rm
diag}(\bm{e}_{y_{0}}^{T}C)\bm{p}_{0}$, $P_{C}^{y_{t}}$ defined as in the
previous lemma and where $\psi(t)$ represents the probability associated to
the sequence of events $y_{0}^{t}$. Clearly, the output $\bm{\psi}(t)$ depends
on the sequence of $P_{C}^{y_{t}},$ which in turn depends on the outcomes of
the sequence. The output at any time $k>0$ can be computed as
$\bm{\psi}({y_{0}^{k}})=\bm{1}^{T}\prod_{i=k}^{1}P_{C}^{y_{i}}\bm{\phi}_{y_{0}}(1)$,
while for $l=0$ we have $\bm{\psi}({y_{0}})=\bm{1}^{T}\bm{\phi}_{y_{0}}(1)$,
thus recovering the formula of the lemma.

Given a finite set $\mathcal{S}$ of initial distributions of interest, the
corresponding set of initial conditions for this model is
$\Phi=\bigcup_{y_{0}}{\rm diag}(\bm{e}_{y_{0}}^{T}C)\mathcal{S}$. The second
problem that we address in this article can be stated next.

######  Problem 2 (Multi-time marginals).

Given an HMM $\theta=(P,C)$ and a finite set of initial probability
distributions $\mathcal{S}\subset\mathcal{D}(\mathbb{R}^{n})$ find a reduced
HMM $\widecheck{\theta}=(\widecheck{P},\widecheck{C})$ of dimension $d\leq n$
and a linear map $\Phi[\cdot]:\mathcal{S}\to\mathcal{D}(\mathbb{R}^{d})$,
$\bm{p}_{0}\mapsto\widecheck{\bm{p}}_{0}$ such that

${\mathbb{P}}_{\theta,{\bm{p}_{0}}}[\bm{y}_{0}^{k}=y_{0}^{k}]={\mathbb{P}}_{\widecheck{\theta},{\Phi[\bm{p}_{0}]}}[\bm{y}_{0}^{k}=y_{0}^{k}]$

for all sequences of the output process $y_{0}^{k}$ and for all initial
conditions $\bm{p}_{0}\in\mathcal{S}$.

######  Remark.

Although Problem 2 is more natural than Problem 1 for the typical HMM setting,
the latter is also interesting in particular cases, which include efficiently
simulating an unmeasured stochastic evolution, and reproducing the mixing
properties of lifted chains with more compact models.

######  Remark.

As we pointed out before, in Problems 1 and 2 we have assumed that
$\mathcal{S}$ is a finite set. This assumption is not restrictive since, as we
show below, the proposed solution works for any initial condition contained in
${\rm span}\\{\mathcal{S}\\}$. For this reason, if one is interested in the
adaptation of any of the two problems to a subspace of initial conditions one
can study the problem using $\mathcal{S}$ as the set of generators of said
subspace.

##  IV Preliminary results:
A system theoretic viewpoint

Finding minimal realization of linear systems has been a central problem in
control and system theory, for which well-established solutions are available.
Nonetheless, when positivity is required on the reduced model, the minimal
realization problem is, to the best of our knowledge, still open. In this
section, we review some existing results, and extend and adapt them so that
they can be used in our scenarios. In particular, we shall allow for non-
minimal realizations in order to guarantee their positivity.

###  IV-A Single time-marginal problem

Let us start by considering model (5) with initial condition
$\bm{p}_{0}\in\mathcal{S}$. Let us define the non-observable subspace as:

$\mathcal{N}:=\ker\begin{bmatrix}C\\\ CP\\\ \vdots\\\ CP^{n-1}\end{bmatrix}.$
(7)

The subspace $\mathcal{N}$ can be characterized as the largest $P$-invariant
subspace contained in $\ker C$ [29, 30]. In the case of HMM the non-observable
subspace has another useful property.

######  Lemma 3.

For all $\bm{x}\in\mathcal{N}$ it holds $\bm{1}^{T}\bm{x}=0$.

###### Proof.

From the definition of non-observable space we have that
$\bm{x}\in\mathcal{N}$ if and only if $CP^{t}\bm{x}=\bm{0}$ for all $t\geq 0$.
If we then left-multiply by $\bm{1}^{T}$ on both sides we obtain
$\bm{1}^{T}CP^{t}\bm{x}=\bm{1}^{T}P^{t}\bm{x}=\bm{1}^{T}\bm{x}=\bm{1}^{T}\bm{0}=0$
for all $\bm{x}\in\mathcal{N}$. ∎

Next, define $\mathcal{R}$ as the smallest linear space that contains all
probability distributions $\bm{p}(t)$ generated by the HMM for every $t\geq 0$
and any initial distribution $\bm{p}_{0}\in\mathcal{S}$:

$\mathcal{R}:={\rm span}\\{P^{t}\bm{p}_{0}|t\geq
0,\bm{p}_{0}\in\mathcal{S}\\}.$ (8)

######  Remark.

The space $\mathcal{R}$ is, in fact, the reachable subspace of a state-space
model in the typical form:

$\begin{cases}\tilde{\bm{p}}(t+1)=P\tilde{\bm{p}}(t)+B\bm{u}(t)\\\
\bm{q}(t)=C\tilde{\bm{p}}(t)\end{cases}$ (9)

where $B\in\mathbb{R}^{n\times|\mathcal{S}|}$ is a matrix whose columns are
the initial conditions in $\mathcal{S}$. This model reproduces the
trajectories of (5) for inputs corresponding to discrete impulses. The non-
observable subspaces of (5) and (9) are the same, and the subspace
$\mathcal{R}$ coincides with the reachable subspace of model (9), and thus
shares the same properties: $\mathcal{R}$ is the smallest $P$-invariant
subspace that contains ${\rm span}\\{\mathcal{S}\\}$. In light of this, we
call the $\mathcal{R}$ defined above the reachable subspace.

Lastly, define the effective subspace $\mathcal{E}$ as a completion of the
intersection $\mathcal{R}\cap\mathcal{N}$ to the reachable subspace
$\mathcal{R}$, i.e. a subspace such that
$(\mathcal{R}\cap\mathcal{N})\oplus\mathcal{E}=\mathcal{R}$. Notice that the
choice of $\mathcal{E}$ is not unique, in fact, any representative of the
quotient space $\mathcal{R}/(\mathcal{R}\cap\mathcal{N})$ is a suitable
candidate for this choice. In Section VII we shall argue that the choice of
$\mathcal{E}$ plays a key role in constructing a good reduction.

It is well known that the restriction of model (9) to (any) $\mathcal{E}$
corresponds to a minimal realization (yet not necessarily positive or
stochastic), and the algorithm provided by Rosenbrock [31] can be used to
compute such a reduced model. The next corollary shows that the same is true
for the HMM (5), while also allowing for extensions of the effective space.

######  Corollary 2.

Consider an effective subspace $\mathcal{E}$ for the HMM (5) and a subspace
$\mathcal{V}$ such that $\mathcal{E}\subseteq\mathcal{V}$ with
$d=\dim(\mathcal{V}).$ Let $\Pi_{\mathcal{V}}$ be the orthogonal projection
onto $\mathcal{V}$ with respect to an arbitrary inner product
$\left<\cdot,\cdot\right>$. Let $R:\mathbb{R}^{n}\to\mathbb{R}^{d}$ and
$J:\mathbb{R}^{d}\to\mathcal{V}$ be two (non-square) factors of the orthogonal
projection, $\Pi_{\mathcal{V}}=JR$.

Define the reduced model $(\widecheck{P},\widecheck{C})=(RPJ,CJ)$ and the map
$\widecheck{\bm{p}}_{0}=R\bm{p}_{0}$, for all $\bm{p}_{0}\in\mathcal{S}$. Then
the linear systems associated to the pairs $(P,C)$ and
$(\widecheck{P},\widecheck{C})$ reproduce the same marginal distribution at a
specific time instant, i.e.

$CP^{t}\bm{p}_{0}=\widecheck{C}\widecheck{P}^{t}\widecheck{\bm{p}}_{0}$

for all $t\geq 0$ and any initial condition $\bm{p}_{0}\in{\rm
span}\\{\mathcal{S}\\}$.

###### Proof.

This result follows from the application of Theorem 4 reported in Appendix A
with only one $F_{i}=P$, $H=C$ and $\bm{x}(0)=\bm{p}_{0}$. ∎

In the following sections we shall construct $\mathcal{V}$ so that the
reduction is also an HMM.

###  IV-B Multi time-marginal problem

The minimal reduction of the system producing the multi-time distribution can
be obtained along the same lines. Following the approach of [16] in a system-
theoretic setting, we can define the reachable, non-observable and effective
subspaces for the multi-time problem. To avoid confusion with the previous
definitions, we call these the conditioned subspaces and denote them with a
$\mathcal{C}$ subscript. Given an HMM $(P,C)$ and a set of initial conditions
$\mathcal{S}$ we define the conditioned non-observable subspace as:

$\mathcal{N_{C}}:=\\{\bm{v}\in\mathbb{R}^{n}|\bm{1}^{T}P_{C}^{y_{0}^{l}}\bm{v}=0,\quad\forall
y_{0}^{l}\\},$ (10)

and the conditioned reachable subspace as

$\mathcal{R_{C}}:={\rm
span}\\{P_{C}^{y_{0}^{l}}\bm{p}_{0},\quad\forall{y_{0}^{l}},\quad\forall\bm{p}_{0}\in\mathcal{S}\\}.$
(11)

We can then define the conditioned effective subspace $\mathcal{E_{C}}$ as a
completion of the intersection $\mathcal{R_{C}}\cap\mathcal{N_{C}}$ to the
conditioned reachable subspace $\mathcal{R_{C}}$, i.e.
$\mathcal{E_{C}}\oplus(\mathcal{R_{C}}\cap\mathcal{N_{C}})=\mathcal{R_{C}}$.
As before, the choice of $\mathcal{E_{C}}$ is not unique, as any
representative of the quotient space
$\mathcal{R_{C}}/(\mathcal{R_{C}}\cap\mathcal{N_{C}})$ is a suitable choice.

The properties of these spaces have been described in [16, Lemma 3, Section
3]. We recap them in the following Lemma for the reader’s convenience.

######  Lemma 4.

$\mathcal{N_{C}}$ and $\mathcal{R_{C}}$ are $P$-invariant, ${\rm
diag}(\bm{e}_{i}^{T}C)$-invariant for all $i$ and thus,
$P_{C}^{y_{0}^{l}}$-invariant for all sequences $y_{0}^{l}$.

A result similar to Cayley-Hamilton Theorem holds and let us compute the
spaces by using a finite number of generators:

$\displaystyle\mathcal{N_{C}}$
$\displaystyle=\\{\bm{v}\in\mathbb{R}^{n}|\bm{1}^{T}P_{C}^{y_{0}^{l}}\bm{v}=0,\quad\forall{y_{0}^{l}}\text{
s.t. }l<n\\},$ $\displaystyle\mathcal{R_{C}}$ $\displaystyle={\rm
span}\\{P_{C}^{y_{0}^{l}}\bm{p}_{0},\quad\forall\bm{p}_{0}\in\mathcal{S},\quad\forall{y_{0}^{l}}\text{
s.t. }l<n\\}.$

We can then notice that $\mathcal{N_{C}}$ is the non-observable subspace of
model (6) see e.g. [32], $\mathcal{R_{C}}$ is its reachable subspace and
$\mathcal{E_{C}}$ is its effective subspace. The second statement holds
trivially, while the first holds because $\mathcal{N}$ is ${\rm
diag}(\bm{e}_{i}^{T}C)$-invariant for all $i$. The third follows by combining
the first two.

An useful property of the propagator $P_{C}^{y_{0}^{k}}$ is proved in the
following Lemma.

######  Lemma 5.

The sum over all sequences $y_{0}^{k}$ of the same length $k$ of
$P_{C}^{y_{0}^{k}}$ is equal to the $k$th power of P, i.e.

$\sum_{y_{0}^{k}}P_{C}^{y_{0}^{k}}=P^{k}$

###### Proof.

Observing that $\sum_{y_{i}}{\rm diag}(\bm{e}_{y_{i}}C)=I$ for all $i$ and
summing over all the possible strings ${y_{0}^{l}}$, starting from the first
character, the statement follows directly. ∎

The next Proposition shows that, in general, solving the multi-time marginal
case requires a larger model than the single-time case defined before.

######  Proposition 3.

It holds that

$\ker C\supseteq\mathcal{N}\supseteq\mathcal{N_{C}},$
$\mathcal{S}\subseteq\mathcal{R}\subseteq\mathcal{R_{C}},$

and also

$\mathcal{E}\subseteq\mathcal{E_{C}}.$

The proof of this Lemma can be found in Appendix B.

######  Remark.

Note that this result further motivates the distinction between problems 2 and
1. In fact this Proposition shows that, at least in principle, there could be
a larger reduction if we are only interested in describing only the evolution
of the marginal distribution at a specific time. Moreover, the conditioned
effective subspace contains the effective subspace, thus showing, due to
Corollary 2, that a solution for problem 2 is also a solution for problem 1.

As we did in the previous subsection we now consider a generalization of model
reduction for the multi-time marginal problem.

######  Corollary 3.

Let consider any effective subspace $\mathcal{E}_{\cal C}$ and let a subspace
$\mathcal{V}$ such that $\mathcal{E}_{\cal C}\subseteq\mathcal{V}$ with
$d=\dim(\mathcal{V})$, and let $\Pi_{\mathcal{V}}$ be the orthogonal
projection onto $\mathcal{V}$ with respect to an arbitrary inner product
$\left<\cdot,\cdot\right>$. Let $R:\mathbb{R}^{n}\to\mathbb{R}^{d}$ and
$J:\mathbb{R}^{d}\to\mathcal{V}$ be two (non-square) factors of the orthogonal
projection, $\Pi_{\mathcal{V}}=JR$.

Let then consider the reduced model
$(\\{\widecheck{P}_{C}^{y_{i}}\\},\bm{1}_{m}^{T})=(\\{RP_{C}^{y_{i}}J\\},\bm{1}_{n}^{T}J)$
and the map $\bm{\widecheck{}}{\phi}(1)=R\bm{\phi}(1)$ for all
$\bm{\phi}(1)\in\Phi$. Then the two models described by equations (6) and
denoted by the couples $(\\{P_{C}^{y_{i}}\\},\bm{1}_{n}^{T})$ and
$(\\{\widecheck{P}_{C}^{y_{i}}\\},\bm{1}_{m}^{T})$ reproduce the same
probability of a sequence of outcomes, i.e.

$\bm{1}_{n}^{T}\prod_{j=k}^{0}P_{C}^{y_{j}}\bm{\phi}(1)=\bm{1}_{m}^{T}\prod_{j=k}^{0}\widecheck{P}_{C}^{y_{j}}\widecheck{\bm{\phi}}(1)$

for any sequence $y_{o}^{k}$ and any initial condition $\bm{\phi}(1)\in{\rm
span}\\{\Phi\\}$.

###### Proof.

This result follows from the application of Theorem 4 reported in Appendix A
with $F_{i}={\rm diag}(\bm{e}_{y_{i}}^{T}C)P$, $H=\bm{1}^{T}$, $\bm{x}(0)={\rm
diag}(\bm{e}_{y_{0}}^{T}C)\bm{p}_{0}$. ∎

######  Remark.

Corollary 3 provides a reduction for model (6) but generally does not provide
a reduction for (5) and the relative initial condition. Nevertheless, the
particular choices we propose in Section VI for the multi-time case also
provides a reduction for the single-time marginal model.

##  V Single-time solution

In this section we illustrate how to obtain solutions to Problem 1
appropriately choosing $\mathcal{V}$ in Corollary 2. We first discuss the
intuition behind the method, next we present the proposed solution in form of
a parametric algorithm, and prove that, under appropriate constraints, the
algorithm indeed provides a solution. Finally, in Section VII, propose a way
to choose the relevant parameters.

###  V-A Intuition

The core idea behind the method stems from the fact that in order to define a
HMM we need an underlying probability space and, as we have seen in Section
II, any probability space is associated to an algebra. This directly suggests
that, in order to preserve the (stochastic) HMM structure in the reduction it
is natural to restrict the model to an algebra whose dual contains the
effective subspace, and then use the dual of the conditional expectation to
obtain a stochastic reduction.

More in detail, consider the two stochastic reduction matrices $R$ and $J$
obtained in Section II-B as factors of the dual of a conditional expectation
${\mathbb{E}}^{T}_{|\mathscr{A},\overline{\bm{p}}},$ which is an orthogonal
projection onto $\bm{p}\wedge\mathscr{A}$ with respect to the inner product
$\left<\cdot,\cdot\right>_{\bm{p}^{-1}}$. Then, according to Corollary 2 we
know that as long as $\mathcal{E}\subseteq\mathcal{V}=\bm{p}\wedge\mathscr{A}$
then the reduced model reproduces the same marginal distribution as the
original one.

In order to choose $\mathscr{A}$ such that
$\mathcal{E}\subseteq\bm{p}\wedge\mathscr{A}$ we can $\wedge$-multiply left
and right by $\bm{p}^{-1}$ obtaining
$\bm{p}^{-1}\wedge\mathcal{E}\subseteq\mathscr{A}$. Let ${\rm alg}(X)$ denote
the minimal sub-algebra of ${\mathbb{R}}^{n}$ containing the set $X.$ Then, if
we define $\mathscr{A}:={\rm alg}(\bm{p}^{-1}\wedge\mathcal{E})$, we ensure
that $\mathcal{E}\subseteq\bm{p}\wedge\mathscr{A}$ is satisfied and that the
reduced model reproduces the same marginal at a single time.

To make this idea more concrete, we provide a simple illustrative example,
which also highlights the importance of choosing the distribution $\bm{p}$ to
be used in ${\mathbb{E}}^{T}_{|\mathscr{A},\overline{\bm{p}}}$.

######  Example 1.

Let us consider the following HMM:

$\displaystyle P$ $\displaystyle=\begin{bmatrix}2/5&0&1/5\\\ 0&2/5&1/5\\\
3/5&3/5&3/5\end{bmatrix},\quad\mathcal{S}=\left\\{\begin{bmatrix}1/5\\\ 1/5\\\
3/5\end{bmatrix}\right\\}$ $\displaystyle C$
$\displaystyle=\begin{bmatrix}1&1&0\\\ 0&0&1\end{bmatrix}.$

Notice that $\bm{p}_{0}$ is an equilibrium, $P\bm{p}_{0}=\bm{p}_{0}$ thus the
output distribution is equal to
$\bm{q}(t)=\begin{bmatrix}2/5&3/5\end{bmatrix}^{T}$, $\forall t\geq 0$. We can
then compute the following.

$\displaystyle\mathcal{R}={\rm span}\left\\{\begin{bmatrix}1/5\\\ 1/5\\\
3/5\end{bmatrix}\right\\},\quad\mathcal{N}={\rm
span}\left\\{\begin{bmatrix}1\\\ -1\\\ 0\end{bmatrix}\right\\}$

and $\mathcal{R}\cap\mathcal{N}={\rm span}\\{\bm{0}\\}$ and we can thus choose
$\mathcal{E}=\mathcal{R}$. If we then choose $\bm{p}=\bm{1}$ we obtain

$\mathscr{A}={\rm alg}(\mathcal{R})={\rm span}\left\\{\begin{bmatrix}1\\\ 1\\\
0\end{bmatrix},\begin{bmatrix}0\\\ 0\\\ 1\end{bmatrix}\right\\}$

and thus the relative factors of the dual of the conditional expectation are

$R=\begin{bmatrix}1&1&0\\\ 0&0&1\end{bmatrix},\quad J=\begin{bmatrix}1/2&0\\\
1/2&0\\\ 0&1\end{bmatrix}$

and the associated reduced HMM is

$\widecheck{P}=\begin{bmatrix}2/5&2/5\\\
3/5&3/5\end{bmatrix},\quad\widecheck{C}=\begin{bmatrix}1&0\\\
0&1\end{bmatrix},\quad\widecheck{\bm{p}}_{0}=\begin{bmatrix}2/5\\\
3/5\end{bmatrix}$

which correctly reproduces the output marginal distribution
$\bm{q}(t)=\begin{bmatrix}2/5&3/5\end{bmatrix}^{T}$, $\forall t\geq 0$.

On the other hand if we were to choose $\bm{p}=\bm{p}_{0}$ we would obtain a
different result. In fact, in that case, we have

$\mathscr{A}={\rm alg}(\bm{p}^{-1}\wedge\mathcal{R})={\rm
span}\left\\{\begin{bmatrix}1\\\ 1\\\ 1\end{bmatrix}\right\\}$

and thus the relative factors of the dual of the conditional expectation are
$R=\begin{bmatrix}1&1&1\end{bmatrix}$, and
$J=\begin{bmatrix}1/5&1/5&3/5\end{bmatrix}^{T}$ and the associated reduced HMM
is $\widecheck{P}=1$, $\widecheck{C}=\begin{bmatrix}2/5&3/5\end{bmatrix}$ and
$\bm{p}_{0}=1$ which also reproduces the output marginal distribution and is
clearly minimal (optimal reduction). This shows that the choice of $\bm{p}$ is
important if we are interested in minimizing the dimension of the reduced
model.

###  V-B Proposed solution

We now formalize the proposed method to solve Problem 1 in the following
Algorithm. Let $\Gamma(\mathcal{R},\mathcal{N})$ a map that selects an
effective space $\cal{E}$ given some $\mathcal{R},\mathcal{N}.$

Input : $(P,C)$, $\mathcal{S}$.

Parameters : $\bm{p}$, $\Gamma$.

1 Compute $\mathcal{R}$ and $\mathcal{N}$;

2 Compute $\mathcal{E}=\Gamma(\mathcal{R},\mathcal{N})$;

3 Compute $\mathscr{A}:={\rm alg}({\bm{p}}^{-1}\wedge\mathcal{E})$;

4 Compute $\mathbb{E}_{|\mathscr{A},{\bm{p}}}$ and its factors $R$ and $J$;

Output : $(\widecheck{P},\widecheck{C})=(RPJ,CJ)$ and $R$.

Algorithm 1 HMM reduction for problem 1

Notice that this algorithm depends, in addition to its inputs, on two
parameters: the first one, $\bm{p}$, is a positive vector; the second one, the
map $\Gamma$ that selects the effective subspace. We will discuss more in
detail the choice of the effective subspace in Section VII.

We are finally ready to prove that Algorithm 1 solves the single-time marginal
problem.

######  Theorem 1.

For any choice of $\mathcal{E}$ and $\bm{p}$ positive i.e. ${\bm{p}_{i}}>0$
$\forall i$, Algorithm 1 provides a solution to Problem 1.

###### Proof.

To prove the statement we have to prove that: i) The reduced model
$\widecheck{\theta}=(\widecheck{P},\widecheck{C})$ and the linear map $R$
provide the same marginal distribution at any time as the original model; ii)
the reduced model $\widecheck{\theta}$ is an HMM, and $R\bm{p}_{0}$ is a
probability vector.

We shall start by proving the first point. We do so leveraging Corollary 2.
First of all we have that, for any vector $\bm{p}$ such that $\bm{p}_{i}>0$
for all $i$ the inner product $\left<\cdot,\cdot\right>_{\bm{p}}$ is positive-
definite and thus well defined. Moreover, by definition of the algebra
$\mathscr{A}$, we have that, for any choice of the effective subspace
$\mathcal{E}$ it holds $\mathcal{E}\subseteq\bm{p}\wedge\mathscr{A}$ so, by
choosing $\mathcal{V}=\bm{p}\wedge\mathscr{A}$, and using the restriction and
injection map defined in equation (4) i) follows from Corollary 2.

Regarding ii) we have that, if $\mathscr{A}$ is unital, then Proposition 2
ensures that $J$ and $R$ are stochastic and thus $RPJ$ and $CJ$ are stochastic
and $R\bm{p}_{0}$ is a probability vector for any $\bm{p}_{0}$ probability
vector. If $\mathscr{A}$ is not unital, because of Corollary 1 we have, that
$J$ is stochastic (and thus $CJ$ is stochastic) but $R$ is only stochastic
over ${\rm supp}(\mathscr{A})$, i.e. $\bm{1}_{d}^{T}R=\bm{1}^{T}_{{\rm
supp}(\mathscr{A})}$. We next show that this condition is sufficient to show
that the reduced model is stochastic.

We shall first notice that ${\rm supp}(\mathcal{E})={\rm
supp}(\mathscr{A})\subsetneq\mathbb{R}^{n}$. Let assume that $\dim({\rm
supp}(\mathcal{E}))=k$. Then we can consider a permutation (that is a double-
stochastic change of basis) $T$ such that
$T\bm{x}=\left[\begin{array}[]{c|c}\bm{x}^{\prime}&\bm{0}_{n-k}^{T}\end{array}\right]^{T}$
for all $\bm{x}\in\mathcal{E}$, with $\bm{x}^{\prime}\in\mathbb{R}^{k}$. Then,
since $\mathcal{E}$ is $P$-invariant then

$\left[\begin{array}[]{c}\bm{x}^{\prime}\\\
\hline\cr\bm{0}_{n-k}\end{array}\right]=\underbrace{\left[\begin{array}[]{c|c}P_{11}&P_{12}\\\
\hline\cr
P_{21}&P_{22}\end{array}\right]}_{TPT^{T}}\left[\begin{array}[]{c}\bm{x}^{\prime}\\\
\hline\cr\bm{0}_{n-k}\end{array}\right]\in\mathcal{E}$

and thus $P_{21}=0$. This shows that ${\rm supp}(\mathcal{E})$ is
$P$-invariant. Then, since $P$, $T$ and $T^{T}$ are stochastic, then $TPT^{T}$
is stochastic. This implies that $\bm{1}_{k}^{T}P_{11}=\bm{1}_{k}^{T}$. Then,
it holds that $\bm{1}_{{\rm supp}(\mathscr{A})}^{T}T^{T}TPT^{T}=$

$\left[\begin{array}[]{c|c}\bm{1}_{k}^{T}&\bm{0}_{n-k}^{T}\end{array}\right]\left[\begin{array}[]{c|c}P_{11}&P_{12}\\\
\hline\cr
0&P_{22}\end{array}\right]=\left[\begin{array}[]{c|c}\bm{1}_{k}^{T}&\bm{0}_{n-k}^{T}\end{array}\right]$

or, in other words $\bm{1}_{{\rm supp}(\mathscr{A})}^{T}P=\bm{1}_{{\rm
supp}(\mathscr{A})}^{T}$. Then, we can verify that $\widecheck{P}$ is
stochastic by verifying the following chain of equivalences:
$\bm{1}_{d}^{T}RPJ=\bm{1}_{{\rm supp}(\mathscr{A})}^{T}PJ=\bm{1}_{{\rm
supp}(\mathscr{A})}^{T}J=\bm{1}_{d}^{T}$ where the last equality comes from
Corollary 1. Finally, to prove that $R\bm{p}_{0}$ is a probability vector we
can observe that
$\bm{1}_{n}^{T}\bm{p}_{0}=\bm{1}^{T}\Pi_{\mathcal{E}}\bm{p}_{0}+\underbrace{\bm{1}^{T}\Pi_{\mathcal{R}\cap\mathcal{N}}\bm{p}_{0}}_{=\bm{0}}=1$
and then re-use the reasoning above. ∎

######  Remark.

In the proof of Theorem 1 we stated that a positive vector $\bm{p}$ is
necessary to have a well defined inner product
$\left<\cdot,\cdot\right>_{\bm{p}}$. This assumption, however, can be relaxed
to the following: $\bm{p}$ is positive over ${\rm supp}(\mathcal{E})={\rm
supp}(\mathscr{A})$, i.e. $\bm{p}_{i}>0$ for all $i$ such that
$\bm{e}_{i}^{T}\bm{x}\neq 0$ for some $\bm{x}\in\mathcal{E}$. This is due to
the fact that the values of $\bm{p}$ where $\mathcal{E}$ has no support has no
role in the projection.

Although such $\bm{p}$ defines a positive semi-definite inner product over
$\mathbb{R}^{n}$, it provides a positive definite inner product over ${\rm
supp}(\mathcal{S})$ and this is sufficient to define the orthogonal projection
onto $\mathscr{A}$. Consider, for example, the following case: assume ${\rm
supp}(\mathscr{A})\subsetneq\mathbb{R}^{n}$ then let $\bm{p}_{s}$ be a
positive vector over the ${\rm supp}(\mathscr{A})$, $\bm{p}_{n}$ be a positive
vector over the remaining support, i.e. s.t. $\bm{p}:=\bm{p}_{s}+\bm{p}_{n}$,
${\rm supp}(\bm{p})=\mathbb{R}^{n}$. We can then notice that
$\bm{p}\wedge\bm{x}=\bm{p}_{s}\wedge\bm{x}$ and
$\left<\bm{y},\bm{x}\right>_{\bm{p}}=\left<\bm{y},\bm{x}\right>_{\bm{p}_{s}}$
for all $\bm{x}\in{\rm supp}(\mathscr{A})$ and $\bm{y}\in\mathbb{R}^{n}$. This
implies that

${\mathbb{E}}_{|\mathscr{A},\bm{p}}^{T}=\sum_{j=1}^{d}\frac{(\bm{p}\wedge\bm{a}_{j})\bm{a}_{j}^{T}}{\left<\bm{a}_{j},\bm{a}_{j}\right>_{\bm{p}}}=\sum_{j=1}^{d}\frac{(\bm{p}_{s}\wedge\bm{a}_{j})\bm{a}_{j}^{T}}{\left<\bm{a}_{j},\bm{a}_{j}\right>_{\bm{p}_{s}}}={\mathbb{E}}_{|\mathscr{A},\bm{p}_{s}}^{T}.$

The role of the positivity of $\bm{p}$ will be further discussed in Section
VII.

##  VI Multi-time solution

The solution of Problem 2 follows the same ideas presented in the previous
section. In fact, the algorithm we propose to solve Problem 2 is identical to
the previous algorithm but for the involved subspaces. We now present our
proposed method to solve Problem 2. This method takes the form of the
following Algorithm, where $\Gamma$ is defined as in the previous section.

Input : $(P,C)$, $\mathcal{S}$.

Parameters : $\bm{p}$, $\Gamma$.

1 Compute $\mathcal{R_{C}}$ and $\mathcal{N_{C}}$;

2 Compute $\mathcal{E_{C}}=\Gamma(\mathcal{R_{C}},\mathcal{N_{C}})$;

3 Compute $\mathscr{A}_{\mathcal{C}}={\rm
alg}({\bm{p}}^{-1}\wedge\mathcal{E_{C}})$;

4 Compute $\mathbb{E}_{|\mathscr{A}_{\mathcal{C}},{\bm{p}}}$ and its factors
$R$ and $J$;

Output : $(\widecheck{P},\widecheck{C})=(RPJ,CJ)$ and $R$

Algorithm 2 HMM reduction for problem 2

Before we prove that Algorithm 2 solves Problem 2, we observe a property of
the algebra and the factorization of the projector which is reported in the
following Lemma.

######  Lemma 6.

Let $R$ and $J$ be the two factors of
$\mathbb{E}_{|\mathscr{A}_{\mathcal{C}},{\bm{p}}}$, as defined in equation
(4). Then it holds $R{\rm diag}(\bm{e}_{i}^{T}C)={\rm
diag}(\bm{e}_{i}^{T}CJ)R$ for all $i$.

The proof of this Lemma can be found in Appendix B.

We are finally ready to prove that Algorithm 2 solves the multi-time marginal
problem.

######  Theorem 2.

For any choice of $\mathcal{E_{C}}$ and $\bm{p}$ positive, i.e.
${\bm{p}_{i}}>0$ $\forall i$, Algorithm 2 provides a solution to Problem 2.

###### Proof.

The proof of this theorem follows the lines of the proof of Theorem 1. In
fact, the proof of the fact that the reduced HMM $\widecheck{\theta}$ is
stochastic and $R\bm{p}_{0}$ is a probability vector is identical to the one
given in 1. The only difference in the two proofs regards proof of the fact
that the reduced model $\widecheck{\theta}$ with initial condition
$R\bm{p}_{0}$ provides the same probability of a sequence of events as the
model $\theta$ with initial condition $\bm{p}_{0}$.

From Corollary 3 we have that $(R{\rm diag}(\bm{e}_{i}^{T}C)PJ,\bm{1}^{T}J)$
with initial condition $R{\rm diag}(\bm{e}_{i}^{T}C)\bm{p}_{0}$ generates the
same probability as the original model. Then, using Lemma 6 we have that
$R{\rm diag}(\bm{e}_{i}^{T}C)PJ={\rm diag}(\bm{e}_{i}^{T}CJ)RPJ$ and $R{\rm
diag}(\bm{e}_{i}^{T}C)\bm{p}_{0}={\rm diag}(\bm{e}_{i}^{T}CJ)R\bm{p}_{0}$ thus
leading to the reduced HMM $\widecheck{\theta}=(RPJ,CJ)$ and initial
conditions $R\bm{p}_{0}$. ∎

##  VII On the optimal choice of the parameters

In this section we discuss what is the best choice of the parameters for
Algorithms 1 and 2. The structure of the two algorithms is identical hence we
only discuss the optimal choice of $\mathcal{E}$ and $\bm{p}$. The notion of
optimality is related to the dimension of the reduced system meaning: we want
to find a choice of $\mathcal{E}$ and $\bm{p}$ positive such that the reduced
model returned by Algorithm 1 has minimal dimension. This is equivalent to
finding $\mathcal{E}$ and $\bm{p}$ such that ${\rm
alg}(\bm{p}^{-1}\wedge\mathcal{E})$ has minimal dimension. We shall start the
discussion by finding the optimal choice of $\bm{p}$ assuming that an
effective subspace $\mathcal{E}$ is given. Before we prove the main result of
this section, we shall first state the following useful result.

######  Lemma 7.

Given a vector space $\mathcal{W}\subseteq\mathbb{R}^{n}$ with generators
$\\{\bm{w}_{i}\\}$, $\mathcal{W}={\rm span}\\{\bm{w}_{i}\\}$ there exists a
vector $\overline{\bm{w}}:=\sum_{i}\lambda_{i}\bm{w}_{i}$, with
$\lambda_{i}\neq 0$ for all $i$ and such that ${\rm
supp}(\overline{\bm{w}})={\rm supp}(\mathcal{W})$.

The proof of this Lemma can be found in Appendix B.

######  Theorem 3.

Let consider a vector space $\mathcal{W}\subseteq\mathbb{R}^{n}$ and a vector
$\overline{\bm{w}}$ as in Lemma 7. Then there exists a unique algebra
$\mathscr{A}^{*}$ of minimal dimension such that
$\mathcal{W}\subseteq\bm{x}\wedge\mathscr{A}^{*}$ for some
$\bm{x}\in\mathbb{R}^{n}.$ Moreover, $\mathscr{A}^{*}={\rm
alg}(\overline{\bm{w}}^{-1}\wedge\mathcal{W})$ and it is unital over the
support of $\mathcal{W}$, i.e. $\bm{1}_{{\rm
supp}(\mathcal{W})}\in\mathscr{A}^{*}$.

###### Proof.

The existence of such a $\overline{\bm{w}}$ is proved in Lemma 7.

Since $\mathscr{A}=\mathbb{R}^{n}$ satisfies
$\mathcal{W}\subseteq\bm{x}\wedge\mathscr{A}$, for all
$\bm{x}\in\mathbb{R}^{n}$ and its possible sub-algebras are finite
(corresponding to the partition of $n$), $\mathscr{A}^{*}$ exists. To prove
that it is unique solution we proceed by contradiction. Let assume that there
exist two different algebras $\mathscr{A},\mathscr{B}\subseteq\mathbb{R}^{n}$
with minimal dimension $\dim(\mathscr{A})=\dim(\mathscr{B})$ and two vectors
$\overline{\bm{a}},\overline{\bm{b}}\in\mathbb{R}^{n}$ such that
$\mathcal{W}\subseteq\overline{\bm{a}}\wedge\mathscr{A}$ and
$\mathcal{W}\subseteq\overline{\bm{b}}\wedge\mathscr{B}$. From Proposition 1
we know that $\mathscr{A}={\rm span}\\{\bm{a}_{j}\\}$ and $\mathscr{B}={\rm
span}\\{\bm{b}_{j}\\}$ where $\\{\bm{a}_{i}\\}$ and $\\{\bm{b}_{i}\\}$ are the
finest resolution of the identity in ${\rm idem}(\mathscr{A})$ and ${\rm
idem}(\mathscr{B})$ respectively. Clearly, if $\bm{a}_{i}=\bm{b}_{i}$ for all
$i$ then $\mathscr{A}=\mathscr{B}$ which yields a contradiction. Therefore, we
assume that there exists an index $j$ such that $\bm{a}_{j}\neq\bm{b}_{i}$ for
all $i$. We can then notice that for all $\bm{v}\in\mathcal{W}$, we can write
$\bm{v}=\sum_{i}\mu_{i}\overline{\bm{a}}\wedge\bm{a}_{i}=\sum_{i}\nu_{i}\overline{\bm{b}}\wedge\bm{b}_{i}.$

For $j$ such that $\bm{a}_{j}\neq\bm{b}_{i}$ or all $i$ we can then write

$\bm{a}_{j}\wedge\bm{v}=\mu_{j}\overline{\bm{a}}\wedge\bm{a}_{j}=\sum_{i}\nu_{i}\bm{a}_{j}\wedge\overline{\bm{b}}\wedge\bm{b}_{i}.$

The first equality implies that over the support of each $\bm{a}_{j}$ every
$\bm{v}$ must be proportional to $\overline{\bm{a}}\wedge\bm{a}_{j}$. The
second equality, on the other hand, due to the fact $\bm{a}_{j}\neq\bm{b}_{j}$
implies at least two of the products
$\bm{a}_{j}\wedge\overline{\bm{b}}\wedge\bm{b}_{i}$ must be non-zero. In order
for the nontrivial sum to be always proportional to
$\overline{\bm{a}}\wedge\bm{a}_{j}$ it must be that the coefficients $\nu_{i}$
appear always in a fixed ratio. Hence, the corresponding $\bm{b}_{i}$ can be
substituted by their sum, and still generate the full $\cal W$ when multiplied
by a suitable vector $\overline{\bm{b}}$. This shows that $\mathscr{B}$ could
not be a minimal algebra unless $\bm{a}_{i}=\bm{b}_{i}$ for all $i,$ up to a
reordering.

Let then $\mathscr{A}^{*}$ be the unique algebra of minimal dimension such
that $\mathcal{W}\subseteq{\bm{x}}\wedge\mathscr{A}^{*}$ for some $\bm{w}$.
From Proposition 1 we know that $\mathscr{A}^{*}={\rm span}\\{\bm{a}_{j}\\}$
where $\\{\bm{a}_{i}\\}$ is the finest resolution of the identity in ${\rm
idem}(\mathscr{A}^{*})$. In particular $\\{\bm{a}_{j}\\}$ forms an orthogonal
basis for $\mathscr{A}^{*}$ and its elements have completing mutually-
orthogonal supports, i.e. ${\rm supp}(\bm{a}_{k})\perp{\rm supp}(\bm{a}_{j})$
for $k\neq j$ and $\sum_{j}\bm{a}_{j}=\bm{1}_{{\rm supp}(\mathcal{W})}$. We
can then observe that $\bm{x}\wedge\mathscr{A}^{*}={\rm
span}\\{\bm{x}\wedge\bm{a}_{j}\\}$ and that the vectors
$\bm{x}\wedge\bm{a}_{j}$ have complementary mutually-orthogonal supports. Then
for $\mathcal{W}\subseteq\bm{x}\wedge\mathscr{A}^{*}$ to hold it must be that
$\bm{w}=\sum_{j}\mu_{j}\bm{x}\wedge\bm{a}_{j}$ for all $\bm{w}\in\mathcal{W}$.

By the above discussion we can write
$\bm{w}_{i}=\sum_{j}\mu_{j}^{i}\bm{x}\wedge\bm{a}_{j}$ for each generator of
$\mathcal{W}$. Notice that, for all $j$, $\mu_{j}^{i}\neq 0$ for at least one
$i$. Let then use the definition of $\overline{\bm{w}}$ given in the statement
and, substituting the form of the $\bm{w}_{i}$ we just report we obtain
$\overline{\bm{w}}=\sum_{j}\sigma_{j}\bm{x}\wedge\bm{a}_{j}$ with
$\sigma_{j}=\sum_{i}\lambda_{i}\mu_{j}^{i}$. From the argument above, from the
fact that $\lambda_{i}\neq 0$ for all $i$ and from the fact that, by
hypothesis, $\overline{\bm{w}}$ has maximal support, we have that
$\sigma_{j}\neq 0$ for all $j$. Because of the structure of
$\\{\bm{x}\wedge\bm{a}_{j}\\}$ we have that

$(\bm{a}_{j}\wedge\overline{\bm{w}})^{-1}=\bm{a}_{j}\wedge\overline{\bm{w}}^{-1}=\sigma_{j}^{-1}(\bm{x}\wedge\bm{a}_{j})^{-1}=\sigma_{j}^{-1}\bm{x}^{-1}\wedge\bm{a}_{j},$

and thus
$\overline{\bm{w}}^{-1}=\sum_{j}\sigma_{j}^{-1}\bm{x}^{-1}\wedge\bm{a}_{j}.$
From this we have that the vector space
$\overline{\bm{w}}^{-1}\wedge\mathcal{W}$ is generated by vectors of the type

$\overline{\bm{w}}^{-1}\wedge\bm{w}_{i}=\sum_{j,k}\sigma_{j}^{-1}\mu_{k}^{i}\bm{x}^{-1}\wedge\bm{a}_{j}\wedge\bm{x}\wedge\bm{a}_{k}=\sum_{j}\sigma_{j}^{-1}\mu_{j}^{i}\bm{a}_{j}.$

This proves that
$\overline{\bm{w}}^{-1}\wedge\mathcal{W}\subseteq\mathscr{A}^{*}$ and that any
vector $\bm{v}\in\overline{\bm{w}}^{-1}\wedge\mathcal{W}$ can be written as
$\bm{v}=\sum_{i}v_{i}\overline{\bm{w}}^{-1}\wedge\bm{w}_{i}=\sum_{j}\xi_{j}\bm{a}_{j}$
with $\xi_{j}:=\sum_{i}v_{i}\sigma_{j}^{-1}\mu_{j}^{i}$. Let then consider any
two vectors $\bm{v},\bm{u}\in\overline{\bm{w}}^{-1}\wedge\mathcal{W}$ and
compute their $\wedge$-product,

$\bm{v}\wedge\bm{u}=\left(\sum_{j}\xi_{j}\bm{a}_{j}\right)\wedge\left(\sum_{j}\hat{\xi}_{j}\bm{a}_{j}\right)=\sum_{j}\xi_{j}\hat{\xi}_{j}\bm{a}_{j}.$

This implies that ${\rm
alg}(\overline{\bm{w}}^{-1}\wedge\mathcal{W})\subseteq\mathscr{A}^{*}$. On the
other hand, it trivially holds that
$\mathcal{W}\subseteq\overline{\bm{w}}\wedge{\rm
alg}(\overline{\bm{w}}^{-1}\wedge\mathcal{W})$. But then, since we assumed
that $\mathscr{A}^{*}$ was the unique algebra of minimal dimension such that
$\mathcal{W}\subseteq{\bm{x}}\wedge\mathscr{A}^{*}$ for some $\bm{x}$ it must
hold that ${\rm
alg}(\overline{\bm{w}}^{-1}\wedge\mathcal{W})=\mathscr{A}^{*}$.

Finally, since $\overline{\bm{w}}\in\mathcal{W}$, then
$\overline{\bm{w}}^{-1}\wedge\overline{\bm{w}}=\bm{1}_{{\rm
supp}(\mathcal{W})}\in(\overline{\bm{w}}^{-1}\wedge\mathcal{W})\subseteq\mathscr{A}^{*}$.
∎

######  Remark.

Theorem 3 shows that, given any choice of the effective subspace, we can
construct a vector $\overline{\bm{w}}$ such that the algebra ${\rm
alg}(\overline{\bm{w}}^{-1}\wedge\mathcal{E})$ has minimal dimension. However,
not all such $\overline{\bm{w}}$ are positive over the support of
$\mathcal{E}$. As a matter of fact, it could happen that some choices of
$\mathcal{E}$ do not contain any non-negative vector, while
$\overline{\bm{w}}=\bm{p}$ being non-negative is fundamental to construct a
stochastic reduction.

Theorem 3 is nonetheless sufficient to determine the optimal reduction for a
class of HMMs, namely observable ones.

######  Proposition 4.

Let $\\{\bm{r}_{i}\\}$ be an $N$-dimensional set of positive generators of
$\mathcal{R}$ and let $\overline{\bm{p}}:=\sum\bm{r}_{i}/N$. Then, if the
couple $(P,C)$ is observable, $\mathscr{A}:={\rm
alg}(\overline{\bm{p}}^{-1}\wedge\mathcal{R})$ provides the optimal reduction.

###### Proof.

By hypothesis we have that the couple $(P,C)$ is observable and thus
$\mathcal{N}=\\{\bm{0}\\}$. This implies that any choice of $\mathcal{E}$ is
just a change of basis of $\mathcal{R}$ and we can thus without loss of
generality assume that $\mathcal{E}=\mathcal{R}$. Then, using Theorem 3 we
have that $\bm{p}=\sum_{i}\bm{r}_{i}/N$, provides the minimal dimension for
${\rm alg}(\bm{p}^{-1}\wedge\mathcal{R})$ and thus the optimal reduction. ∎

Notice that this results applies in particular to finite-state Markov chains.
The corresponding optimal reduction is then a maximally-lumped version of the
original process [23].

In order to address the general case, in addition to a distribution $\bf p$ we
also need to choose an effective subspace. Example 2 below illustrate sthat
not all effective spaces are equivalent and lead to different dimension for
the reduced model, making this choice critical towards the optimality of the
reduction. The most natural choice for the effective subspace is of course the
orthogonal complement (with respect to the natural inner product $\left<{\bf
x},{\bf y}\right>={\bf x}^{T}{\bf y}$) of $\mathcal{R}\cap\mathcal{N}$ in
$\mathcal{R}$. For the sake of clarity, in the following we denote this choice
of the effective subspace as $\mathcal{E}_{\perp}$. Let then
$\\{\bm{\varepsilon}_{i}\\}_{i=1,\ldots,d}$ be the set of generators of
$\mathcal{E}_{\perp}.$ Then any choice of the effective subspace can be
described as $\mathcal{E}={\rm
span}\\{\bm{\varepsilon}_{i}+\bm{n}_{i}\\}_{i=1,\ldots,d},$ where
$\\{\bm{n}_{i}\\}_{i=1,\ldots,d}$ is a set of vectors in $\mathcal{N}$.

We next show that the choice of the orthogonal complement
$\mathcal{E}_{\perp}$ always allows for finding a positive vector
$\overline{\bm{w}}=\overline{\bm{p}}$ as in the statement of Theorem 3, and
hence a valid stochastic reduction. The following proposition is instrumental
to this aim.

######  Proposition 5.

Let $\bm{p}\in\mathbb{R}^{n}$ be a probability vector, and let $\mathcal{V}$
be a vector space such that $\bm{1}^{T}\bm{v}=0$ for all
$\bm{v}\in\mathcal{V}$. Let then $\Pi_{\mathcal{V}}$ be the orthogonal
projector on $\mathcal{V}$ with respect to the standard inner product
$\left<\cdot,\cdot\right>$. Then $\bm{q}:=\bm{p}-\Pi_{\mathcal{V}}\bm{p}$ is a
probability vector.

###### Proof.

Let us start by defining $\bm{w}:=\bm{1}/2-\bm{p}$. We can then write
$\bm{p}=\bm{1}/2-\bm{w}$ to notice that $\bm{p}_{i}\in[0,1]$ if and only if
$-1/2\leq\bm{w}_{i}\leq 1/2$, that is if and only if
$\left|\left|\bm{w}\right|\right|_{\infty}\leq 1/2$. Moreover, we have that
$\bm{1}^{T}\bm{p}=1$ if and only if $\bm{1}^{T}\bm{w}=(n-2)/2$.

We can then compute $\bm{q}$:

$\displaystyle\bm{q}$
$\displaystyle=\bm{1}/2-\bm{w}-\Pi_{\mathcal{V}}\bm{1}/2+\Pi_{\mathcal{V}}\bm{w}$
$\displaystyle=\bm{1}/2-\underbrace{(I-\Pi_{\mathcal{V}})}_{=:\Pi_{\mathcal{V}^{\perp}}}\bm{w}=\bm{1}/2-\Pi_{\mathcal{V}^{\perp}}\bm{w}$

where we used the the hypothesis $\bm{1}^{T}\bm{v}=0$ for all
$\bm{v}\in\mathcal{V}$ to say that $\Pi_{\mathcal{V}}\bm{1}=\bm{0}$. Then,
since $\Pi_{\mathcal{V}^{\perp}}$ is an orthogonal projection, and thus a
contraction in norm, we have that
$\left|\left|\Pi_{\mathcal{V}^{\perp}}\bm{w}\right|\right|_{\infty}\leq\left|\left|\bm{w}\right|\right|_{\infty}$.
Then, using the argument above, we have that $\bm{q}$ is a non-negative vector
with $\bm{q}_{i}\in[0,1]$. Lastly we have that
$\bm{1}^{T}\bm{q}=\bm{1}^{T}\bm{1}/2-\bm{1}^{T}\bm{w}=n/2-(n-2)/2=1$. ∎

######  Remark.

We should notice that we stated and proved the previous result regarding only
the standard inner product $\left<\cdot,\cdot\right>$ for sake of simplicity.
However, the same can be stated if the orthogonal projector
$\Pi_{\mathcal{V}}$ is defined with respect to a modified inner product
$\left<\cdot,\cdot\right>_{\bm{x}}$. The proof is identical to the one above.

The result we are after is then obtained as a corollary of the previous one.

######  Corollary 4.

Let $\mathcal{E}_{\perp}$ be the orthogonal complement of
$\mathcal{R}\cap\mathcal{N}$ to $\mathcal{R}$. Let $\\{\bm{r}_{i}\\}$ be an
$N$ dimensional set of probability vectors such that $\mathcal{R}={\rm
span}\\{\bm{r}_{i}\\}$. Then
$\bm{\varepsilon}_{i}:=\bm{r}_{i}-\Pi_{\mathcal{R}\cap\mathcal{N}}\bm{r}_{i}$
are such that $\mathcal{E}_{\perp}={\rm span}\\{\bm{\varepsilon}_{i}\\}$.
Moreover, $\overline{\bm{\varepsilon}}=\sum_{i}\bm{\varepsilon}_{i}/N$
satisfies ${\rm supp}(\overline{\bm{\varepsilon}})={\rm supp}(\mathcal{E})$
and $\overline{\bm{\varepsilon}}_{i}\geq 0$ for all $i$.

###### Proof.

From Lemma 3 we have that $\bm{1}^{T}\bm{x}=0$ for all $\bm{x}\in\mathcal{N}$
and thus, by applying the proposition above on every generator of
$\mathcal{R}$ we have that the set $\\{\bm{\varepsilon}_{i}\\}$ is a set of
probability vector. Being $\overline{\bm{\varepsilon}}$ a convex combination
of probability vectors it is itself a probability vector and it shares the
same support as $\mathcal{E}$. ∎

Other choices are possible, and the choice of the effective subspace can
influence the dimension of the reduced model, as illustrated in the follpowing
example.

######  Example 2.

Consider the following spaces:

$\displaystyle\mathcal{R}={\rm span}\left\\{\begin{bmatrix}1/2\\\ 1/2\\\ 0\\\
0\end{bmatrix},\begin{bmatrix}0\\\ 0\\\ 1\\\
0\end{bmatrix},\begin{bmatrix}0\\\ 0\\\ 0\\\
1\end{bmatrix}\right\\},\quad\mathcal{N}={\rm span}\left\\{\begin{bmatrix}0\\\
0\\\ 1\\\ -1\end{bmatrix}\right\\}$

then we clearly have that $\mathcal{R}\cap\mathcal{N}=\mathcal{N}$. Let us
denote with $\mathcal{E}^{*}$ the orthogonal complement of
$\mathcal{R}\cap\mathcal{N}$ to $\mathcal{R}$, i.e.

$\displaystyle\mathcal{E}_{\perp}={\rm span}\left\\{\begin{bmatrix}1/2\\\
1/2\\\ 0\\\ 0\end{bmatrix},\begin{bmatrix}0\\\ 0\\\ 1/2\\\
1/2\end{bmatrix}\right\\}.$

We can easily notice that $\mathcal{E}_{\perp}$ is a unital algebra. Let us
now consider another completion $\mathcal{E}$ of $\mathcal{R}\cap\mathcal{N}$
to $\mathcal{R}$. In general, we can write

$\displaystyle\mathcal{E}={\rm span}\left\\{\begin{bmatrix}1\\\ 1\\\ a\\\
-a\end{bmatrix},\begin{bmatrix}0\\\ 0\\\ 1+b\\\ 1-b\end{bmatrix}\right\\}$

for some values $a,b\in\mathbb{R}$. We can then consider two cases. First, if
$a=0$ and $b\neq 0$ we can choose
$\overline{\bm{v}}=\begin{bmatrix}1&1&1+b&1-b\end{bmatrix}^{T}$ thus obtaining
${\rm alg}(\overline{\bm{v}}^{-1}\wedge\mathcal{E})=\mathcal{E}^{*}$. On the
other hand, if we have $a\neq 0$ and $b\neq 0$ we can choose
$\overline{\bm{w}}=\begin{bmatrix}1&1&a+1+b&-a+1-b\end{bmatrix}^{T}$ (assuming
that $a+b\neq\pm 1$) thus obtaining

$\displaystyle{\rm alg}(\overline{\bm{w}}^{-1}\wedge\mathcal{E})={\rm
span}\left\\{\begin{bmatrix}1\\\ 1\\\ 0\\\ 0\end{bmatrix},\begin{bmatrix}0\\\
0\\\ 1\\\ 0\end{bmatrix},\begin{bmatrix}0\\\ 0\\\ 0\\\
1\end{bmatrix}\right\\}.$

This example shows that the choice of the effective subspace can affect the
size of the reduced model.

Based on the analytical and numerical examples we examined, we formulate the
following conjecture on the optimality of the natural orthogonal complement.

######  Conjecture 1.

Let $\mathcal{E}_{\perp}$ be defined as above and let $\overline{\bm{p}}$ be
defined as in Corollary 4. Then, given any other choice of $\mathcal{E}$ and
$\bm{w}$ non-negative it holds that

$\dim(\mathcal{E}_{\perp})\leq\dim({\rm
alg}(\overline{\bm{p}}^{-1}\wedge\mathcal{E}_{\perp}))\leq\dim({\rm
alg}({\bm{w}}^{-1}\wedge\mathcal{E})).$

######  Remark.

The first inequality is true by construction since $\overline{p}$ is positive.
Moreover, if $\dim(\mathcal{E}_{\perp})=\dim({\rm
alg}(\overline{\bm{p}}^{-1}\wedge\mathcal{E}_{\perp})),$ since
$\dim(\mathcal{E}^{\perp})=\dim(\mathcal{E})$ and
$\dim(\mathcal{E})\leq\dim({\rm alg}({\bm{w}}^{-1}\wedge\mathcal{E})),$ then
the choice of $\mathcal{E}_{\perp}$ is optimal. Also notice that, removing the
assumption that ${\bm{w}}$ is non-negative makes the statement false. A
counterexample is presented at the end of Example 4. However, having $\bm{w}$
non-negative is necessary in our framework in order to obtain a stochastic
reduced model.

##  VIII Examples

######  Example 3.

Let consider the HMM provided in [16, Example 3]:

$\displaystyle P$
$\displaystyle=\left[\begin{array}[]{ccccc}1/3&1/6&1/4&1/4&0\\\
1/6&1/3&0&1/4&1/4\\\ 1/3&1/6&1/4&1/4&0\\\ 1/6&1/6&1/6&0&1/2\\\
0&1/6&1/3&1/4&1/4\end{array}\right],\quad\mathcal{S}=\left\\{\begin{bmatrix}1/5\\\
1/5\\\ 1/5\\\ 1/5\\\ 1/5\end{bmatrix}\right\\}$ $\displaystyle C$
$\displaystyle=\left[\begin{array}[]{ccccc}1&1&1&0&0\\\ 0&0&0&1&0\\\
0&0&0&0&1\\\ \end{array}\right].$

We shall start by studying the single-time marginal problem. We can observe
that $\bm{p}_{0}\in\mathcal{S}$ is an equilibrium for $P$ and thus
$\mathcal{R}={\rm span}\\{\mathcal{S}\\}$ and also that $\mathcal{N}={\rm
span}\\{\begin{bmatrix}1&-2&1&0&0\end{bmatrix}^{T}\\}$. Clearly the
intersection contains only the zero vector,
$\mathcal{R}\cap\mathcal{N}=\\{\bm{0}\\}$ and thus the effective subspace can
be taken as the reachable one: $\mathcal{E}_{\perp}=\mathcal{R}$. If we then
take $\overline{\bm{p}}=\bm{p}_{0}$ we obtain $\mathscr{A}={\rm
alg}(\overline{\bm{p}}^{-1}\wedge\mathcal{E})={\rm span}\\{\bm{1}\\}$. The
corresponding stochastic reduction and injection matrices are $R=\bm{1}^{T}$
and $J=\overline{\bm{p}}$ which provide the (trivial) reduced model:

$\displaystyle\widecheck{P}$
$\displaystyle=\begin{bmatrix}1\end{bmatrix},\quad\widecheck{\mathcal{S}}=\left\\{\begin{bmatrix}1\end{bmatrix}\right\\},\quad\widecheck{C}=\begin{bmatrix}3/5&1/5&1/5\end{bmatrix}^{T}.$

We next focus on the multi-time marginal problem. We have that
$\mathcal{N_{C}}=\mathcal{N},$ while the conditioned-reachable is equal to:

$\mathcal{R_{C}}={\rm span}\left\\{\begin{bmatrix}1/5\\\ 1/5\\\ 1/5\\\ 0\\\
0\end{bmatrix},\begin{bmatrix}0\\\ 0\\\ 0\\\ 1/5\\\
0\end{bmatrix},\begin{bmatrix}0\\\ 0\\\ 0\\\ 0\\\
1/5\end{bmatrix},\begin{bmatrix}1\\\ -2\\\ 1\\\ 0\\\ 0\end{bmatrix}\right\\}.$

This implies that the intersection
$\mathcal{R_{C}}\cap\mathcal{N_{C}}=\mathcal{N_{C}}$ and thus:

$\mathcal{E_{C}}_{\perp}={\rm span}\left\\{\begin{bmatrix}1\\\ 1\\\ 1\\\ 0\\\
0\end{bmatrix},\begin{bmatrix}0\\\ 0\\\ 0\\\ 1\\\
0\end{bmatrix},\begin{bmatrix}0\\\ 0\\\ 0\\\ 0\\\ 1\end{bmatrix}\right\\}.$

Then, we can notice that $\mathcal{E_{C}}$ is a unital algebra and by taking
$\overline{\bm{p}}=\bm{1}/5$ we obtain the stochastic reduction and injection
matrices

$R=\begin{bmatrix}1&1&1&0&0\\\ 0&0&0&1&0\\\ 0&0&0&0&1\end{bmatrix},\quad
J=\begin{bmatrix}1/3&0&0\\\ 1/3&0&0\\\ 1/3&0&0\\\ 0&1&0\\\ 0&0&1\end{bmatrix}$

that leads to the reduced model

$\displaystyle\widecheck{P}$ $\displaystyle=\begin{bmatrix}2/3&3/4&1/4\\\
1/6&0&1/2\\\
1/6&1/4&1/4\end{bmatrix},\quad\widecheck{\mathcal{S}}=\left\\{\begin{bmatrix}3/5\\\
1/5\\\ 1/5\end{bmatrix}\right\\}$ $\displaystyle\widecheck{C}$
$\displaystyle=\begin{bmatrix}1&0&0\\\ 0&1&0\\\ 0&0&1\end{bmatrix}.$

######  Example 4.

Consider the HMM defined by:

$\displaystyle P$ $\displaystyle=\left[\begin{array}[]{ccccc}1/2&0&1/3&1/4\\\
0&1/3&1/3&1/4\\\ 1/2&0&1/3&0\\\
0&2/3&0&1/2\end{array}\right],\quad\mathcal{S}=\left\\{\begin{bmatrix}1\\\
0\\\ 0\\\ 0\end{bmatrix},\begin{bmatrix}0\\\ 1\\\ 0\\\
0\end{bmatrix}\right\\}$ $\displaystyle C$
$\displaystyle=\left[\begin{array}[]{ccccc}1/4&1/4&1/2&7/16\\\
3/4&3/4&1/2&9/16\end{array}\right].$

In this case we are only interested in the single-time marginal problem. We
can notice that $\mathcal{R}=\mathbb{R}^{n}$ and thus

$\mathcal{R}\cap\mathcal{N}=\mathcal{N}={\rm span}\left\\{\begin{bmatrix}1\\\
-1\\\ 0\\\ 0\end{bmatrix},\begin{bmatrix}-1\\\ 0\\\ -3\\\
4\end{bmatrix}\right\\}.$

Then we can consider the effective subspace as the orthogonal complement of
$\mathcal{N}$, that is

$\mathcal{E}_{\perp}={\rm span}\left\\{\begin{bmatrix}4/9\\\ 4/9\\\ 0\\\
1/9\end{bmatrix},\begin{bmatrix}0\\\ 0\\\ 4/7\\\ 3/7\end{bmatrix}\right\\}.$

Then we can define $\overline{\bm{p}}:=\bm{1}/4$ to obtain

$\mathscr{A}={\rm alg}(\overline{\bm{p}}^{-1}\wedge\mathcal{E}_{\perp})={\rm
span}\left\\{\begin{bmatrix}1\\\ 1\\\ 0\\\ 0\end{bmatrix},\begin{bmatrix}0\\\
0\\\ 1\\\ 0\end{bmatrix},\begin{bmatrix}0\\\ 0\\\ 0\\\
1\end{bmatrix}\right\\}.$

Notice that in this case the dimension of the algebra is greater than the
effective subspace. We thus obtain the stochastic reduction and injection
matrices

$R=\begin{bmatrix}1&1&0&0\\\ 0&0&1&0\\\ 0&0&0&1\end{bmatrix},\quad
J=\begin{bmatrix}1/2&0&0\\\ 1/2&0&0\\\ 0&1&0\\\ 0&0&1\end{bmatrix}$

that leads to the reduced model

$\displaystyle\widecheck{P}$ $\displaystyle=\begin{bmatrix}5/12&2/3&1/2\\\
1/4&1/3&0\\\
1/3&0&1/2\end{bmatrix},\quad\widecheck{\mathcal{S}}=\left\\{\begin{bmatrix}1\\\
0\\\ 0\end{bmatrix}\right\\}$ $\displaystyle\widecheck{C}$
$\displaystyle=\begin{bmatrix}1/4&1/2&7/16\\\ 3/4&1/2&9/16\end{bmatrix}.$

Suppose that, instead of the orthogonal complement, we were to consider the
following space as effective subspace:

$\mathcal{E}={\rm span}\left\\{\begin{bmatrix}6\\\ 5/2\\\ 3/2\\\
-1\end{bmatrix},\begin{bmatrix}2\\\ 5/6\\\ 25/2\\\
-25/3\end{bmatrix}\right\\}.$

We can immediately notice that there is no convex combination of the
generators of $\mathcal{E}$ such that it is positive, however, if we consider
$\bm{v}=\begin{bmatrix}8&10/3&14&-28/3\end{bmatrix}^{T}$ we have that

$\mathscr{A}={\rm alg}({\bm{v}}^{-1}\wedge\mathcal{E})={\rm
span}\left\\{\begin{bmatrix}1\\\ 1\\\ 0\\\ 0\end{bmatrix},\begin{bmatrix}0\\\
0\\\ 1\\\ 1\end{bmatrix}\right\\}$

thus showing that a smaller algebra could be found for the reduction, if we
were to consider vectors that are not non-negative.

##  IX Conclusions and outlook

In this work, we exploited system-theoretic ideas and algebraic representation
of probability spaces to obtain effective reductions of HMMs that preserve the
marginals of the original output process, in either the single- or multi-time
case. While optimal reductions are explicitly characterized for observable
HMMs, the freedom of choice in the effective subspace makes finding the
optimal reductions more challenging in the general case. Nonetheless, we
provide an algorithm that produces reduced HMMs of minimal dimension in all
considered examples. Proving its conjectured minimality in general will be the
focus of future work.

Other natural developments of the proposed framework include a relaxation of
the method so that it allows for approximate preservation of the marginals,
thus yielding significant reductions in practical situations where noise and
partial knowledge might make the exact equivalence we require in this work too
stringent. In fact, future work will be devoted to the adaptation and
application of the method to approximate coarse graining of large-scale
systems, to address otherwise untreatable problems [13, 14, 15]. The algebraic
approach also naturally extends to the non-commutative domain, and our method
will be extended to quantum systems, in particular quantum walks and open
systems in general. Analogies between HMM and quantum walks have been already
noted in [33], as well as [34] and [35], which extend the result of [16] to
include quantum walks. Lastly, the algebraic viewpoint makes our results
potentially interesting towards the solution of outstanding open problems in
realization theory and model reduction for positive systems [36].

##  X Acknowledgements

T.G. and F.T. wish to thank Lorenzo Finesso, Augusto Ferrante and Lorenza
Viola for motivating and stimulating discussions on the topics of this work.

## References

  * [1] L.R. Rabiner  “A tutorial on hidden Markov models and selected applications in speech recognition”  In _Proceedings of the IEEE_ 77.2, 1989, pp. 257–286
  * [2] Negin Najkar, Farbod Razzazi and Hossein Sameti  “A novel approach to HMM-based speech recognition systems using particle swarm optimization” The BIC-TA 2009 Special Issue  In _Mathematical and Computer Modelling_ 52.11, 2010, pp. 1910–1920
  * [3] P Baldi, Y Chauvin, T Hunkapiller and M A McClure  “Hidden Markov models of biological primary sequence information.”  In _Proceedings of the National Academy of Sciences_ 91.3, 1994, pp. 1059–1063
  * [4] Arthur L Delcher et al.  “Improved microbial gene identification with GLIMMER”  In _Nucleic acids research_ 27.23 Oxford University Press, 1999, pp. 4636–4641
  * [5] Anders Krogh, I Saira Mian and David Haussler  “A hidden Markov model that finds genes in E. coli DNA”  In _Nucleic acids research_ 22.22 Oxford University Press, 1994, pp. 4768–4778
  * [6] M. Vidyasagar  “Hidden Markov Processes: Theory and Applications to Biology”  Princeton University Press, 2014
  * [7] Marina Cidota and Monica Dumitrescu  “A multinomial - Hidden Markov model for communication systems influenced by external factors”  In _2012 7th IEEE International Symposium on Applied Computational Intelligence and Informatics (SACI)_ , 2012, pp. 235–240
  * [8] Alberto Dainotti et al.  “Internet traffic modeling by means of Hidden Markov Models”  In _Computer Networks_ 52.14, 2008, pp. 2645–2662
  * [9] Kavé Salamatian and Sandrine Vaton  “Hidden markov modeling for network communication channels”  In _ACM SIGMETRICS Performance Evaluation Review_ 29.1 ACM New York, NY, USA, 2001, pp. 92–101
  * [10] M Vidyasagar  “(Hidden) Markov Processes: Theory and Applications to Biology”, 2011, pp. 288
  * [11] Laurent Mevel and Lorenzo Finesso  “Bayesian estimation of hidden Markov models”  In _Proceedings of the Mathematical Theory of Networks and Systems Conference, MTNS-2000_ , 2000
  * [12] Qingqing Huang, Rong Ge, Sham Kakade and Munther Dahleh  “Minimal Realization Problems for Hidden Markov Models”  In _IEEE Transactions on Signal Processing_ 64.7, 2016, pp. 1896–1904
  * [13] Athanasios C Antoulas  “Approximation of large-scale dynamical systems”  SIAM, 2005
  * [14] X Cheng and JMA Scherpen  “Model Reduction Methods for Complex Network Systems”  In _Annual Review of Control, Robotics, and Autonomous Systems_ 4 Annual Reviews, 2021, pp. 425–453
  * [15] Henrik Sandberg and Richard M Murray  “Model reduction of interconnected linear systems”  In _Optimal Control Applications and Methods_ 30.3 Wiley Online Library, 2009, pp. 225–245
  * [16] H. Ito, S.-I. Amari and K. Kobayashi  “Identifiability of hidden Markov information sources and their minimum degrees of freedom”  In _IEEE Transactions on Information Theory_ 38.2, 1992, pp. 324–333
  * [17] John Von Neumann  “Mathematical foundations of quantum mechanics: New edition”  Princeton university press, 2018
  * [18] Ola Bratteli and Derek William Robinson  “Operator algebras and quantum statistical mechanics: Volume 1: C*-and W*-Algebras. Symmetry Groups. Decomposition of States”  Springer Science & Business Media, 2012
  * [19] Paul A Meyer  “Quantum probability for probabilists”  Springer Science & Business Media, 1995
  * [20] Terrence Tao  “254A, Notes 5: Free probability”, 2010  URL: https://terrytao.wordpress.com/2010/02/10/245a-notes-5-free-probability/
  * [21] Alexander Schönhuth  “Complete identification of binary-valued hidden Markov processes”  In _arXiv preprint arXiv:1101.3712_ , 2011
  * [22] Tommaso Grigoletto and Francesco Ticozzi  “Approximate reduction of Hidden Markov Models with algebraic tools”  In _In preparation_ , 2022
  * [23] John G. Kemeny and James Laurie Snell  “Finite Markov Chains: With a New Appendix ”Generalization of a Fundamental Matrix””, Undergraduate Texts in Mathematics  New York, NY Heidelberg Berlin: Springer, 1983
  * [24] L.B. White, R. Mahony and G.D. Brushe  “Lumpable hidden Markov models-model reduction and reduced complexity filtering”  In _IEEE Transactions on Automatic Control_ 45.12, 2000, pp. 2297–2306
  * [25] Nihat Ay and James P Crutchfield  “Reductions of hidden information sources”  In _Journal of Statistical Physics_ 120.3 Springer, 2005, pp. 659–684
  * [26] Simon Apers, Alain Sarlette and Francesco Ticozzi  “Characterizing limits and opportunities in speeding up Markov chain mixing”  In _Stochastic Processes and their Applications_ 136, 2021, pp. 145–191
  * [27] Hans Maassen  “Quantum probability”  In _Quantum Probability Communications: Qp-pq (Volumes 12)_ 12 World Scientific, 2003, pp. 23
  * [28] Tommaso Grigoletto and Francesco Ticozzi  “Model Reduction for Quantum Open Dynamic: A System-Theoretic Approach”  In _In preparation_ , 2022
  * [29] G. Marro and G. Basile  “Controlled and Conditioned Invariants in Linear System Theory”, 1994
  * [30] W. M. Wonham  “Linear Multivariable Control: A Geometric Approach”
  * [31] Howard Harry Rosenbrock  “State-space and multivariable theory”  Wiley Interscience Division, 1970
  * [32] Shuzhi Sam Ge, Zhendong Sun and Tong Heng Lee  “Reachability and controllability of switched linear discrete-time systems”  In _IEEE Transactions on Automatic Control_ 46.9 IEEE, 2001, pp. 1437–1441
  * [33] Simon Apers, Alain Sarlette and Francesco Ticozzi  “Simulation of quantum walks and fast mixing with classical processes”  In _Phys. Rev. A_ 98 American Physical Society, 2018, pp. 032115
  * [34] Ulrich Faigle and Alexander Schönhuth  “Efficient Tests for Equivalence of Hidden Markov Processes and Quantum Random Walks”  In _IEEE Transactions on Information Theory_ 57.3, 2011, pp. 1746–1753
  * [35] Alexander Schonhuth  “Simple and efficient solution of the identifiability problem for hidden Markov sources and quantum random walks”  In _2008 International Symposium on Information Theory and Its Applications_ , 2008, pp. 1–6
  * [36] Luca Benvenuti and Lorenzo Farina  “A tutorial on the positive realization problem”  In _IEEE Transactions on automatic control_ 49.5 IEEE, 2004, pp. 651–664

##  Appendix A A reduction result for switching autonomous systems

This appendix is dedicated to introduce a general condition ensuring exact
model reduction for switching autonomous systems. Consider a discrete-time,
autonomous, switching, linear system

$\begin{cases}\bm{x}(t+1)=F_{i}\bm{x}(t)\\\ \bm{y}(t)=H\bm{x}(t)\\\
\bm{x}(0)\in\mathcal{I}\end{cases}$

denoted by the triplet $(\\{F_{i}\\},H,\mathcal{I})$. The evolution at any
time clearly depends on the sequence of evolutions $F_{i}$ activated. Let us
denote with $\bm{y}(s_{0}^{l})$ the output of the system at time $l$
associated to a sequence $s_{0}^{l}=s_{l},\dots,s_{0}$ of length $l$ of
selected evolution $F_{s_{k}}$. The output at any time $l>0$ can be computed
as $\bm{y}(s_{0}^{l})=H\prod_{j=l}^{0}F_{{\tt{s}}_{j}}\bm{x}_{0}$ while for
$t=0$ we have $\bm{y}(0)=H\bm{x}_{0}$.

Let $\mathcal{R}\subseteq\mathbb{R}^{n}$ be a linear subspace such that
$\mathcal{I}\subseteq\mathcal{R}$ and is $F_{i}$-invariant, i.e.
$F_{i}\mathcal{R}\subseteq\mathcal{R}$, for all $i$. Let
$\mathcal{N}\subseteq\mathbb{R}^{n}$ be a linear subspace such that
$\mathcal{N}\subseteq\ker H$ and is $F_{i}$-invariant, i.e.
$\mathcal{N}F_{i}\subseteq\mathcal{N}$, for all $i$. Let then define
$\mathcal{E}$ to be any completion of $\mathcal{R}\cap\mathcal{N}$ to
$\mathcal{R}$, i.e.
$\mathcal{R}=(\mathcal{R}\cap\mathcal{N})\oplus\mathcal{E}$.

######  Theorem 4.

Consider any subspace $\mathcal{V}$ such that
$\mathcal{E}\subseteq\mathcal{V}$ with $m=\dim(\mathcal{V})$ and let
$\Pi_{\mathcal{V}}$ be the orthogonal projection onto $\mathcal{V}$ with
respect to an inner product $\left<\cdot,\cdot\right>$. Let
$R:\mathbb{R}^{n}\to\mathbb{R}^{m}$ and $J:\mathbb{R}^{m}\to\mathcal{V}$ be
two factors of the orthogonal projection, $\Pi_{\mathcal{V}}=JR$.

Let consider the reduced model
$(\\{\widecheck{F}_{i}\\},\widecheck{H},\widecheck{\mathcal{I}})=(\\{RF_{i}J\\},HJ,R\mathcal{I})$.
Then the reduced model reproduces the same output as the original model, i.e.

$H\prod_{j=l}^{0}F_{{\tt{s}}_{j}}\bm{x}_{0}=\widecheck{H}\prod_{j=l}^{0}\widecheck{F}_{{\tt{s}}_{j}}\widecheck{\bm{x}}_{0}$

for any sequence $s_{0}^{l}$ and any initial condition $\bm{x}_{0}\in{\rm
span}\\{\mathcal{I}\\}$ and the relative $\widecheck{\bm{x}}_{0}=R\bm{x}_{0}$.

$\displaystyle\left[\prod_{j=l}^{0}F_{{\tt{s}}_{j}}-\Pi_{\mathcal{V}}\prod_{j=l}^{0}F_{{\tt{s}}_{j}}\Pi_{\mathcal{V}}\right]\bm{x}_{0}$
$\displaystyle=\left[(\Pi_{\cal{V}}+\Pi_{\mathcal{T}})F_{{\tt{s}}_{l}}(\Pi_{\cal{V}}+\Pi_{\mathcal{T}})\prod_{j=l-1}^{0}F_{{\tt{s}}_{j}}-\Pi_{\mathcal{V}}\prod_{j=l}^{0}F_{{\tt{s}}_{j}}\Pi_{\mathcal{V}}\right]\bm{x}_{0}$
$\displaystyle=\left[[\Pi_{\cal{V}}F_{{\tt{s}}_{l}}\Pi_{\cal{V}}+\Pi_{\mathcal{T}}F_{{\tt{s}}_{l}}\Pi_{\cal{V}}+F_{{\tt{s}}_{l}}\Pi_{\mathcal{T}}]\prod_{j=l-1}^{0}F_{{\tt{s}}_{j}}-\Pi_{\cal{V}}F_{{\tt{s}}_{l}}\Pi_{\cal{V}}\Pi_{\mathcal{V}}\prod_{j=l-1}^{0}F_{{\tt{s}}_{j}}\Pi_{\mathcal{V}}\right]\bm{x}_{0}$
$\displaystyle=\Pi_{\cal{V}}F_{{\tt{s}}_{l}}\Pi_{\cal{V}}\underbrace{\left(\prod_{j=l-1}^{0}F_{{\tt{s}}_{j}}-\Pi_{\mathcal{V}}\prod_{j=l-1}^{0}F_{{\tt{s}}_{j}}\Pi_{\mathcal{V}}\right)\bm{x}_{0}}_{\bm{v}}+\left[[\Pi_{\mathcal{T}}F_{{\tt{s}}_{l}}\Pi_{\cal{V}}+F_{{\tt{s}}_{l}}\Pi_{\mathcal{T}}]\prod_{j=l-1}^{0}F_{{\tt{s}}_{j}}\right]\bm{x}_{0}$
$\displaystyle=\Pi_{\cal{V}}F_{{\tt{s}}_{l}}\Pi_{\cal{V}}\bm{v}+\Pi_{\mathcal{T}}F_{{\tt{s}}_{l}}\Pi_{\cal{V}}\prod_{j=l-1}^{0}F_{{\tt{s}}_{j}}\bm{x}_{0}+F_{{\tt{s}}_{l}}\Pi_{\mathcal{T}}\prod_{j=l-1}^{0}F_{{\tt{s}}_{j}}\bm{x}_{0}$
(12)

###### Proof.

Let $\mathcal{W}_{1}$ be the completion of $\mathcal{R}\cap\mathcal{N}$ to
$\mathcal{N}$, i.e.
$\mathcal{N}=\mathcal{W}_{1}\oplus(\mathcal{R}\cap\mathcal{N})$; let
$\mathcal{W}_{2}$ be the completion of
$(\mathcal{R}\cap\mathcal{N})\oplus\mathcal{E}\oplus\mathcal{W}_{1}$ to
$\mathbb{R}^{n}$, i.e.
$\mathbb{R}^{n}=\mathcal{W}_{1}\oplus\mathcal{W}_{2}\oplus\mathcal{E}\oplus(\mathcal{R}\cap\mathcal{N})$;
let $\mathcal{T}$ the remainder sub-space, such that $\mathbb{R}^{n}=\cal
V\oplus\mathcal{T}$ and thus
$\mathcal{T}\subseteq(\mathcal{N}\cap\mathcal{R})\oplus\mathcal{W}_{1}\oplus\mathcal{W}_{2}$.
Let us also denote with $\Pi_{\mathcal{T}}$ the orthogonal projector onto
$\mathcal{T}$ with respect to the considered inner product
$\left<\cdot,\cdot\right>$.

We can notice that, for any sequence $s_{0}^{l}$ we have that
$\widecheck{H}\prod_{j=l}^{0}\widecheck{F}_{{\tt{s}}_{j}}\widecheck{\bm{x}}_{0}=H\Pi_{\mathcal{V}}\prod_{j=l}^{0}F_{{\tt{s}}_{j}}\Pi_{\mathcal{V}}\bm{x}_{0}$
and thus the statement can be also be put in the form

$H\left[\prod_{j=l}^{0}F_{{\tt{s}}_{j}}-\Pi_{\mathcal{V}}\prod_{j=l}^{0}F_{{\tt{s}}_{j}}\Pi_{\mathcal{V}}\right]\bm{x}_{0}=0$

for any sequence $s_{0}^{l}$ and for any $\bm{x}_{0}\in\mathcal{I}$. To prove
the statement we will thus show that for any sequence $s_{0}^{l}$ and for any
initial condition $\bm{x}_{0}\in\mathcal{I}$ it holds

$\left[\prod_{j=l}^{0}F_{{\tt{s}}_{j}}-\Pi_{\mathcal{V}}\prod_{j=l}^{0}F_{{\tt{s}}_{j}}\Pi_{\mathcal{V}}\right]\bm{x}_{0}\in\mathcal{N}\cap\mathcal{R}.$

We will prove this statement by induction.

Let then consider the case of $t=0$. We have to prove $[I-\Pi_{\cal
V}]\bm{x}_{0}\in\mathcal{N}\cap\mathcal{R}$. Then by noticing that,
$I-\Pi_{\cal V}=\Pi_{\mathcal{T}}$ $\bm{p}_{0}\in\cal R$ and that
$\Pi_{\mathcal{T}}\bm{p}_{0}\in\cal{N^{O}}\cap\mathcal{R}$, the statement is
proved in the case $t=0$.

Assume then that

$\bm{v}:=\left[\prod_{j=l-1}^{0}F_{{\tt{s}}_{j}}-\Pi_{\mathcal{V}}\prod_{j=l-1}^{0}F_{{\tt{s}}_{j}}\Pi_{\mathcal{V}}\right]\bm{x}_{0}\in\mathcal{N}\cap\mathcal{R}$

and we want to prove that

$\left[\prod_{j=l}^{0}F_{{\tt{s}}_{j}}-\Pi_{\mathcal{V}}\prod_{j=l}^{0}F_{{\tt{s}}_{j}}\Pi_{\mathcal{V}}\right]\bm{x}_{0}\in\mathcal{N}\cap\mathcal{R}.$

By rewriting this as in Equation (12) we can observe that it is equal to the
sum of three part. We can then notice that:

  * •

$\bm{v}\in\mathcal{N}\cap\mathcal{R}$ by assumption thus, $\Pi_{\cal
V}\bm{v}\in\cal{N^{O}}\cap\mathcal{R}$, $P\Pi_{\cal
V}\bm{v}\in\cal{N^{O}}\cap\mathcal{R}$ and also $\Pi_{\cal V}P\Pi_{\cal
V}\bm{v}\in\cal{N^{O}}\cap\mathcal{R}$;

  * •

$\prod_{j=l-1}^{0}F_{{\tt{s}}_{j}}\bm{x}_{0}\in\mathcal{R}$ by hypothesis,
$\Pi_{\mathcal{T}}\prod_{j=l-1}^{0}F_{{\tt{s}}_{j}}\bm{x}_{0}\in\cal{N^{O}}\cap\mathcal{R}$
and
$F_{{\tt{s}}_{l}}\Pi_{\mathcal{T}}\prod_{j=l-1}^{0}F_{{\tt{s}}_{j}}\bm{x}_{0}\in\cal{N^{O}}\cap\mathcal{R}$;

  * •

$\prod_{j=l-1}^{0}F_{{\tt{s}}_{j}}\bm{x}_{0}\in\mathcal{R}$ by hypothesis,
$\Pi_{\mathcal{V}}\prod_{j=l-1}^{0}F_{{\tt{s}}_{j}}\bm{x}_{0}\in\mathcal{R}$,
$F_{{\tt{s}}_{l}}\Pi_{\cal
V}\prod_{j=l-1}^{0}F_{{\tt{s}}_{j}}\bm{x}_{0}\in\cal R$ and
$\Pi_{\mathcal{R}}F_{{\tt{s}}_{j}}\Pi_{\cal
V}\prod_{j=l-1}^{0}F_{{\tt{s}}_{j}}\bm{x}_{0}\in\cal{N^{O}}\cap\cal R$.

Finally, since all the three summands belong to $\mathcal{N}\cap\mathcal{R}$,
their sum also belongs to the same subspace, and the statement is proved. ∎

##  Appendix B Proofs

This Appendix collects some proofs that were not included in the main text to
improve readability.

###### Proof of Proposition 1.

Let start from the first part of the statement. The fact that $\mathscr{A}$ is
closed under linear combinations and $\bm{1}\in\mathscr{A}$ follows directly
from the definition of $\mathscr{A}$. The closure of $\mathscr{A}$ under
element-wise product follows from the closure of $\mathcal{F}$ under the same
operation. In particular let consider $\bm{x},\bm{y}\in\mathscr{A}$, then
$\bm{x}\wedge\bm{y}=\sum_{i,j}x_{i}y_{j}\bm{f}_{i}\wedge\bm{f}_{j}$ and ,
since $\bm{f}_{i}\in\mathcal{F}$ for all $i$,
$\bm{f}_{i}\wedge\bm{f}_{j}\in\mathcal{F}$ and thus
$\bm{x}\wedge\bm{y}\in\mathscr{A}$. So $\mathscr{A}$ is an algebra, namely the
set of $\cal F$-measurable random variables, and it is the minimal one by
construction.

We can then consider the second part of the statement. First of all, notice
that the vectors that are idempotent for the element-wise product are composed
only of zeros and ones. Let then consider a general element
$\bm{x}\in\mathscr{A}$ and let $x_{i^{*}}=\max_{i=1,\dots,n}|x_{i}|$. We can
then compute $\bm{x}^{\prime}=\bm{x}/x_{i^{*}}\in\mathscr{A}$ that will have
value 1 in the positions where $\bm{x}$ has value $x_{i^{*}}$, possibly values
-1 in the position where $\bm{x}$ has value $-x_{i^{*}}$ and values in the
range $(-1,1)$ in all the others positions. We can then define
$\bm{x}^{\prime\prime}=0.5(\bm{x}^{\prime}+\bm{x}^{\prime}\wedge\bm{x}^{\prime})\in\mathscr{A}$
that will have have value 1 in the positions where $\bm{x}$ has value
$x_{i^{*}}$ and values in the range $(-1,1)$ in all the others positions.
Finally the first idempotent element of the desired set is
$\bm{f}_{1}=\lim_{n\to\infty}(\bm{x}^{\prime\prime})^{n}\in\mathscr{A}$ with
element-wise power. Notice that $\bm{f}_{1}$ will have 1 in the same positions
as $\bm{x}^{\prime}$ and zeros in all the others. This implies that
$\bm{f}_{1}$ is idempotent. By iterating the procedure on
$\bm{x}-x_{i^{*}}\bm{f}_{1},$ and so on, we obtain the whole set of idempotent
elements $\\{\bm{f}_{i}\\}\subset\mathscr{A}$ such that
$\bm{x}=\sum_{i}x_{i}\bm{f}_{i}$ up to a reordering of the coefficients
$x_{i}$. We shall denote with ${\rm idem}(\bm{x})$ the function that, given an
element $\bm{x}$, returns the set of idempotent elements $\\{\bm{f}_{i}\\}$
that generate $\bm{x}$. We then have that ${\rm
idem}(\mathscr{A})\supseteq\cup_{\bm{x}\in\mathscr{A}}{\rm idem}(\bm{x})$ by
definition, while to prove ${\rm
idem}(\mathscr{A})\subseteq\cup_{\bm{x}\in\mathscr{A}}{\rm idem}(\bm{x})$ it
suffice to notice that each element of ${\rm idem}(\mathscr{A})$ is also an
element of $\mathscr{A}$. This implies ${\rm
idem}(\mathscr{A})=\cup_{\bm{x}\in\mathscr{A}}{\rm idem}(\bm{x})$. Then, by
construction, it holds that ${\rm span}\\{{\rm
idem}(\mathscr{A})\\}=\mathscr{A}$.

We shall then notice that $\mathcal{F}={\rm idem}(\mathscr{A})$ contains the
elements, $\bm{0},\bm{1}\in\mathcal{A}$, and is closed under the operations
$\wedge$, $\vee$ and $\neg$. This shows that ${\rm idem}(\mathscr{A})$ is a
$\sigma$-algebra. Then, since $\mathscr{A}={\rm span}\\{{\rm
idem}(\mathscr{A})\\}$ then any element in $\mathscr{A}$ is ${\rm
idem}(\mathscr{A})$-measurable. Moreover, ${\rm idem}(\mathscr{A})$ is minimal
because subtracting any element form it would make that element (seen as a
r.v.) non measurable. We thus have $\mathcal{F}={\rm idem}(\mathscr{A})$.

Finally, ${\rm res}(\mathcal{F})\subset\mathcal{F}$ is such that
$\bm{f}_{i}\wedge\bm{f}_{j}=\bm{0}$, for all $\bm{f}_{i},\bm{f}_{j}\in{\rm
res}(\mathcal{F})$ $i\neq j$. This implies that
$\left<\bm{f}_{i},\bm{f}_{j}\right>=\delta_{i-j}$ which means that is a set of
orthogonal vectors. Moreover $\bm{f}=\vee_{\bm{f}_{j}\in S}\bm{f}_{j}$ with
$S\subseteq{\rm res}(\mathcal{F})$ for all
$\bm{f}\in\mathcal{F}\setminus\\{\bm{0}\\}$ or, equivalently,
$\bm{f}=\sum_{j}c_{j}\bm{f}_{j}$ with $c_{j}\in\\{0,1\\}$ for all
$\bm{f}\in\mathcal{F}$. This implies that $\mathscr{A}={\rm span}\\{{\rm
res}(\mathcal{A})\\}$ and thus ${\rm res}(\mathscr{A})$ is an orthogonal basis
for $\mathscr{A}$ and $\dim(\mathscr{A})=|{\rm res}(\mathscr{A})|$. ∎

###### Proof of Lemma 1.

First of all note that the modified inner product can be written in many
equivalent forms:
$\left<\bm{v},\bm{w}\right>_{\bm{p}}={\mathbb{E}}_{\bm{p}}[\bm{v}\wedge\bm{w}]=\left<\bm{p},\bm{v}\wedge\bm{w}\right>=\left<\bm{p}\wedge\bm{v},\bm{w}\right>=\left<\bm{v},\bm{p}\wedge\bm{w}\right>$.

Let us then consider ${\mathbb{E}}_{|\mathscr{A},\bm{p}}$. We can notice that
${\rm image}({\mathbb{E}}_{|\mathscr{A},\bm{p}})=\mathscr{A}$ and that
${\mathbb{E}}_{|\mathscr{A},\bm{p}}^{2}={\mathbb{E}}_{|\mathscr{A},\bm{p}}$.
It remains to be proven the fact that ${\mathbb{E}}_{|\mathscr{A},\bm{p}}$ is
self adjoint with respect to the inner product
$\left<\cdot,\cdot\right>_{\bm{p}}$, that is
$\left<\bm{v},{\mathbb{E}}_{|\mathscr{A},\bm{p}}\bm{w}\right>_{\bm{p}}=\left<{\mathbb{E}}_{|\mathscr{A},\bm{p}}\bm{w},\bm{v}\right>_{\bm{p}}$.
Such an equality can be rewritten, using equivalent forms of the modified
inner product above, as
$\left<\bm{v},\bm{p}\wedge\bm{p}\wedge{\mathbb{E}}_{|\mathscr{A},\bm{p}}\bm{w}\right>=\left<\bm{p}\wedge\bm{p}\wedge{\mathbb{E}}_{|\mathscr{A},\bm{p}}\bm{v},\bm{w}\right>$.
That is equivalent to prove that
$\bm{p}\wedge{\mathbb{E}}_{|\mathscr{A},\bm{p}}$ is self-adjoint with respect
to the standard inner product, which can be verified by simply computing it.

Identical reasoning can be done for ${\mathbb{E}}_{|\mathscr{A},\bm{p}}^{T}$.
Note that ${\rm
image}({\mathbb{E}}_{|\mathscr{A},\bm{p}}^{T})=\bm{p}\wedge\mathscr{A}$, that
$({\mathbb{E}}_{|\mathscr{A},\bm{p}}^{T})^{2}={\mathbb{E}}_{|\mathscr{A},\bm{p}}^{T}$
and that $\bm{p}^{-1}\wedge{\mathbb{E}}_{|\mathscr{A},\bm{p}}$ is self adjoint
with respect to the standard inner product and the statement is proved. ∎

###### Proof of Proposition 3.

Both $\ker C\supseteq\mathcal{N}$ and $\mathcal{S}\subseteq\mathcal{R}$ are
well-known properties. We have to prove that
$\mathcal{N}\supseteq\mathcal{N_{C}}$ and
$\mathcal{R}\subseteq\mathcal{R_{C}}$.

Regarding the reachable space we have that ${\rm
span}\\{P^{y_{0}^{l}}\bm{p}_{0},\forall{y_{0}^{l}}\text{ s.t.
}l=k,\forall\bm{p}_{0}\in\mathcal{S}\\}\supseteq{\rm
span}\\{P^{k}\bm{p}_{0},\forall\bm{p}_{0}\in\mathcal{S}\\}$ for all $k\geq 0$.
This is proven directly using lemma 5.

For the non-observable subspace it holds that

$\begin{bmatrix}\bm{1}^{T}{\rm diag}(\bm{e}_{0})PP_{C}^{y_{0}^{l-1}}\\\
\vdots\\\ \bm{1}^{T}{\rm
diag}(\bm{e}_{m})PP_{C}^{y_{0}^{l-1}}\end{bmatrix}=CPP_{C}^{y_{0}^{l-1}}\bm{p}_{0}.$

Then, we have that $\ker[CPP_{C}^{y_{0}^{l-1}}]=\ker[CP^{l}]$ for all
$y_{0}^{l-1}$ of length $l$, for any length $l$. Once again this is proved by
using Lemma 5. Consider a vector $\bm{v}\in\ker[CPP_{C}^{y_{0}^{l-1}}]$ for
all ${y_{0}^{l-1}}$. Then it holds that $CPP_{C}^{y_{0}^{l-1}}\bm{v}=0$
summing both sides of this equation over all sequences ${y_{0}^{l-1}}$ of
length $l-1$ and using the Lemma above we obtain
$CP^{|{y_{0}^{l-1}}|+1}\bm{v}=0$, thus proving the statement.

The statement on the effective subspaces follows directly from the other two.
∎

In order to prove Lemma 6 we need the following property of the algebra
$\mathscr{A}_{\mathcal{C}}$.

######  Lemma 8.

$\mathscr{A}_{\mathcal{C}}$ is ${\rm diag}(\bm{e}_{i}^{T}C)$-invariant for all
$i$.

###### Proof.

In the following we will name $\bm{c}_{i}=C^{T}\bm{e}_{i}$ for any $i$ for
convenience. We shall start by observing, from Lemma 4, that $\mathcal{E_{C}}$
is ${\rm diag}(\bm{c}_{i})$-invariant for all $i$. Then, for any choice of
positive $\bm{p}$, we have that $\bm{p}^{-1}\wedge\mathcal{E_{C}}$ is ${\rm
diag}(\bm{c}_{i})$-invariant since, given any vector
$\bm{x}\in\mathcal{E_{C}}$ it holds that
$\bm{c}_{i}\wedge\bm{p}^{-1}\wedge\bm{x}=\bm{p}^{-1}\wedge\bm{c}_{i}\wedge\bm{x}$
and, $\bm{x}^{\prime}=\bm{c}_{i}\wedge\bm{x}\in\mathcal{E_{C}}$ and thus
$\bm{p}^{-1}\wedge\bm{x}^{\prime}\in\bm{p}^{-1}\wedge\mathcal{E_{C}}$.

It remains to be proven the fact that, given a ${\rm
diag}(\bm{c}_{i})$-invariant vector space $\mathcal{W}$, then ${\rm
alg}(\mathcal{W})$ is also ${\rm diag}(\bm{c}_{i})$-invariant. Let
$\\{\bm{w}_{\ell}\\}$ be the set of dimension $k$ of generators of
$\mathcal{W}$. Then we have that ${\rm alg}(\mathcal{W})={\rm
span}\\{\bm{w}_{\ell},\bm{w}_{\ell}\wedge\bm{w}_{j},\dots\\}$ for all $\ell$
and for all mixed products of the type $\wedge_{j}\bm{w}_{\ell_{j}}$ with
$i_{j}=0,\dots,k$. Then, as before we have that
$\bm{c}_{i}\wedge\bm{w}_{i}\in\mathcal{W}$ and thus
$\bm{c}_{i}\wedge(\wedge_{j}\bm{w}_{i_{j}})\in{\rm alg}(\mathcal{W})$. ∎

###### Proof of Lemma 6.

Once again, we will name $\bm{c}_{i}=C^{T}\bm{e}_{i}$ for any $i$ for
convenience. The left hand side of the equation is equivalent to $R{\rm
diag}(\bm{c}_{i})=\sum_{j}\bm{e}_{j}(\bm{a}_{j}\wedge\bm{c}_{i})^{T}$. Then,
because of Lemma 8 we have that
$\bm{a}_{j}\wedge\bm{c}_{i}\in\mathscr{A}_{\mathcal{C}}$ and thus, we can
write $\bm{a}_{j}\wedge\bm{c}_{i}=\sum_{k}\lambda_{j,k}\bm{a}_{k}$. Moreover,
because $\bm{a}_{j}$ are idempotent for $\wedge$, we have that
$\bm{a}_{j}\wedge\bm{c}_{i}=\bm{a}_{j}\wedge\bm{a}_{j}\wedge\bm{c}_{i}=\sum_{k}\lambda_{j,k}\underbrace{\bm{a}_{j}\wedge\bm{a}_{k}}_{\bm{a}_{j}\delta_{j-k}}=\lambda_{j,j}\bm{a}_{j}$,
thus obtaining $R{\rm
diag}(\bm{c}_{i})=\sum_{j}\lambda_{j,j}\bm{e}_{j}\bm{a}_{j}^{T}$.

On the other hand, using the same reasoning, we have that
$J^{T}\bm{c}_{i}=\sum_{j}\bm{e}_{j}\left<\bm{p},\bm{a}_{j}\wedge\bm{c}_{i}\right>/\left<\bm{p},\bm{a}_{j}\right>=\sum_{j}\lambda_{j,j}\bm{e}_{j}$
and thus ${\rm
diag}(J^{T}\bm{c}_{i})R=\sum_{j}\lambda_{j,j}\bm{e}_{j}\bm{a}_{j}^{T}$. ∎

###### Proof of Lemma 7.

We shall start by constructing a vector $\widetilde{\bm{w}}$ such that ${\rm
supp}(\widetilde{\bm{w}})={\rm supp}(\mathcal{W})$. Starting from it we then
construct a vector $\overline{\bm{w}}$ such that it is a linear combination of
every generator.

By definition of support of a vector space, for each $\bm{e}_{i}\in{\rm
supp}(\mathcal{W})$ there exists a vector $\bm{x}_{i}\in\mathcal{W}$ such that
$\bm{e}_{i}^{T}\bm{x}_{i}\neq 0$, forming a set $\\{\bm{x}_{i}\\}$. Without
loss of generality, we assume ${i=0,\dots,m}$ with $m=\dim({\rm
supp}(\mathcal{W}))$. We can then define $\widetilde{\bm{w}}_{0}=\bm{x}_{0}$
and iteratively compute
$\widetilde{\bm{w}}_{i}=\widetilde{\bm{w}}_{i-1}+\lambda_{i}\bm{x}_{i}$ with
$\lambda_{i}\notin\\{-\bm{e}_{j}^{T}\widetilde{\bm{w}}_{i-1}/\bm{e}_{j}^{T}\bm{x}_{i},\forall
j|\bm{e}_{j}^{T}\bm{x}_{i}\neq 0\\}\cup\\{0\\}$. Since this set is finite, it
is always possible to choose a suitable $\lambda_{i}\in\mathbb{R}$ for each
$i$. At the end of the iteration process, we obtain
$\widetilde{\bm{w}}=\widetilde{\bm{w}}_{m}=\sum_{i=0}^{m}\lambda_{i}\bm{x}_{i}\in\mathcal{W}$.
To prove that ${\rm supp}(\widetilde{\bm{w}})={\rm supp}(\mathcal{W})$ we can
simply observe that
$\bm{e}_{j}^{T}\widetilde{\bm{w}}=\sum_{i=0}^{m}\lambda_{i}\bm{e}_{j}^{T}\bm{x}_{i}\neq
0$ by construction for all $\bm{e}_{j}\in{\rm supp}(\mathcal{W})$. On the
other hand, for every $\bm{e}_{j}\notin{\rm supp}(\mathcal{W})$,
$\bm{e}_{j}^{T}\bm{x}_{i}=0$ for all $i$ and thus
$\bm{e}_{j}^{T}\widetilde{\bm{w}}=0$.

This $\widetilde{\bm{w}}$ must be described as a linear combination of some of
the generators, say $\widetilde{\bm{w}}=\sum_{i\in S}\lambda_{i}\bm{w}_{i}$,
for some set of indices $S$. We can then use the same procedure as before:
take $\bm{w}_{i}$ such that $i\notin S$, by choosing any
$\lambda_{i}\notin\\{-\bm{e}_{j}^{T}\widetilde{\bm{w}}/\bm{e}_{j}^{T}\bm{w}_{i},\forall
j|\bm{e}_{j}^{T}\bm{w}_{i}\neq 0\\}\cup\\{0\\}$ we have ${\rm
supp}(\widetilde{\bm{w}}+\lambda_{i}\bm{w}_{i})={\rm supp}(\mathcal{W})$.
Iterating this procedure on the remaining vectors $\\{\bm{w}_{i}|i\notin S\\}$
we obtain $\overline{\bm{w}}=\widetilde{\bm{w}}+\sum_{i\notin
S}\lambda_{i}\bm{w}_{i}$ such that ${\rm supp}(\overline{\bm{w}}):={\rm
supp}(\mathcal{W})$. ∎