# AN INFORMATION-THEORETIC APPROACH FOR AUTOMATICALLY DETERMINING
THE NUMBER OF STATE GROUPS WHEN AGGREGATING MARKOV CHAINS

Isaac J. Sledge1, _Member, IEEE_ José C. Príncipe2,3, _Life Fellow, IEEE_
1 Advanced Signal Processing and Automated Target Recognition Branch, Naval
Surface Warfare Center—Panama City
2 Department of Electrical and Computer Engineering, University of Florida
3 Department of Biomedical Engineering, University of Florida
This work was funded by ONR grants N00014-15-1-2013 and N00014-14-1-0542. The
first author was additionally funded by a UF Research Fellowship, a UF Robert
C. Pittman Fellowship, and an ASEE NREIP Fellowship.

## ABSTRACT

A fundamental problem when aggregating Markov chains is the specification of
the number of state groups. Too few state groups may fail to sufficiently
capture the pertinent dynamics of the original, high-order Markov chain. Too
many state groups may lead to a non-parsimonious, reduced-order Markov chain
whose complexity rivals that of the original. In this paper, we show that an
augmented value-of-information-based approach to aggregating Markov chains
facilitates the determination of the number of state groups. The optimal
state-group count coincides with the case where the complexity of the reduced-
order chain is balanced against the mutual dependence between the original-
and reduced-order chain dynamics.

_Index Terms_ —Aggregation, model reduction, Markov chains, information theory

## 1\. INTRODUCTION

Markov models have been widely adopted in a variety of disciplines. Part of
their appeal is that the application and simulation of such models is rather
efficient, provided that the corresponding state-space has a small to moderate
size. Dealing with large state spaces is often troublesome, in comparison, as
it may not be possible to adequately and efficiently simulate the underlying
models [1, 2, 3, 4, 5].

A means of rendering the simulation of large-scale models tractable is crucial
for many applications. One way to do this is by reducing the overall size of
the Markov-chain state space via aggregation [6]. Aggregation typically
entails either defining and utilizing a function to partition nodes in the
probability transition graph associated with the large-scale chain. Groups of
nodes, which are related by the their inter-state transition probabilities and
have strong interactions, are combined and treated as a single aggregated node
in a new graph. This results in a lower-order chain with a reduced state
space. A stochastic matrix for the lower-order chain is then specified, which
describes the transitions from one super-state to another. This stochastic
matrix should roughly mimic the dynamics of the original chain despite the
potential loss in information [7, 8, 9].

There are a variety of methods for aggregating Markov chains. Some of the
earliest work exploited the strong-weak interaction structure of nearly
completely decomposable Markov chains to obtain reduced-order approximations
[10, 11, 12, 13]. Both uncontrolled [14, 15] and controlled Markov chains [16,
17] have been extensively studied in the literature.

In this paper, we consider an approach for aggregating nearly-completely-
decomposable Markov chains, which is composed of two information-theoretic
processes [18]. The first process entails quantifying the dissimilarity of
nodes in the original and reduced-order probability transition graphs, despite
the difference in state space sizes. The second process involves iteratively
partitioning similar nodes without explicit knowledge of the number of groups.
For this second process, we consider the use of an information-theoretic
criterion known as the value of information [19, 20] to efficiently partition
the probability transition graph. The value of information is a constrained,
modified-free-energy-difference criterion that describes the maximum benefit
associated with a given quantity of information in order to minimize the
average distortion [21, 22, 23]. It is an optimal, non-linear conversion
between information, usually in the Shannon sense [24], and either costs or
utilities, in the von-Neumann-Morgenstern sense [25].

Optimizing the value of information in a grouped-coordinate-descent manner
yields a single free parameter that represents the effect of the information
bound. Increasing this parameter from some base value yields a hierarchy of
partitions that monotonically decrease the modified-free-energy difference.
Each hierarchy element corresponds to a partition with an increasing
information bound amount and hence a potentially increasing number of state
groups. Finer-scale group structure in the transition matrix is captured as
the parameter value rises. After some free-parameter value threshold, however,
there are diminishing returns on the aggregation quality. Finding this
threshold, in a completely data-driven fashion, is thus crucial: over-
partitioning the original chain leads to a non-parsimonious representation
that can be computationally expensive to evaluate.

To automatically discern the optimal number of state groups for arbitrary
Markov chains, we modify the value-of-information cost function and hence its
updates. For this modified criterion, the first update step trades off the
divergence of the original and aggregated chain transition probabilities
against the mutual dependence between the original and aggregated chain
dynamics. The remaining updates then trade off between how well the reduced-
order model dynamics are compressed versus how much information about the
original-chain dynamics is retained. That is, it follows an information-
bottleneck model [26] with the added effect that the resulting Markov chain
resembles the original. Through update schedule, we are guaranteed that the
negative modified-free-energy-difference curve is, in general, convex. We can
therefore find a maximal value on the curve. This value corresponds to the
situation where the aggregation process begins to overfit to noise in the
Markov-chain transition dynamics versus the underlying nearly-completely-
decomposable structure if more state groups are added.

$\textnormal{min}_{\Psi^{(k)}\in\mathbb{R}_{+}^{n\times
m},\,\Theta^{(k)}\in\mathbb{R}_{+}^{m\times
n}}\Bigg{(}\sum_{i=1}^{n}\sum_{j=1}^{m}\gamma_{i}\psi_{i,j}^{(k)}\sum_{p=1}^{n}\pi_{i,k}\textnormal{log}(\pi_{i,p}/\vartheta_{j,p}^{(k)})\,\Bigg{|}\\!\begin{array}[]{c}0\\!\leq\\!\vartheta_{i,q}^{(k)},\psi_{i,q}^{(k)}\\!\leq\\!1,\;\sum_{q=1}^{m}\vartheta_{i,q}^{(k)}\\!=\\!1,\vspace{0.01cm}\\\
\sum_{q=1}^{m}\psi_{i,q}^{(k)}\\!=\\!1\,\,\forall
i,j,k\end{array}\\!\\!\Bigg{)},\,\forall k$ (1)

$\textnormal{min}_{{\Psi^{(k)}\in\mathbb{R}_{+}^{n\times
m}}}\left(\\!\\!\\!\begin{array}[]{c}\mathbb{I}_{(k=0)}\sum_{i=1}^{n}\sum_{j=1}^{m}\gamma_{i}\psi_{i,j}^{(k)}\sum_{p=1}^{n}\pi_{i,p}\textnormal{log}(\pi_{i,p}/\vartheta_{j,p}^{(k)})\,+\vspace{0.05cm}\\\
\mathbb{I}_{(k>0)}\sum_{q}\sum_{j=1}^{m}\omega_{q}\kappa_{q,j}^{(k)}\textnormal{log}(\kappa_{q,j}^{(k)}/\alpha_{j}^{(k)})\end{array}\\!\\!\left|\\!\begin{array}[]{c}\sum_{j=1}^{m}\alpha_{j}^{(k)}\sum_{i=1}^{n}\psi_{i,j}^{(k)}\textnormal{log}(\psi_{i,j}^{(k)}/\gamma_{i})\leq
r\vspace{0.05cm}\\\
\kappa_{q,j}^{(k)}\\!=\\!\sum_{i=1}^{n}\gamma_{i}\,\eta_{q,i}\,\psi_{i,j}^{(k)}/\alpha_{j}^{(k)}\vspace{0.05cm}\\\
0\\!\leq\\!\vartheta_{i,q}^{(k)},\psi_{i,q}^{(k)}\\!\leq\\!1,\;\sum_{q=1}^{m}\vartheta_{i,q}^{(k)}\\!=\\!1,\,\sum_{q=1}^{m}\psi_{i,q}^{(k)}\\!=\\!1\end{array}\\!\\!\\!\right.\right)\\!,\,\forall
k$ (2)

$\displaystyle\alpha_{j}^{(0)}\leftarrow\sum_{i=1}^{n}\gamma_{i}\,\psi^{(0)}_{i,j},\;\;\psi_{i,j}^{(1)}\leftarrow\\!\Bigg{(}\alpha_{j}^{(0)}e^{-\beta\sum_{r=1}^{n}\pi_{i,r}\textnormal{log}(\pi_{i,r}/\vartheta_{j,r})}\\!\Bigg{)}\\!\Bigg{/}\\!\Bigg{(}\sum_{p=1}^{m}\alpha_{p}^{(0)}e^{-\beta\sum_{r=1}^{n}\pi_{i,r}\textnormal{log}(\pi_{i,r}/\vartheta_{p,r})}\Bigg{)}\vspace{-0.05cm}$
(3)

$\displaystyle\alpha_{j}^{(k)}\leftarrow\sum_{i=1}^{n}\gamma_{i}\,\psi_{i,j}^{(k)},\;\;\kappa_{q,j}^{(k)}\leftarrow\sum_{i=1}^{n}\gamma_{i}\,\eta_{q,i}\,\psi_{i,j}^{(k)}/\alpha_{j}^{(k)},\;\;\psi_{i,j}^{(k+1)}\leftarrow\Bigg{(}\alpha_{j}^{(k)}e^{-\beta\sum_{q}\eta_{q,i}\textnormal{log}(\eta_{q,i}/\kappa_{q,j}^{(k)})}\\!\Bigg{)}\\!\Bigg{/}\\!\Bigg{(}\sum_{p=1}^{m}\alpha_{p}^{(k)}e^{-\beta\sum_{q}\eta_{q,i}\textnormal{log}(\eta_{q,i}/\kappa_{q,p}^{(k)})}\\!\Bigg{)}$
(4)

