# Tree edit distance for hierarchical data compatible with HMIL paradigm

Břetislav Šopík<EMAIL_ADDRESS>Tomáš Strenáčik  Avast Software,
Pikrtova 1737/1a, 14000 Prague, Czech Republic

##  I Introduction

In contemporary data analysis in industrial and academic research we often
need to work with data that has a hierarchical structure. The analysis of such
data is naturally more difficult than the analysis of data with a flat
structure because the schema of the hierarchically organized dataset may
possess important information which is lost if we ignore it. A common task of
a dataset analysis is to evaluate the difference between two of its instances.
If the dataset has a flat structure and consists of numerical vectors,
appropriate distance function from vector spaces can be used. Similarly, we
can utilize the Levenshtein edit distanceWagner-Fischer-1974  for comparison
of two strings, etc. However, this task gets significantly more challenging
when we consider hierarchically structured data consisting of fields of
multiple data types. Because the schema of hierarchically organized data has a
form of a rooted tree, the applicable distance function may belong to the
class of _tree edit distances_ (TED). These distance functions are widely
studied topic in the literature Bille-2005  and are a special case of more
general edit distances on graphs Blumenthal-2019 .

There are many formats wich allow for the hierarchical organization of data,
e.g., JSON111https://www.json.org/json-en.html, XML222https://www.w3.org/XML/,
YAML333https://yaml.org/ or Apache Parquet444https://parquet.apache.org/. In
this work we focus on the JSON format which is arguably one of the most widely
used. Interestingly, despite a significant body of research on TED, we are not
aware of any implementation of TED applicable to hierarchically structured
data in the JSON format apart of the approximate solution by Augsten _et al_.
Augsten-etal-2008-A ; Augsten-etal-2008-B  which was implemented in a Python
package _jqgram_ 555https://github.com/hoonto/jqgram.

Nowadays, data analysis is a common part of a work on a machine learning (ML)
problem. Solving ML problems on data with hierarchical structure is as
challenging as the data analysis for the very same reason. Successful and
generally applicable ML frameworks were missing, until recently, when
Hierarchical multi-instance learning (HMIL) paradigm was developed.Pevny-
Somol-2016 ; Mandlik-2021  It allows for end-to-end ML in AutoML fashion on
hierarchically ordered data which contain structural elements in form of bags
of equivalent observations (instances).

In this work, we present TED applicable to hierarchically structured data that
is expressed in the JSON format and compatible with the HMIL framework. In
practical terms the HMIL framework compatibility means that all JSON elements
of the Array data type are interpreted as unordered bags. A more detailed
discussion of the notion of HMIL compatibility can be found further in the
text.

The manuscript is organized as follows: Section II compares the JSON format
with the HMIL framework and defines a mapping between them. It also outlines
relevant parts of the TED research and explains why they are not applicable to
our case. In section III we define the edit distance applicable to data in
JSON format compatible with the HMIL framework. Section IV presents an
algorithm for calculating the distance and proof that the distance is minimal.
The concluding section V reviews the proposed solution, presents a recipe for
computation and discusses possible applications.

##  II Related theory

###  II.1 Comparison of JSON format and HMIL framework

####  II.1.1 JSON sample

The JSON format recognizes elementary data types _Boolean_ , _Number_ ,
_String_ and _null_. It also recognizes two composite data types _Object_ and
_Array_. _Object_ is a key-value dictionary in which the key is _String_ and
value is any JSON data type. _Array_ is an ordered sequence of elements of any
JSON data type. Empty _Object_ or _Array_ is allowed as well. A _JSON sample_
is a hierarchical structure consisting of elements of elementary or composite
data types.

We define _JSON schema_ as an abstract representation of a JSON sample
capturing its hierarchy, used data types of its structural elements and names
of labels in Object type elements. Elaborate definition of the JSON schema is
beyond the purpose of this work. A sufficient framework is the _JSON Schema_
project666https://json-schema.org/. We say that a JSON sample $J$ obeys some
schema $S$ if it is compatible with $S$ within the applied framework.

####  II.1.2 HMIL sample

As noted in the introduction, the HMIL paradigm was developed to allow for
AutoML on data with hierarchical structure. This paradigm was implemented in a
set of Julia libraries under a common name Hierarchical Multi-instance
Learning Library (HMill)777https://github.com/CTUAvastLab/Mill.jl. Let us
describe the AutoML procedure within the HMill implementation: It begins by
discovering the underlying schema of structural organization obeyed by all
samples of the input dataset and represents it in _HMill schema_. The HMill
schema is then utilized to automatically create appropriate neural network
model with precise topology and also to map samples of the input dataset into
_HMill samples_. Finally, the mapped HMill samples are used to train the
model.

Every HMill sample has a structure of a tree composed of three types of
abstract data nodes — _array node_ , _bag node_ and _product node_. In this
tree, leaves are of type array node. Array nodes store information of
elementary data types, categorical variables or numerical vectors and embed it
into a relevant vector space. Inner nodes are formed by nodes of type bag node
or product node and store the structural information. The bag node represents
an unordered collection of elements of some type of the abstract data nodes.
The product node represents an ordered tuple joining independent elements of
abstract data node type.

For simplicity and clarity of the following discussion we define a notion of
_HMIL sample_ which is an equivalent of the HMill sample with the only
difference that the array node of the HMIL sample is just a data container and
lacks the data embedding functionality. By doing this we restrain ourselves
from technical discussions about the implementation of the embedding with no
impact on the presented results of this work.

Similarly to the case of JSON samples, we can define a notion of HMIL schema.
As a result we can also define a notion of HMIL sample or set of HMIL samples
obeying a particular HMIL schema.

####  II.1.3 Mapping of JSON sample into HMIL sample and HMIL compatibility

In order to proceed further we define an isomorphism
$\phi:\mathcal{J}\to\mathcal{H}$, where $\mathcal{J}$ is a set of all JSON
samples and $\mathcal{H}$ is a set of all HMIL samples. It allows us to map
any JSON sample $J\in\mathcal{J}$ into a HMIL sample $H=\phi(J)$,
$H\in\mathcal{H}$. The key principles of the isomorphism $\phi$ are the
following:

  * •

Field of elementary data type is mapped into the array node with the
corresponding data type.

  * •

Composite data type _Object_ is mapped into the product node. That is because
the JSON _Object_ is a key-value dictionary which can be ordered by keys and
every of its values is an independent JSON data type. Similarly, product node
represents an ordered tuple of independent elements of abstract data node
type.

  * •

Composite data type _Array_ is mapped into the bag node. We treat every JSON
_Array_ as an unordered collection of elements of a particular JSON data type.
Thus it can be mapped into a bag node which represents an unordered collection
of elements of particular abstract data node type.

The defined mapping of the JSON _Array_ type in $\phi$ has important
consequences. Despite the JSON _Array_ is defined as an ordered sequence of
elements, it may be utilized to contain elements where ordering is irrelevant.
We argue that it is indeed commonly used this way. The defined isomorphism
$\phi$ is correct for datasets where ordering in all its JSON _Array_ elements
is irrelevant. We call such datasets _HMIL compatible_. The proposed edit
distance is correct for JSON samples from HMIL compatible datasets.

###  II.2 Tree edit distances

The most commonly studied tree structure with respect to TED is a _rooted
labeled tree_ (RLT) with labeled nodes and edit operationsBille-2005 :

  * •

_Relabel_ : Change the label of a node of the tree.

  * •

_Delete_ : Delete a non-root node $v$ of the tree with parent $v^{\prime}$.
Connect all the children of $v$ with the parent $v^{\prime}$.

  * •

_Insert_ : Insert a node $v$ in the tree so that it has parent $v^{\prime}$.
Reconnect some of the children of $v^{\prime}$ to be children of $v$.

This means that we are allowed to delete or insert inner nodes of the tree.
However, other problem settings were considered as well, e.g., Selkow
Selkow-1977  studied the edit distance problem where only deletions/insertions
of the leaves or sub-trees were allowed.

Literature recognizes two types of RLT — ordered and unordered. For ordered
RLT every node of the tree has exact left-to-right ordering of its children.
For unordered RLT none of the nodes has its children ordered. This property
has huge impact on the algorithmic complexity of the edit distance
computation. It was proven that for unordered RLT the computation of the edit
distance is NP-hard problem Zhang-etal-1992 , whereas in the ordered case
algorithms with polynomial asymptotic complexity were found Tai-1979 ; Zhang-
Shasha-1989 .

##  III Edit distance

In order to define the edit distance
$d_{\mathcal{J}}:\mathcal{J}\times\mathcal{J}\to\mathbb{R}_{\geq 0}$ on JSON
samples of HMIL compatible dataset we need to find a way how to represent any
HMIL sample as a RLT structure and also to define a suitable edit distance on
such RLT structures. This in technical terms means that we aim to find
appropriate isomorphism $\psi:\mathcal{H}_{\phi(\mathcal{J})}\to\mathcal{T}$
which maps $\mathcal{H}_{\phi(\mathcal{J})}=\\{\phi(J),\forall
J\in\mathcal{J}\\}$, $\mathcal{H}_{\phi(\mathcal{J})}\subset\mathcal{H}$, into
a set of all RLT structures $\mathcal{T}$. We also need to define edit
operations applicable to the mapped RLT
$\mathcal{T}_{\psi\circ\phi(\mathcal{J})}=\\{\psi(H),\forall
H\in\mathcal{H}_{\phi(\mathcal{J})}\\}$,
$\mathcal{T}_{\psi\circ\phi(\mathcal{J})}\subset\mathcal{T}$, which induce
correct TED $d:\mathcal{T}\times\mathcal{T}\to\mathbb{R}_{\geq 0}$. Finally,
the corresponding edit distance on JSON samples equals
$d_{\mathcal{J}}(J_{1},J_{2})=d(\psi\circ\phi(J_{1}),\psi\circ\phi(J_{2}))$;
$J_{1},J_{2}\in\mathcal{J}$.

We argue that none of the RLT structures studied in the literature (see
subsection II.2) is a valid target $\mathcal{T}_{\psi\circ\phi(\mathcal{J})}$
in our use case for several reasons. First two reasons are connected to the
RLT structures and the last one to the allowed edit operations:

  1. 1.

In general, HMIL compatible JSON sample can not be isomorphic to RLT which is
exclusively ordered or unordered. The HMIL mapping maps JSON type _Object_ to
ordered product node and _Array_ to unordered bag node. We must define TED on
a tree structure which allows for nodes of both ordered and unordered type.

  2. 2.

HMIL compatible JSON sample is isomorphic to a HMIL sample in which the inner
nodes store only the structural information and elementary information is
stored in the array nodes. Similarly, the corresponding RLT must contain the
elementary information only in its leaves.

  3. 3.

When evaluating TED between two HMIL compatible JSON samples which obey the
same HMIL schema we want to be sure that any sequence of edit operations
applied to them produces a sample which follows the HMIL schema. We call such
edit operations _schema-preserving_ operations.

Given the listed restrictions we define the following mapping of HMIL sample
into RLT and schema-preserving edit operations which induce the appropriate
TED.

###  III.1 Mapping of HMIL sample into RLT

Let us define three _node types_ a tree $T$ may consist of: Bag, Object and
Value. We define several functions acting on the nodes. Function $\nu(v)$
returns the _node type_ of a node $v$. Function $l(v)$ returns _label of the
node_ $v$. Function $\chi(v)$ returns a _bag of all children_ of the node $v$.
In addition, let us have two functions acting on the edges between nodes.
Function $l(v\dashrightarrow w)$ returns _label of the edge_ $v\dashrightarrow
w$ and function $\kappa(v)$ returns a _bag of all labels of edges_ between a
node $v$ and its children $\chi(v)$. Finally, we also define _data type_ of
the label of the node $v$ which is one of those supported by the JSON format:
null, Boolean, String, Number. The data type of a label $l(v)$ is obtained by
function $\tau(v)$. Figure 1 illustrates an arbitrary RLT structure.

object/.style=circle, draw, anchor=center, bag/.style=diamond, draw,
anchor=center, valuenumber/.style=rectangle,draw, fill=colornumber,
anchor=center, valuestring/.style=rectangle,draw, fill=colorstring,
anchor=center, valueboolean/.style=rectangle,draw, fill=colorboolean,
anchor=center [,object, for tree= l sep=2cm, s sep+=0.9em, grow=south [x,
valuestring, edge label = node [midway,fill=white] $k_{1}$] [,object, edge
label = node [midway, fill=white] $k_{2}$ [x, valueboolean, edge label = node
[midway, fill=white] $k_{5}$] [x, valuenumber, edge label = node [midway,
fill=white] $k_{6}$] [, object, edge label = node [midway, fill=white]
$k_{7}$]] [, bag, edge label = node [midway, fill=white] $k_{3}$ [x,
valuestring] [x, valuestring] [x, valuestring] [x, valuestring]] [, bag, edge
label = node [midway, fill=white] $k_{4}$] ] [anchor=north west] at (current
bounding box.north east)  Object Node Bag Node x Value Node — String x Value
Node — Boolean x Value Node — Number ;

Figure 1: A Rooted Labeled Tree. The node type and node data type are
represented by the node shape and color, respectively. Edges are labeled as
$k_{1},\dots,k_{7}$. Child nodes of a Bag node are indistinguishable by their
edge labels.

We define isomorphic mapping $\psi$ of a HMIL sample $H\in\mathcal{H}$ into a
corresponding RLT structure $T=\psi(H)$, $T\in\mathcal{T}$ as follows:

  * •

Product node in $H$ is mapped into $T$ as an Object node with labeled edges
that are mutually unique. If $\nu(v)=\text{Object}$ then
$|\chi(v)|=|\kappa(v)|$. The labels of edges are equal to those in the
corresponding JSON Object element.

  * •

