arXiv:1709.02932v1 [math.CO] 9 Sep 2017

IDENTIFYING COMBINATORIALLY SYMMETRIC HIDDEN
MARKOV MODELS

DANIEL KLAUS BURGARTH
Department of Mathematics, Aberystwyth University, Aberystwyth SY23 3BZ, UK
Abstract. We provide a sufficient criterion for the unique parameter identification of combinatorially symmetric Hidden Markov Models based on the
structure of their transition matrix. If the observed states of the chain form a
zero forcing set of the graph of the Markov model then it is uniquely identifiable
and an explicit reconstruction method is given.

1. Introduction
Hidden Markov Models are a major workhorse of speech recognition, gene analysis, computational finance and, more generally, machine learning [1]. The key idea
is to consider a very simple Markov chain as an underlying model, but only allow for
a restricted set of observations, while the remaining part of the dynamics remains
hidden. Such models naturally lead to a vast variety of statistical questions, such
as the estimation of the initial state, prediction of future events, or identification
of the parameters of the underlying dynamics.
In terms of learning the parameters of a Hidden Markov Model, powerful algorithms such as the Baum-Welch algorithm [1] have been developed. These algorithms are statistical in nature and iteratively maximise likelihood functions. The
aim of the present paper is to approach parameter identification in such models
from a much more elementary perspective. Namely, we set the problem not as a
statistical, but as a matrix problem, and ask the question: given a Hidden Markov
Model with a certain structure, how many states do we need to observe such that
its parameters are uniquely determined?
The type of inverse problem we consider is inspired by the work of Gladwell [2],
and analogous to parameter identification in quantum physics [3]. In the context of
linear Markov chains, questions similar in spirit were discussed in [4], were it was
shown that certain ‘local’ perturbations in infinite chains are uniquely identified by
their impact on hitting times. We consider a simpler problem on finite chains, but
for arbitrary topology of the Markov model.
We find that a sufficient criterion for the unique identifiability can be easily
given in terms of the structure of the matrix of transition probabilities/rates of the
discrete/continuous Markov chain, provided this matrix is combinatorially symmetric. Namely, if the set of states we observe is a zero forcing set [5] of the simple
graph which describes the non-zero pattern of the matrix, then the Hidden Markov
Model can be uniquely identified. This holds for discrete (Theorem 1) as well as for
Date: April 9, 2018.
1

2

IDENTIFYING COMBINATORIALLY SYMMETRIC HIDDEN MARKOV MODELS

continuous (Theorem 2) chains. The proof is constructive and therefore provides
an easy-to implement algorithm for the identification, although we do not consider
the statistical properties of the problem and in particular the efficiency when only
limited information is provided.
2. Setup
Throughout this article we consider homogeneous and finite Markov chains with
states s = 1, . . . , S. To begin, let us consider discrete-time Markov chains with
states Xn described by a right stochastic transition matrix P . In particular, the
transition probability P(Xn+1 = j|Xn = i) is given by the matrix element (P )ij ≥ 0
PS
of P , independently of n. P is row stochastic with j=1 (P )ij = 1. We will refer
to properties of the Markov chain and its transition matrix P interchangeably. A
central property of matrices which we use in this article is combinatorial symmetry [6]:
Definition 1 (Combinatorial symmetry). A matrix M is combinatorially symmetric if and only if for all indices i, j, (M )ij 6= 0 implies (M )ji 6= 0.
The advantage of the combinatorical symmetry is that we can describe the nonzero pattern of M by an undirected graph. For the purpose of this work, we ignore
the diagonal entries of M when constructing this graph such that it has no selfedges:
Definition 2. For a combinatorially symmetric matrix M of order S, define a
simple graph G(M ) = (V, E) with S vertices. The edges are given by the non-zero
pattern of the off-diagonal elements of M , {i, j} ∈ E ⇔ (M )ij 6= 0, i < j.
Another central concept in this article is zero forcing:
Definition 3 (Zero Forcing [7, 8]). Consider a subset Z of vertices on a simple
graph which are initially coloured blue. Let the colour propagate on the graph according to the following rules: 1) if a vertex is blue, it remains blue; and 2 ) if a
blue vertex i has exactly one non-blue neighbour j, this neighbour becomes blue. If
eventually all vertices turn blue, we call the original set Z a zero forcing set.
For an example, consider Fig. 1. Furthermore, for any simple graph, we can
consider a minimal zero forcing set Z such that for all forcing sets Z ′ , |Z| ≤ |Z ′ |.
The number of elements in that set is called the zero forcing number of the graph,
Z(G). It is easy to see that a path has forcing number 1, and a lattice of size
n × m, n ≤ m, has forcing number n. For sparse graphs, the zero forcing number
tends to be much smaller than the order.
3. Main result
We consider the case of an endlessly evolving finite Markov chain ‘observed’ on
a certain set A of states. That is, at a given time n, we may check if the chain is on
any state within A, and if it is, we know in which one. If it isn’t, we only know that
it is in one of the hidden states outside A, without knowing in which one. When
discussing this setup we are not worried about statistical efficiency of estimation,
but only about what could be estimated uniquely, in principle, provided enough
samples are taken. This leads us to