## 2\. METHODOLOGY

Our approach for aggregating Markov chains can be described as follows. Given
a stochastic matrix $\Pi\\!\in\\!\mathbb{R}^{n\times n}_{+}$ of transition
probabilities between $n$ states, we seek to partition this matrix to produce
a reduced-size stochastic matrix $\Phi\\!\in\\!\mathbb{R}^{m\times m}_{+}$
with $m$ states. Since there are many possible $\Phi$’s that can be formed, we
would like one with the least divergence to $\Pi$ for some measure. Due to the
different sizes of $\Pi$ and $\Phi$, though, directly assessing divergence is
not possible. To facilitate this comparison, we consider the construction of a
joint-model stochastic matrix $\Theta\\!\in\\!\mathbb{R}^{m\times n}_{+}$ that
encodes the dynamics of $\Phi$.

The definition of $\Theta$ relies on finding a partition matrix
$\Psi\\!\in\\!\mathbb{R}^{m\times n}_{+}$ for determining which states in
$\Pi$ should be combined to create an aggregated state in $\Phi$. We show that
an optimal $\Psi$ and $\Theta$, and hence $\Phi$, can be found by solving a
modified value-of-information criterion. We then characterize the errors
associated with estimating this modified value-of-information for Markov
chains with a finite number of states. Removing the errors penalizes marginal
improvements in the divergence associated with including more state groups
$m$. This non-linearly transforms the value of information such that it
contains a global maximum for a single state group count. We then specify an
expression for this value, which coincides where the aggregation complexity is
balanced against the preserved information.

2.1 Preliminaries

For our approach, we consider a first-order, homogeneous Markov chain defined
on a finite state space. We assume that is nearly-completely decomposable.

Definition 2.1. The transition model of a first-order, homogeneous, nearly-
completely-decomposable Markov chain is a weighted, directed graph $R_{\pi}$
given by the three-tuple $(V_{\pi},E_{\pi},\Pi)$ with:

  * (i) A set of $n$ vertices $V_{\pi}\\!=\\!v_{\pi}^{1}\cup\ldots\cup v_{\pi}^{n}$ representing the states of the Markov chain.

  * (ii) A set of $n\\!\times\\!n$ edge connections $E_{\pi}\subset V_{\pi}\\!\times\\!V_{\pi}$ between reachable states in the Markov chain.

  * (iii) A stochastic transition matrix $\Pi\\!\in\\!\mathbb{R}_{+}^{n\times n}$. Here, $[\Pi]_{i,j}\\!=$
$\pi_{i,j}$ represents the non-negative transition probability between states
$i$ and $j$. We impose the constraint that the probability of experiencing a
state transition is independent of time. Moreover, for a block-diagonal matrix
$\Pi^{*}$ with zeros along the diagonal, we have that
$\Pi\\!=\\!\Pi^{*}\\!+\\!\varepsilon C$.
$\Pi^{*}\\!\in\\!\mathbb{R}_{+}^{n\times n}$ is a completely-decomposable
stochastic matrix with $m$ indecomposable sub-matrix blocks $\Pi^{*}_{i}$ of
order $n_{i}$. The matrix $C\\!\in\\!\mathbb{R}_{+}^{n\times n}$ satisfies
$\sum_{k=1}^{n_{i}}c_{p_{i},k_{i}}\\!=\\!-\sum_{j\neq
i}\sum_{q=1}^{n_{j}}c_{p_{i},q_{j}}$ $\forall p_{i}$, for blocks $\Pi^{*}_{i}$
and $\Pi^{*}_{j}$.

Throughout, we assume that all Markov chains are irreducible and aperiodic. As
a consequence, there is a unique invariant probability distribution $\gamma$
associated with the chain such that $\gamma^{\top}\Pi\\!=\\!\gamma^{\top}$.

We are interested in comparing pairs of nearly-completely-decomposable Markov
chains. A means to do this is by considering given rows of the stochastic
transition matrix $\Pi$ with those of a reduced-order chain’s stochastic
matrix $\Phi$. We will perform this comparison via the negative Kullback-
Leibler divergence. It coincides with the Donsker-Varadhan rate function
appearing in the large-deviations theory of Markov chains [27, 28] and
measures the dissimilarity between chains defined on the same discrete state
space.

Since we are considering the problem of chain aggregation, the discrete state
spaces will be different. One chain $R_{\pi}$ will have $n$ states while
another $R_{\varphi}$ will have $m$ states. The dimensionalities of given rows
in the corresponding transition matrices will hence not be equivalent, which
precludes a direct comparison using the discrete Kullback-Leibler divergence.
To resolve this issue, we consider construction of a joint model
$R_{\vartheta}$. This joint model defines a joint state space composed of the
states from $R_{\pi}$ and $R_{\varphi}$. It, however, re-defines the edge set
along with the weighting matrix. This weighting matrix $\Theta$ has the same
number of columns as $\Pi$ and the same dynamics as $\Phi$, which facilitates
comparisons using conventional divergences.

The joint model relies on the specification of a partition matrix $\Psi$ for
mapping states from the reduced-order model $R_{\varphi}$ to the original
model $R_{\pi}$. Here, we consider probabilistic partition functions so as to
capture the inherent uncertainty in the state combination.

Definition 2.2. Let $R_{\pi}\\!=\\!(V_{\pi},E_{\pi},\Pi)$ and
$R_{\varphi}\\!=\\!(V_{\varphi},E_{\varphi},\Phi)$ be transition models of two
Markov chains over $n$ and $m$ states, respectively. A probabilistic partition
function $\psi$ is a surjective mapping between two state index sets,
$\mathbb{Z}_{1:n}$ and $\mathbb{Z}_{1:m}$, such that
$\psi^{-1}(\mathbb{Z}_{1:m})$ is a partition of $\mathbb{Z}_{1:n}$, which has
a given probabilistic chance of occurring. That is,
$\psi^{-1}(j)\\!\subset\\!\mathbb{Z}_{1:n}\times\mathbb{R}_{+}^{n}$ is not
empty and where
$\psi^{-1}(1)\cup\ldots\cup\,\psi^{-1}(m)\\!=\\!\mathbb{Z}_{1:n}^{m}\times\mathbb{R}_{+}^{m\times
n}$, with the real-valued responses being non-negative and summing to one.

The probabilistic partition of a state index set induces a probabilistic
partition matrix $[\Psi]_{i,j}\\!=\\!\psi_{i,j}$, where
$\psi_{i,j}\\!=\\!\zeta$ if $i\\!\in\\!\psi^{-1}(j)$ occurs with probability
$\zeta$. The set of all probabilistic partition matrices is
$\\{\Psi\\!\in\\!\mathbb{R}_{+}^{n\times
m}|[\Psi]_{i,j}\\!=\\!\psi_{i,j}\\!\in\\![0,1],\;\sum_{j=1}^{m}\psi_{i,j}\\!=\\!1\\}$.

Definition 2.3. Let $R_{\pi}\\!=\\!(V_{\pi},E_{\pi},\Pi)$ and
$R_{\varphi}\\!=\\!(V_{\varphi},E_{\varphi},\Phi)$ be transition models of two
Markov chains over $n$ and $m$ states, respectively, where $m\\!<\\!n$.
$R_{\vartheta}\\!=\\!(V_{\vartheta},E_{\vartheta},\Theta)$ is a joint model,
with $m\\!+\\!n$ states, that is defined by

  * (i) A vertex set $V_{\vartheta}\\!=\\!V_{\pi}\cup V_{\varphi}$, which is the union of all state vertices in $R_{\pi}$ and $R_{\varphi}$.

  * (ii) An edge set $E_{\vartheta}\subset V_{\varphi}\\!\times\\!V_{\pi}$, which are one-to-many mappings from the states in the original transition model $R_{\pi}$ to the reduced-order transition model $R_{\varphi}$.

  * (iii) A weighting matrix $\Theta\\!\in\\!\mathbb{R}_{+}^{m\times n}$. The partition function $\psi$ provides a relationship between the stochastic matrices $\Phi$ and $\Theta$ of $R_{\varphi}$ and $R_{\vartheta}$, respectively. This is given by $\Phi\\!=\\!\Theta\Psi$, or, rather,
$\varphi_{i,j}\\!=\\!\sum_{k=1}^{n}\vartheta_{k,j}\psi_{k,i}$ $\forall i,j$,
where $\Psi$ is a probabilistic partition matrix; here,
$\psi_{i,j}\\!=\\!p(v_{\varphi}^{j}|v_{\pi}^{i})$ and
$\varphi_{i,j}\\!=\\!p(v_{\varphi}^{j}|v_{\varphi}^{i})$.

Our corresponding technical report should be consulted for further details
about these choices and illustrations of the various concepts [29]. This
report also contains proofs for many of the ensuing claims.

2.2 Aggregating Markov Chains

For any given transition model $R_{\pi}$, we would like to find, by way of the
joint model $R_{\vartheta}$, another transition model $R_{\varphi}$ with fewer
states that resembles the dynamics encoded by $R_{\pi}$. At the very least, a
model $R_{\vartheta}$ should be sought with a weighting matrix $\Theta$ that
has the least expected divergence with respect to the transition matrix $\Pi$
of $R_{\pi}$ for some partition.