Bag node in $H$ is mapped into $T$ as a Bag node with unordered edges with no
labels. If $\nu(v)=\text{Bag}$ then $\kappa(v)=\emptyset$.

  * •

Product node and bag node in $H$ are inner nodes of the HMIL schema, they
describe only the hierarchical structure. This implies that the labels of the
corresponding inner nodes in $T$ have implicitly a null value. If
$\nu(v)\in\\{\text{Bag},\text{Object}\\}$ then $l(v)=\text{null}$.

  * •

Array node in $H$ is mapped into $T$ as a Value node with label equal to the
data type and value of the corresponding field in the JSON sample. A node of
type Value has no children, thus if $\nu(v)=\text{Value}$ then
$\chi(v)=\emptyset$.

Figure 2 depicts the mappings between a JSON sample, corresponding HMIL sample
and a mapped RLT structure.

⬇

{

”name”: ”John”,

”inventory”: {

”full”: False,

”coins”: [

2,

1,

2

]

}

}

(a) JSON sample

cell/.style=rectangle,draw [pn$(\\{\cdot\leavevmode\hbox to0pt{\vbox
to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}},\cdot\\})$, cell,
[an$($John$)$, cell] [pn$(\\{\cdot,\cdot\\})$, cell, [an$($False$)$, cell]
[bn$(\\{\cdot,\cdot,\cdot\\})$, cell, for tree=calign=last [an$(2)$, cell]
[an$(1)$, cell] [an$(2)$, cell] ] ] ]

(b) HMIL Data node

object/.style=circle, draw, anchor=center, bag/.style=diamond, draw,
anchor=center, valuenumber/.style=rectangle,draw, fill=colornumber,
anchor=center, valuestring/.style=rectangle,draw, fill=colorstring,
anchor=center, valueboolean/.style=rectangle,draw, fill=colorboolean,
anchor=center [ ,object, for tree= l sep=1cm, s sep+=0.5cm, grow=south [John,
valuestring, edge label = node [midway, left] name] [, object, edge label =
node [midway, right] inventory [False, valueboolean, edge label = node
[midway, left] full] [, bag, edge label = node [midway, right] coins, for
tree=calign=last [2, valuenumber] [1, valuenumber] [2, valuenumber] ] ] ]

(c) Rooted Labeled Tree

$\phi$$\psi$

Figure 2: Three representations of arbitrary hierarchical sample. The mapping
between (a) and (b) is done by $\phi$ and the mapping between (b) and (c) is
realized by $\psi$. In (b), the _an_ , _bn_ and _pn_ represent the _array_ ,
_bag_ and _product_ nodes in accordance with the HMIL terminology.

If the samples of the HMIL dataset obey some HMIL schema we utilize the
isomorphism $\psi$ to define the corresponding _RLT schema_ which puts
structural limitations on $\mathcal{T}_{\psi\circ\phi(\mathcal{J})}$. The
schema-preserving edit operations are those which preserve the compatibility
of $T$ with the corresponding RLT schema.

###  III.2 Schema-preserving edit operations

Edit operations which violate the RLT schema of $T$ — and subsequently the
HMIL schema of the corresponding $H$ — are those that change its inner nodes.
Thus, in order to define the schema-preserving edit operations we allow only
those that act on the leaves of $T$.

We depict edit operations as $v\to v^{\prime}$ where $v$, $v^{\prime}$ are
nodes of $T$. We also use a special symbol $\lambda$ to depict a non-existing
node. The allowed edit operations read:

  * •

_Relabel operation_ $v\to v^{\prime}$: We may change the label of a node $v$
of a type Value, $\nu(v)=\text{Value}$, to a value of the same data type
$\tau(v)=\tau(v^{\prime})$.

  * •

_Delete operation_ $v\to\lambda$: We may delete a leaf $v$ of $T$, i.e., a
node with $\chi(v)=\emptyset$, with label of any data type and value.

  * •

_Insert operation_ $\lambda\to v$: We may insert a leaf $v$ into $T$ of any
node type. In case the dataset follows some RLT schema the resulting tree must
be compatible with it.

The defined elementary edit operations can be composed into a sequence of
$k\in\mathbb{N}$ operations $S=s_{1}\circ s_{2}\circ\dots s_{k}$. By applying
$S$ we transform a tree $T_{1}$ into $T_{2}$ which we depict as $T_{1}\to
T_{2}$. In this sequence, we begin with $T_{1}=T_{(0)}$ and each edit
operation $s_{i}$ performs transformation $T_{(i-1)}\to T_{(i)}$ until we
reach the final tree $T_{2}=T_{(k)}$. As a corollary, the defined edit
operations chain into sequences which allow only for deletion, insertion or
relabeling of whole subtrees.

###  III.3 Cost function

The cost function $\gamma$ connected with relabeling, deleting or inserting a
leaf of a tree may differ for every elementary type and actual compared
values. We constraint $\gamma$ to be a proper distance function defined on
nodes of the same type. Let us define a type function $\tau$ returning the
data type of the node $v$. Then for any nodes $v_{1},v_{2},v_{3}$ of the same
node type and data type the function $\gamma$ has the following properties:

$\displaystyle\gamma(v_{1},v_{1})$ $\displaystyle=0$
$\displaystyle\text{identity of indiscernibles},$ (1)
$\displaystyle\gamma(v_{1},v_{2})$ $\displaystyle=\gamma(v_{2},v_{1})$
$\displaystyle\text{symmetry},$ (2) $\displaystyle\gamma(v_{1},v_{2})$
$\displaystyle\leq\gamma(v_{1},v_{3})+\gamma(v_{3},v_{2})$
$\displaystyle\text{triangular inequality},$ (3) which also implies
$\displaystyle\gamma(v_{1},v_{2})$ $\displaystyle\geq 0$
$\displaystyle\text{non-negativity}.$ (4)

We extend $\gamma$ to the sequence of edit operations $S$ by
$\gamma(S)=\sum_{i=1}^{|S|}\gamma(s_{i})$, where the notation $\gamma(s_{i})$
is a placeholder for $\gamma(v,v^{\prime})$ which is cost of the edit
operation $s_{i}$ involving nodes $v\to v^{\prime}$. Finally, the distance
function $d$ between trees $T_{1},T_{2}\in\mathcal{T}$ is defined as

$d(T_{1},T_{2})=\min_{S}\\{\gamma(S)|\text{$S$ is a sequence of edit
operations transforming $T_{1}$ to $T_{2}$}\\}.$ (5)

Since $\gamma$ is a distance function $d$ is a distance function too.

###  III.4 Edit distance mapping

Similarly to literature on TEDZhang-Shasha-1989 ; Bille-2005  we find it
helpful to define _edit distance mapping_ of transformation $T_{1}\to T_{2}$
denoted as $(M,T_{1},T_{2})$ (or $M$ for short). It is a set of tuples of
nodes from $T_{1}$ and $T_{2}$ that are related via edit operations

$(M,T_{1},T_{2})=\\{(v,w)|\text{$w\in T_{2}$ is a transformation target of
$v\in T_{1}$}\\},$ (6)

Let us have a function $\pi(v)$ returning a _parent of a node_ $v\in T$ if
exists. The defined edit operations imply that the mapping $M$ satisfies the
following properties:

  1. 1.

Nodes in a tuple are of the same node type and data type, i.e.,
$\forall(v,w)\in M$: $\nu(v)=\nu(w)$ and $\tau(v)=\tau(w)$.

  2. 2.

The mapping is one-to-one, i.e., $\forall(v_{1},w_{1}),(v_{2},w_{2})\in M$:
$v_{1}=v_{2}$ iff $w_{1}=w_{2}$.

  3. 3.

Parents are part of the mapping as well, i.e., if $(v,w)\in M$ then
$(\pi(v),\pi(w))\in M$.

  4. 4.

If $(v,w)\notin M$ then no descendant of $v\in T_{1}$ and of $w\in T_{2}$ is
in $M$.

  5. 5.

Labels of edges from parents are equal, i.e., $\forall(v,w)\in M$: if
$\nu(\pi(v))=\text{Object}$ then $l(\pi(v)\dashrightarrow
v)=l(\pi(w)\dashrightarrow w)$.

Let $N_{1}$ and $N_{2}$ be the set of nodes in $T_{1}$ and $T_{2}$,
respectively, not included in $M$. We can define a _cost of the mapping_ $M$
as

$\gamma(M)=\sum_{(v,w)\in M}\gamma(v\to w)+\sum_{v\in
N_{1}}\gamma(v\to\lambda)+\sum_{w\in N_{2}}\gamma(\lambda\to w).$ (7)

Following the proof in Zhang-Shasha-1989  we obtain the following relation
between mapping and sequence of edit operations.

###### Lemma 1

If $(M,T_{1},T_{2})$ is a mapping of edit sequence $S$ transforming $T_{1}$ to
$T_{2}$ then $\gamma(M)\leq\gamma(S)$. For any mapping $(M,T_{1},T_{2})$ there
exists an edit sequence such that $\gamma(S)=\gamma(M)$.

By combination of (5) and Lemma 1 we obtain that the minimum cost mapping is
equivalent to the edit distance

$d(T_{1},T_{2})=\min_{M}\\{\gamma(M)|\text{$(M,T_{1},T_{2})$ is an edit
distance mapping}\\}.$ (8)

##  IV Algorithm for calculating the minimum cost

We label an empty tree as $\Lambda$ and we define a function $\rho(T)$ which
returns a _root node_ of a tree $T$. Let us have a tree $A$ with a root
$a=\rho(A)$ and the rest of nodes divided into a set of $m\geq 0$ mutually
disjoint subtrees $\\{A_{1},\dots,A_{m}\\}$. Then we have the following
recursive rules evaluating the costs of creating or deleting $A$:

$\displaystyle d(\Lambda,\Lambda)$ $\displaystyle=0,$ (9) $\displaystyle
d(A,\Lambda)$
$\displaystyle=\sum_{i=1}^{m}d(A_{i},\Lambda)+\gamma(a,\lambda),$ (10)
$\displaystyle d(\Lambda,A)$
$\displaystyle=\gamma(\lambda,a)+\sum_{i=1}^{m}d(\Lambda,A_{i}).$ (11)

Let us also have a tree $B$ with $b=\rho(B)$ and set of $n\geq 0$ mutually
disjoint subtrees $\\{B_{1},\dots,B_{n}\\}$. We have:

  * •

If $\nu(a)\neq\nu(b)$ then

$d(A,B)=d(A,\Lambda)+d(\Lambda,B).$ (12)

  * •

If $\nu(a)=\nu(b)\land\nu(a)=\text{Value}$ then

$d(A,B)=\begin{cases}\gamma(a,b)\quad\text{if $\tau(a)=\tau(b)$,}\\\
\gamma(a,\lambda)+\gamma(\lambda,b)\quad\text{if
$\tau(a)\neq\tau(b)$}.\end{cases}$ (13)

  * •

If $\nu(a)=\nu(b)\land\nu(a)=\text{Object}$ then

$d(A,B)=\sum_{i=1}^{m}\sum_{j=1}^{n}d(A_{i},B_{j})\,\delta\left(l(a\dashrightarrow\rho(A_{i})),l(b\dashrightarrow\rho(B_{j}))\right)\\\
+\sum_{k\in\kappa(a)\setminus\kappa(b)}\sum_{i=1}^{m}d(A_{i},\Lambda)\,\delta\left(l(a\dashrightarrow\rho(A_{i})),k\right)\\\
+\sum_{k\in\kappa(b)\setminus\kappa(a)}\sum_{j=1}^{n}d(\Lambda,B_{j})\,\delta\left(l(b\dashrightarrow\rho(B_{j})),k\right).$
(14)

Here the Kroenecker $\delta$-function reads

$\delta(x,y)=\begin{cases}1\quad\text{if $x=y$,}\\\
0\quad\text{otherwise}.\end{cases}$ (15)

The first contribution in (14) is a sum of distances between subtrees
$d(A_{i},B_{j})$ which share the same edge label
$l(a\dashrightarrow\rho(A_{i}))$ and $l(b\dashrightarrow\rho(B_{j}))$,
respectively. The second contribution is a sum of deletion costs
$d(A_{i},\Lambda)$ of subtrees $A_{i}$ which do not have edge label
$l(a\dashrightarrow\rho(A_{i}))$ in $\kappa(b)$. Similarly, the third
contribution is a sum of insertion costs $d(\Lambda,B_{j})$ of subtrees
$B_{j}$ which do not have edge label $l(b\dashrightarrow\rho(B_{j}))$ in
$\kappa(a)$.

  * •

If $\nu(a)=\nu(b)\land\nu(a)=\text{Bag}$ then

$d(A,B)=\sum_{i,j=1}^{\max(m,n)}\mathcal{M}_{ij}\Delta_{ij}.$ (16)

Here $\Delta$ is a square matrix of distances with
$\text{rank}(\Delta)=\max(m,n)$ and elements

$\Delta_{ij}=\begin{cases}d(A_{i},B_{j})\quad\text{for $1\leq i\leq m$ and
$1\leq j\leq n$};\\\ d(A_{i},\Lambda)\quad\text{for $1\leq i\leq m$ and
$n<j\leq m$, if $m>n$};\\\ d(\Lambda,B_{j})\quad\text{for $m<i\leq n$ and
$1\leq j\leq n$, if $n>m$}.\end{cases}$ (17)

Matrix $\mathcal{M}$ is minimum cost mapping of $\Delta$ with elements
$\mathcal{M}_{ij}\in\\{0,1\\}$. The mapping can be found by application of,
e.g., HungarianKuhn-1955  or BlossomVKolmogorov-2009  algorithm.

An illustration of the edit distance calculation between two rooted labeled
trees is included in Appendix A.

###  IV.1 Proof of the minimum cost