IDENTIFYING COMBINATORIALLY SYMMETRIC HIDDEN MARKOV MODELS

3

Lemma 1. If a set A of states of a finite discrete time Markov chain can be
observed, and G(P ) is connected, then the corresponding dynamics (P n )ij can be
estimated arbitrarily well for all i, j ∈ A and for all n ∈ N.
Proof. Since the Markov chain is irreducible, by observing state i we are guaranteed
that eventually we well find Xk = i for some k. We then wait for time n and measure
state j, thereby sampling the probability above. We repeat until we have a precise
enough estimate.

Setting n = 1 in the Lemma implies that (P )ij , i, j ∈ A is fixed by the observations in A. While this is rather obvious– after all, the states are directly observed–
the interesting question is what can be inferred indirectly about neighbouring nodes.
The following Lemma provides a crucial step.
Lemma 2. Consider a set of states A of a Markov chain. Assume (P n )ij is known
for all i, j ∈ A and for all n ∈ N. Let k ∈ A and ℓ ∈ A = V \A be states such that ℓ
is the only incoming and only outgoing neighbor of k in A (so (P )ℓk 6= 0, (P )kℓ 6= 0
and j ∈ A, (P )jk 6= 0 ⇒ j = ℓ and j ∈ A, (P )kj 6= 0 ⇒ j = ℓ). Then we can infer
(P n )ij for all i, j ∈ A ∪ {ℓ} and for all n ∈ N uniquely.
Proof. Because of row stochasticity and ℓ being the only element in A with (P )kj 6=
0, we have
X
X
(P )kj =
(P )kj + (P )kℓ
(1)
1=
j

j∈A

The first term is known by assumption, so Equation 1 determines (P )kℓ . Furthermore, for any i ∈ A, we have through Chapman-Kolmogorov that for all n,
X
(2)
(P )kj (P n )ji
(P n+1 )ki =
j

=

(3)

X

(P )kj (P n )ji + (P )kℓ (P n )ℓi ,

j∈A

where the left hand side and the first term of the right hand side are already
determined, hence fixing (P n )ℓi . Similarly, using that (P )ℓk is the only non-zero
term connecting k with A, we consider for all n and for all i ∈ A
X
(4)
(P n )ij (P )jk
(P n+1 )ik =
j

=

(5)

X

(P n )ij (P )jk + (P n )iℓ (P )ℓk

j∈A
n

providing us with (P )iℓ . Finally, for all n,
X
(6)
(P n )ℓj (P )jk
(P n+1 )ℓk =
j

=

(7)

X

(P n )ℓj (P )jk + (P n )ℓℓ (P )ℓk ,

j∈A
n

where (P )ℓℓ is the only unknown. Concluding, we know (P n )ij on A ∪ {ℓ}.
We are now ready to prove the main theorem.



4

IDENTIFYING COMBINATORIALLY SYMMETRIC HIDDEN MARKOV MODELS

Theorem 1. Consider combinatorially symmetric discrete-time Markov chain P
with connected graph G(P ). If the observable set of vertices on G(P ) is zero forcing,
then the Markov chain is uniquely determined through the dynamics of the observed
states.
Proof. We apply Lemma 1 to the initial set A and increase it inductively using zero
forcing and combinatoric symmetry in Lemma 2 until all vertices are included. 
Corollary 1. The zero forcing number of a combinatorially symmetric discretetime Markov chain P with connected graph G(P ) is an upper bound to the minimal
number of observed states which uniquely determine it.