Definition 2.4. Let $R_{\pi}\\!=\\!(V_{\pi},E_{\pi},\Pi)$,
$R_{\varphi}\\!=\\!(V_{\varphi},E_{\varphi},\Phi)$, and
$R_{\vartheta}\\!=\\!(V_{\vartheta},E_{\vartheta},\Theta)$ be transition
models of two Markov chains over $n$ and $m$ states and the joint model over
$n\\!+\\!m$ states, respectively. The least expected divergence between $\Pi$
and $\Theta$, and hence $\Pi$ and $\Phi$, is given in (1). Here,
$\gamma_{i}\\!=\\!p(v_{\pi}^{i})$ and
$\pi_{i,k}\\!=\\!p(v_{\pi}^{i}|v_{\pi}^{k})$.

The least expected distortion possesses too few constraints to make discerning
the number of state groups $m$ viable, though.

$\textnormal{min}_{{\Psi^{(k)}\in\mathbb{R}_{+}^{n\times
m}}}\left(\\!\\!\\!\\!\left.\begin{array}[]{c}\;\mathbb{I}_{(k=0)}\sum_{i=1}^{n}\sum_{j=1}^{m}\gamma_{i}\psi_{i,j}^{(k)}\sum_{p=1}^{n}\pi_{i,p}\textnormal{log}(\pi_{i,p}/\vartheta_{j,p}^{(k)})+\mathbb{I}_{(k>0)}\sum_{q}\sum_{j=1}^{m}\omega_{q}\kappa_{q,j}^{(k)}\textnormal{log}(\kappa_{q,j}^{(k)}/\alpha_{j}^{(k)})\vspace{0.125cm}\\\
+\,\mathbb{I}_{(k=0)}\sum_{g=2}^{2}\frac{(-1)^{g}}{\textnormal{log}(2)(g^{2}\\!-\\!g)}\sum_{j=1}^{m}\mathbb{E}[(\sum_{i=1}^{n}\overline{\gamma}_{i}\psi_{i,j}^{(k)})^{g}]/(\alpha_{j}^{(k)})^{g-1}\vspace{0.125cm}\\\
-\,\mathbb{I}_{(k>0)}\sum_{g=2}^{\infty}\frac{(-1)^{g}}{\textnormal{log}(2)(g^{2}\\!-\\!g)}\sum_{q}\sum_{j=1}^{m}\frac{\omega_{q}^{g-1}\mathbb{E}[(\sum_{i=1}^{n}\overline{\eta}_{q,i}\rho_{i,j}^{(k)})^{g}]-(\rho_{q,j}^{(k)})^{g-1}\mathbb{E}[(\sum_{i=1}^{n}\gamma_{y}\overline{\eta}_{q,i})^{g}]}{(\rho_{q,j}^{(k)})^{g-1}\omega_{q}^{g-1}}\end{array}\\!\\!\right|\,\cdots\right)\\!,\,\forall
k$ (5)