Our aim is to prove that equations (12)-(14) and (16) calculate costs of the
minimum cost mapping $(M,A,B)$ and hence the edit distance $d(A,B)$ as defined
in (8). The situation $\nu(a)\neq\nu(b)$ implies not only that $(a,b)\notin M$
but consequently that $M=\emptyset$. The equation (12) is a direct application
of (7) to such case. The situation $\nu(a)=\nu(b)\land\nu(a)=\text{Value}$
leads to a mere evaluation of the difference of the particular Value nodes in
(13). The situation $\nu(a)=\nu(b)\land\nu(a)=\text{Object}$ is also
straightforward because all nodes $(\rho(A_{i}),\rho(B_{j}))$ that share the
same edge label
$l(a\dashrightarrow\rho(A_{i}))=l(b\dashrightarrow\rho(B_{j}))$ also belong to
the mapping $(\rho(A_{i}),\rho(B_{j}))\in M$. Again, the equation (14) is a
direct application of (7). The last situation
$\nu(a)=\nu(b)\land\nu(a)=\text{Bag}$ is resolved by calculating the cost
according to the found minimum cost mapping of subtrees
$\\{A_{1},\dots,A_{m}\\}\cup\\{\Lambda\\}$ to
$\\{B_{1},\dots,B_{n}\\}\cup\\{\Lambda\\}$. We conclude that the calculated
cost in each situation represents the cost of the minimum cost mapping and
thus is equal to the distance $d(A,B)$.

##  V Conclusion

In this work, we have developed an edit distance applicable to JSON samples
compatible with the HMIL framework. By HMIL compatibility we mean that all
elements of JSON Array data type are interpreted as unordered bags. The
distance between two JSON samples $J_{1}$ and $J_{2}$ is calculated first by
representing them as rooted labeled trees $T_{1}=\psi\circ\phi(J_{1})$ and
$T_{2}=\psi\circ\phi(J_{2})$ and then by applying formulas depicted in
(12)-(14) and (16) recursively.

The proposed edit distance is applicable to any task where exact evaluation of
the difference between hierarchically organized and HMIL compatible data is
needed. An example of the use case within the HMIL framework is to use this
edit distance to gain insight into the distribution of the training data. This
can help to adjust the sampling of the dataset so that a sufficient number of
samples is selected into the training of the HMIL model also from the weakly
populated regions of the dataset phase space.

## References

  * (1) R. A. Wagner and M. J. Fischer, “The string-to-string correction problem,” J. ACM, vol. 21, p. 168–173, Jan. 1974.
  * (2) P. Bille, “A survey on tree edit distance and related problems,” Theoretical Computer Science, vol. 337, pp. 217–239, 2005.
  * (3) D. B. Blumenthal, New Techniques for Graph Edit Distance Computation.  2019\.
  * (4) N. Augsten, M. Böhlen, and J. Gamper, “The pq-gram distance between ordered labeled trees,” ACM Trans. Database Syst., vol. 35, Feb. 2008.
  * (5) N. Augsten, M. Böhlen, C. Dyreson, and J. Gamper, “Approximate joins for data-centric xml,” pp. 814–823, 05 2008.
  * (6) T. Pevný and P. Somol, “Discriminative models for multi-instance problems with tree structure,” AISec 2016 - Proc. 2016 ACM Work. Artif. Intell. Secur. co-located with CCS 2016, 2016.
  * (7) Š. Mandlík and T. Pevný, “Mapping the internet: Modelling entity interactions in complex heterogeneous networks,” 2021.
  * (8) S. M. Selkow, “The tree-to-tree editing problem,” Inform. Process Lett., vol. 6, pp. 184–186, 1977.
  * (9) K. Zhang, R. Statman, and D. Shasha, “On the editing distance between unordered labeled trees,” Inform. Process Lett., vol. 42, pp. 133–139, 1992.
  * (10) K.-C. Tai, “The tree-to-tree correction problem,” J. ACM, vol. 26, pp. 422–433, 1979.
  * (11) K. Zhang and D. Shasha, “Simple fast algorithms for the editing distance between trees and related problems,” SIAM J. Comput., vol. 18, pp. 1245–1262, 1989.
  * (12) H. W. Kuhn, “The hungarian method for the assignment problem,” Naval Research Logistics Quarterly, vol. 2, no. 1‐2, pp. 83–97, 1955.
  * (13) V. Kolmogorov, “Blossom v: a new implementation of a minimum cost perfect matching algorithm,” Mathematical Programming Computation, vol. 1, no. 1, pp. 43–67, 2009.

##  Appendix A Example of the edit distance calculation

Let us now describe an example of the calculation of the edit distance between
two RLT structures $T_{1}$ and $T_{2}$ as defined by formula (8). Figure 3
captures the edit distance mapping $(M,T_{1},T_{2})$. For illustration
purposes, we define the cost of edit operations for two nodes $u$ and $v$ of
the same node type and data type (including the null node $\lambda$) to
$\gamma(u,v)=1$. For simplicity, all operations of the edit sequence $S$ are
depicted together in Figure 3. In this example, the edit sequence
$S=S_{1}\circ S_{2}\circ S_{3}$ may be divided into three sequences of related
edit operations:

  * •

Node relabel operation ($S_{1}$): Change of a String Value node label in
$T_{1}$ from value ”A” to ”B” in $T_{2}$. According to the equation (13), the
cost of this operation equals $\gamma($”A”,”B”$)=1$.

  * •

Bag node removal ($S_{2}$): Two Bag nodes (and all their child nodes) are
removed from $T_{1}$. In accordance with equation (10), this operation
consists of the edit sequence $S_{2}=s_{1}\circ s_{2}\circ\dots\circ s_{6}$
with operations $s_{1},\dots,s_{4}$ removing a Value node and $s_{5},s_{6}$
removing a leaf Bag node. For each removed node $v$ the total edit distance
increases by $\gamma(v,\lambda)=1$.

  * •

Insertion of an Object node with one child node ($S_{3}$): The edit distance
is increased by two, as described in equation (11). First, an Object node with
no children is inserted into $T_{1}$. Then, a Value node is inserted into the
recently added Object node. The edge labels $k_{8}$ and $k_{9}$ are arbitrary
in this case.

As a result, the edit distance between $T_{1}$ and $T_{2}$ equals
$d(T_{1},T_{2})=9$.

object/.style=circle, draw, anchor=center, bag/.style=diamond, draw,
anchor=center, valuenumber/.style=rectangle,draw, fill=colornumber,
anchor=center, valuestring/.style=rectangle,draw, fill=colorstring,
anchor=center, valueboolean/.style=rectangle,draw, fill=colorboolean,
anchor=center [,object, name=t1, for tree= l sep=2cm, s sep+=0.9em, grow=south
[x, valueboolean, edge label = node [midway,fill=white] $k_{1}$] [,object,
edge label = node [midway, fill=white] $k_{2}$ [A , valuestring, edge label =
node [midway, fill=white] $k_{5}$] [x, valuenumber, edge label = node [midway,
fill=white] $k_{6}$] [, object, edge label = node [midway, fill=white]
$k_{7}$]] [, bag, name=a1, edge label = node [midway, fill=white] $k_{3}$ [x,
valuenumber, name=a2] [x, valuenumber, name=a3] [x, valuenumber, name=a4] [x,
valuenumber, name=a5]] [, bag, name=a6, edge label = node [midway, fill=white]
$k_{4}$] ] [black,dashed] [ create hullcoords/.code= (hullcoord1) at (a1);
(hullcoord2) at (a6); (hullcoord3) at (a5); (hullcoord4) at (a2); (hullcoord0)
at (hullcoord4); (hullcoord5) at (hullcoord1); , create hullcoords ]
($(hullcoord1)!0.4cm!-90:(hullcoord0)$) let 1 =
($(hullcoord1)-(hullcoord0.0)$), 1 = atan2(1,1) + 90, 2 =
($(hullcoord2.0)-(hullcoord1)$), 2 = atan2(2,2) + 90, delta = Mod(2-1,360) -
360 in arc [start angle=1, delta angle=delta, radius=0.4cm] –
($(hullcoord2.0)!0.4cm!-90:(hullcoord1)$) let 1 =
($(hullcoord2)-(hullcoord1.0)$), 1 = atan2(1,1) + 90, 2 =
($(hullcoord3.0)-(hullcoord2)$), 2 = atan2(2,2) + 90, delta = Mod(2-1,360) -
360 in arc [start angle=1, delta angle=delta, radius=0.4cm] –
($(hullcoord3.0)!0.4cm!-90:(hullcoord2)$) let 1 =
($(hullcoord3)-(hullcoord2.0)$), 1 = atan2(1,1) + 90, 2 =
($(hullcoord4.0)-(hullcoord3)$), 2 = atan2(2,2) + 90, delta = Mod(2-1,360) -
360 in arc [start angle=1, delta angle=delta, radius=0.4cm] –
($(hullcoord4.0)!0.4cm!-90:(hullcoord3)$) let 1 =
($(hullcoord4)-(hullcoord3.0)$), 1 = atan2(1,1) + 90, 2 =
($(hullcoord5.0)-(hullcoord4)$), 2 = atan2(2,2) + 90, delta = Mod(2-1,360) -
360 in arc [start angle=1, delta angle=delta, radius=0.4cm] –
($(hullcoord5.0)!0.4cm!-90:(hullcoord4)$) ; [right=0.4cm of a6] removal;
[left=0.5cm of t1] $T_{1}$; object/.style=circle, draw, anchor=center,
bag/.style=diamond, draw, anchor=center, valuenumber/.style=rectangle,draw,
fill=colornumber, anchor=center, valuestring/.style=rectangle,draw,
fill=colorstring, anchor=center, valueboolean/.style=rectangle,draw,
fill=colorboolean, anchor=center [,object, name=t2, for tree= l sep=2cm, s
sep+=0.9em, grow=south [x, valueboolean, edge label = node [midway,fill=white]
$k_{1}$] [,object, edge label = node [midway, fill=white] $k_{2}$ [B ,
valuestring, edge label = node [midway, fill=white] $k_{5}$] [x, valuenumber,
edge label = node [midway, fill=white] $k_{6}$] [, object, edge label = node
[midway, fill=white] $k_{7}$]] [, object, name=b1, edge label = node [midway,
fill=white] $k_{8}$ [x, valuenumber, name=b2, edge label=node [midway,
fill=white] $k_{9}$]] ] [black,dashed] [ create hullcoords/.code= (hullcoord1)
at (b1); (hullcoord2) at (b2); (hullcoord0) at (hullcoord2); (hullcoord3) at
(hullcoord1); , create hullcoords ] ($(hullcoord1)!0.4cm!-90:(hullcoord0)$)
let 1 = ($(hullcoord1)-(hullcoord0.0)$), 1 = atan2(1,1) + 90, 2 =
($(hullcoord2.0)-(hullcoord1)$), 2 = atan2(2,2) + 90, delta = Mod(2-1,360) -
360 in arc [start angle=1, delta angle=delta, radius=0.4cm] –
($(hullcoord2.0)!0.4cm!-90:(hullcoord1)$) let 1 =
($(hullcoord2)-(hullcoord1.0)$), 1 = atan2(1,1) + 90, 2 =
($(hullcoord3.0)-(hullcoord2)$), 2 = atan2(2,2) + 90, delta = Mod(2-1,360) -
360 in arc [start angle=1, delta angle=delta, radius=0.4cm] –
($(hullcoord3.0)!0.4cm!-90:(hullcoord2)$) ; [left=0.15 of b1] addition;
[left=0.5cm of t2] $T_{2}$;

value change

Figure 3: Tree edit distance mapping $(M,T_{1},T_{2})$. Dashed lines represent
edit operations. The color and shape of a node represents the node data type
and node type respectively as shown in Figure 1.


# Large deviation principle of Multiplicative Ising models on Markov-Cayley
Trees

Jung-Chao Ban  Department of Mathematical Sciences, National Chengchi
University, Taipei 11605, Taiwan, ROC.  Math. Division, National Center for
Theoretical Science, National Taiwan University, Taipei 10617, Taiwan. ROC.
<EMAIL_ADDRESS>,  Wen-Guei Hu  College of Mathematics, Sichuan University,
Chengdu, 610065, China<EMAIL_ADDRESS>and  Zongfan Zhang  College of
Mathematics, Sichuan University, Chengdu, 610065, China
<EMAIL_ADDRESS>
###### Abstract.

In this paper, we study the large deviation principle (LDP) for two types
(Type I and Type II) of multiplicative Ising models. For Types I and II, the
explicit formulas for the free energy functions and the associated rate
functions are derived. Furthermore, we prove that those free energy functions
are differentiable, which indicates that both systems are characterized by a
lack of phase transition phenomena.

###### Key words and phrases:

Large deviation principle, Free energy, Multiplicative Ising models

Ban is partially supported by the National Science and Technology Council, ROC
(Contract NSTC 111-2115-M-004-005-MY3). Hu is partially supported by the
National Natural Science Foundation of China (Grant No.12271381).

##  1\. Introduction

In this article, we study the large deviation principle (LDP) for the lattice
spin systems with Ising $\pm 1$ spins on a Markov-Cayley tree $\mathcal{T}$
(defined later). Before presenting the main findings, below is an explanation
of the motivation behind this study. The _large deviation principle_ , broadly
speaking, is premised on the understanding that the asymptotic behavior of
probabilities $\mathbb{P}\\{\frac{1}{N}S_{N}\in\Gamma\\}$ as
$N\rightarrow\infty$, where $\Gamma\subseteq\mathbb{R}$ and $\frac{1}{N}S_{N}$
is an ergodic average. The LDP problem for the standard average
$\frac{1}{N}S_{N}=\frac{1}{N}\sum_{i=1}^{N}X_{i}$, where
$\\{X_{i}\\}_{i=1}^{\infty}$ is a sequence of i.i.d. random variables or
driven by a dynamical system, has been thoroughly investigated, with the best
general references being [14, 15].