4. Discussion of requirements
In order to obtain necessary and sufficient criteria for the inverse problem provided, let us develop another perspective. For a given simple graph, consider the
combinatorially symmetric Markov chains which provide such graph. The observed
(P n )ij , i, j ∈ A are polynomials in the unknown elements of P . For example, for a
path on three vertices,

(8)



P11
P = P21
0

P12
P22
P32


0
P23  ,
P33

we obtain
(9)

(P )11 = P11

(10)

2
(P 2 )11 = P11
+ P12 P21

(11)

3
(P 3 )11 = P11
+ 2P11 P12 P21 + P12 P21 P22
···

(P n )11 = · · · .
The question of unique identification of the Markov chain can then be rephrased
into the unique solvability of the above system of polynomial equations (combined
with the row normalisation providing further equations). For larger systems this
quickly becomes intractable, but it allows us to discuss some of the conditions posed
above. Firstly, we note that the positivity of the non-zero entries was never used
in the previous sections. It is therefore interesting to ask if one can apply Theorem
1 for matrices without row normalisation? The above example of the path gives an
immediate counterexample, because P21 and P12 always occur as a product, in any
order n, and cannot be separated without another equation.
Furthermore, an important assumption in the above is the combinatorial symmetry of the Markov chain. What happens if this is not the case? As an example,
consider the directed cycle on S vertices. The zero forcing condition can easily be
extended to directed graphs giving the directed cycle a forcing number of 1. Setting

IDENTIFYING COMBINATORIALLY SYMMETRIC HIDDEN MARKOV MODELS

5

6

3
1

5
2

4

7

8

9

10

Figure 1. The penta-sun H5 [5]. The zero forcing number is 3,
and an example of a forcing set is {9, 10, 1}. If we only observe the
smaller set {9, 10} (blue), we can use Lemma 2 to obtain (P n )ik
for i, k ∈ {2, 4, 7, 8, 9, 10} and all n.
up the polynomials as above, we obtain
(12)

(P )11 = 0

(13)

(P 2 )11 = 0

(14)

···

(15)

(P S )11 =

S−1
Y

Pi i+1

S−1
Y

Pi i+1

i=1

(16)

(P S+1 )11 =

i=1

S
X

Pii

i=1

··· .
It is clear by symmetry that P is not uniquely determined. We conjecture that
the minimum number of vertices to be observed is actually S − 1. Therefore, an
analogous version of Theorem 1, replacing combinatorial symmetry with a directed
graph and generalising zero forcing along those lines, does not hold.
Another natural question is if there are combinatorially symmetric Markov chains
which can be identified from a number of nodes smaller than their zero forcing
number. This would be analogous to the relationship between zero forcing and
maximum nullity (see, e.g., [5]), where it is known that the forcing number is an
upper bound to the nullity, but that this bound is not always tight. We conjecture that the same happens here, and a natural candidate to test would be
one for which the maximum nullity is unequal to the forcing number, such as

6

IDENTIFYING COMBINATORIALLY SYMMETRIC HIDDEN MARKOV MODELS

H5 (compare Fig. 1), which has a forcing number of 3 and a maximum nullity of 2. We conjecture that the corresponding Markov chain can be uniquely
identified using nodes {9, 10} and will provide some evidence towards this conjecture. Firstly, using Lemma 2 we see that we can obtain (P n )ik for i, k ∈
{2, 4, 7, 8, 9, 10} and all n easily. This leaves us with the 14 unknown parameters P11 , P12 , P21 , P23 , P32 , P33 , P36 , P63 , P66 , P34 , P43 , P45 , P54 , P55 . By using rowstochasticity we may eliminate P12 , P23 , P36 , P45 , P55 , P66 to be left with 8 unknowns. We claim that these can be obtained from (P 2 )22 , (P 2 )44 , (P 2 )24 , (P 2 )42 ,
(P 3 )22 , (P 3 )44 , (P 3 )42 , and (P 4 )22 . Expanding the matrix powers in terms of the
matrix elements like in Equation 9, we obtain a set of 8 polynomial equations
(which are, however, too complex to be worthwhile writing down explicitly here).
For example, (P 4 )22 is linear in P63 and the only equation involving this parameter,
which leaves us with 7 remaining equations and unknowns. (P 2 )42 and (P 3 )42 can
be combined to obtain