$\psi_{i,j}^{(1)}\leftarrow\\!\Bigg{(}\sum_{y=1}^{n}\gamma_{y}\,\psi_{y,j}^{(0)}\,\textnormal{exp}\Bigg{(}\\!\\!-\\!\beta\Bigg{(}\sum_{p=1}^{n}\pi_{i,p}\textnormal{log}\Bigg{(}\frac{\pi_{i,p}}{\vartheta_{j,p}^{(0)}}\Bigg{)}\\!\Bigg{)}+\sum_{g=2}^{\infty}(-1)^{g}\sum_{p=1}^{m}\frac{\mathbb{E}[(\sum_{s=1}^{n}\overline{\gamma}_{s}\psi_{s,p}^{(0)})^{g}]}{g(\alpha_{p}^{(0)})^{g}}-\frac{\mathbb{E}[\,\overline{\gamma}_{i}(\sum_{s=1}^{n}\overline{\gamma}_{s}\psi_{s,p}^{(0)})^{g-1}]}{(g\\!-\\!1)\gamma_{i}(\alpha_{p}^{(0)})^{g-1}}\Bigg{)}\\!\Bigg{/}\\!\Bigg{(}\cdots\Bigg{)}\vspace{-0.05cm}$
(6)

$\\!\\!\\!\\!\\!\begin{array}[]{c}\displaystyle\alpha_{j}^{(k)}\leftarrow\sum_{i=1}^{n}\gamma_{i}\,\psi_{i,j}^{(k)},\;\;\kappa_{q,j}^{(k)}\leftarrow\sum_{i=1}^{n}\gamma_{i}\,\eta_{q,i}\,\psi_{i,j}^{(k)}/\alpha_{j}^{(k)},\;\;\overline{\kappa}_{q,j}^{(k)}\leftarrow\sum_{i=1}^{n}\overline{\eta}_{q,i}\,\tau_{i,j}^{(k)},\vspace{0.075cm}\\\
\displaystyle\psi_{i,j}^{(k+1)}\leftarrow\\!\Bigg{(}\alpha_{j}^{(k)}\textnormal{exp}\Bigg{(}\\!\\!-\\!\beta\Bigg{(}\sum_{q}\eta_{q,i}\textnormal{log}\Bigg{(}\frac{\eta_{q,i}}{\kappa_{q,j}^{(k)}}\Bigg{)}\\!\Bigg{)}\\!-\\!\beta\sum_{g=2}^{\infty}(-1)^{g}\Bigg{(}\sum_{q}\frac{\mathbb{E}[(\overline{\kappa}_{q,j}^{(k)})^{g}]}{\eta_{q,i}^{-1}\,g(\kappa_{q,j}^{(k)})^{g}}-\frac{\mathbb{E}[\overline{\eta}_{q,i}(\overline{\kappa}_{q,j}^{(k)})^{g-1}]}{(g\\!-\\!1)(\kappa_{q,j}^{(k)})^{g}}\Bigg{)}\\!\Bigg{)}\\!\Bigg{)}\\!\Bigg{/}\\!\Bigg{(}\cdots\Bigg{)}\end{array}\\!\\!\\!\\!\\!$
(7)

To help discern $m$, we impose that the partitions should minimize the
information loss associated with the state quantization process. That is, the
mutual dependence between states in the high-order and low-order chains should
be maximized with respect to a supplied bound. Simultaneously, the least
expected divergence, for this bound, should be achieved while also seeking a
maximal compression of the dynamics. Realizing each of these competing
objectives leads to a combined value-of-information and information-bottleneck
aggregation process.

Definition 2.5. Let $R_{\pi}\\!=\\!(V_{\pi},E_{\pi},\Pi)$,
$R_{\varphi}\\!=\\!(V_{\varphi},E_{\varphi},\Phi)$, and
$R_{\vartheta}\\!=\\!(V_{\vartheta},E_{\vartheta},\Theta)$ be transition
models of two Markov chains over $n$ and $m$ states and the joint model over
$n\\!+\\!m$ states, respectively. An optimal reduced-order transition model
$R_{\varphi}$ with respect to the original model $R_{\pi}$ can be found as
follows:

  * (i) Optimal partitioning: Find a probabilistic partition matrix $\Psi$ that solves (2) for some $r\\!\in\\!\mathbb{R}_{+}$; $r$ has an upper bound of $-\sum_{i=1}^{n}\gamma_{i}\textnormal{log}(\gamma_{i})$. As well, find the corresponding weighting matrix for $R_{\vartheta}$: $\Theta\\!=\\!U^{\top}\Pi$, where $[U]_{i,j}\\!=\\!\gamma_{i}\psi_{i,j}/\sum_{p=1}^{n}\gamma_{p}\psi_{p,j}$.

  * (ii) Transition matrix construction: Obtain the transition matrix for $R_{\varphi}$ via: $\varphi_{i,j}\\!=\\!\sum_{k=1}^{n}\vartheta_{k,j}\psi_{k,i}$ using the optimal weights $\Theta$ and the probabilistic partition matrix $\Psi$ from step (i).

Here, $\alpha_{j}\\!=\\!p(v_{\varphi}^{j})$, $\omega_{q}\\!=\\!p(q)$,
$\eta_{q,i}\\!=\\!p(q|v_{\pi}^{i})$, and
$\kappa_{q,j}\\!=\\!p(q|v_{\varphi}^{j})$ for some intermediate random
variable $q$.

A reason for considering this combined model is that simply trading off
between the preserved information and the model complexity, as in the
information bottleneck, does not encode notions of the underlying weighted-
graph geometry. This is because Shannon information is geometrically
invariant: it yields an infinite set of degenerate solutions that do not
minimize a specific divergence measure.

Global solutions to (2) can be found via the initial condition in (3) and the
expectation-maximization-like updates in (4).

Proposition 2.1. Let $R_{\pi}\\!=\\!(V_{\pi},E_{\pi},\Pi)$ and
$R_{\varphi}\\!=\\!(V_{\varphi},E_{\varphi},\Phi)$ be transition models of two
Markov chains over $n$ and $m$ states. The optimal partition matrix $\Psi$
that globally solves (2) can be found via the alternating update in (3) for
iteration $k\\!=\\!0$ and the alternating updates in (4) for iterations
$k\\!=\\!1,2,\ldots$ Here, $\beta\\!\in\\!\mathbb{R}_{+}$ is a Lagrange
multiplier for handling the constraint bound $r\\!\in\\!\mathbb{R}_{+}$.

The following proposition shows that the number of reduced-model state groups
increases once $\beta$ reaches certain critical values.

Proposition 2.2. Let $R_{\pi}\\!=\\!(V_{\pi},E_{\pi},\Pi)$ and
$R_{\varphi}\\!=\\!(V_{\varphi},E_{\varphi},\Phi)$ be transition models of two
Markov chains over $n$ and $m$ states. For some $\beta_{0}$, suppose
$\Theta_{\beta_{0}}$, the matrix $\Theta$ for that value of $\beta_{0}$,
satisfies the following inequality
$d^{2}/d\epsilon^{2}\,F(\Psi,K,\alpha;\Pi,\Theta_{\beta_{0}}\\!+\\!\epsilon
Q,H,\gamma)|_{\epsilon=0}>0$, for the modified value-of-information Lagrangian
from (2). Here, $Q\\!\in\\!\mathbb{R}_{+}^{m\times n}$ is such that
$\sum_{k=1}^{m}q_{k,1:n}^{\top}q_{k,1:n}\\!=\\!1$ and
$\sum_{j=1}^{n}q_{i,j}\\!=\\!0$ $\,\forall i$. A critical value $\beta_{c}$
satisfies

$\beta_{c}\\!=\\!\textnormal{min}_{\beta>\beta_{0}}\,(d^{2}/d\epsilon^{2}\,F(\Psi,K,\alpha;\Pi,\Theta_{\beta}\\!+\\!\epsilon
Q,H,\gamma)|_{\epsilon=0}\leq 0).$

The number of rows in $\Theta$ and columns in $\Psi$ needs to be increased, by
one, once $\beta\\!>\\!\beta_{c}$, since a phase change occurs.

Sweeping over critical values of $\beta$ yields a hierarchy of probabilistic
partitions $\Psi$ and hence reduced-order-model transition matrices $\Phi$
with different numbers of state groups.

This proposition does not, however, reveal a way to find the optimal number of
state groups. To do that, we will determine when the modified value-of-
information begins to overfit to the transition-dynamics noise. This leads to
additional terms that we can subtract from the criterion to essentially
regularize the aggregation and penalize for using too many or too few state
groups than can be resolved in the transition dynamics.

2.2.1 Aggregated State Group Count

We assume, for the modified value-of-information, that overfitting to noise is
a byproduct of dealing with finite-state-space Markov chains and hence
introducing estimation errors into the joint probabilities. Characterizing the
error effects and removing them yields a version of the value-of-information
curve that is either convex or monotonically non-decreasing then monotonically
non-increasing.

Definition 2.6. Let $R_{\pi}\\!=\\!(V_{\pi},E_{\pi},\Pi)$,
$R_{\varphi}\\!=\\!(V_{\varphi},E_{\varphi},\Phi)$, and
$R_{\vartheta}\\!=\\!(V_{\vartheta},E_{\vartheta},\Theta)$ be transition
models of two Markov chains over $n$ and $m$ states and the joint model over
$n\\!+\\!m$ states, respectively. An optimal reduced-order transition model
$R_{\varphi}$, with respect to the original model $R_{\pi}$, can be found as
follows:

  * (i) Optimal partitioning: Find a probabilistic partition matrix $\Psi$ that solves (5) for some $r\\!\in\\!\mathbb{R}_{+}$. Equation (5) has the same constraint set as (2). Find the corresponding weighting matrix for $R_{\vartheta}$: $\Theta\\!=\\!U^{\top}\Pi$, where $U$ is defined above.

  * (ii) Transition matrix construction: Obtain the transition matrix for $R_{\varphi}$ via: $\varphi_{i,j}\\!=\\!\sum_{k=1}^{n}\vartheta_{k,j}\psi_{k,i}$ using the optimal weights $\Theta$ and the probabilistic partition matrix $\Psi$ from step (i).

The systematic underestimation/overestimation error in (2) is $g$th-order
minimized when solving (5).

Proposition 2.3. Let $R_{\pi}\\!=\\!(V_{\pi},E_{\pi},\Pi)$ and
$R_{\varphi}\\!=\\!(V_{\varphi},E_{\varphi},\Phi)$ be transition models of two
Markov chains over $n$ and $m$ states. The optimal partition matrix $\Psi$ for
$R_{\pi}$ that globally solves (5) and facilitates the construction of
$R_{\varphi}$ can be found via the updates in (6) for iteration $k\\!=\\!0$
and the update in (7) for iterations $k\\!=\\!1,2,\ldots$ For (6) and (7), the
denominators are such that the partition-matrix entries are normalized to
become probabilities.

Here, $\alpha_{j}\\!=\\!p(v_{\varphi}^{j})$,
$\gamma_{i}\\!=\\!p(v_{\pi}^{i})$,
$\psi_{i,j}\\!=\\!p(v_{\varphi}^{j}|v_{\pi}^{i})$,
$\eta_{q,i}\\!=\\!p(q|v_{\pi}^{i})$,
$\kappa_{q,j}\\!=\\!p(q|v_{\varphi}^{j})$,
$\tau_{i,j}\\!=\\!p(v_{\pi}^{i}|v_{\varphi}^{j})$, and
$\rho_{q,j}\\!=\\!p(q,v_{\varphi}^{j})$. The terms $\overline{\kappa}_{q,j}$
and $\overline{\eta}_{q,i}$ represent the estimation errors associated with
$\kappa_{q,j}$ and $\eta_{q,i}$, while $\overline{\gamma}_{i}$ is the error
associated with approximating $\gamma_{i}$. We assume that the average error
is zero: $\mathbb{E}[\overline{\eta}_{q,i}]\\!=\\!0$ and
$\mathbb{E}[\overline{\gamma}_{i}]\\!=\\!0$.

---
(a)
(b)
Figure 1: Modified value-of-information-based partitioning results for 9-state
nearly-completely-decomposable Markov chains with: (a) four discernible state
groups and (b) seven discernible state groups. In both (a) and (b), we show
the original stochastic matrix $\Pi$ with hardened versions of the partitions
$\Psi$ overlaid for four critical values of $\beta$; as noted in the previous
section, $m$ can be inferred from each value of $\beta$. The unique colors in
the partition plots correspond to which state group in $\Phi$ a state in $\Pi$
is most likely to be associated. The right-most plots highlight the Shannon
information in blue and the error-subtracted Shannon information in green.
After a certain number of clusters, the Shannon information plateaus,
indicating that there is negligible benefit for including more state groups in
$\Phi$. The modified Shannon information begins to decrease when this occurs;
the results align with the discernible number of groups for these chains.

Due to the monotonicity properties of (5), we can construct upper and lower
bounds for it and characterize their rate of change with respect to $\beta$.
This permits algebraically discerning where maxima of the equivalent dual
problem (5) occur.

Proposition 2.4. Let $R_{\pi}\\!=\\!(V_{\pi},E_{\pi},\Pi)$,
$R_{\varphi}\\!=\\!(V_{\varphi},E_{\varphi},\Phi)$, and
$R_{\vartheta}\\!=\\!(V_{\vartheta},E_{\vartheta},\Theta)$ be transition
models of two Markov chains over $n$ and $m$ states and the joint model over
$n\\!+\\!m$ states, respectively. The dual problem to (5) achieves a maximum
for the Lagrange multiplier value
$\beta^{*}\\!=\\!2^{\sum_{i=1}^{n}\sum_{j=1}^{m}\gamma_{i}\psi_{i,j}\textnormal{log}(\psi_{i,j}/\alpha_{j})}/2n$.

As before, the partitioning process defined by (6) and (7) undergoes a series
of phase changes whereby the number of state groups increase once $\beta$
exceeds some critical value. The value of $\beta^{*}$ specified by the
preceding proposition coincides with a partitioning where a certain number of
state groups are defined. It can be taken as the point in (5) where the
complexity of the dynamics compression is balanced against the information
contained about the original Markov chain in the reduced-order Markov chain.
For (2), $\beta^{*}$ often marks the beginning of the value-of-information’s
asymptotic region where there are diminishing returns for including more
clusters.

## 3\. SIMULATIONS

In this section, we assess the empirical performance of the modified value-of-
information criterion. We gauge how well the predicted ‘optimal’ free-
parameter value aligns with the discernible number of state groups for nearly-
completely-decomposable Markov chains.

3.1 Simulation Protocols

We adopted the following simulation protocols for our aggregation framework.
We initialized the aggregation process with a partition matrix of all ones,
$\Psi\\!=\\![1]_{9\times 1}$, signifying that each state belongs to a single
group. This is the global optimal solution of the aggregation problem and
coincides with a parameter value $\beta$ of zero for the modified value-of-
information. We then found the subsequent critical values of $\beta$ and
increased the column count of $\Psi$. We determined which state group would be
further split and modified both the new column and an existing column of
$\Psi$ to randomly allocate the appropriate states. This initialization
process bootstraps the quantization for the new cluster and typically achieves
convergence in only a few iterations. It also permits the value of information
to reliably track the global minimizer as $\beta$ increases.

For certain problems, a priori specifying a fixed amount of partition updates
may not permit finding a steady-state solution. We therefore run the
alternating updates until no entries of the partition matrix change across two
iterations.

3.2 Simulation Results

We established the performance of the aggregation partitioning process through
two examples. The first, shown in figure 1(a), corresponds to a Markov chain
with nine states and four state groups with strong intra-group interactions
and weak inter-group interactions. This is a relatively simple aggregation
problem. The second example, presented in figure 1(b), is of a nine-state
Markov chain with a single dominant state group and six outlying states with
near-equal transition probabilities. This is a more challenging problem than
the first, as the outlying states cannot be reliably combined without
adversely impacting the mutual dependence.

In figures 1(a) and 1(b), we provided partitions for four critical values of
the free parameter $\beta$. The ‘optimal’ value of $\beta$, as predicted by
our modified value of information, leads to four and seven state groups for
the first and second examples, respectively. Here, we considered a second-
order approximation of the underestimation/overestimation error, i.e.,
$g\\!=\\!2$. Higher-order approximations did not modify the shape of the
resulting Shannon-information curves much compared to those in figures 1(a)
and 1(b); the resulting ‘optimal’ number of state groups remained the same in
these cases.

For both examples, the associated partitions for the ‘optimal’ values of
$\beta$ align well with an inspection of the dynamics of the stochastic
matrix: the partitions separate states that are more likely to transition to
each other from those that are not. Those partitions for ‘non-optimal’
$\beta$’s either over- or under-quantize the chain states. That is, for
critical $\beta$’s before the ‘optimal’ value, there is a moderate increase in
the Shannon information, while the remaining $\beta$s only yield modest
increases. The ‘optimal’ value of $\beta$ for both examples, in contrast, lies
at the ‘knee’ of this curve, which is where the divergence minimization is
balanced against the competing objective of state-mutual-dependence
maximization with respect to some bound. It is also where the complexity of
the aggregation result is in harmony with the information it contains about
the original Markov chain.

To lend credence to these results, we considered forty reformulated graph-
based partition validity measures [30, 31] across a hundred Monte Carlo
simulations. For the Markov chain in figure 1(a), thirty-three indices
specified that there were four state groups while seven indices indicated that
there were three state groups. The results for the chain in figure 1(b) had
more uncertainty, which was due to the high number of outlying states and the
ability to combine them in multiple ways to reduce the models’ divergence. Ten
indices suggested that there were two state groups, eight indices chose three
state groups, while the remaining twenty-two favored either six or seven state
groups almost equally.

## REFERENCES

  * [1] E. F. Arruda and M. D. Fragoso, “Standard dynamic programming applied to time aggregated Markov decision processes,” in _Proceedings of the IEEE Conference on Decision and Control (CDC)_ , Shanghai, China, December 15-18 2009, pp. 2576–2580. Available: http://dx.doi.org/10.1109/CDC.2009.5400692
  * [2] R. W. Aldhaheri and H. K. Khalil, “Aggregation of the policy iteration method for nearly completely decomposable Markov chains,” _IEEE Transactions on Automatic Control_ , vol. 36, no. 2, pp. 178–187, 1991. Available: http://dx.doi.org/10.1109/9.67293
  * [3] Z. Ren and B. H. Krogh, “Markov decision processes with fractional costs,” _IEEE Transactions on Automatic Control_ , vol. 50, no. 5, pp. 646–650, 2005\. Available: http://dx.doi.org/10.1109/TAC.2005.846520
  * [4] T. Sun, Q. Zhao, and P. B. Luh, “Incremental value iteration for time-aggregated Markov decision processes,” _IEEE Transactions on Automatic Control_ , vol. 52, no. 11, pp. 2177–2182, 2007. Available: http://dx.doi.org/10.1109/TAC.2007.908359
  * [5] Q. S. Jia, “On state aggregation to approximate complex value functions in large-scale Markov decision processes,” _IEEE Transactions on Automatic Control_ , vol. 56, no. 2, pp. 333–334, 2011. Available: http://dx.doi.org/10.1109/TAC.2010.2052697
  * [6] M. Aoki, “Some approximation methods for estimation and control of large scale systems,” _IEEE Transactions on Automatic Control_ , vol. 23, no. 2, pp. 173–182, 1978. Available: http://dx.doi.org/10.1109/TAC.1978.1101705
  * [7] K. Deng, Y. Sun, P. G. Mehta, and S. P. Meyn, “An information-theoretic framework to aggregate a Markov chain,” in _Proceedings of the American Control Conference (ACC)_ , St. Louis, MO, USA, June 10-12 2009, pp. 731–736. Available: http://dx.doi.org/10.1109/ACC.2009.5160607
  * [8] K. Deng, P. G. Mehta, and S. P. Meyn, “Optimal Kullback-Leibler aggregation via spectral theory of Markov chains,” _IEEE Transactions on Automatic Control_ , vol. 56, no. 12, pp. 2793–2808, 2011. Available: http://dx.doi.org/10.1109/TAC.2011.2141350
  * [9] B. C. Geiger, T. Petrov, G. Kubin, and H. Koeppl, “Optimal Kullback-Leibler aggregation via information bottleneck,” _IEEE Transactions on Automatic Control_ , vol. 60, no. 4, pp. 1010–1022, 2015. Available: http://dx.doi.org/10.1109/TAC.2014.2364971
  * [10] R. W. Aldhaheri and H. K. Khalil, “Aggregation and optimal control of nearly completely decomposable Markov chains,” in _Proceedings of the IEEE Conference on Decision and Control (CDC)_ , Tampa, FL, USA, December 13-15 1989, pp. 1277–1282. Available: http://dx.doi.org/10.1109/CDC.1989.70343
  * [11] G. Kotsalis and M. Dahleh, “Model reduction of irreducible Markov chains,” in _Proceedings of the IEEE Conference on Decision and Control (CDC)_ , Maui, HI, USA, December 9-12 2003, pp. 5727–5728. Available: http://dx.doi.org/10.1109/CDC.2003.1271917
  * [12] H. A. Simon and A. Ando, “Aggregation of variables in dynamic systems,” _Econometrica_ , vol. 29, no. 2, pp. 111–138, 1961. Available: http://dx.doi.org/10.2307/1909285
  * [13] P. J. Courtois, “Error analysis in nearly-completely decomposable stochastic systems,” _Econometrica_ , vol. 43, no. 4, pp. 691–709, 1975. Available: http://dx.doi.org/10.2307/1913078
  * [14] A. A. Pervozvanskii and I. N. Smirnov, “Stationary-state evaluation for a complex system with slowly varying couplings,” _Kibernetika_ , vol. 3, no. 1, pp. 45–51, 1974. Available: http://dx.doi.org/10.1007/BF01071538
  * [15] V. G. Gaitsgori and A. A. Pervozvanskii, “Aggregation of states in a Markov chain with weak interaction,” _Kibernetika_ , vol. 4, no. 1, pp. 91–98, 1975\. Available: http://dx.doi.org/10.1007/BF01069471
  * [16] D. Teneketzis, S. H. Javid, and B. Sridhar, “Control of weakly-coupled Markov chains,” in _Proceedings of the IEEE Conference on Decision and Control (CDC)_ , Albuquerque, NM, USA, December 10-12 1980, pp. 137–142. Available: http://dx.doi.org/10.1109/CDC.1980.272033
  * [17] F. Delebecque and J.-P. Quadrat, “Optimal control of Markov chains admitting strong and weak interactions,” _Automatica_ , vol. 17, no. 2, pp. 281–296, 1981. Available: http://dx.doi.org/10.1016/0005-1098(81)90047-9
  * [18] J. C. Príncipe, _Information Theoretic Learning_. New York City, NY, USA: Springer-Verlag, 2010.
  * [19] R. L. Stratonovich, “On value of information,” _Izvestiya of USSR Academy of Sciences, Technical Cybernetics_ , vol. 5, no. 1, pp. 3–12, 1965.
  * [20] R. L. Stratonovich and B. A. Grishanin, “Value of information when an estimated random variable is hidden,” _Izvestiya of USSR Academy of Sciences, Technical Cybernetics_ , vol. 6, no. 1, pp. 3–15, 1966.
  * [21] I. J. Sledge and J. C. Príncipe, “Analysis of agent expertise in Ms. Pac-Man using value-of-information-based policies,” _IEEE Transactions on Computational Intelligence and Artificial Intelligence in Games_ , 2018, (accepted, in press). Available: http://dx.doi.org/10.1109/TG.2018.2808201
  * [22] I. J. Sledge, M. S. Emigh, and J. C. Príncipe, “Guided policy exploration for Markov decision processes using an uncertainty-based value-of-information criterion,” _IEEE Transactions on Neural Networks and Learning Systems_ , vol. 29, no. 6, pp. 2080–2098, 2018. Available: http://dx.doi.org/10.1109/TNNLS.2018.2812709
  * [23] I. J. Sledge and J. C. Príncipe, “An analysis of the value of information when exploring stochastic, discrete multi-armed bandits,” _Entropy_ , vol. 20, no. 3, pp. 155(1–34), 2018. Available: http://dx.doi.org/10.3390/e20030155
  * [24] T. M. Cover and J. A. Thomas, _Elements of Information Theory_. New York, NY, USA: John Wiley and Sons, 2006.
  * [25] J. von Neumann and O. Morgenstern, _Theory of Games and Economic Behavior_. Princeton, NJ, USA: Princeton University Press, 1953.
  * [26] N. Tishby, F. C. Pereira, and W. Bialek, “The information bottleneck method,” in _Proceedings of the Allerton Conference on Communication, Control and Computing_ , Monticello, IL, USA, September 22-24 1999, pp. 368–377.
  * [27] M. D. Donsker and S. R. S. Varadhan, “Asymptotic evaluation of certain Markov process expectations for large time I.” _Communications of Pure and Applied Mathematics_ , vol. 28, no. 1, pp. 1–47, 1975. Available: http://dx.doi.org/10.1002/cpa.3160280102
  * [28] ——, “Asymptotic evaluation of certain Markov process expectations for large time II.” _Communications of Pure and Applied Mathematics_ , vol. 28, no. 2, pp. 279–301, 1975. Available: http://dx.doi.org/10.1002/cpa.3160280206
  * [29] I. J. Sledge and J. C. Príncipe, “Reduction of Markov chains using a value-of-information-based approach,” University of Florida, Gainesville, FL, USA, Computational NeuroEngineering Laboratory Report CNEL-2018-10-1, 2018\. Available: https://www.dropbox.com/s/rvgkt1cwbz9o6zb/Sledge-UFTechRep-2018-1col.pdf?dl=0
  * [30] I. J. Sledge, J. C. Bezdek, T. C. Havens, and J. M. Keller, “Relational generalizations of cluster validity indices,” _IEEE Transactions on Fuzzy Systems_ , vol. 18, no. 4, pp. 771–786, 2010, (under review). Available: http://dx.doi.org/10.1109/TFUZZ.2010.2048114
  * [31] I. J. Sledge, T. C. Havens, J. C. Bezdek, and J. M. Keller, “Relational duals of cluster-validity functions for the $c$-means family,” _IEEE Transactions on Fuzzy Systems_ , vol. 18, no. 6, pp. 1160–1170, 2010, (under review). Available: http://dx.doi.org/10.1109/TFUZZ.2010.2079331


# On the nearly freeness of conic-line arrangements with nodes, tacnodes, and
ordinary triple points

Aleksandra Gałecka

###### Abstract

In the present note we provide a partial classification of nearly free conic-
line arrangements in the complex plane having nodes, tacnodes, and ordinary
triple points. In this setting, our theoretical bound tells us that the degree
of such an arrangement is bounded from above by $12$. We construct examples of
nearly free conic-line arrangements having degree $3,4,5,6,7$, and we prove
that in degree $10$, $11$, and $12$ there is no such arrangement.

Keywords 14C20, 32S22

Mathematics Subject Classification (2020) nearly free curves, conic-line
arrangements

##  1 Introduction

The theory of plane curve arrangements has recently gained a lot of attention
among researchers. It is worth recalling some recent papers devoted to
rational curve arrangements in the complex projective plane, for instance [10,
11, 12]. One of the most interesting open questions that appears in the
literature is the so-called numerical Terao’s conjecture. There are some
variants of this conjecture, but we focus here on the following. Let
$\mathcal{C},\mathcal{C}^{\prime}\subset\mathbb{P}^{2}_{\mathbb{C}}$ be two
reduced curves such that they have the same weak combinatorics, i.e., they
have the same number of irreducible components of the same degree, and the
same number of singularities of a given topological type. Assume that
$\mathcal{C}^{\prime}$ is free, then $\mathcal{C}$ has to be free. For
instance, Pokora and Dimca in [6] proved that the numerical Terao’s conjecture
holds in the class of conic-line arrangements with nodes, tacnodes, and
ordinary triple points. On the other hand, it is known that numerical Terao’s
conjecture does not hold in the class of (triangular) line arrangements [8].
From this perspective, it is natural to understand wider classes of curves and
hopefully this effort will help us to understand numerical Terao’s conjecture
better. In the light of the original Terao’s conjecture for line arrangements,
which tells us that the freeness is determined by the intersection poset,
Dimca and Sticlaru in [3] defined a new class of curves that is called nearly
free. Here our aim is to understand nearly free complex conic-line arrangement
with nodes, tacnodes, and ordinary triple points. Our motivation comes from
aforementioned paper by Dimca and Pokora [6], where the authors classify all
free conic-line arrangement with nodes, tacnodes, and ordinary triple points.
Let us briefly present the main outcome of the note. First of all, we observe
in Proposition 4.2 that if $\mathcal{C}$ is a conic-line arrangement in the
complex plane with nodes, tacnodes, and ordinary triple points, then its
degree is bounded from above by $12$. Then we start to analyse, case by case,
in which degree we can find a nearly free conic-line arrangement – it turns
out that we can find such arrangements in degree $3,4,5,6,7$. However, for the
degree $10$, $11$, and $12$ we show that there does not exist any conic-line
arrangement in the complex plane with the prescribed above singularities that
is nearly free. Based on the above discussion, one needs to decide the
existence of nearly free conic-line arrangements in degree $8,9$.

Through the paper we work exclusively over the complex numbers. Our
computations are performed with `Singular` [1].

##  2 Conic-line arrangements with nodes, tacnodes, and ordinary triple points

Let $\mathcal{C}\subset\mathbb{P}^{2}_{\mathbb{C}}$ be an arrangement
consisting of $d\geqslant 1$ lines and $k\geqslant 1$ smooth conics. We assume
that $\mathcal{C}$ has only $n_{2}$ nodes, $t$ tacnodes, and $n_{3}$ ordinary
triple points. Denote by $m$ the degree of $\mathcal{C}$ which is equal to
$m=2k+d$. Then we have the following combinatorial count

$4\cdot\binom{k}{2}+2kd+\binom{d}{2}=\binom{m}{2}-k=n_{2}+2t+3n_{3},$

and this formula follows from Bézout theorem.

Focusing on simple singularities like nodes, tacnodes, and ordinary triple
points is the first non-trivial case when non-ordinary singularities occurs.
For the discussion we will need also the notion of the global and local
Tjurina numbers of singularities.

######  Definition 2.1.

Let $f:(\mathbb{C}^{2},0)\rightarrow(\mathbb{C},0)$ be the germ of an isolated
singularity. Then the (local) Tjurina number at $p=(0,0)$ is defined as

$\tau_{p}:={\rm dim}_{\mathbb{C}}\frac{\mathbb{C}\\{x,y\\}}{\langle
f,\partial_{x}\,f,\partial_{y}\,f\rangle}.$

The total Tjurina number of a reduced curve $C$ is defined as

$\tau(C):=\sum_{p\in{\rm Sing}(C)}\tau_{p},$

where the sum goes over all singular points of $C$.

######  Remark 2.2.

Let us recall that if $p$ is a node, then $\tau_{p}=1$, if $q$ is a tacnode,
then $\tau_{q}=3$, and if $r$ is an ordinary triple point, then $\tau_{r}=4$.
Based on it, if $\mathcal{C}$ is a conic-line arrangement with $n_{2}$ nodes,
$t$ tacnodes, and $n_{3}$ ordinary triple points, then

$\tau(\mathcal{C})=n_{2}+3t+4n_{3}.$

##  3 Nearly freeness of reduced curves

Let $C$ be a reduced curve $\mathbb{P}^{2}_{\mathbb{C}}$ of degree $m$ given
by $f\in S:=\mathbb{C}[x,y,z]$. We denote by $J_{f}$ the Jacobian ideal
generated by the partial derivatives
$\partial_{x}f,\,\partial_{y}f,\,\partial_{z}f$. Moreover, we denote by
$r:={\rm mdr}(f)$ the minimal degree of a non-trivial relation among the
partial derivatives, i.e., the minimal degree $r$ of a triple $(a,b,c)\in
S_{r}^{3}$ such that

$a\cdot\partial_{x}f+b\cdot\partial_{y}f+c\cdot\partial_{z}f=0.$

We denote by $\mathfrak{m}=\langle x,y,z\rangle$ the irrelevant ideal.
Consider the graded $S$-module $N(f)=I_{f}/J_{f}$, where $I_{f}$ is the
saturation of $J_{f}$ with respect to $\mathfrak{m}$.

######  Definition 3.1.

A reduced plane curve $C$ is _nearly free_ if $N(f)\neq 0$ and for every $k$
one has ${\rm dim}\,N(f)_{k}\leqslant 1$.

In order to study nearly freeness of conic-line arrangements, we will use [2,
Theorem 1.3].

######  Theorem 3.2 (Dimca).

Let $\mathcal{C}\subset\mathbb{P}^{2}_{\mathbb{C}}$ be a conic-line
arrangement of degree $m$ and let $f=0$ be its defining equation. Denote by
$r:={\rm mdr}(f)$. Then $\mathcal{C}$ is nearly free if and only if

$r^{2}-r(m-1)+(m-1)^{2}=\tau(\mathcal{C})+1,$ (1)

where $\tau(\mathcal{C})$ is the total Tjurina number of $\mathcal{C}$.

######  Remark 3.3.

In the original formulation of the above result there was the assumption that
$r\leqslant m/2$. However, it turns out that it is not necessary, and this
follows from [7, Theorem 3.2].

Now we are going to discuss the freeness from the homological viewpoint. We
need the following result which comes from [5].

######  Theorem 3.4 (Dimca-Sticlaru).

If $C\subset\mathbb{P}^{2}_{\mathbb{C}}$ is a nearly free reduced curve of
degree $m$ given by $f\in S_{m}$, then the minimal resolution of the Milnor
algebra $M(f)$ has the following form:

$\begin{split}0\rightarrow S(-d_{2}-m)\rightarrow S(-d_{1}-(m-1))\oplus
S(-d_{2}-(m-1))\oplus S(-d_{2}-(m-1))\\\ \rightarrow S^{3}(-m+1)\rightarrow
S\rightarrow M(f)\rightarrow 0\end{split}$

for some integers $d_{1}\leqslant d_{2}$ such that $d_{1}+d_{2}=m$.

In the setting of the above theorem, the pair $(d_{1},d_{2})$ is called the
set of exponents of the nearly free curve $C$.

##  4 Nearly free arrangements of conic and lines with nodes, tacnodes, and
triple points

In order to understand conic-line arrangements with nodes, tacnodes, and
ordinary tiple points that are nearly free, we provide an upper-bound on the
degree of such arrangements. We need the following result [6, Proposition
4.7].

######  Proposition 4.1.

Let $\mathcal{C}\,:\,f=0$ be a conic-line arrangement of degree $m$ in
$\mathbb{P}^{2}_{\mathbb{C}}$ such that it has only nodes, tacnodes, and
ordinary triple intersection points. Then one has

${\rm mdr}(f)\geqslant\frac{2}{3}m-2.$

If $\mathcal{C}\,:f=0$ is a nearly free conic-line arrangement of degree $m$
with nodes, tacnodes, and ordinary triple intersection points with the
exponents $(d_{1},d_{2})$, $d_{1}\leqslant d_{2}$, then ${\rm mdr}(f)=d_{1}$,
and since

$2d_{1}\leqslant d_{1}+d_{2}=m$

we obtain that ${\rm mdr}(f)\leqslant m/2$. Combining it with the above
proposition, we arrive at

$\frac{2}{3}m-2\leqslant{\rm mdr}(f)\leqslant m/2.$

It gives us the following result.

######  Proposition 4.2.

If $\mathcal{C}\subset\mathbb{P}^{2}_{\mathbb{C}}$ is a nearly free conic-line
arrangement of of degree $m$ with nodes, tacnodes, and ordinary triple
intersection points, then $m\leqslant 12$.

Based on the above proposition, we can formulate the following problem.

######  Problem 4.3.

Classify all weak combinatorics of conic-line arrangements with nodes,
tacnodes, and ordinary triple points in $\mathbb{P}^{2}_{\mathbb{C}}$ that are
nearly free.

Here by a weak combinatorics we mean the vector $(d,k;n_{2},t,n_{3})$, where
$d$ is the number of lines, $k$ is the number of conics (and of course
$m=2k+d$).

Let us pass to some combinatorial constraints on the singular points of such
conic-line arrangements that come from the data of the exponents
$(d_{1},d_{2})$. If $\mathcal{C}$ is a nearly free conic-line arrangement with
$k$ conics and $d$ lines, $d_{1}+d_{2}=m$, then following equality holds

$d^{2}_{1}+d_{2}^{2}+d_{1}d_{2}-d_{1}-2d_{2}=n_{2}+3t+4n_{3}.$ (2)

Since $\binom{d_{1}+d_{2}}{2}-k=n_{2}+2t+3n_{3}$, we can obtain the following
equality

$t+n_{3}=d^{2}_{1}+d_{2}^{2}+d_{1}d_{2}-d_{1}-2d_{2}-\binom{d_{1}+d_{2}}{2}+k.$

This gives

$2(t+n_{3})=d_{1}^{2}+d_{2}^{2}-d_{1}-3d_{2}+2k.$ (3)

The last ingredient that we will use in our classification problem is the
following proposition which is a direct consequence of the previously known
results from [6, 9].

######  Proposition 4.4.

Let $\mathcal{C}$ be a conic-line arrangement in $\mathbb{P}^{2}_{\mathbb{C}}$
of degree $m=2k+d\geqslant 6$ having only $n_{2}$ nodes, $t$ tacnodes, and
$n_{3}$ ordinary triple points. Then we have the following inequality

$8k+n_{2}+\frac{3}{4}n_{3}\geqslant d+\frac{5}{2}t.$

###### Proof.

It follows from the discussions in the framework of [6, Theorem 2.1] and [9,
Theorem B]. ∎

##  5 Partial classification of nearly free conic-line arrangements

Here we perform a step-by-step approach towards the classification problem of
our nearly free conic-line arrangements in the complex projective plane having
$k\geqslant 1$ conics and $d\geqslant 1$ lines. We start with constructing
explicit examples of nearly free conic-line arrangements having degree up to
$7$. Then we present our argument standing behind the non-existence of nearly
free conic-line arrangement with nodes, tacnodes, and ordinary triple points
having degree $m\in\\{10,11,12\\}$. Unfortunately, our method does not allow
us to decide on the non-existence of conic-line arrangements having degree
$m\in\\{8,9\\}$, but we hope to resolve that problem by using a different
approach.

###  5.1 Case $m=3$

Let us consider the following arrangement
$\mathcal{C}_{3}=\\{\ell,C\\}\subset\mathbb{P}^{2}_{\mathbb{C}}$ defined by

$F(x,y,z)=(x^{2}+y^{2}-16z^{2})\cdot(y-x+4z).$

It is easy to see that $\mathcal{C}_{3}$ has only $n_{2}=2$ and $t=n_{3}=0$,
so its total Tjurina number $\tau(\mathcal{C}_{3})$ is equal to $2$. Using
`Singular`, we can compute ${\rm mdr}(F)$ which is equal to $1$.
By Theorem 3.2 we see that

$3=1-2+4=r^{2}-r(m-1)+(m-1)^{2}=\tau(\mathcal{C}_{3})+1=2+1,$

so $\mathcal{C}_{3}$ is nearly free. Observe that this is the only possible
nearly free conic-line arrangement with nodes, tacnodes, ordinary triple
points and $m=3$. Since $d_{1}+d_{2}=3$ and $d_{1}\leqslant d_{2}$, we can
have only $(d_{1},d_{2})=(1,2)$. Recall that ${\rm mdr}(f)=d_{1}=1$, and

$3=1^{2}-1\cdot(3-1)+(3-1)^{2}=\tau(\mathcal{C})+1.$

It means that $\tau(\mathcal{C})=2$, and the only possibility is to have
$n_{2}=2$ and $t=0$, which completes our justification.

Figure 1: A nearly free arrangement with one conic and one line.

###  5.2 Case $m=4$

Now we consider the following arrangement
$\mathcal{C}_{4}=\\{\ell_{1},\ell_{2},C\\}\subset\mathbb{P}^{2}_{\mathbb{C}}$
given by

$F(x,y,z)=(x^{2}+y^{2}-16z^{2})\cdot(y-x-4z)\cdot(y+x-4z).$

It is easy to see that for $\mathcal{C}_{4}$ we have $n_{2}=2$ and $n_{3}=1$,
so its total Tjurina number $\tau(\mathcal{C}_{4})$ is equal to $6$. Using
`Singular`, we can compute ${\rm mdr}(F)$ that is equal to $2$.
Using Theorem 3.2, we see that

$7=4-6+9=r^{2}-r(m-1)+(m-1)^{2}=\tau(\mathcal{C}_{4})+1=6+1,$

so $\mathcal{C}_{4}$ is nearly free.

Figure 2: A nearly free arrangement of degree $m=4$ with two nodes and one
triple point.

Now we show that for $m=4$ there is another possible nearly free conic-line
arrangement. Observe that for $m=4$ we have two possible pairs of the
exponents, namely $(d_{1},d_{2})=(1,3)$ and $(d_{1},d_{2})=(2,2)$, and since
$k\geqslant 1$, $d\geqslant 1$, our conic-line arrangement $\mathcal{C}$
consists of $k=1$ conics and $d=2$ lines. We see that for both possibilities
of the exponents we have $\tau(\mathcal{C})=6$. The following weak
combinatorics for conic line arrangements with nodes, tacnodes, and ordinary
triple points and $m=4$ are admissible:

$n_{2}$ | $t$ | $n_{3}$
---|---|---
5 | 0 | 0
3 | 1 | 0
1 | 2 | 0
2 | 0 | 1

Based on that, an arrangement with $3$ double points and one tacnode can be
also nearly free. Consider the arrangement
$\mathcal{C}_{4}^{{}^{\prime}}=\\{\ell_{1},\ell_{2},C\\}\subset\mathbb{P}^{2}_{\mathbb{C}}$
given by

$G(x,y,z)=(x^{2}+y^{2}-16z^{2})\cdot(y-4z)\cdot(y-x).$

Using `Singular`, we can compute that ${\rm mdr}(G)$ is equal to $2$ and

$7=4-6+9=r^{2}-r(m-1)+(m-1)^{2}=\tau(\mathcal{C}_{4}^{{}^{\prime}})+1=3+3\cdot
1+1,$

Figure 3: A nearly free arrangement of degree $m=4$ with three nodes and one
tacnode.

so $\mathcal{C}_{4}^{{}^{\prime}}$ is nearly free.

###  5.3 Case $m=5$

We consider here the following arrangement
$\mathcal{C}_{5}=\\{\ell_{1},\ell_{2},\ell_{3},C\\}\subset\mathbb{P}^{2}_{\mathbb{C}}$
given by

$F(x,y,z)=(x^{2}+y^{2}-16z^{2})\cdot(y-x+4z)\cdot(y+x-4z)\cdot(y-x-4z).$

It is easy to see that for $\mathcal{C}_{5}$ we have $n_{2}=3$ and $n_{3}=2$,
so its total Tjurina number $\tau(\mathcal{C}_{5})$ is equal to $11$. Using
`Singular`, we can compute ${\rm mdr}(F)$ which is equal to $2$.
Using Theorem 3.2, we have

$12=4-8+16=r^{2}-r(m-1)+(m-1)^{2}=\tau(\mathcal{C}_{5})+1=11+1,$

so $\mathcal{C}_{5}$ is nearly free.

Figure 4: A nearly free arrangement with one conic and three lines.

###  5.4 Case $m=6$

We consider here the following arrangement
$\mathcal{C}_{6}=\\{\ell_{1},\ell_{2},\ell_{3},\ell_{4},C\\}\subset\mathbb{P}^{2}_{\mathbb{C}}$
given by

$F(x,y,z)=(x^{2}+y^{2}-16z^{2})\cdot(y-x+4z)\cdot(y+x-4z)\cdot(y-x-4z)\cdot(y+x+4z).$

It is easy to see that for $\mathcal{C}_{3}$ we have $n_{2}=2$ and $n_{3}=4$,
so its total Tjurina number $\tau(\mathcal{C}_{6})$ is equal to $18$. Using
`Singular`, we can compute ${\rm mdr}(F)$ which is equal to $2$.
Using Theorem 3.2, we obtain

$19=4-10+25=r^{2}-r(m-1)+(m-1)^{2}=\tau(\mathcal{C}_{6})+1=18+1,$

so $\mathcal{C}_{6}$ is nearly free.

Figure 5: A nearly free arrangement with one conic and four lines.

###  5.5 Case $m=7$

Let us consider here the following arrangement
$\mathcal{C}_{7}=\\{\ell_{1},\ell_{2},\ell_{3},\ell_{4},\ell_{5},C\\}\subset\mathbb{P}^{2}_{\mathbb{C}}$
given by

$F(x,y,z)=(x^{2}+y^{2}-z^{2})\cdot(x^{2}-z^{2})\cdot(y^{2}-z^{2})\cdot(y+x).$

It is easy to see that for $\mathcal{C}_{7}$ we have $n_{2}=6$, $t=4$, and
$n_{3}=2$, so its total Tjurina number $\tau(\mathcal{C}_{7})$ is equal to
$26$. Using `Singular`, we can compute ${\rm mdr}(F)$ that is equal to $3$.
Using Theorem 3.2, we see

$27=9-18+36=r^{2}-r(m-1)+(m-1)^{2}=\tau(\mathcal{C}_{7})+1=26+1,$

so $\mathcal{C}_{7}$ is nearly free.

Figure 6: A nearly free arrangement with one conic and five lines.

###  5.6 Case $m=10$.

Assume that $\mathcal{C}\subset\mathbb{P}^{2}_{\mathbb{C}}$ is a nearly free
conic-line arrangement with $m=10$ having the exponents $(d_{1},d_{2})$,
$d_{1}\leqslant d_{2}$. By Proposition 4.1, we have

$d_{1}={\rm mdr}(f)\geqslant\frac{2}{3}m-2=\frac{20}{3}-2=4\,\frac{2}{3},$

which implies that $d_{1}\geqslant 5$. However, it means that we need to
consider the only one case, namely $(d_{1},d_{2})=(5,5)$. Using equation (3)
we obtain

$t+n_{3}=15+k.$

and it means, in particular, that $k\in\\{1,2,3,4\\}$.
By the combinatorial count, we have

$\binom{10}{2}-k=n_{2}+2(t+n_{3})+n_{3},$

so we arrive at

$15-3k=n_{2}+n_{3},$

and it means, in particular, that $k\in\\{1,2,3,4\\}$. Hence

$t=15+k-n_{3}=15+k-(15-3k-n_{2})=4k+n_{2}.$

Now we are going plug this data into inequality from Proposition 4.4.
We have

$8k+n_{2}+\frac{3}{4}(15-3k-n_{2})\geqslant(10-2k)+\frac{5}{2}(4k+n_{2}).$

After some simple manipulations we obtain

$5\geqslant 9k+9n_{2},$

which is a contradiction since $k\in\\{1,2,3,4\\}$. This proves the following
result.

######  Theorem 5.1.

There does not exists any nearly free conic-line arrangement in the complex
projective plane with nodes, tacnodes, and ordinary triple points having
degree $m=10$.

###  5.7 Case $m=11$.

Assume that $\mathcal{C}\subset\mathbb{P}^{2}_{\mathbb{C}}$ is a nearly free
conic-line arrangement with $m=11$ having the exponents $(d_{1},d_{2})$,
$d_{1}\leqslant d_{2}$. By Proposition 4.1, we have that

$d_{1}={\rm mdr}(f)\geqslant\frac{2}{3}m-2=\frac{22}{3}-2=5\,\frac{1}{3},$

so $d_{1}\geqslant 6$. However, it means that such a nearly free curve cannot
exists, and we have the following proposition.

######  Proposition 5.2.

There does not exists any nearly free conic-line arrangement in the complex
projective plane with nodes, tacnodes, and ordinary triple points having
degree $m=11$.

###  5.8 Case $m=12$.

Assume that $\mathcal{C}\subset\mathbb{P}^{2}_{\mathbb{C}}$ is a nearly free
conic-line arrangement with $m=12$ having the exponents $(d_{1},d_{2})$ with
$d_{1}\leqslant d_{2}$. Using Proposition 4.1, we see that

$d_{1}={\rm mdr}(f)\geqslant\frac{2}{3}m-2=\frac{2}{3}\cdot 12-2=6,$

so the only one case to consider is $(d_{1},d_{2})=(6,6)$. Using equation (3)
we obtain

$2(t+n_{3})=48+2k,$

and plugging this into the combinatorial count we get

$n_{2}+n_{3}=18-3k.$

In particular, $k\in\\{1,2,3,4,5\\}$.
Using Proposition 4.4 we have

$5k+18\geqslant d+\frac{5}{2}t,$

so finally

$t\leqslant\frac{2}{5}\bigg{(}5k+18-d\bigg{)}.$

We have the following possibilities, depending on $k$, namely

$k$ | $n_{3}$ | $t\leqslant$
---|---|---
1 | 15 | 5
2 | 12 | 8
3 | 9 | 11
4 | 6 | 14
5 | 3 | 16

.

Since in all the cases listed above we have $t+n_{3}\leqslant 20$, we arrive
at a contradiction with respect to the condition that $t+n_{3}=24+k$. This
allows us to conclude our discussion by the following result.

######  Theorem 5.3.

There does not exists any nearly free conic-line arrangement in the complex
projective plane with nodes, tacnodes, and ordinary triple points having
degree $m=12$.

## Acknowledgments

This note is a part of the author’s Master Thesis that is written under the
supervision of Piotr Pokora. The research was conducted in the framework of
The Excellence Initiative - Research University Programme at the Pedagogical
University of Cracow.

The author would like to warmly thank an anonymous referee for very useful
suggestions and remarks that allowed to improve the paper, especially for
explaining the non-existence case with $m=10$.

## References

  * [1] W. Decker, G.-M. Greuel, G. Pfister, and H. Schönemann,  Singular 4-1-1 — A computer algebra system for polynomial computations.  http://www.singular.uni-kl.de, 2018.
  * [2] A. Dimca, Freeness versus Maximal Global Tjurina Number for Plane Curves. Math. Proc. Camb. Philos. Soc. 163(1): 161 –172 (2017).
  * [3] A. Dimca and G. Sticlaru, Free divisors and rational cuspidal plane curves. Math. Res. Lett. 24(4): 1023 – 1042 (2017).
  * [4] A. Dimca and G. Sticlaru, On the exponents of free and nearly free projective plane curves. Rev. Mat. Complut. 30(2): 259 – 268 (2017).
  * [5] A. Dimca and G. Sticlaru, Free and Nearly Free Curves vs. Rational Cuspidal Plane Curves. Publ. Res. Inst. Math. Sci. 54(1): 163 – 179 (2018).
  * [6] A. Dimca and P. Pokora, On conic-line arrangements with nodes, tacnodes, and ordinary triple points. J. Algebraic Combin. https://doi.org/10.1007/s10801-022-01116-3 (2022).
  * [7] A. A. Du Plessis and C. T. C. Wall, Application of the theory of the discriminant to highly singular plane curves. Math. Proc. Camb. Philos. Soc. 126(2): 259 – 266 (1999).
  * [8] S. Marchesi and J. Valés, Triangular arrangements on the projective plane. arXiv:1903.08885.
  * [9] P. Pokora, $\mathcal{Q}$-conic arrangements in the complex projective plane. arXiv:2203.11503.
  * [10] P. Pokora and T. Szemberg, Conic-line arrangements in the complex projective plane. Discrete Comput. Geom. https://doi.org/10.1007/s00454-022-00397-6 (2022).
  * [11] H. Schenck and S. Tohaneanu, Freeness of conic-line arrangements in $\mathbb{P}^{2}$. Comment. Math. Helv. 84(2): 235 – 258 (2009).
  * [12] H. Schenck, H. Terao, M. Yoshinaga, Logarithmic vector fields for curve configurations in $\mathbb{P}^{2}$ with quasihomogeneous singularities. Math. Res. Lett. 25: 1977–1992 (2018).

Aleksandra Gałecka
Department of Mathematics, Pedagogical University of Kraków, Podchora̧żych 2,
PL-30-084 Kraków, Poland.
E-mail address<EMAIL_ADDRESS>