Motivated by the multiple ergodic theory ([2, 18, 19, 20]) or nonconventional
ergodic theory111The term ‘nonconventional’ was introduced in [17], and now is
standard in ergodic theory. (cf.[17, 23, 24, 25, 26]), the LDP for the
multiple ergodic average can be framed in the following terms. Let
$(X,\mathcal{B},\mu)$ be a probability space, $T_{1},\ldots,T_{l}:X\rightarrow
X$ be commuting, invertible measure preserving transformations,
$f_{1},\ldots,f_{l}\in L^{\infty}(\mu)$ and
$p_{1},\ldots,p_{l}\in\mathbb{Z}[t]$, such that the _nonconventional averages_
involves considering the multiple ergodic average

(1.1)
$\frac{1}{N}S_{N}(x)=\frac{1}{N}\sum_{i=1}^{N}f_{1}(T_{1}^{p_{1}(i)}x)\cdots
f_{l}(T_{l}^{p_{l}(i)}x)\text{,}$

or more broadly,

(1.2)
$\frac{1}{N}S_{N}(x)=\frac{1}{N}\sum_{i=1}^{N}\Phi(T_{1}^{p_{1}(i)}x,\ldots,T_{l}^{p_{l}(i)}x),$

where $\Phi:X^{l}\rightarrow\mathbb{R}$. It is important to note that
characterizing the convergence (norm, almost everywhere) of (1.1) or (1.2) is
extremely challenging (cf.[1, 11, 16, 22, 26]).

Kifer [23, 24] and Kifer-Varadhan [25] initially considered the LDP problem
for the multiple ergodic averages of the form

$\frac{1}{N}\sum_{i=1}^{N}F\left(X(q_{1}(i)),\ldots,X(q_{l}(i))\right)\text{,}$

where $X(i)$, $i\geq 0$ is a Markov process satisfying Doeblin’s condition,
and $F$ is a locally Hölder continuous function with polynomial growth. Later,
Carinci et al. [12] addressed the LDP problem for the multiple average along
arithmetic progressions below on $\mathbb{N}$.

$\frac{1}{N}S_{N}(\\{X_{i}\\})=\frac{1}{N}\sum_{i=1}^{N}f_{1}(X_{i})f_{2}(X_{2i})\cdots
f_{l}(X_{li})$

and especially on the average, is of the form (1.4). In [12], the _rate
function_ associated with the multiple ergodic average $S_{N}/N$ (1.4) is
defined by

(1.3) $I_{r}(x)=\lim_{\epsilon\rightarrow
0}\lim_{N\rightarrow\infty}-\frac{1}{N}\log\mathbb{P}_{r}\left(\frac{S_{N}}{N}\rightarrow[x-\epsilon,x+\epsilon]\right)\text{.}$

The authors prove that (1.3) exists and satisfies the _Fenchel-Legendre
transform_ of the free energy function as follows:

$I_{r}(x)=\sup_{\beta\in\mathbb{R}}\left\\{\beta
x-F_{r}(\beta)\right\\}\text{,}$

where $F_{r}(\beta)$ is the _free energy function_ defined in (1.5). If
$F_{r}(\beta)$ is differentiable, say $F_{r}^{\prime}(\eta)=y$, the rate
function can be clearly demonstrated as $I_{r}(y)=\eta y-F_{r}(\eta)$.
Therefore, the explicit formula for the free energy function is significant
for the rate function of the LDP problem.

Let $\mathcal{A}=\\{+1,-1\\}$ and $\mathbb{P}_{p}$ be the product of Bernoulli
with parameter $p$ on $\mathcal{A}$. For $\sigma\in\mathcal{A}^{\mathbb{Z}}$,
the authors [13] investigate the thermodynamic limit of the _free energy
function_ associated with the multiple ergodic average

(1.4)
$\frac{1}{N}S_{N}(\sigma)=\frac{1}{N}\sum_{i=1}^{N}\sigma_{i}\sigma_{2i},$

defined as

(1.5)
$F_{r}(\beta)=\lim_{N\rightarrow\infty}\frac{1}{N}\log\mathbb{E}_{r}\left(e^{\beta
S_{N}}\right)\text{.}$

If we consider the multiple ergodic sum $S_{N}$ (1.4) as a Hamiltonian and the
parameter $\beta$ as the ‘inverse temperature’ in the lattice spin system
$\mathcal{A}^{\mathbb{Z}}$, this is the simplest version of the
_multiplicative Ising model_ defined in [13]. In contrast to the Hamiltonian
of the standard Ising model222The Hamiltonian is of the form
$S_{N}(\sigma)=\sum_{i=1}^{N}\sigma_{i}\sigma_{i+1}$., such an interaction is
much harder to process because it fails to be translation-invariant and is a
long-range interaction (cf. [12, 13]). The thermodynamic limit, entropy and
existence of the Gibbs measure with respect to multiple ergodic averages
$S_{N}(\sigma)/N$ are shown in [13].

A natural question arises: can we extend the above-mentioned LDP result to a
multidimensional multiplicative Ising model? The question is interesting since
multidimensional Ising models reveal rich and different phenomena on the
thermodynamic limit and phase transition problems, compared to one-dimensional
ones (cf.[14, 21]). Recently, the LDP and explicit formula of the free energy
function for the multiple ergodic average have been extended to
$\mathbb{N}^{d}$, $d\geq 2$ [7], and the main purpose of this paper is to
establish the LDP for a multiplicative Ising model on a general tree
$\mathcal{T}$. We stress that although $\mathbb{N}^{d}$ and $\mathcal{T}$ are
both multidimensional lattices, the methods of establishing the LDP for those
lattices are quite different. The reason is that the concept of ‘amenability’
is not true anymore for $\mathcal{T}$, that is,
$\left|\mathcal{T}_{n}\right|/\left|\Delta_{n}\right|$ does not tend to $0$ as
$n\rightarrow\infty$, where $\Delta_{n}$ (resp. $\mathcal{T}_{n}$) is the set
of all vertices of $\mathcal{T}$ with distance from the root being at most $n$
(resp. $=n$), and $\left|A\right|$ stands for the cardinality of the set $A$.

Let $\mathcal{T}$ be a _Markov-Cayley tree_. Precisely, if we write
$\mathcal{T}$ as a countable graph with a root $\epsilon$ and without loops,
there exists an alphabet $\Sigma=\\{1,\ldots,d\\}$, such that the set of the
vertices of $\mathcal{T}_{n}\subseteq\Sigma^{n}$ can be identified as the
‘admissible $n$-words’ with respect to an _adjacency matrix_ $M$, that is,

$\mathcal{T}_{n}=\left\\{(x_{1},\ldots,x_{n})\in\Sigma^{n}:M(x_{i},x_{i+1})=1\text{
for }i=1,\ldots,n-1\right\\}\text{.}$

For instance, the adjacency matrix for the conventional $d$-tree is a full
$d\times d$ matrix over $\\{0,1\\}$. In this paper, we focus on the broad
class of trees, namely, the Markov-Cayley trees that satisfy the following
property:

(1.6)
$\lim_{n\rightarrow\infty}\frac{\left|\mathcal{T}_{n+1}\right|}{\left|\mathcal{T}_{n}\right|}=\gamma>1\text{.}$

This indicates that the vertices of the $n$-levels of $\mathcal{T}$ increase
exponentially. When $M$ is a square matrix, we denote by $\left\|M\right\|$
the matrix norm of $M$, i.e., $\left\|M\right\|=\mathbf{1}^{t}M\mathbf{1},$
$\mathbf{1}=(1,1,\ldots,1)^{t}$. Since
$\left|\mathcal{T}_{n}\right|=\left\|M^{n-1}\right\|$, $n\geq 2$ for a Markov-
Cayley tree $\mathcal{T}$, the condition (1.6) is equivalent to

(1.7)
$\lim_{n\rightarrow\infty}\frac{\left\|M^{n+1}\right\|}{\left\|M^{n}\right\|}=\gamma>1\text{.}$

Hence, we assume that $\mathcal{T}$ is a Markov-Cayley tree that satisfies
(1.7) in what follows. It should be pointed out that condition (1.6) is a
general condition if T is not a Markov-Cayley tree. We emphasize that the
dynamics of the shift on a tree $\mathcal{T}$ (called _tree-shift_) are quite
interesting and have attracted a lot of attention recently (cf.[3, 4, 5, 6, 8,
9, 27, 28]).

In this article, we consider a larger category of the (nonconventional)
ergodic sums as well, namely,
$S_{N}^{\bigstar}=\sum_{i=1}^{N}\sigma_{i}\sigma_{ia(i)}$, where
$\\{a(i)\\}_{i\geq 1}\subseteq\mathbb{N}$ with $a(i)\geq 2$ $\forall i\geq 1$.
Let $\mathbb{P}_{p}$ be the product of Bernoulli with the parameter $p$ on
$\mathcal{A}=\\{+1,-1\\}$, we define the associated _free energy function_ as
follows:

(1.8)
$F_{p}(\beta)=\limsup\limits_{N\rightarrow\infty}\frac{\log\mathbb{E}_{p}(e^{\beta
S_{N}^{\bigstar}})}{\left|\Delta_{Na(N)-1}\right|}\text{,}$

and the _large deviation rate function_ of the multiple average
$S_{N}^{\bigstar}/\left|\Delta_{Na(N)-1}\right|$ on tree $\Delta_{Na(N)-1}$ is
defined as

(1.9) $I_{p}(x)=\lim_{\epsilon\rightarrow
0}\lim_{N\rightarrow\infty}-\frac{1}{\left|\Delta_{Na(N)-1}\right|}\log\mathbb{P}_{p}\left(\frac{S_{N}^{\bigstar}}{\left|\Delta_{Na(N)-1}\right|}\in[x-\epsilon,x+\epsilon]\right)\text{.}$

In view of $S_{N}^{\bigstar}$, we deal with the following two types:

I. Let $a(i)=i$ for all $i\geq 1$. In this circumstance, the ergodic sum is of
the form