(17)
P33 = (P 3 )42 − (P 2 )42 P22 − (P 2 )42 P44 − P48 P72 P78 /(P 2 )42 .
The equations from (P 2 )22 , (P 2 )44 , (P 2 )24 and (P 2 )42 are linear in P11 , P54 , P34 and
P43 respectively and can thus eliminate those variables. This leaves us with two
equations originating from (P 3 )22 and (P 3 )44 and two unknown P32 and P21 . These
equations are rather complex in their coefficients but quartic in the variables (and
quadratic in P32 and P21 , respectively). Usually this equation system would have
4 solutions, while for certain degenerate cases it might have infinitely many. What
makes it hard to analyse these equations is that we found examples with several
feasible solutions for P32 and P21 , which nonetheless all lead to a unique feasible
solution for P (e.g, a valid stochastic matrix P ). While we were unable to prove
in general that the whole set of equations has a unique feasible solution, we have
checked 10000 randomly created Markov chains with the graph H5 and found via
exact computer algebra that they had only one feasible solution. This leads us to
conjecture that this chain is identifiable from two sites (at the least, the numerical analysis shows that most systems with this graph are uniquely identifiable).
One may therefore speculate that the identifiability is related more closely to the
maximum nullity after all.
Perhaps this discussion highlights another point- checking identifiability is a very
complicated subject of algebraic geometry in general, and even if the system might
be uniquely solvable, finding this solution is hard, both analytically and numerically.
On the other hand, Zero Forcing is easy to check, and the inductive protocol for
identification above is constructive and easy to implement.
5. Continuous time Markov chains
A naive way to consider the case of continuous Markov chains would be to integrate their dynamics for some time t and then refer to the discrete case. However,
typically these discrete Markov chains will be described by the fully connected
graphs and the above protocol would require to observe S − 1 states. It is therefore
advisable to attempt the analysis with the transition rate matrix Q instead. It is
well known
P that Q has non-positive off-diagonals and normalised diagonal elements
(Q)ii =
j6=i (Q)ij . Furthermore P (t) = exp(Qt) is the transition matrix of a
Markov chain for all t ∈ R≥0 .

IDENTIFYING COMBINATORIALLY SYMMETRIC HIDDEN MARKOV MODELS

7

We assume that Q is combinatorially symmetric and define the graph of the
continuous time Markov chain following Definition 2 as G(Q). Provided this graph
is connected, the analogous version to Lemma 1 is that for i, j observable, P (t)ij
can be estimated arbitrarily well for all times. Via
dn
= (Qn )ij
P (t)ij
(18)
dtn
t=0
we can perform the same iteration as in
PLemma 2 along a zero forcing set, with the
row stochasticity replaced by (Q)ii = j6=i (Q)ij . This leads us to the following
Theorem 2. Consider combinatorially symmetric continuous-time Markov chain
Q with graph G(Q). If the observable set of vertices on G(Q) is zero forcing, then the
Markov chain is uniquely determined through the dynamics of the observed states.
acknowledgments
I acknowledge the feedback of Leslie Hogben, Bryan Shader and Tracy Hall and
our enjoyable discussions at the AIM workshop ‘Zero forcing and its applications’,
as well as the AIM for providing the funding to attend this workshop. This work
was supported by the EPSRC Grant No. EP/M01634X/1.
References
[1] O. Cappé, E. Moulines, T. Rydén, Inference in Hidden Markov Models, Springer, New York,
2005.
[2] G. M. L. Gladwell Inverse Problems in Vibration, Kluwer, New York, 2005.
[3] D. Burgarth, K. Maruyama, Indirect Hamiltonian Identification through a small gateway,
New Journal of Physics 11 103019, 2009.
[4] V. de la Peña, H. Gzyl, and P. McDonald. Hitting time and inverse problems for Markov
chains, Journal of Applied Probability 45, 640 (2008).
[5] L. Hogben (editor), Handbook of linear algebra, Second Edition, CRC Press, Boca Raton,
2014.
[6] J. S. Maybee. Combinatorially symmetric matrices, Linear Algebra and its Applications, 8,
529, 1974.
[7] F. Barioli, W. Barrett, S. Fallat, H. T. Hall, L. Hogben, B. Shader, P. van den Driessche, H.
van der Holst. Zero forcing parameters and minimum rank problems Linear Algebra and its
Applications 433, 401, 2010.
[8] D. Burgarth and V. Giovannetti, Full control by locally induced relaxation, Physical Review
Letters 99, 100501, 2007.