$S_{N}^{\\#}=\sum_{i=1}^{N}\sigma_{i}\sigma_{i^{2}},$

and here we remark that $a(1)=1$ is allowed and let $\sigma_{1}\sigma_{1}=1$.
The corresponding multiple average is
$S_{N}^{\\#}/\left|\Delta_{N^{2}-1}\right|$.

II. Let $a(i)=q$ $\forall i\geq 1$ and $2\leq q\in\mathbb{N}$, the ergodic sum
is of the form

$S_{N}^{(q)}=\sum_{i=1}^{N}\sigma_{i}\sigma_{qi}$

with the average $S_{N}^{(q)}/\left|\Delta_{qN-1}\right|$.

For Type I, we have the following results.

######  Theorem 1.1 (LDP for Type I).

The following assertions hold true.

  1. (1)

The explicit formula of the free energy function corresponding to the sum
$S_{N}^{\\#}$ is

$F_{p}(\beta)=\frac{\gamma-1}{\gamma}\log\left[pe^{\beta}+(1-p)e^{-\beta}\right]+\mathcal{G}_{\\#}(\beta)\text{,}$

where $\mathcal{G}_{\\#}(\beta)$ is defined in (3.10).

  2. (2)

The function $\beta\rightarrow F_{p}(\beta)$ is differentiable.

  3. (3)

The multiple average $S_{N}^{\\#}/\left|\Delta_{N^{2}-1}\right|$ satisfies a
large deviation principle with the rate function

$I_{p}(x)=\sup_{\beta\in\mathbb{R}}(\beta x-F_{p}(\beta))\text{.}$

Moreover, if $\left(F_{p}\right)^{\prime}(\eta)=y$, then $I_{p}(y)=\eta
y-F_{p}(\eta)$.

We note that if $p=\frac{1}{2}$, it can be easily computed that
$\mathcal{G}_{\\#}(\beta)=0$ and

(1.10)
$F_{\frac{1}{2}}(\beta)=\frac{\gamma-1}{\gamma}\log\left[\frac{1}{2}\left(e^{\beta}+e^{-\beta}\right)\right].$

Meanwhile, the rate function can be computed rigorously as

$I_{\frac{1}{2}}(y)=\frac{\gamma-1}{\gamma}\left(\eta\frac{e^{\eta}-e^{-\eta}}{e^{\eta}+e^{-\eta}}-\log\frac{e^{\eta}+e^{-\eta}}{2}\right)\
\text{with}\ \
y=\frac{\gamma-1}{\gamma}\cdot\frac{e^{\eta}-e^{-\eta}}{e^{\eta}+e^{-\eta}}.$

In particular, if $a(i)=i^{\alpha-1}$ for any $i\geq 1$ and a given integer
$\alpha\geq 2$, the sum
$S_{N}^{\\#}(\alpha)=\sum_{i=1}^{N}\sigma_{i}\sigma_{i^{\alpha}}$ is the
generalized case of $S_{N}^{\\#}$, and Corollary 1.2 below demonstrates that
the free energy function $F_{p}(\beta)$ is a constant function for all
$\alpha\geq 2$ and $p=1/2$.

######  Corollary 1.2.

For $p=1/2$, the free energy function of $F_{p}(\beta)$ with respect to the
ergodic sum $S_{N}^{\\#}(\alpha)$ equals (1.10) for all $\alpha\geq 2$.

For Type II, we have the following results.

######  Theorem 1.3 (LDP for Type II).

The following assertions hold true.

  1. (1)

The free energy function corresponding to the sum $S_{N}^{(q)}$ is

$F_{p}(\beta)=\frac{\gamma^{q-1}\left(\gamma-1\right)}{\gamma^{q}-1}\log\left[pe^{\beta}+(1-p)e^{-\beta}\right]+\mathcal{G}_{q}(\beta)\text{,}$

where $\mathcal{G}_{q}(\beta)$ is given by (4.4).

  2. (2)

The function $\beta\rightarrow F_{p}(\beta)$ is differentiable.

  3. (3)

The multiple average $S_{N}^{(q)}/\left|\Delta_{qN-1}\right|$ defined on
$\mathcal{T}$ satisfies a large deviation principle with the rate function

$I_{p}(x)=\sup_{\beta\in\mathbb{R}}(\beta x-F_{p}(\beta))\text{.}$

Moreover, if $\left(F_{p}\right)^{\prime}(\eta)=y$, then $I_{p}(y)=\eta
y-F_{p}(\eta)$.

We remark that if $p=\frac{1}{2}$, it can be easily seen that
$\mathcal{G}_{q}(\beta)=0$ and

$F_{\frac{1}{2}}(\beta)=\frac{\gamma^{q-1}\left(\gamma-1\right)}{\gamma^{q}-1}\log\left[\frac{1}{2}\left(e^{\beta}+e^{-\beta}\right)\right]\text{.}$

Thus, the rate function is

$I_{\frac{1}{2}}(y)=\frac{\gamma^{q-1}\left(\gamma-1\right)}{\gamma^{q}-1}\left(\eta\frac{e^{\eta}-e^{-\eta}}{e^{\eta}+e^{-\eta}}-\log\frac{e^{\eta}+e^{-\eta}}{2}\right)\text{,}$

where

$y=\frac{\gamma^{q-1}\left(\gamma-1\right)}{\gamma^{q}-1}\left(\frac{e^{\eta}-e^{-\eta}}{e^{\eta}+e^{-\eta}}\right)\text{.}$

For $q=2$, the Ising sum $S_{N}^{(2)}$ is considered as follows when
$\mathcal{T}$ is a $d$-tree or the golden-mean tree (defined in Section 2).
The formula for $F_{p}(\beta)$ and $\mathcal{G}_{2}(\beta)$ can be computed
explicitly.

######  Example 1.4.

The following assertions hold true.

1. For $d\geq 2$, let $\mathcal{T}$ be a conventional $d$-tree, then the matrix $M$ is the full matrix. This means that $R(k+1,j)=d^{k}$ and $C(k-1,j)=d^{k-2}$ (which are defined in Section 2 and represent the row sum and column sum, respectively) for all $k\geq 1$ and $1\leq j\leq d$. From Theorem 1.3, the free energy function associated with the sum $S_{N}^{(2)}$ is given by

$F_{p}(\beta)=\frac{d}{d+1}\log\left[pe^{\beta}+(1-p)e^{-\beta}\right]+\mathcal{G}_{2}(\beta)$

with

$\mathcal{G}_{2}(\beta)=\limsup_{N\to\infty}\frac{d-1}{d}\\!\sum_{k=\lfloor\\!N/2\rfloor\\!+\\!1}^{N}\frac{1}{d^{2N\\!-k}}\log\left[1+\frac{1\\!-\\!p}{p}\left(\frac{(1\\!-\\!p)e^{\beta}+pe^{-\beta}}{pe^{\beta}+(1\\!-\\!p)e^{-\beta}}\right)^{d^{k}}\right].$

2. Suppose that $\mathcal{T}$ is the golden-mean tree, then it satisfies $\gamma=\frac{\sqrt{5}+1}{2}$ and the associated transition matrix $M$ whose rows are $11$, $10$. Then we have $R(k\\!+\\!1,j)=(M^{k})_{j,1}+(M^{k})_{j,2}$ and $C(k\\!-\\!1,j)=(M^{k-2})_{1,j}+(M^{k-2})_{2,j}$ for all $k\geq 1$ and $j=1,2$. According to Theorem 1.3, the free energy function related to the sum $S_{N}^{(2)}$ is obtained as

$F_{p}(\beta)=\frac{\sqrt{5}-1}{2}\log\left[pe^{\beta}+(1-p)e^{-\beta}\right]+\mathcal{G}_{2}(\beta),$

where

$\mathcal{G}_{2}(\beta)=\limsup_{N\to\infty}\sum_{k=\lfloor\\!N/2\rfloor+1}^{N}\sum_{j=1}^{2}\frac{C(k\\!-\\!1,j)}{|\Delta_{2N-1}|}\log\left(1+\frac{E_{j}^{-}}{E_{j}^{+}}\right).$

These results are far from conclusive, and we end this section by pointing out
the following problem.

######  Problem 1.5.

Is it possible to address the LDP problem for a multiplicative Ising model on
a Markov-Cayley tree $\mathcal{T}$ with respect to the multiple ergodic
average

$\frac{1}{N}S_{N}(\sigma)=\frac{1}{N}\sum_{n=1}^{N}\sigma_{a(n)}\sigma_{b(n)},$

where $a(n)=pn+c$ and $b(n)=qn+d$, where $\gcd(p,q)=1$ and $c,b\in\mathbb{Z}$?

##  2\. Preliminaries

Let $\mathcal{T}$ be the tree, as it can be also viewed as the set of all
finite words on a finite alphabet $\Sigma$. Every word $u$ on $\Sigma$
corresponds to a vertex of $\mathcal{T}$, with the empty word $\epsilon$
corresponding to the root. Given $\nu\in\mathcal{T}$, we define the length of
the unique path from $\epsilon$ to $\nu$ as $|\nu|$. Then, for each $n\geq 0$
the set of vertices of the $n$-th level of $\mathcal{T}$ is denoted by
$\mathcal{T}_{n}=\left\\{\nu\in\mathcal{T}:|\nu|=n\right\\}$ and the $n$-th
subtree of $\mathcal{T}$ is defined by
$\Delta_{n}=\bigcup_{i=0}^{n}\mathcal{T}_{i}$, which implies all vertices in
$\Delta_{n}$ whose distance from $\epsilon$ is at most $n$. Given a vertex
$\nu\in\mathcal{T}$, denote by $e(\nu)$ the number of edges of $\nu$. For
$d\geq 2$, a tree $\mathcal{T}$ is called the $d$-tree if $e(\epsilon)=d$ and
$e(\nu)=d+1$ for all $\nu\neq\epsilon$. Then it can be checked that
$|\Delta_{n}|=1+d+\cdots+d^{n}$ for the $d$-tree.

Let $\Sigma=\\{1,2,\cdots,d\\}$ and $M=[m_{i,j}]$ be a $d\times d$ essential
0-1 transition matrix. A matrix is _essential_ if it has no zero rows and zero
columns. Denote by $\Sigma^{*}_{M}$ the collection of all finite words
generated by $M$ together with the empty word $\epsilon$. Then the Markov-
Cayley tree is defined as $\mathcal{T}=\Sigma^{*}_{M}$, which implies that
each node of $\mathcal{T}$ is a finite word in $\Sigma^{*}_{M}$. And we have
$|\mathcal{T}_{1}|=d$ and $|\mathcal{T}_{n}|=\|M^{n-1}\|$ for $n\geq 2$. It is
clear to see that

$|\Delta_{n}|=1+d+\sum_{j=2}^{n}\left\|M^{j-1}\right\|.$

For example, if we consider $\Sigma=\\{1,2\\}$ and the matrix
$M=\begin{bmatrix}1&1\\\ 1&0\end{bmatrix}$, the collection of finite words
corresponding to $M$ with the empty word $\epsilon$ can be obtained as
$\Sigma^{*}_{M}=\\{\epsilon,1,2,11,12,21,111,112,121,211,212,\cdots\\}$, as
shown in Figure 1. Clearly, the golden-mean tree is also an expandable tree
with $\gamma=\frac{\sqrt{5}+1}{2}$. However, there are trees that are not
Markov-Cayley, but they meet the condition (1.6), e.g. the exploding tree in
[10].

Figure 1. Golden-mean tree.

Let $\mathcal{T}=\Sigma_{M}^{*}$, where $M$ is a $d\times d$ essential binary
matrix. For $k\geq 2$ and $1\leq i\leq d$, the number of nodes (i.e. finite
words) beginning with ‘$i$’ on the $k$-th level of $\mathcal{T}$ is equal to
the _row sum_

$R(k,i)=\sum_{j=1}^{d}(M^{k-1})_{i,j}$

of the matrix $M^{k-1}$. Similarly, for $1\leq j\leq d$ the number of nodes
(i.e. finite words) ending with ‘$j$’ on the $k$-th level of $\mathcal{T}$ is
equal to the _column sum_

$C(k,j)=\sum_{i=1}^{d}(M^{k-1})_{i,j}$

of the matrix $M^{k-1}$. Notably, the row sum $R(k,i)$ is essentially the
number of nodes (i.e. finite words which have length $k$) formed by the symbol
‘$i$’ through $k-1$ steps from the first level to the $k$-th level on
$\mathcal{T}$. In other words, $R(k,i)$ is also the number of paths formed by
this symbol ‘$i$’ from the $1$-st level to the $k$-th level on $\mathcal{T}$.

In the following, we consider spin systems with Ising $\pm 1$ spins on a
Markov-Cayley tree $\mathcal{T}$. Let $\mathbb{P}_{p}$ be the product of
Bernoulli with the parameter $p$ on two symbols $\mathcal{A}=\\{+1,-1\\}$. A
_configuration_ $\sigma$ is an element of the space
$\mathcal{A}^{\mathcal{T}}$. We study the _ergodic sum_
$S_{N}^{\bigstar}=\sum_{i=1}^{N}\sigma_{i}\sigma_{ia(i)}$ defined on
$\mathcal{T}$ as the “Hamiltonian”, where $\\{a(i)\\}_{i=1}^{\infty}$ is an
integer sequence with $a(i)\geq 2$ and $\sigma_{i}\in\mathcal{T}_{i-1}$ for
all $i\geq 1$. The following theorem shows the connection between the rate
function and the free energy function.

######  Theorem 2.1.

(Gärtner-Ellis theorem [14]) If the limit (1.8) exists and such limit is
finite in a neighborhood of origin, then the rate function (1.9) is equal to
the Fenchel-Legendre transform of (1.8), namely

$I_{p}(x)=\sup_{\beta\in\mathbb{R}}\left(\beta x-F_{p}(\beta)\right).$

Furthermore, if $F_{p}(\beta)$ is a differentiable function, written as
$(F_{p})^{\prime}(\eta)=y$, then we have

$I_{p}(y)=\eta y-F_{p}(\eta).$

The rest of this paper is devoted to proofs of Theorems 1.1 and 1.3.

##  3\. Proof of Theorem 1.1

In this section, we deal with the LDP problem of Type I on a Markov-Cayley
tree $\mathcal{T}$. The multiplicative Ising model
$S_{N}^{\\#}=\sum_{i=1}^{N}\sigma_{i}\sigma_{i^{2}}$ defined on $\mathcal{T}$
will be considered. Denote by
$\mathcal{D}_{\text{I}}=\\{-1,1\\}^{\Delta_{N^{2}-1}}$ the subspace. Then, the
partition function of $S_{N}^{\\#}$ is represented by

$Z(\beta)=\sum_{\sigma\in\mathcal{D}_{\text{I}}}\exp\\!\left\\{\beta\sum_{i=1}^{N}\sigma_{i}\sigma_{i^{2}}\right\\}$

with coupling strength $\beta$ and free boundary conditions. Proposition 3.1
below demonstrates how the free energy function is affected by the tree
structure.

######  Proposition 3.1.

The free energy function of the sum $S_{N}^{\\#}$ defined on a Markov-Cayley
tree that satisfies (1.7) is rewritten as

$\mathcal{F}_{p}(\beta)=\limsup_{N\to\infty}\frac{1}{|\Delta_{N^{2}-1}|}\log\mathbb{E}_{p}\left(\exp\\!\left\\{\beta\\!\sum_{i=\lfloor\sqrt{N}\rfloor\\!+\\!1}^{N}\\!\sigma_{i}\sigma_{i^{2}}\right\\}\right).$

###### Proof.

Without loss of generality, we assume $\beta>0$. Divide the sum $S_{N}^{\\#}$
into the following two parts

$S_{N,1}^{\\#}=\sum_{i=1}^{\lfloor\sqrt{N}\rfloor}\sigma_{i}\sigma_{i^{2}}\ \
\text{and}\ \
S_{N,2}^{\\#}=\sum_{i=\lfloor\sqrt{N}\rfloor+1}^{N}\sigma_{i}\sigma_{i^{2}}.$

Then we have

$Z(\beta)=\sum_{\sigma\in\mathcal{D}_{\text{I}}}\exp\\!\left\\{\beta(S_{N,1}^{\\#}+S_{N,2}^{\\#})\right\\}=\sum_{\sigma\in\mathcal{D}_{\text{I}}}\exp\\!\left\\{\beta
S_{N,1}^{\\#}\right\\}\cdot\exp\\!\left\\{\beta S_{N,2}^{\\#}\right\\}.$

Based on the decomposition above, one labels every node of the subtree
$\Delta_{\lfloor\sqrt{N}\rfloor^{2}-1}$ with symbol ‘$+1$’. Thus, the upper
bound of $S_{N,1}^{\\#}$ can be obtained as

(3.1)
$\max\\!\left(S_{N,1}^{\\#}\right)=\sum_{i=1}^{\lfloor\sqrt{N}\rfloor}|\mathcal{T}_{i^{2}-1}|=1+\sum_{i=2}^{\lfloor\sqrt{N}\rfloor}\|M^{i^{2}-2}\|$

(this is not the only way to reach the upper bound). Since the symbols
‘$+1,-1$’ are arbitrary, it follows $-\max(S_{N,1}^{\\#})\leq
S_{N,1}^{\\#}\leq\max(S_{N,1}^{\\#})$. This implies

(3.2)
$\sum_{\sigma\in\mathcal{D}_{\text{I}}}\frac{1}{M(\beta)}\exp\\!\left\\{\beta
S_{N,2}^{\\#}\right\\}\leq
Z(\beta)\leq\sum_{\sigma\in\mathcal{D}_{\text{I}}}M(\beta)\exp\\!\left\\{\beta
S_{N,2}^{\\#}\right\\},$

where $M(\beta)=\exp\\!\left\\{\beta\max(S_{N,1}^{\\#})\right\\}$. On the
other hand, there exist non-negative integers $a_{1},a_{2},b_{1},b_{2}$
satisfying $a_{1}+b_{1}=|\Delta_{\lfloor\sqrt{N}\rfloor^{2}-1}|$ and
$a_{2}+b_{2}=|\Delta_{\lfloor\sqrt{N}\rfloor^{2}-1}|$ such that

(3.3)
$p^{a_{1}}(1-p)^{b_{1}}\frac{1}{M(\beta)}\leq\mathbb{E}_{p}\left(\exp\\{\beta
S_{N,1}^{\\#}\\}\right)\leq p^{a_{2}}(1-p)^{b_{2}}M(\beta).$

Using (1.7) and (3.1), we easily see that

(3.4)
$\limsup_{N\to\infty}\frac{1}{|\Delta_{N^{2}-1}|}\log\mathbb{E}_{p}\left(\exp\\{\beta
S_{N,1}^{\\#}\\}\right)=0.$

Hence, combining (1.8) and (3.4), one gets

$\mathcal{F}_{p}(\beta)=\limsup_{N\to\infty}\frac{\log\mathbb{E}_{p}\left(\exp\\{\beta
S_{N,2}^{\\#}\\}\right)}{|\Delta_{N^{2}-1}|}.$

The proof is complete. ∎

The next two lemmas are crucial to the proof of Theorem 1.1.

######  Lemma 3.2.

For $k\geq 3$ and $1\leq j\leq d$, the number of nodes (i.e. finite words)
ending with ‘$j$’ on the corresponding $(k-1)$-th level of a Markov-Cayley
tree is

(3.5) $C(k-1,j)=\sum_{\ell=1}^{d}(M^{k-2})_{\ell,j}.$

###### Proof.

The result is clear from the definition of the column sum, so we omit its
proof. ∎

######  Lemma 3.3.

For $k\geq 3$ and $1\leq j\leq d$, under the action of the Ising sum
$S_{N}^{\\#}$, each node (i.e. finite word) ending with ‘$j$’ on the
corresponding $(k-1)$-th level of a Markov-Cayley tree generates Ising
potentials with

(3.6) $R\left(k^{2}-k+1,j\right)=\sum_{m=1}^{d}(M^{(k-1)k})_{j,m}$

vertices on the $(k^{2}-1)$-th level of the Markov-Cayley tree.

###### Proof.

A notable fact is that if two spins can generate an Ising potential on trees,
they are on the same path. Thus, the Ising model of Type I implies that for
$k\geq 3$ and $1\leq j\leq d$, we only need to find out how many paths a node
ending with ‘$j$’ on the $(k-1)$-th level will generate on the $(k^{2}-1)$-th
level. To accomplish this aim, we view this node ending with ‘$j$’ as a new
node (which has length $1$ ) beginning with ‘$j$’. By this means, we obtain a
solution for how many paths the symbol ‘$j$’ on the $1$-th level will generate
on the $(k^{2}-k+1)$-th level. By the significance of the row sum on Markov-
Cayley trees, the symbol ‘$j$’ on the $1$-th level will generate
$R(k^{2}-k+1,j)$ paths on the $(k^{2}-k+1)$-th level. This finishes the proof.
∎

######  Remark 3.4.

For $k\geq 3$ and $1\leq j\leq d$, the number of nodes on the $(k^{2}-1)$-th
level of a Markov-Cayley tree can be expressed as

(3.7) $\|M^{k^{2}-2}\|=\sum_{j=1}^{d}R\left(k^{2}-k+1,j\right)C(k-1,j).$

Now we define the notation of tree blocks. For $y>x\geq 0$, $1\leq j\leq d$
and $n\geq 1$, if one node ending with ‘$j$’ of the $x$-th level generates a
path with each of $n$ nodes of the $y$-th level on a Markov-Cayley tree
$\mathcal{T}$, we call this subsystem of $n+1$ nodes a _tree block_
$\mathcal{T}_{b}(x,y,n,j)$. For example, the tree block in Lemma 3.3 is
written as
$\mathcal{T}_{b}(k\\!-\\!1,k^{2}\\!-\\!1,R(k^{2}\\!-\\!k\\!+\\!1,j),j)$. Then
the expectation of such a tree block
$\mathcal{T}_{b}(k\\!-\\!1,k^{2}\\!-\\!1,R(k^{2}\\!-\\!k\\!+\\!1,j),j)$ for
any $k\geq 3$ and $1\leq j\leq d$ can be denoted by
$E_{j}=E_{j}^{+}+E_{j}^{-}$, where

(3.8) $\left\\{\begin{array}[]{rl}E_{j}^{+}&=\ \
p\left[pe^{\beta}+(1-p)e^{-\beta}\right]^{R\left(k^{2}-k+1,j\right)}\\\
E_{j}^{-}&=\ \
(1-p)\left[(1-p)e^{\beta}+pe^{-\beta}\right]^{R\left(k^{2}-k+1,j\right)}\end{array}\right.$

are the expectations when this node ending with ‘$j$’ takes $+1$ and $-1$,
respectively.

In the following, we give the detailed proof of Theorem 1.1.

###### Proof of Theorem 1.1.

Let us suppose that $\mathcal{T}$ is a Markov-Cayley tree that satisfies
(1.7).

1. By Proposition 3.1, our aim is to compute the Ising potentials generated by nodes on the $\lfloor\\!\sqrt{N}\rfloor$-th level to the $(N\\!-\\!1)$-th level of $\Delta_{N^{2}\\!-\\!1}$. That is to say, we can omit the front part $\Delta_{\lfloor\\!\sqrt{N}\rfloor\\!-\\!1}$ of the subtree $\Delta_{N^{2}\\!-\\!1}$. However, for any $\lfloor\\!\sqrt{N}\rfloor\\!+\\!1\leq k\leq N$ and $1\leq j\leq d$, each node ending with ‘$j$’ on the $(k\\!-\\!1)$-th level generates Ising potentials with only $R\left(k^{2}\\!-\\!k\\!+\\!1,j\right)$ nodes on the $(k^{2}\\!-\\!1)$-th level. In other words, each tree block $\mathcal{T}_{b}(k\\!-\\!1,k^{2}\\!-\\!1,R(k^{2}\\!-\\!k\\!+\\!1,j),j)$ is independent in such a situation. Hence using Lemma 3.2, we have

(3.9)
$\mathbb{E}_{p}\left(\exp\\!\left\\{\beta\\!\sum_{k=\lfloor\sqrt{N}\rfloor\\!+\\!1}^{N}\\!\sigma_{k}\sigma_{k^{2}}\right\\}\right)=\prod_{k=\lfloor\sqrt{N}\rfloor\\!+\\!1}^{N}\prod_{j=1}^{d}\left(E_{j}^{+}+E_{j}^{-}\right)^{C(k\\!-\\!1,j)}.$

Furthermore, taking the logarithm, (3.9) yields

$\log\mathbb{E}_{p}\left(\exp\\!\left\\{\beta\\!\sum_{k=\lfloor\\!\sqrt{N}\rfloor\\!+\\!1}^{N}\\!\sigma_{k}\sigma_{k^{2}}\right\\}\right)=\\!\sum_{k=\lfloor\\!\sqrt{N}\rfloor\\!+\\!1}^{N}\sum_{j=1}^{d}C(k\\!-\\!1,j)\log\left[E_{j}^{+}\left(1\\!+\\!\frac{E_{j}^{-}}{E_{j}^{+}}\right)\right].$

Therefore, combining the above equation, (1.7) and Remark 3.4, we can get

$\displaystyle F_{p}(\beta)$
$\displaystyle=\limsup_{N\to\infty}\frac{1}{|\Delta_{N^{2}-\\!1}|}\\!\sum_{k=\lfloor\sqrt{N}\rfloor\\!+\\!1}^{N}\sum_{j=1}^{d}C(k\\!-\\!1,j)\left[\log
E_{j}^{+}+\log\left(1+\frac{E_{j}^{-}}{E_{j}^{+}}\right)\right]$
$\displaystyle=\limsup_{N\to\infty}\\!\sum_{k=\lfloor\\!\sqrt{N}\rfloor\\!+\\!1}^{N}\\!\sum_{j=1}^{d}\frac{C(k\\!-\\!1,j)R\left(k^{2}\\!-\\!k\\!+\\!1,j\right)}{|\Delta_{N^{2}-\\!1}|}\log\left[pe^{\beta}\\!+\\!(1\\!-\\!p)e^{-\\!\beta}\right]\\!+\\!\mathcal{G}_{\\#}(\beta)$
$\displaystyle=\limsup_{N\to\infty}\sum_{k=\lfloor\sqrt{N}\rfloor+1}^{N}\frac{\|M^{k^{2}-2}\|}{|\Delta_{N^{2}-1}|}\log\left[pe^{\beta}+(1-p)e^{-\beta}\right]+\mathcal{G}_{\\#}(\beta)$
$\displaystyle=\frac{\gamma-1}{\gamma}\log\left[pe^{\beta}+(1-p)e^{-\beta}\right]+\mathcal{G}_{\\#}(\beta),$

where

(3.10)
$\mathcal{G}_{\\#}(\beta)=\limsup_{N\to\infty}\sum_{k=\lfloor\sqrt{N}\rfloor+1}^{N}\sum_{j=1}^{d}\frac{C(k\\!-\\!1,j)}{|\Delta_{N^{2}-1}|}\log\left(1+\frac{E_{j}^{-}}{E_{j}^{+}}\right).$

2. In order to show that $F_{p}(\beta)$ is differentiable, we need to demonstrate that both $\mathcal{G}_{\\#}(\beta)$ and its derivatives converge uniformly. For the first statement, we define

(3.11)
$B(\beta)\\!=\\!\frac{(1\\!-\\!p)e^{\beta}\\!+\\!pe^{-\beta}}{pe^{\beta}\\!+\\!(1\\!-\\!p)e^{-\beta}}\
\ \text{and}\ \
\mathcal{L}(\beta)=\\!\lim_{k\to\infty}\\!\log\\!\left(1\\!+\\!\\!\frac{1\\!-\\!p}{p}\left[B(\beta)\right]^{R(k^{2}\\!-\\!k\\!+\\!1,j)}\right).$

Then we have

a. If $B(\beta)<1$, $\mathcal{L}(\beta)=0$ which implies
$\mathcal{G}_{\\#}(\beta)=0$;

b. If $B(\beta)=1$, $\mathcal{L}(\beta)=\log(1/p)$ which also implies
$\mathcal{G}_{\\#}(\beta)=0$;

c. If $B(\beta)>1$, we have

$\mathcal{L}(\beta)=\lim_{k\to\infty}\log\left(\frac{1-p}{p}\left[B(\beta)\right]^{R(k^{2}\\!-\\!k\\!+\\!1,j)}\right)$

which implies

$\displaystyle\mathcal{G}_{\\#}(\beta)$
$\displaystyle=\limsup_{N\to\infty}\sum_{k=\lfloor\sqrt{N}\rfloor+1}^{N}\sum_{j=1}^{d}\frac{C(k\\!-\\!1,j)}{|\Delta_{N^{2}-1}|}\log\left(\frac{1-p}{p}\left[B(\beta)\right]^{R(k^{2}\\!-\\!k\\!+\\!1,j)}\right)$
$\displaystyle=\limsup_{N\to\infty}\sum_{k=\lfloor\sqrt{N}\rfloor+1}^{N}\sum_{j=1}^{d}\frac{C(k\\!-\\!1,j)R(k^{2}\\!-k\\!+\\!1,j)}{|\Delta_{N^{2}-1}|}\log
B(\beta)$ $\displaystyle=\frac{\gamma-1}{\gamma}\log B(\beta).$

In conclusion, $\mathcal{G}_{\\#}(\beta)$ has the property of uniform
convergence.

For the second statement, we only need to show that the series

$\mathcal{S}_{\\#}(\beta)=\limsup_{N\to\infty}\sum_{k=\lfloor\sqrt{N}\rfloor+1}^{N}\sum_{j=1}^{d}\frac{C(k\\!-\\!1,j)}{|\Delta_{N^{2}-1}|}\left[\log\left(1+\frac{E_{j}^{-}}{E_{j}^{+}}\right)\right]^{\prime}$

converges uniformly with regards to $\beta\in\mathbb{R}$. Actually, for $k\geq
3$ and $1\leq j\leq d$, we have

$\displaystyle\left[\log\left(1\\!+\\!\frac{E_{j}^{-}}{E_{j}^{+}}\right)\right]^{\prime}$
$\displaystyle=\frac{R(k^{2}\\!-\\!k\\!+\\!1,j)\frac{1-p}{p}\left[B(\beta)\right]^{R(k^{2}\\!-\\!k\\!+\\!1,j)\\!-\\!1}}{1+\frac{1-p}{p}\left[B(\beta)\right]^{R(k^{2}\\!-\\!k\\!+\\!1,j)}}\cdot\left[B(\beta)\right]^{\prime}$
$\displaystyle=\frac{R(k^{2}\\!-\\!k\\!+\\!1,j)\frac{1-p}{p}\left[B(\beta)\right]^{R(k^{2}\\!-\\!k\\!+\\!1,j)\\!-\\!1}}{1+\frac{1-p}{p}\left[B(\beta)\right]^{R(k^{2}\\!-\\!k\\!+\\!1,j)}}\cdot\frac{2(1-2p)}{(pe^{\beta}\\!+\\!(1\\!-\\!p)e^{-\beta})^{2}}\text{.}$

It is not difficult to see that

$\displaystyle\left\arrowvert\left[\log\left(1\\!+\\!\frac{E_{j}^{-}}{E_{j}^{+}}\right)\right]^{\prime}\right\arrowvert$
$\displaystyle\leq\left\arrowvert\frac{R(k^{2}\\!-\\!k\\!+\\!1,j)\frac{1\\!-\\!p}{p}\\!\left[B(\beta)\right]^{R(k^{2}\\!-\\!k\\!+\\!1,j)\\!-\\!1}}{\frac{1-p}{p}\left[B(\beta)\right]^{R(k^{2}\\!-\\!k\\!+\\!1,j)}}\right\arrowvert\\!\\!\left\arrowvert\frac{2(1\\!-\\!2p)}{(pe^{\beta}\\!+\\!(1\\!-\\!p)e^{-\\!\beta})^{2}}\right\arrowvert$
$\displaystyle=R(k^{2}\\!-\\!k\\!+\\!1,j)\left\arrowvert\frac{pe^{\beta}\\!+\\!(1\\!-\\!p)e^{-\beta}}{(1\\!-\\!p)e^{\beta}\\!+\\!pe^{-\beta}}\right\arrowvert\\!\left\arrowvert\frac{2(1-2p)}{(pe^{\beta}\\!+\\!(1\\!-\\!p)e^{-\beta})^{2}}\right\arrowvert$
$\displaystyle=R(k^{2}\\!-\\!k\\!+\\!1,j)\left\arrowvert\frac{2(1-2p)}{p(1\\!-\\!p)(e^{\beta}\\!+\\!e^{-\beta})^{2}\\!+\\!(1\\!-\\!2p)^{2}}\right\arrowvert$

Then, for any bounded closed interval $[a,b]\subseteq\mathbb{R}$, there exists
a constant $N_{a,b}\geq 0$ such that

(3.12)
$\left\arrowvert\frac{2(1-2p)}{p(1-p)(e^{\beta}+e^{-\beta})^{2}+(1-2p)^{2}}\right\arrowvert\leq
N_{a,b}.$

By (3.7), it follows that

$\displaystyle\mathcal{S}_{\\#}(\beta)$
$\displaystyle\leq\limsup_{N\to\infty}\sum_{k=\lfloor\sqrt{N}\rfloor+1}^{N}\sum_{j=1}^{d}\frac{C(k\\!-\\!1,j)R(k^{2}\\!-\\!k\\!+\\!1,j)}{|\Delta_{N^{2}-1}|}N_{a,b}$
$\displaystyle=\limsup_{N\to\infty}\sum_{k=\lfloor\sqrt{N}\rfloor+1}^{N}\frac{\|M^{k^{2}-2}\|}{|\Delta_{N^{2}-1}|}N_{a,b}$
$\displaystyle=\frac{\gamma-1}{\gamma}N_{a,b}.$

On the basis of the Weierstrass M-test, the uniform convergence of
$\mathcal{S}_{\\#}(\beta)$ is demonstrated. Therefore, $F_{p}(\beta)$ is
differentiable because of the arbitrariness of $a$ and $b$.

3. Applying Theorem 2.1 to (1) and (2) of Theorem 1.1, the result follows. ∎

Given an integer $\alpha\geq 2$, we consider the sequence $a(i)=i^{\alpha-1}$
for all $i\geq 1$. The sum
$S_{N}^{\\#}(\alpha)=\sum_{i=1}^{N}\sigma_{i}\sigma_{i^{\alpha}}$ can be
viewed as the general case of Type I. If we replace $k^{2}$ with $k^{\alpha}$
in Lemma 3.3, the tree block associated with $S_{N}^{\\#}(\alpha)$ can be
written as
$\mathcal{T}_{b}(k\\!-\\!1,k^{\alpha}\\!-\\!1,R\left(k^{\alpha}\\!-\\!k\\!+\\!1,j\right),j)$
for $k\geq 3$ and $1\leq j\leq d$. Then the expectation of such a tree block
is represented as $\bar{E}_{j}=\bar{E}_{j}^{+}+\bar{E}_{j}^{-}$, where

(3.13) $\left\\{\begin{array}[]{rl}\bar{E}_{j}^{+}&=\ \
p\left[pe^{\beta}+(1-p)e^{-\beta}\right]^{R\left(k^{\alpha}-k+1,j\right)}\\\
\bar{E}_{j}^{-}&=\ \
(1-p)\left[(1-p)e^{\beta}+pe^{-\beta}\right]^{R\left(k^{\alpha}-k+1,j\right)}\end{array}\right.$

are the expectations when this node ending with ‘$j$’ takes $+1$ and $-1$,
respectively.

Referring to the previous notations and settings, Corollary 1.2 is proven in
the following.

###### Proof of Corollary 1.2.

Similar to the discussion of the proof of Theorem 1.1, one can see that each
tree block
$\mathcal{T}_{b}(k\\!-\\!1,k^{\alpha}\\!-\\!1,R\left(k^{\alpha}\\!-\\!k\\!+\\!1,j\right),j)$
is also independent on $\Delta_{N^{\alpha}-\\!1}$ for
$\lfloor\\!\sqrt[\alpha]{N}\rfloor\\!+\\!1\leq k\leq N$ and $1\leq j\leq d$.
By Lemma 3.2, we can get

$\mathbb{E}_{p}\left(\exp\\!\left\\{\beta\\!\sum_{k=\lfloor\\!\sqrt[\alpha]{N}\rfloor\\!+\\!1}^{N}\\!\sigma_{k}\sigma_{k^{\alpha}}\right\\}\right)=\prod_{k=\lfloor\\!\sqrt[\alpha]{N}\rfloor\\!+\\!1}^{N}\prod_{j=1}^{d}\left(\bar{E}_{j}^{+}+\bar{E}_{j}^{-}\right)^{C(k-1,j)}.$

It can be verified without difficulty from Proposition 3.1 that

$\displaystyle F_{p}(\beta)$
$\displaystyle=\limsup_{N\to\infty}\frac{1}{|\Delta_{N^{\alpha}-\\!1}|}\log\mathbb{E}_{p}\left(\exp\\!\left\\{\beta\\!\sum_{k=\lfloor\\!\sqrt[\alpha]{N}\rfloor\\!+\\!1}^{N}\\!\sigma_{k}\sigma_{k^{\alpha}}\right\\}\right)$
$\displaystyle=\limsup_{N\to\infty}\sum_{k=\lfloor\\!\sqrt[\alpha]{N}\rfloor\\!+\\!1}^{N}\sum_{j=1}^{d}\frac{C(k\\!-\\!1,j)}{|\Delta_{N^{\alpha}-\\!1}|}\left[\log\bar{E}_{j}^{+}+\log\left(1+\frac{\bar{E}_{j}^{-}}{\bar{E}_{j}^{+}}\right)\right].$

Now take $p=\frac{1}{2}$ in the above equation. We can easily see that
$\log(1+\bar{E}_{j}^{-}/\bar{E}_{j}^{+})=\log 2$. On the other hand, for
$k\geq 3$ and $1\leq j\leq d$, referring to Remark 3.4 the number of nodes on
the $(k^{\alpha}-1)$-th level can be represented as

(3.14)
$\|M^{k^{\alpha}-2}\|=\sum_{j=1}^{d}R\left(k^{\alpha}-k+1,j\right)C(k-1,j).$

Combining (1.7) and (3.14) , the free energy function is obtained as

$\displaystyle F_{\frac{1}{2}}(\beta)$
$\displaystyle=\limsup_{N\to\infty}\sum_{k=\lfloor\\!\\!\sqrt[\alpha]{N}\rfloor\\!+\\!1}^{N}\sum_{j=1}^{d}\frac{C(k\\!-\\!1,j)}{|\Delta_{N^{\alpha}-\\!1}|}\left(\log\bar{E}_{j}^{+}+\log
2\right)$
$\displaystyle=\limsup_{N\to\infty}\sum_{k=\lfloor\\!\\!\sqrt[\alpha]{N}\rfloor\\!+\\!1}^{N}\sum_{j=1}^{d}\frac{C(k\\!-\\!1,j)}{|\Delta_{N^{\alpha}-\\!1}|}\\!\left[\log\frac{1}{2}\\!+\\!R\left(k^{\alpha}\\!\\!-\\!k\\!\\!+\\!\\!1,j\right)\log\\!\frac{e^{\beta}\\!\\!+\\!e^{-\\!\beta}}{2}\right]$
$\displaystyle=\limsup_{N\to\infty}\sum_{k=\lfloor\\!\\!\sqrt[\alpha]{N}\rfloor\\!+\\!1}^{N}\sum_{j=1}^{d}\frac{\|M^{k^{\alpha}-2}\|}{|\Delta_{N^{\alpha}-\\!1}|}\log\left[\frac{1}{2}\left(e^{\beta}+e^{-\beta}\right)\right]$
$\displaystyle=\frac{\gamma-1}{\gamma}\log\left[\frac{1}{2}\left(e^{\beta}+e^{-\beta}\right)\right]$

That is precisely what we wanted to prove. ∎

We emphasize that the free energy function is independent of the value of
$\alpha$ when $p=\frac{1}{2}$.

##  4\. Proof of Theorem 1.3

This section presents the proof for Theorem 1.3. Our attention focuses on a
multiplicative sum of Type II, namely
$S_{N}^{(q)}=\sum_{i=1}^{N}\sigma_{i}\sigma_{qi}$ for $q\geq 2$, which is
defined on a Markov-Cayley tree $\mathcal{T}$. Thus, the state space is
$\mathcal{D}_{\text{II}}=\\{-1,1\\}^{\Delta_{qN-1}}$, and the partition
function of $S_{N}^{(q)}$ on $\Delta_{qN-1}$ is written as

(4.1)
$Z(\beta)=\sum_{\sigma\in\mathcal{D}_{\text{II}}}\exp\\!\left\\{\beta\sum_{i=1}^{N}\sigma_{i}\sigma_{qi}\right\\}$

with free boundary conditions. Proposition 4.1 is analogous to Proposition
3.1. We omit the proof since they are almost identical.

######  Proposition 4.1.

The free energy function of the sum $S_{N}^{(q)}$ defined on a Markov-Cayley
tree that satisfies (1.7) is rewritten as

$\mathcal{F}_{p}(\beta)=\limsup_{N\to\infty}\frac{1}{|\Delta_{qN-1}|}\log\mathbb{E}_{p}\left(\exp\\!\left\\{\beta\\!\sum_{i=\lfloor\frac{N}{q}\rfloor+1}^{N}\\!\sigma_{i}\sigma_{qi}\right\\}\right).$

The following lemma is useful for the proof Theorem 1.3.

######  Lemma 4.2.

For $k\geq 3$ and $1\leq j\leq d$, under the action of the Ising sum
$S_{N}^{(q)}$, each node (i.e. finite word) ending with ‘$j$’ on the
corresponding $(k\\!-\\!1)$-th level of a Markov-Cayley tree generates Ising
potentials with

$R\left((q-1)k+1,j\right)=\sum_{m=1}^{d}(M^{(q-1)k})_{j,m}$

vertices on the $(qk\\!-\\!1)$-th level of the Markov-Cayley tree. The
corresponding potential is

(4.2)
$U(\\{k,qk\\},\sigma)=\beta\sum_{i=1}^{R((q\\!-\\!1)k\\!+\\!1,j)}\sigma_{k}\sigma_{qk,i},$

where $\sigma_{k},\sigma_{qk,i}$ are i.i.d. random variables taking values in
set $\\{-1,+1\\}$.

###### Proof.

Refer to the proof of Lemma 3.3. For any $k\geq 3$ and $1\leq j\leq d$, our
goal is to discover how many paths a node ending with ‘$j$’ on the
$(k\\!-\\!1)$-th level will generate on the $(qk\\!-\\!1)$-th level. This is
equivalent to the number of paths that the symbol ‘$j$’ on the $1$-st level
generates on the $((q\\!-\\!1)k\\!+\\!1)$-th level. By definition of the row
sum, the symbol ‘$j$’ on the $1$-st level will generate
$R\left((q\\!-\\!1)k\\!+\\!1,j\right)$ paths on the
$((q\\!-\\!1)k\\!+\\!1)$-th level. It is clear that (4.2) follows. ∎

######  Remark 4.3.

For $k\geq 3$ and $1\leq j\leq d$, the number of nodes on the $(qk-1)$-th
level of a Markov-Cayley tree can be expressed as

$\|M^{qk-2}\|=\sum_{j=1}^{d}R\left((q-1)k+1,j\right)C(k-1,j).$

Recall the definition of tree blocks in Section 3. According to the
multiplicative relation of the Ising model $S_{N}^{(q)}$, for $k\geq 3$ and
$1\leq j\leq d$ one can get the corresponding tree block written as
$\mathcal{T}_{b}(k\\!-\\!1,qk\\!-\\!1,R(qk\\!-\\!k\\!+\\!1,j),j)$ . Then the
expectation of such a tree block is expressed as $F_{j}=F_{j}^{+}+F_{j}^{-}$,
where

(4.3) $\left\\{\begin{array}[]{rl}F_{j}^{+}&=\ \
p\left[pe^{\beta}+(1-p)e^{-\beta}\right]^{R\left((q-1)k+1,j\right)}\\\
F_{j}^{-}&=\ \
(1-p)\left[(1-p)e^{\beta}+pe^{-\beta}\right]^{R\left((q-1)k+1,j\right)}\end{array}\right.$

are the expectations when this node ending with ‘$j$’ takes $+1$ and $-1$,
respectively.

The proof of Theorem 1.3 is presented.

###### Proof of Theorem 1.3.

Initially, suppose that $\mathcal{T}$ is a Markov-Cayley tree and satisfies
(1.7).

1. Proposition 4.1 says that the energy distribution on $\Delta_{\lfloor N/q\rfloor-1}$ has no effect on the energy distribution of $\Delta_{qN-1}$ as $N$ approaches infinity. This means that we only need to calculate the Ising potentials generated by nodes on the $\lfloor\\!N/q\rfloor$-th level to the $(N\\!-\\!1)$-th level of $\Delta_{qN\\!-\\!1}$. For $\lfloor\\!N/q\rfloor\\!+\\!1\leq k\leq N$ and $1\leq j\leq d$, each node ending with ‘$j$’ of the $(k\\!-\\!1)$-th level will generate Ising potentials with only $R((q\\!-\\!1)k\\!+\\!1,j)$ nodes of the $(qk\\!-\\!1)$-th level. This implies that every subsystem $\mathcal{T}_{b}(k\\!-\\!1,qk\\!-\\!1,R(qk\\!-\\!k\\!+\\!1,j),j)$ is independent of each other. Then applying Lemma 3.2, we have

$\mathbb{E}_{p}\left(\exp\\!\left\\{\beta\\!\sum_{k=\lfloor\\!N/q\rfloor\\!+\\!1}^{N}\\!\sigma_{k}\sigma_{qk}\right\\}\right)=\prod_{k=\lfloor\\!N/q\rfloor\\!+\\!1}^{N}\prod_{j=1}^{d}\left(F_{j}^{+}+F_{j}^{-}\right)^{C(k-1,j)},$

which yields

$\log\mathbb{E}_{p}\left(\exp\\!\left\\{\beta\\!\sum_{k=\lfloor\\!N/q\rfloor\\!+\\!1}^{N}\\!\sigma_{k}\sigma_{qk}\right\\}\right)=\sum_{k=\lfloor\\!N/q\rfloor\\!+\\!1}^{N}\sum_{j=1}^{d}C(k\\!-\\!1,j)\log\left[F_{j}^{+}\left(1\\!+\\!\frac{F_{j}^{-}}{F_{j}^{+}}\right)\right].$

In connection with (1.7) and Remark 4.3, we obtain

$\displaystyle F_{p}(\beta)$
$\displaystyle=\limsup_{N\to\infty}\\!\sum_{k=\lfloor\\!N/q\rfloor+1}^{N}\\!\sum_{j=1}^{d}\frac{C(k\\!-\\!1,j)}{|\Delta_{qN-1}|}\left[\log
F_{j}^{+}+\log\left(1+\frac{F_{j}^{-}}{F_{j}^{+}}\right)\right]$
$\displaystyle=\limsup_{N\to\infty}\\!\sum_{k=\lfloor\\!N/q\rfloor\\!+\\!1}^{N}\\!\sum_{j=1}^{d}\frac{C(k\\!-\\!\\!1,j)R\left((q\\!-\\!\\!1)k\\!+\\!\\!1,j\right)}{|\Delta_{qN-1}|}\log\left[pe^{\beta}\\!\\!+\\!(1\\!-\\!p)e^{-\beta}\right]\\!+\\!\mathcal{G}_{q}(\beta)$
$\displaystyle=\limsup_{N\to\infty}\sum_{k=\lfloor\\!N/q\rfloor+1}^{N}\frac{\|M^{qk-2}\|}{|\Delta_{qN-1}|}\log\left[pe^{\beta}+(1-p)e^{-\beta}\right]+\mathcal{G}_{q}(\beta)$
$\displaystyle=\frac{\gamma^{q-1}(\gamma-1)}{\gamma^{q}-1}\log\left[pe^{\beta}+(1-p)e^{-\beta}\right]+\mathcal{G}_{q}(\beta),$

where

(4.4)
$\mathcal{G}_{q}(\beta)=\limsup_{N\to\infty}\sum_{k=\lfloor\\!N/q\rfloor+1}^{N}\sum_{j=1}^{d}\frac{C(k\\!-\\!1,j)}{|\Delta_{qN-1}|}\log\left(1+\frac{F_{j}^{-}}{F_{j}^{+}}\right).$

2. The discussion of the differentiation of $F_{p}(\beta)$ is similar to the proof of (2) in Theorem 1.1. Recalling that $B(\beta)$ in (3.11), we let

$\bar{\mathcal{L}}(\beta)=\lim_{k\to\infty}\log\left(1+\frac{1-p}{p}\left[B(\beta)\right]^{R((q-1)k+1,j)}\right).$

Then, we use the same method to analyze $B(\beta)$ and
$\bar{\mathcal{L}}(\beta)$, which shows that $\mathcal{G}_{q}(\beta)$ is
uniformly convergent with respect to $\beta\in\mathbb{R}$. Further, we will
prove the convergence of the series

$\mathcal{S}_{q}(\beta)=\limsup_{N\to\infty}\sum_{k=\lfloor\\!N/q\rfloor\\!+\\!1}^{N}\sum_{j=1}^{d}\frac{C(k-1,j)}{|\Delta_{qN-1}|}\left[\log\left(1+\frac{F_{j}^{-}}{F_{j}^{+}}\right)\right]^{\prime}.$

Indeed, for $k\geq 3$ and $1\leq j\leq d$ we can verify that

$\displaystyle\left[\log\left(1\\!+\\!\frac{F_{j}^{-}}{F_{j}^{+}}\right)\right]^{\prime}$
$\displaystyle=\frac{R((q\\!-\\!1)k\\!+\\!1,j)\frac{1-p}{p}B^{R((q\\!-\\!1)k\\!+\\!1,j)\\!-\\!1}}{1+\frac{1-p}{p}B^{R((q-1)k+1,j)}}\cdot\left[B(\beta)\right]^{\prime}$
$\displaystyle=\frac{R((q\\!-\\!1)k\\!+\\!1,j)\frac{1-p}{p}B^{R((q\\!-\\!1)k\\!+\\!1,j)\\!-\\!1}}{1+\frac{1-p}{p}B^{R((q-1)k+1,j)}}\cdot\frac{2(1-2p)}{(pe^{\beta}\\!+\\!(1\\!-\\!p)e^{-\beta})^{2}}$

which implies that

$\displaystyle\left\arrowvert\left[\log\left(1\\!+\\!\frac{F_{j}^{-}}{F_{j}^{+}}\right)\right]^{\prime}\right\arrowvert$
$\displaystyle\leq\left\arrowvert\frac{R((q\\!-\\!1)k\\!+\\!1,j)\frac{1\\!-\\!p}{p}B^{R((q\\!-\\!1)k\\!+\\!1,j)\\!-\\!1}}{\frac{1-p}{p}B^{R((q-1)k+1,j)}}\right\arrowvert\left\arrowvert\frac{2(1-2p)}{(pe^{\beta}\\!+\\!(1\\!-\\!p)e^{-\\!\beta})^{2}}\right\arrowvert$
$\displaystyle=R((q\\!-\\!1)k\\!+\\!1,j)\left\arrowvert\frac{pe^{\beta}\\!+\\!(1\\!-\\!p)e^{-\beta}}{(1\\!-\\!p)e^{\beta}\\!+\\!pe^{-\beta}}\right\arrowvert\left\arrowvert\frac{2(1-2p)}{(pe^{\beta}\\!+\\!(1\\!-\\!p)e^{-\beta})^{2}}\right\arrowvert$
$\displaystyle=R((q\\!-\\!1)k\\!+\\!1,j)\left\arrowvert\frac{2(1-2p)}{p(1\\!-\\!p)(e^{\beta}\\!+\\!e^{-\beta})^{2}\\!+\\!(1\\!-\\!2p)^{2}}\right\arrowvert$

Combining (3.12) and Remark 4.3, we conclude that

$\displaystyle\mathcal{S}_{q}(\beta)$
$\displaystyle\leq\limsup_{N\to\infty}\sum_{k=\lfloor\\!N/q\rfloor\\!+\\!1}^{N}\sum_{j=1}^{d}\frac{C(k\\!-\\!1,j)R((q\\!-\\!1)k\\!+\\!1,j)}{|\Delta_{qN-1}|}N_{a,b}$
$\displaystyle=\limsup_{N\to\infty}\sum_{k=\lfloor\\!N/q\rfloor+1}^{N}\frac{\|M^{qk-2}\|}{|\Delta_{qN-1}|}N_{a,b}$
$\displaystyle=\frac{\gamma^{q-1}(\gamma-1)}{\gamma^{q}-1}N_{a,b}.$

It is therefore a fact for us to realize by the Weierstrass M-test that the
sum $\mathcal{S}_{q}(\beta)$ has uniform convergence. This implies that
$F_{p}(\beta)$ is a differentiable function.

3. The result follows from Theorem 2.1 and the statements (1), (2) of Theorem 1.3. ∎

## References

  * [1] I. Assani, _Pointwise convergence of ergodic averages along cubes_ , Journal d’Analyse Mathématique 110 (2010), no. 1, 241–269.
  * [2] I. Assani and K. Presser, _A survey of the return times theorem_ , Ergodic Theory and Dynamical Systems. Proceedings of the Ergodic Theory workshops at University of North Carolina at Chapel Hill, 2011–2012, 2014, p. 126.
  * [3] J.-C. Ban and C.-H. Chang, _Tree-shifts: Irreducibility, mixing, and chaos of tree-shifts_ , Trans. Am. Math. Soc. 369 (2017), 8389–8407.
  * [4] J.-C. Ban, C.-H. Chang, W.-G. Hu, G.-Y. Lai, and Y.-L. Wu, _Characterization and topological behavior of homomorphism tree-shifts_ , Topology and its Applications 302 (2021), 107848.
  * [5] J.-C. Ban, C.-H. Chang, W.-G. Hu, and Y.-L. Wu, _On structure of topological entropy for tree-shift of finite type_ , Journal of Differential Equations 292 (2021), 325–353.
  * [6] J.-C. Ban, C.-H. Chang, and Y.-H. Huang, _Complexity of shift spaces on semigroups_ , Journal of Algebraic Combinatorics (2020), 1–22.
  * [7] J.-C. Ban, W.-G. Hu, and G.-Y. Lai, _Large deviation principle of multidimensional multiple averages on n_ , Indagationes Mathematicae (2021).
  * [8] J.-C. Ban, W.-G. Hu, and G.-Y. Lai, _On the entropy of multidimensional multiplicative integer subshifts_ , Journal of Statistical Physics 182 (2021), no. 2, 1–20.
  * [9] J.-C. Ban, W.-G. Hu, and Z.-F. Zhang, _The entropy of multiplicative subshifts on trees_ , Journal of Differential Equations 352 (2023), 373–397.
  * [10] I. Benjamini and Y. Peres, _Markov chains indexed by trees_ , The Annals of Probability (1994), 219–243.
  * [11] J. Bourgain, _Double recurrence and almost sure convergence_ , Journal für die Reine und Angewandte Mathematik 404 (1990), 140–161.
  * [12] G. Carinci, J.-R. Chazottes, C. Giardina, and F. Redig, _Nonconventional averages along arithmetic progressions and lattice spin systems_ , Indagationes Mathematicae 23 (2012), no. 3, 589–602.
  * [13] J.-R. Chazottes and F. Redig, _Thermodynamic formalism and large deviations for multiplication-invariant potentials on lattice spin systems_ , Electronic Journal of Probability 19 (2014).
  * [14] A. Dembo and O. Zeitouni, _Ldp for finite dimensional spaces_ , Large deviations techniques and applications, Springer, 2009, pp. 11–70.
  * [15] R. S. Ellis, _Entropy, large deviations, and statistical mechanics_ , vol. 1431, Taylor & Francis, 2006.
  * [16] N. Frantzikinakis, _Some open problems on multiple ergodic averages_ , arXiv preprint arXiv:1103.3808 (2011).
  * [17] H. Furstenberg, _Nonconventional ergodic averages_ , The legacy of John von Neumann (Hempstead, NY, 1988) 50 (1988), 43–56.
  * [18] by same author, _Recurrence in ergodic theory and combinatorial number theory_ , vol. 10, Princeton University Press, 2014.
  * [19] H. Furstenberg, Y. Katznelson, and D. Ornstein, _The ergodic theoretical proof of szemeredi’s theorem_ , Bulletin of the American Mathematical Society 7 (1982), no. 3, 527–552.
  * [20] H. Furstenberg and B. Weiss, _A mean ergodic theorem for $\frac{1}{N}\sum_{n=1}^{N}f(t^{n}x)g(t^{n^{2}}x)$_, Convergence in Ergodic Theory and Probability, De Gruyter, 2011, pp. 193–228.
  * [21] H.-O. Georgii, _Gibbs measures and phase transitions_ , vol. 9, Walter de Gruyter, 2011.
  * [22] B. Host and B. Kra, _Nonconventional ergodic averages and nilmanifolds_ , Annals of Mathematics (2005), 397–488.
  * [23] Y. Kifer, _Nonconventional limit theorems_ , Probability Theory and Related Fields 148 (2010), no. 1-2, 71–106.
  * [24] by same author, _Strong approximations for nonconventional sums and almost sure limit theorems_ , Stochastic Processes and their Applications 123 (2013), no. 6, 2286–2302.
  * [25] Y. Kifer and S. Varadhan, _Nonconventional limit theorems in discrete and continuous time via martingales_ , The Annals of Probability 42 (2014), no. 2, 649–688.
  * [26] B. Krause, M. Mirek, and T. Tao, _Pointwise ergodic theorems for non-conventional bilinear polynomial averages_ , Annals of Mathematics 195 (2022), no. 3, 997–1109.
  * [27] K. Petersen and I. Salama, _Tree shift topological entropy_ , Theoret. Comput. Sci. 743 (2018), 64–71.
  * [28] K. Petersen and I. Salama, _Entropy on regular trees_ , Discrete & Continuous Dynamical Systems 40 (2020), no. 7, 4453.