# Statistical Identification of Markov Chain on Trees

Authors: Xuyan Xiang; Xiao Zhang; Xiaoyun Mo
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

The theoretical study of continuous-time homogeneous Markov chains is usually based on a natural assumption of a known transition rate matrix (TRM). However, the TRM of a Markov chain in realistic systems might be unknown and might even need to be identified by partially observable data. Thus, an issue on how to identify the TRM of the underlying Markov chain by partially observable information is derived from the great significance in applications. That is what we call the statistical identification of Markov chain. The Markov chain inversion approach has been derived for basic Markov chains by partial observation at few states. In the current letter, a more extensive class of Markov chain on trees is investigated. Firstly, a type of a more operable derivative constraint is developed. Then, it is shown that all Markov chains on trees can be identified only by such derivative constraints of univariate distributions of sojourn time and/or hitting time at a few states. A numerical example is included to demonstrate the correctness of the proposed algorithms.


---

## Body

## 1. Introduction

The classic study of continuous-time homogeneous Markov chains usually has a natural assumption that it has a known transition probability matrix or a transition rate matrix (TRM). However, the TRM of a Markov chain in realistic systems might be unknown although it is an underlying one (named as the underlying Markov chain), and that is what needs to be identified by observable data. For a Markov chain with a finite state space, it is determinative provided that its TRM is identified. In some realistic systems, moreover, one probably observes the partial motion of the underlying Markov chain. For example, one can only observe the sojourn sequences and hitting sequences on one of the states. Subsequently, one can fit the PDF of sojourn (resp., hitting) time by statistical techniques. It is easy and trivial to identify the TRM of this Markov chain if we know exactly the PDFs of sojourn time and hitting time of every state.A natural question arises as to whether it is possible to identify the TRM by those few states. Due to the transition relations of states which intercommunicate in the underlying Markov chain, it is indeed possible. Thus, an issue on how to identify the TRM of the underlying Markov chain by partially observable information is derived from the great significance in applications.In fact, the continuous-time homogeneous Markov model which described the gating kinetics of single ion channel is a good example to show the real application in biophysics and neuroscience; for example, see [1, 2] and further publications. In experiments, the transition between the various states cannot be directly observed and only transitions between a small number of open states are observable. It is straightforward to derive the sojourn time and hitting time distributions for a single state or a small number of states. The PDFs of sojourn or hitting time generally take the form of a sum of exponentials (e.g., [2–4]). And the best-fitting approach and function can be found with a number of readily available computer programs [5–7].Unfortunately, once the fitting is completed, it is very difficult to use these PDFs to identify the TRM of the underlying Markov chain. The most difficult challenge lies in finding out the hidden solutions and algorithms to perform the reverse operation. Thus, the identification has always been addressed directly using the maximum likelihood estimate (MLE) (e.g., see [8–11] and further references) rather than performing this inversion. Another series of publications using canonical forms of reduced dimensions analyze finite two-state trajectories, in which the system is aggregated into only two states, defined as theon state and theoff state (irreversible transitions are also allowed); see [12, 13] and the references therein for a review. All of them are powerful. However, each approach has pros and cons. None of them can perfectly identify all kinds of Markov chains. In general, for example, the sojourn times fC and fO may not be sufficient for parameterizing a given Markov model. This is shown by [14] where, in general, fC and fO as well as bivariate distributions of subsequent open and closed times, fOC and fCO, are necessary.Note that those discarded the prior information from the underlying topology. Thus, it is indeed possible to perform the complicated inversion since the prior information from the underlying architecture of Markov chain is very helpful to accomplish it. This is what we callstatistical identification of Markov chain (SIMC). We developed a Markov chain inversion approach (MCIA) to open the possibility of solving the SIMC. This issue can be reduced to three steps for applications. The first one is to obtain the necessary data at the fewest possible states by preprocessing the observed data. The second one is to accurately fit the corresponding PDFs of states required by the next step. The final one is to find out the algorithm to identify the TRM of the underlying Markov chain by those PDFs. Throughout this paper,we focus our attention on the final one since there are a number of readily available approaches to fit those PDFs.We explore a class of Markov models where reversibility is maintained. Since some realistic systems obey the principle of microscopic reversibility or detailed balance, this implied the reversibility of the Markov chain. At least in applications to ion channels, an assumption of reversibility is plausible in many circumstances, corresponding to channels which are not coupled to a free energy source such as an ion concentration gradient; for discussion of this assumption, see [15]. As an example, [16, 17] derived a criterion to identify whether it is reversible or not in a three-state Markov system based on the coarse-grained information of two-state trajectories. Throughout the rest of this paper, the unqualified term “Markov chain” usually refers to a reversible Markov chain.It is well known that classic architectures include star-graph, linear, and cycle chains. Thus, some general constraints and the corresponding algorithms for them were explored in former publications [18–20]. There is no obvious strategy for selecting the constraints to use for a general model. A key task is to find out the feasible solutions and the corresponding algorithms to different classes. Then, a subsequent question is whether more complicated architectures are identified by such approach. On this point, any one of them can be viewed as a tree provided that it contains no cycles. This implies that the tree is a very important extension of the star graph and line graph and represents one of the two classes of topologies (whether containing cycles or not). It is known that all Markov chains on trees are reversible [21]. Thus, SIMC on trees will be exploited in this letter, although some of them are still not applied in real systems. It is derived that all Markov chains on trees are identified by our approach. It is mentioned that, for SIMC on trees, the greatest contribution should be to discover the fundamental way and the corresponding algorithm to identify the TRM due to the challenge of performing the reverse operation as stated earlier. Hence, the work further opens up the possibility of carrying out the statistical identification for all reversible Markov chains.Such approach has obvious advantages over MLE in that it can identify the most reversible Markov chain without the requirement of bivariate distributions of subsequent sojourn time and hitting time and in that the computation is accurate based on the accurate sojourn time PDFs and the prior information about the underlying topological structure of the Markov chain.This paper is organized as follows. After recalling the sojourn time distribution, a type of a more operable derivative constraint is developed in Section2. In Section 3, the solution to SIMC on trees is provided by such derivative constraints. In addition, we address the solutions to three particular and regular representatives of trees, including theoretical conclusions, proofs, and algorithms. Finally, a numerical example is included to demonstrate the correctness of the proposed model.


## 2. Distributions of Hitting Time and Its Derivative Relationships

Throughout this section,diag(⋯) denotes a diagonal matrix whose entries on the diagonal are those of them, and ⊤ denotes transpose, 1 a column vector of ones, and0 a matrix (vector) of zeros, with the dimensions of these being clear from their context. Furthermore, Aij and Ai denote the (i,j)th entry and the ith column vector of the matrix A, respectively.Let{Xt:t≥0} be a reversible Markov chain with finite state space S={0,1,…,M}, conservative TRM Q=(qij)S×S such that Q1=0(qij≥0,j≠i;qi≡-qii>0), and equilibrium distribution π~=[π0,π1,…,πM]⊤ such that (1)Π1/2QΠ-1/2=Π1/2QΠ-1/2⊤,π~⊤1=1,where Π=diag(π0,π1,…,πM), and the first one (i.e., πiqij=πjqji for any i,j∈S) implies the reversibility.Assume that the state space may be partitioned asS=C∪O1∪O2∪⋯∪Os into r+s(⩾1) classes, where C denotes the class of closed states (unobservable), O1={1,2,…,r} the class of open states being distinguishable (i.e., having r different open levels), and Oi(i=2,…,s) the class of aggregated open states (i.e., having other common open levels); for example, see [2].A proper subsetO of the open class O=O1∪O2∪⋯∪Os is observed such that either Ok⊆O or Ok∩O=∅ for k=2,…,s (this condition allows one to obtain the sojourn time and hitting time sequences of O from experimental recording). Let C=S-O. The state space is now partitioned as S=O∪C. The TRM Q may be partitioned as, by the classes O and C, (2)Q=QooQocQcoQcc.The corresponding partition is used for the equilibrium distribution π~; that is, π~⊤=[π~o⊤,π~c⊤].


### 2.1. Distributions of Hitting Time

The sojourn time and hitting time ofO can be defined as σ=inf{t>0,Xt∉O} and τ=inf{t>0,Xt∈O}, with the usual convention that the infimum over an empty set is infinity, respectively. They are also the hitting time and sojourn time of C, respectively.For some basic results on aggregated continuous-time Markov chains, refer to [1, 2, 20, 22]. Thus, just some of them, required in the sequel, are now recalled.For ease of exposition, letN be the number of C, and C≡{1,2,…,N}, Πc≡diag(π1,π2,…,πN). Note that Qcc is nonsingular since {X(t)} is irreducible, and hence all the eigenvalues of Qcc have strictly negative real parts. Assume that -α1,-α2,…,-αN are all real eigenvalues of Qcc such that αi>0. By symmetric reparameterization with respect to (·,·)Πc, Qcc can be diagonalized with an orthogonal matrix E and we can obtain a matrix W=Πc-1/2E and then set D=W-1 and A=diag(α1,α2,…,αN). Then, one can get(3)Qcc=-D-1AD,D⊤D=Πc,DQcc=-AD,ΠcQcc=-D⊤AD.Theorem 1.
The PDF of hitting time ofO (resp., the sojourn time of C) takes the following form: (4)fτt=π~c⊤1-1D1⊤Aexp⁡-AtD1=∑i=1Nγiexp⁡-αit,t>0.Note that the above is a sum of N-exponentials, γiexp⁡(-αit), where -αi(αi>0) are the real eigenvalues of Qcc and γi=αi(D1)i⊤(D1)i(π~c⊤1)-1.In particular, ifO only contains a single state i, that is, O={i}, then the PDF of the sojourn time degenerates to an exponential form.Corollary 2.
The PDF of the sojourn timeσ at a single state i takes a form of an exponential (5)fσt=qiexp⁡-qit,t>0.


### 2.2. The Derivative Constraints

LetΓ=(γ1,…,γN) and(6)dn=ΓAn-11=∑i=1Nγiαin-1,n≥1,cn=πc⊤1dn=1-πo⊤1dn.Then, -1ndn is the nth derivative of the hitting time PDF of O at t=0.By (6), dn=(πc⊤1)-1∑i=1N(D1)i⊤(D1)iαin=(πc⊤1)-1(D1)⊤An(D1). By (3), DQcc=-AD, and then D⊤A2D=-D⊤ADQcc=(-1)2ΠcQcc2. One can apply such operation repeatedly to conclude D⊤AnD=(-1)nΠcQccn.A class of constraints commonly used can be derived from the derivatives of the hitting time distribution att=0.Theorem 3.
The derivatives of the hitting time distribution ofO at t=0 are related to the transition rates with the formula (7)cn=-1n1⊤ΠcQccn1=-1n∑i∈Cπi∑j∈CQccnij.It is noted that many other constraints are required to identify the general Markov chains [20]. However, derivative constraints are the most common ones. Thus, we will more deeply discover the intrinsic laws in derivative constraints. Further, we will show that only by applying the derivative constraints is it possible to solve most of the Markov chains such as the trees; see the next section.In particular, the most useful and commonly used constraints are the first three ones.Corollary 4.
The following equations hold:(8)c1=∑j∈Cπj∑i∈Oqji,c2=∑j∈Cπj∑i∈Oqji2,c3=-∑s∈C∑j∈Cπsqsj∑l∈Oqsl∑i∈Oqji.In particular, a single state i has a more simple and visual form of cn, and by far the most common and convenient are those for a single state.Corollary 5.
Observing a single statei, one can get the following equations for a tree: (9)c1=∑j≠iπjqji,c2=∑j≠iπjqji2,c3=∑j≠iπjqji2qj,c4=∑j≠iπjqji2∑s∈Cqjsqsj,c2s+1=∑j≠iπjqji2∑a1,…,as-1∈Cqja1qa1a2⋯qas-2as-1qas-1qas-1as-2⋯qa2a1qa1j,c2s+2=∑j≠iπjqji2∑a1,…,as∈Cqja1qa1a2⋯qas-1asqasas-1⋯qa2a1qa1j.The right-hand side of the first equation gives a sum over all exit rate flows for state i because of πjqji=πiqij. Conditional upon the first equation, the second and the third one are obvious. The expression within the bracket of c2s+1 (resp. c2s+2) is the sum over rates of possible (2s-1)-step (resp., 2s-step) transitions departing from a state j, having a direct transition to i, and returning to itself. Those possible transitions imply the intrinsic relationships to Qcc so that most transitions can be identified by those hitting PDFs.By the end of this section, we show that the abovecn(n≥1) are known from the required PDFs at O and follow from Lemma 6. First of all, Corollary 2 shows that qi=1/Eσ, where Eσ is the expected sojourn time for state i. Corollary 5 shows that c1=∑j≠iπjqji=∑j≠iπiqij=πiqi. In addition, c1=(1-πi)d1. It suffices to yield πi=d1/(qi+d1)=c1Eσ, which implies the following lemma.Lemma 6.
The PDFs of sojourn time and hitting time at a single statei show that(10)qi=1Eσ,πi=d1qi+d1=c1Eσ.For observations at O, one can obtain the corresponding dn. Thus, (6) shows that cn(n≥1) is known, which is equal to dn times a known constant πc⊤1 from the observation at O. The reason is as follows. Lemma 6 shows that, based on statistics for a single state i, one can obtain by its PDF πi for any i∈O, followed by cn=πc⊤1dn=1-∑i∈Oπidn(n≥1).


## 2.1. Distributions of Hitting Time

The sojourn time and hitting time ofO can be defined as σ=inf{t>0,Xt∉O} and τ=inf{t>0,Xt∈O}, with the usual convention that the infimum over an empty set is infinity, respectively. They are also the hitting time and sojourn time of C, respectively.For some basic results on aggregated continuous-time Markov chains, refer to [1, 2, 20, 22]. Thus, just some of them, required in the sequel, are now recalled.For ease of exposition, letN be the number of C, and C≡{1,2,…,N}, Πc≡diag(π1,π2,…,πN). Note that Qcc is nonsingular since {X(t)} is irreducible, and hence all the eigenvalues of Qcc have strictly negative real parts. Assume that -α1,-α2,…,-αN are all real eigenvalues of Qcc such that αi>0. By symmetric reparameterization with respect to (·,·)Πc, Qcc can be diagonalized with an orthogonal matrix E and we can obtain a matrix W=Πc-1/2E and then set D=W-1 and A=diag(α1,α2,…,αN). Then, one can get(3)Qcc=-D-1AD,D⊤D=Πc,DQcc=-AD,ΠcQcc=-D⊤AD.Theorem 1.
The PDF of hitting time ofO (resp., the sojourn time of C) takes the following form: (4)fτt=π~c⊤1-1D1⊤Aexp⁡-AtD1=∑i=1Nγiexp⁡-αit,t>0.Note that the above is a sum of N-exponentials, γiexp⁡(-αit), where -αi(αi>0) are the real eigenvalues of Qcc and γi=αi(D1)i⊤(D1)i(π~c⊤1)-1.In particular, ifO only contains a single state i, that is, O={i}, then the PDF of the sojourn time degenerates to an exponential form.Corollary 2.
The PDF of the sojourn timeσ at a single state i takes a form of an exponential (5)fσt=qiexp⁡-qit,t>0.


## 2.2. The Derivative Constraints

LetΓ=(γ1,…,γN) and(6)dn=ΓAn-11=∑i=1Nγiαin-1,n≥1,cn=πc⊤1dn=1-πo⊤1dn.Then, -1ndn is the nth derivative of the hitting time PDF of O at t=0.By (6), dn=(πc⊤1)-1∑i=1N(D1)i⊤(D1)iαin=(πc⊤1)-1(D1)⊤An(D1). By (3), DQcc=-AD, and then D⊤A2D=-D⊤ADQcc=(-1)2ΠcQcc2. One can apply such operation repeatedly to conclude D⊤AnD=(-1)nΠcQccn.A class of constraints commonly used can be derived from the derivatives of the hitting time distribution att=0.Theorem 3.
The derivatives of the hitting time distribution ofO at t=0 are related to the transition rates with the formula (7)cn=-1n1⊤ΠcQccn1=-1n∑i∈Cπi∑j∈CQccnij.It is noted that many other constraints are required to identify the general Markov chains [20]. However, derivative constraints are the most common ones. Thus, we will more deeply discover the intrinsic laws in derivative constraints. Further, we will show that only by applying the derivative constraints is it possible to solve most of the Markov chains such as the trees; see the next section.In particular, the most useful and commonly used constraints are the first three ones.Corollary 4.
The following equations hold:(8)c1=∑j∈Cπj∑i∈Oqji,c2=∑j∈Cπj∑i∈Oqji2,c3=-∑s∈C∑j∈Cπsqsj∑l∈Oqsl∑i∈Oqji.In particular, a single state i has a more simple and visual form of cn, and by far the most common and convenient are those for a single state.Corollary 5.
Observing a single statei, one can get the following equations for a tree: (9)c1=∑j≠iπjqji,c2=∑j≠iπjqji2,c3=∑j≠iπjqji2qj,c4=∑j≠iπjqji2∑s∈Cqjsqsj,c2s+1=∑j≠iπjqji2∑a1,…,as-1∈Cqja1qa1a2⋯qas-2as-1qas-1qas-1as-2⋯qa2a1qa1j,c2s+2=∑j≠iπjqji2∑a1,…,as∈Cqja1qa1a2⋯qas-1asqasas-1⋯qa2a1qa1j.The right-hand side of the first equation gives a sum over all exit rate flows for state i because of πjqji=πiqij. Conditional upon the first equation, the second and the third one are obvious. The expression within the bracket of c2s+1 (resp. c2s+2) is the sum over rates of possible (2s-1)-step (resp., 2s-step) transitions departing from a state j, having a direct transition to i, and returning to itself. Those possible transitions imply the intrinsic relationships to Qcc so that most transitions can be identified by those hitting PDFs.By the end of this section, we show that the abovecn(n≥1) are known from the required PDFs at O and follow from Lemma 6. First of all, Corollary 2 shows that qi=1/Eσ, where Eσ is the expected sojourn time for state i. Corollary 5 shows that c1=∑j≠iπjqji=∑j≠iπiqij=πiqi. In addition, c1=(1-πi)d1. It suffices to yield πi=d1/(qi+d1)=c1Eσ, which implies the following lemma.Lemma 6.
The PDFs of sojourn time and hitting time at a single statei show that(10)qi=1Eσ,πi=d1qi+d1=c1Eσ.For observations at O, one can obtain the corresponding dn. Thus, (6) shows that cn(n≥1) is known, which is equal to dn times a known constant πc⊤1 from the observation at O. The reason is as follows. Lemma 6 shows that, based on statistics for a single state i, one can obtain by its PDF πi for any i∈O, followed by cn=πc⊤1dn=1-∑i∈Oπidn(n≥1).


## 3. Solutions to Trees

As stated in the Introduction, the tree is a very important extension of the star graph and line graph and represents one of the two classes of topologies. It is known that all Markov chains on trees are reversible [21]. Thus, SIMC on trees will be exploited in this section, although some of them are still not applied in real systems. In this letter, the term “tree” refers to a connected tree. For a Markov chain on a tree with vertices v1,v2,…,vm and with a TRM Q=(qij), its state space is composed of the vertices {v1,…,vm}, an edge between vertex vi and vertex vj implies the nonzero transition rates qij and qji, and qij/qi is the probability of a transition from vi to vj.It is concluded that all Markov chains on trees are identified by our approach. There are various kinds of trees, so we cannot provide individual proofs and algorithms. Without loss of generality, a complete binary tree is provided to show a general proof and solution. According to the classification of Wolfram MathWorld, there are many valid and specific trees: Banana Tree, Cross Graph, E Graph, Fork Graph, Firecracker Graph, H Graph, Spider Graph, and so forth. Cross Graph, E Graph, Fork Graph, H Graph, and Spider Graph can be conformationally viewed as a Star-Branch Graph (a special tree) which can be identified by the algorithms in earlier publications [19, 20]. Double-Star Graph, Banana Tree, and Firecracker Graph are three particular and regular models of them. For demonstration on solutions of specific trees, those three trees will also be addressed as representatives of trees.It is mentioned that, for SIMC on trees, the greatest contribution should be to discover the fundamental way and the corresponding algorithm to identify the TRM due to the challenge of performing the reverse operation as stated earlier.


### 3.1. General Conclusions on the Tree

At the start of this subsection, we present several useful conclusions from the derivative constraints which are convenient to determine the transition rates of Markov chain on trees as the first step.Lemma 7.
For a subchain on a tree such as in Figure1, the following conclusions hold.
(i) One can obtain the quantitiesπi,πj,qi=qij,qj,qji at least from the sojourn and hitting time PDFs at state i; in other words, πi,πj,qi=qij,qj,qji at least can be expressed in terms of real functions of Eσ, c1, c2, and c3.
(ii) Further, one can obtainπi,πj,qi=qij,qj,qji and qk, qjk, qkj, and πk at least from the sojourn and hitting time PDFs at state i, provided that the transitions between j and its other children i1,…,in, that is, qs,j and qj,s for any s∈{i1,…,in}, are all known or have been identified. That is to say, πi,πj,qi=qij,qj,qji and qk, qjk, qkj, and πk at least can be expressed in terms of real functions of Eσ,c1,…,c5 and qs,j,qj,s (s∈{i1,…,in}).Figure 1
Schematic plot of a subchain on a tree.i,i1,…,in are leaves and all children of state j; j,j1,…,jm are all children of state k.Proof.
(i) Firstly,πi,qi=qij are easy to get by Lemma 6. Secondly, by Corollary 5,(11)c1=πjqji,c2=πjqji2,c3=πjqji2qj.Thus,(12)qji=c2c1,πj=c1qji=c12c2,qj=c3c2,which imply the first assertion.
(ii) On the basis of (i), one needs only to find out the algorithm to obtainqk, qjk, qkj, and πk. For ease of exposition, set the constants as X=∑s=i1inqjs, Y=∑s=i1inqjsqsj, and Z=∑s=i1inqjsqsqsj since qs=qs,j and qj,s are all known for any s∈{i1,…,in}.
Firstly, one has(13)qjk=qj-qji-∑s=i1inqjs=c3c2-c2c1-∑s=i1inqjs=c3c2-c2c1-X.Secondly, by Corollary 5,(14)c4=πjqji2qj2+qjkqkj+∑s=i1inqjsqsj,c5=πjqji2qj3+qjkqkqkj+2qjqjkqkj+∑s=i1in2qjqjsqsj+qjsqsqsj.It follows that(15)qkj=c4/c2-qj2-∑s=i1inqjsqsjqjk=c4/c2-c32/c22-∑s=i1inqjsqsjc3/c2-c2/c1-∑s=i1inqjs=c4/c2-c32/c22-∑s=i1inqjsqsjc3/c2-c2/c1-X,qk=c5/c2-qj3-∑s=i1in2qjqjsqsj+qjsqsqsjqjkqkj-2qj=c5/c2-c33/c23-∑s=i1in2c3/c2qjsqsj+qjsqsqsjc4/c2-∑s=i1inqjsqsj-c32/c22-2c3c2=c5/c2-c33/c23-2c3/c2Y+Zc4/c2-c32/c22-Y-2c3c2.Finally, by reversibility, it easily follows that(16)πk=πjqjkqkj=c12/c2c3/c2-c2/c1-∑s=i1inqjs2c4/c2-c32/c22-∑s=i1inqjsqsj=c12/c2c3/c2-c2/c1-X2c4/c2-c32/c22-Y,which completes the proof.Lemma 8.
A subtree such as that in Figure2 is considered, in which im is the root, i1,…,im-1 are the leftmost children, and i1,i11,…,i1n1 are leaves as all children of state i2. Let Dk denote the descendants of state ik for k=1,…,m-1. For example, D1 is empty and D2={i11,…,i1n1}.
One can obtainπs,πs,qs,qst,qts(s,t=i1,i2,…,im) from the sojourn and hitting time PDFs at state i1, provided that the transitions between ik and its descendants in Dk for any k(=2,3,…,m-1) are all known or have been identified.Figure 2
Schematic plot of a subtree.i,i11,…,i1n1 are leaves and all children of state i2; i2,i21,…,i2n2 are all children of state i3; im is the root.Proof.
Firstly, one can obtainπi1,πi2,πi3,qi1=qi1,i2,qi2,qi3,qi2,i1,qi2,i3,qi3,i2 according to (ii) of Lemma 7.
Secondly,qi3,i4=qi3-qi3,i2-∑s=1n2qi3,is, and by Corollary 5, (17)c6=πi2qi2,i12qi2,i3qi3,i4qi4,i3qi3,i2+∑a1,a2∈D3∪i3∖i1qi2,a1qa1,a2qa2,a1qa1,i2,(18)c7=πi2qi2,i12qi2,i3qi3,i4qi4+qi3+qi2qi4,i3qi3,i2+∑a1,a2,a3∈D3∪i3∖i1qi2,a1qa1,a2qa3qa2,a1qa1,i2.Obviously, only the bold part is unknown in (17). Thus, one can determine qi4,i3 by (17). Then, only the bold part is unknown in (18), and qi4 can be determined by (18). Furthermore, πi4=πi3qi3,i4/qi4,i3.
Finally, by induction, it is not difficult to verify thatπs,qs,qst,qts(s,t=i5,i6,…,im) can be identified by the subsequent c8,c9,…,c2m-2,c2m-1.
The proof is completed.Remark 9.
The above conclusion is true by observation atis for any s=i1,i2,…,in1 provided that the transitions between i2 and its other descendants are all known or have been identified.Lemmas7 and 8 show that if a state j in a tree has n children and the transitions between states j and n-1 of the n children as well as the descendants of such n-1 children are all known or have been identified, then the transitions between state j, the nth child (say i), and the parent can be identified by the PDFs of sojourn and hitting time at the nth child (i.e., state i).


### 3.2. Main Results on Trees

Recall the statement in the Introduction; it is trivial to identify the TRM of an underlying Markov chain provided that every state of this chain is observed. People hope that the number of states observed is as few as possible. But there is no strict criterion for determining how many states are observed to use for a general model other than simplicity and ease of solution. However, there is no doubt that it is also of questionable significance to finish it if the number is more than half of the whole chain. Thus, we impose a mild restriction on the number of observed states such that it is smaller than or equal to half of the whole chain.First of all, a solution is first provided to complete the binary tree, in which all interior nodes have two children and all leaves have the same depth or same level.Theorem 10.
If the initial distribution of a Markov chain on a complete binary tree is the equilibrium distribution, then this tree can be identified by the PDFs of the sojourn time and hitting time for all leaves.Proof.
Consider a complete binary tree with a depth ofh; it has 2h leaves at the last level h and has 2h-1 nonleaf nodes (including one root).
Now, let us use mathematical induction to prove these facts as follows.
Step  1.We prove the case with 2 levels. For the convenience of expression, let 1–4 be the leaf from the left to the right at the last level, 5-6 be the node from the left to the right at the former level, and 7 be the root (see Figure 3). Let πi be the corresponding equilibrium distribution for state i for i=1,2,…. Firstly, according to Lemma 6, one can obtain π1,…,π4, and q1=q15, q2=q25, q3=q36, and q4=q46 by observation at states 1–4. Secondly, (i) of Lemma 7 implies that q5, q6, q51, q52, q63, and q64 can be solved. Thus, one has q57=q5-q51-q52 and q67=q6-q63-q64.
By observation at state1 (resp., state 3), according to Corollary 5, one has c4=π5(q51)2[q52+q52q25+q57q75] (resp., c4=π6(q63)2[q62+q64q46+q67q76]) and c5=π5(q51)2[q52q2q25+q52q25q5+q57q75q5+q57q7q75]. Finally, one gets q75 (resp. q76) and q7 by (ii) of Lemma 7. Those complete the proof of 2 levels.
Step  2.We suppose that this claim is true for any complete binary tree with k(≥2) levels. For a complete binary tree with k+1 levels, we then show it is correct as follows. At this point, a complete binary tree with k levels can be viewed as a left or right child. This means that all transition rates in two complete binary trees with k levels can be identified by observation at all leaves between 1 and 2h+1.
For conciseness of notation, letLk (resp. Lk-1) be a subtree belonging to the left child in the complete binary tree with k+1 (resp., k) levels, and let 0-(k+1) be the number of the leftmost nodes at each level from the bottom to the top in such complete binary tree with k+1 levels.
Firstly, by observation at state0, according to Corollary 5, one has(19)c2k+1=π1q102∑a1,…,ak-1≠0∈Lkq1a1qa1a2⋯qak-2ak-1qak-1qak-1ak-2⋯qa2a1qa11=π1q102∑a1,…,ak-1≠0∈Lk-1q1a1qa1a2⋯qak-2ak-1qak-1qak-1ak-2⋯qa2a1qa11+π1q102q12q23⋯qk-1,kqkqk-1,k-2⋯q32q21.By inductive assumptions, there is only one unknown qk in (19). Thus, qk can be determined. Again by inductive assumptions, one can obtain qk,k+1=qk-qk,k-1-qk,s (where s denotes the right child of the node k).
Analagous to the above, one can getqk+1,k by(20)c2k+2=π1q102∑a1,…,ak≠0∈Lkq1a1qa1a2⋯qak-1akqakak-1⋯qa2a1qa11=π1q102∑a1,…,ak≠0∈Lk-1q1a1qa1a2⋯qak-1akqakak-1+π1q102q12q23⋯qk,k+1qk+1,k⋯q32q21.Thus, qk+1,k can be determined by (20).
Those imply that all transition rates from the left subtree (for the tree withk+1 levels) can be identified by observations at the first 2k-1 leaves.
Secondly, one can identify the rest (i.e., right part) of the tree withk+1 levels by duplicate method of the left part.
These have proved that the conclusions of induction are true for a complete binary tree withk+1 levels.
As a matter of fact, this theorem can also be proved simply by Lemma8.Figure 3
Schematic plot of a complete binary tree with two levels.1 and 2 are leaves and two children of state 5; 3 and 4 are leaves and two children of state 6; state 7 is the root.Remark 11.
This proof shows the corresponding algorithm to determine all transition rates. The solution by observation at all leaves is satisfied by the mild restriction on the number of observed states, although the number of leaves is bigger than the number of nonleaf nodes by one. Because it also can be identified by observation at any2h-1 of those 2h leaves, for example, without loss of generality, assume that 1–3 are observable for a tree in Figure 3; one can obtain q1=q15,q51,q2=q25,q52,q5,q57,q7,q75,π1,π2,π5,π7 by observations at 1 and 2 and q3=q36,q63,q6,π3,π6 by observations at 3 and then obtain q76,q67,q6 by observation at 1 or 2; thus, q64=q6-q67-q63, π4=1-π1-π2-π3-π5-π6-π7, and q46=π6q64/π4. If the number of all leaves is less than that of all nonleaf nodes for a tree, such as a tree in which many nodes have only one child, then this solution is very valid. These assertions are valid to n-tree later.One can carry this line of argument a bit further to obtain the following result.Theorem 12.
If the initial distribution of a Markov chain onn-tree is the equilibrium distribution, then this tree can be identified by the PDFs of the sojourn time and hitting time for all leaves.One may proceed as previously explained to obtain a more general conclusion for the tree.Theorem 13.
If the initial distribution of a Markov chain on a tree is the equilibrium distribution, then this tree can be identified by the PDFs of the sojourn time and hitting time for all leaves.Theoretically, the transition rates about statei in a tree can be calculated by PDFS at any leaf from the descendants. However, the one from the shortest path should be optimal to minimize the error propagation.Furthermore, identification by observation at leaves is just one of the solutions for Markov chains on trees. There are also other solutions for particular trees; for example, the number of leaves is bigger than the number of nonleaf nodes by one.


### 3.3. Solutions to Special Trees

In this subsection, Double-Star Graph, Banana Tree, and Firecracker Tree, as representatives of trees, will be addressed for demonstration to solutions of specific trees.


#### 3.3.1. Double-Star Graph

Consider a Double-Star Graph Markov chain{Xt;t≥0} (see Figure 4), where the two central states O1 and O2 are observable states. The transition rate matrix is given as follows: (21)Q=q0q01q02⋯q0,M-1q0,M00⋯0q10q10⋯0000⋯0q200q2⋯0000⋯0⋮⋮⋮⋱⋮⋮⋮⋮⋱⋮qM-1,000⋯qM-1000⋯0qM,000⋯0qMqM,M+1qM,M+2⋯qM,N000⋯0qM+1,MqM+10⋯0000⋯0qM+2,M0qM+2⋯0⋮⋮⋮⋱⋮⋮⋮⋮⋱⋮000⋯0qN,M00⋯qN.One can observe the two central states 0=O1∈O1 and M=O2∈O2.Figure 4
Schematic plot of Markov chain on a Double-Star Graph.For the conciseness of notation, we denotei=Ci(i=1,…,M-1), j=Cj(j=M+1,…,N), and 0=O1, M=O2. Thus, the state space is simple for S={0,1,…,M-1,M,M+1,…,N} and the transition rates qij are nonzero only for i∈0,M or j∈0,M. Thus, one intends to derive qi0, q0i for all i=1,…,M-1 and qjM, qMj for all j=M+1,…,N, as well as q0M, qM0. We set (22)π0=1+q0MqM0+∑i=1M-1q0iqi0+∑j=M+1NqMjqjM-1,πi=π0q0iqi0,1≤i≤M-1;πj=π0q0MqMjqjMqM0,M+1≤j≤N;πM=π0q0MqM0.Then, {π0,…,πM-1,πM,πM+1,…,πN} is the equilibrium distribution and the reversibility in (1) is satisfied.From now on, we investigate the algorithm of how to identify such chain.Firstly, we observe state0 and let σ(0) be its sojourn time. It follows from Corollary 2 that(23)q0=1Eσ0,π0=c10Eσ0.Secondly, we observe the state M and let σ(M) be its sojourn time. It follows from Corollary 2 that(24)qM=1EσM,πM=c1MEσM.Finally, we observe the two states 0 and M, that is, O={0,M}  (C=S-O). Let τ(0,M) (resp., σ(0,M)) be the hitting time (resp., sojourn time) of O. According to Theorem 1, one can get the following lemma.Lemma 14.
The PDF of the hitting timeτ(0,M) is, for t>0, as follows: (25)fτt=∑i=1M-1γiexp⁡-αit+∑j=M+1Nγjexp⁡-αjt,where(26)αi=qi0=qi,1≤i≤M-1;αj=qjM=qj,M+1≤j≤N;γi=π01-π0+πMq0i,1≤i≤M-1;γj=πM1-π0+πMqMj,M+1≤j≤N.Proof.
Here,C={1,…,M-1,M+1,…,N}. So,(27)Qcc=q10⋯000⋯00q2⋯000⋯0⋮⋮⋱⋮⋮⋮⋱⋮00⋯qM-100⋯000⋯0qM+10⋯000⋯00qM+2⋯0⋮⋮⋱⋮⋮⋮⋱⋮00⋯000⋯qN.According to the proof of Theorem 1, -αi=-qi(1≤i≠M≤N) are all real eigenvalues of Qcc, and(28)Pτ0,M>t=∑i≠0,Mπi1-π0+πM∑j≠0,Mpijct=11-π0+πM∑i=1M-1πiexp⁡-αit+∑j=M+1Nπjexp⁡-αjt.Performing the differential calculation in (28), by reversibility,(29)γi=πiαi1-π0+πM=πiqi01-π0+πM=π01-π0+πMq0i,1≤i≤M-1;γj=πjαj1-π0+πM=πjqjM1-π0+πM=πM1-π0+πMqMj,M+1≤j≤N.This completes the proof.The following theorem is an immediate consequence of Lemma14.Theorem 15.
If the initial distribution of the Markov chain with Double-Star Graph in Figure4 is the equilibrium distribution, then it can be identified by the PDFs of the sojourn time and hitting time for the two central states O1 and O2.Proof.
Firstly,q0,π0 and qM,πM can be obtained by (23) and (24). Secondly, according to Lemma 14, qi0(1≤i≤M-1) and qjM(M+1≤j≤N) can be obtained by the first two assertions of (26), because all αi and γi are known from the PDF in Lemma 14 by observation of states 0 and M. Finally, q0i(1≤i≤M-1) and qMj(M+1≤j≤N) can be followed by the final two assertions of (26).Note that this proof shows the corresponding algorithm to determine all transition rates of such Double-Star Graph chain. In the course of calculation, one can easily derive real roots from comparatively accurate PDFs.


#### 3.3.2. Banana Tree Graph

An (n,k)-banana tree, say Bn,k, as defined by Chen et al. [23], is a graph obtained by connecting one leaf of each of n copies of a k-star graph with a single root vertex that is distinct from all the stars. Thus, there are n(k-2) leaves, 2n nodes, and 1 root. This is one of the regular trees.Consider a Markov chain{Xt;t≥0} with Banana Tree Graph Bn,k (see Figure 5).Figure 5
Schematic plot of banana trees (adapted from Wolfram MathWorld).Fork=2 or k=3, it is degenerated into the special case of Star-Branch Graph.Fork=4, there are two leaves for each k-star graph. It is implied that the number 2n of all leaves is less than 1, compared with 2n+1 of all nonleaf nodes. So, observation at all leaves is valid. According to Theorem 13, a normal solution is as follows.Theorem 16.
If the initial distribution of a Markov chain with Banana Tree GraphBn,k(k≤4) is the equilibrium distribution, then it can be identified by the PDFs of the sojourn time and hitting time for all leaves.Fork≥5, the number of all leaves is bigger than that of nonleaf nodes. An optional solution is as follows.Theorem 17.
If the initial distribution of a Markov chain with Banana Tree GraphBn,k(k≥5) is the equilibrium distribution, then it can be identified by the PDFs of the sojourn time and hitting time for the root state and all node states, that is, all nonleaf states.Proof.
For ease of exposition, suppose thatr is the root (see the previous introduction of banana tree in this subsection) of this tree and that o is the central state, l is the leaf, and s are the others at each k-star graph, respectively. Firstly, the corresponding qr, πr, qo, πo, qs, and πs can be obtained by each nonleaf state. Secondly, according to the proof of Double-Star Graph, all ql=qlo, qol can be obtained by observation at all nonleaf states, because their Qcc is similar to that of observation at {O1,O2} for Double-Star Graph. Finally, for each k-star graph, qos=qo-∑l‍qol, qso=πoqos/πs, qsr=qs-qso, and qrs=πsqsr/πr.


#### 3.3.3. Firecracker Graph

An (n,k)- firecracker, say Fn,k, is a graph obtained by the concatenation of n  k-stars by linking one leaf from each [23].A Markov chain{Xt;t≥0} with Firecracker Graph Fn,k (see Figure 6) is provided.Figure 6
Schematic plot of firecracker graphs (adapted from Wolfram MathWorld).Fork=2 or k=3, it is degenerated into the special tree which is similar, but not completely equivalent, to a Star-Branch Graph.Fork≤4, there are two leaves for each k-star graph. It is implied that the number 2n of all leaves is identical to that of all nonleaf nodes. So, observation at all leaves is valid. According to Theorem 13, a normal solution for k≤4 is as follows.Theorem 18.
If the initial distribution of a Markov chain with Firecracker GraphFn,k(k≤4) is the equilibrium distribution, then it can be identified by the PDFs of the sojourn time and hitting time for all leaves.Fork≥5, the number of all leaves is bigger than that of nonleaf nodes. Following the technique of proof in Theorem 17, it is easy to verify such optional solution.Theorem 19.
If the initial distribution of a Markov chain with Firecracker GraphFn,k(k≥5) is the equilibrium distribution, then it can be identified by the PDFs of the sojourn time and hitting time for all nonleaf states.


### 3.4. Numerical Example

To demonstrate how to apply our algorithms to real data, we present a numerical example here. As we mentioned before, we focus on the final step and then we omit the preprocessing of data. Thus, the data we have is the observed PDFs of sojourn time and hitting time at each leaf. Based upon these data, we could find all the transition rates of this tree.Example 1.
The model of a Markov chain is a binary tree in Figure3 with the true transition rates matrix Q=(qij)S×S given by(30)Q=-1000010000-2500250000-3000300000-15015051500-500300030500-1002000009060-150.We can divide the calculation into two steps: fitting sojourn time and hitting time histogram and transition rates estimation.Step 1 (sojourn time and hitting time histogram estimate).
Suppose that we have obtained the PDFs by fitting (simulating) as follows:(31)fτ1t=0.002032e-186.015025t+0.002801e-107.093861t+0.031748e-43.239654t+0.530183e-0.537764t+0.121303e-9.103660t+0.000006e-24.010036tt≥0,(32)fτ2t=0.018133e-185.792813t+0.023965e-106.751426t+1.024495e-1.089438t+0.265559e-8.032879t+0.669767e-30.000000t+0.091104e-23.333445tt≥0,(33)fτ3t=0.098146e-185.213916t+1.004750e-98.503674t+0.063878e-43.082231t+2.304378e-2.701274t+0.960962e-7.138694t+0.001383e-13.360211tt≥0,(34)fτ4t=0.425895e-185.406369t+3.907008e-101.419933t+0.117730e-43.639996t+2.473349e-3.548045t+3.456848e-18.354848t+0.897366e-12.630809tt≥0,(35)fσ1t=25e-25t,fσ2t=10e-10t,fσ3t=15e-50t,fσ4t=30e-50tt≥0,where fσ(i)(t) (resp., fτ(i)(t)) is the PDF of sojourn time (resp., hitting time) at the state i for i=1,2,3,4.Step 2 (transition rate calculations).
Firstly, by (35) and (10), we have(36)q1=q15=10,q2=q25=25,q3=q36=30,q4=q46=15.For state 1, let (37)α1=186.015025,α2=107.093861,α3=43.239654,α4=0.537764,α5=9.103660,α6=24.010036,γ1=0.002032,γ2=0.002801,γ3=0.031748,γ4=0.530183,γ5=0.121303,γ6=0.000006.Because d1(1)=∑i=16γi=0.688073, hence π1=d1(1)/q1+d1(1)=0.064378, 1-π1=0.935622. Since (38)dn1=∑i=16γiαin-1,cn1=1-π1dn1=0.935622dn,we have (39)c11=0.643777,c21=3.218884,c31=160.944206,c41=17945.278970.Similarly, we can get for states 2, 3, and 4, respectively, (40)π2=0.077253,π3=0.128755,π4=0.429185,c12=1.931330,c22=28.969957,c32=1448.497854,c42=152092.274678,c13=3.862661,c23=115.879828,c33=11587.982833,c43=1384763.948498,c14=6.437768,c24=321.888412,c34=32188.841202,c44=3894849.785408.Thus, we can obtain by the algorithm (proof) of Theorem 10 that(41)q51=c21c11=5.000000,q63=c23c13=29.999999,q52=c22c12=15.000000,q64=c24c14=50.000000,q5=c31c21=50.000000,q6=c33c23=100.000000,π5=c112c21=0.128755,π6=c132c23=0.128755,q57=q5-q51-q52=30.000000,q67=q6-q63-q64=20.000000,q75=c41/c21-q52q25-q52c31/c21-c21/c11-q52=90.000007,q76=c43/c23-q64q46-q62c33/c23-c23/c13-q64=59.999999,π7=1-∑i=16πi=0.042919.Thus, the TRM of {Xt:t≥0} is identified as follows:(42)Q=-1000010000-2500250000-3000300000-15015051500-500300029.999999500-99.99999920000090.00000759.999999-150.000006.Comparing matrix (42) with the original Q-matrix (30), it is not difficult to find that our approach is very efficient under the condition that we obtain an accurate PDF of the hitting time and sojourn time at each leaf.Note that ifQ is symmetric, then the corresponding algorithms are also valid. As a matter of fact, the calculation can be more concise due to the identical equilibrium distributions. In addition, it also can be identified by observations at any three states of four leaves as stated in Remark 11 of Theorem 10.


## 3.1. General Conclusions on the Tree

At the start of this subsection, we present several useful conclusions from the derivative constraints which are convenient to determine the transition rates of Markov chain on trees as the first step.Lemma 7.
For a subchain on a tree such as in Figure1, the following conclusions hold.
(i) One can obtain the quantitiesπi,πj,qi=qij,qj,qji at least from the sojourn and hitting time PDFs at state i; in other words, πi,πj,qi=qij,qj,qji at least can be expressed in terms of real functions of Eσ, c1, c2, and c3.
(ii) Further, one can obtainπi,πj,qi=qij,qj,qji and qk, qjk, qkj, and πk at least from the sojourn and hitting time PDFs at state i, provided that the transitions between j and its other children i1,…,in, that is, qs,j and qj,s for any s∈{i1,…,in}, are all known or have been identified. That is to say, πi,πj,qi=qij,qj,qji and qk, qjk, qkj, and πk at least can be expressed in terms of real functions of Eσ,c1,…,c5 and qs,j,qj,s (s∈{i1,…,in}).Figure 1
Schematic plot of a subchain on a tree.i,i1,…,in are leaves and all children of state j; j,j1,…,jm are all children of state k.Proof.
(i) Firstly,πi,qi=qij are easy to get by Lemma 6. Secondly, by Corollary 5,(11)c1=πjqji,c2=πjqji2,c3=πjqji2qj.Thus,(12)qji=c2c1,πj=c1qji=c12c2,qj=c3c2,which imply the first assertion.
(ii) On the basis of (i), one needs only to find out the algorithm to obtainqk, qjk, qkj, and πk. For ease of exposition, set the constants as X=∑s=i1inqjs, Y=∑s=i1inqjsqsj, and Z=∑s=i1inqjsqsqsj since qs=qs,j and qj,s are all known for any s∈{i1,…,in}.
Firstly, one has(13)qjk=qj-qji-∑s=i1inqjs=c3c2-c2c1-∑s=i1inqjs=c3c2-c2c1-X.Secondly, by Corollary 5,(14)c4=πjqji2qj2+qjkqkj+∑s=i1inqjsqsj,c5=πjqji2qj3+qjkqkqkj+2qjqjkqkj+∑s=i1in2qjqjsqsj+qjsqsqsj.It follows that(15)qkj=c4/c2-qj2-∑s=i1inqjsqsjqjk=c4/c2-c32/c22-∑s=i1inqjsqsjc3/c2-c2/c1-∑s=i1inqjs=c4/c2-c32/c22-∑s=i1inqjsqsjc3/c2-c2/c1-X,qk=c5/c2-qj3-∑s=i1in2qjqjsqsj+qjsqsqsjqjkqkj-2qj=c5/c2-c33/c23-∑s=i1in2c3/c2qjsqsj+qjsqsqsjc4/c2-∑s=i1inqjsqsj-c32/c22-2c3c2=c5/c2-c33/c23-2c3/c2Y+Zc4/c2-c32/c22-Y-2c3c2.Finally, by reversibility, it easily follows that(16)πk=πjqjkqkj=c12/c2c3/c2-c2/c1-∑s=i1inqjs2c4/c2-c32/c22-∑s=i1inqjsqsj=c12/c2c3/c2-c2/c1-X2c4/c2-c32/c22-Y,which completes the proof.Lemma 8.
A subtree such as that in Figure2 is considered, in which im is the root, i1,…,im-1 are the leftmost children, and i1,i11,…,i1n1 are leaves as all children of state i2. Let Dk denote the descendants of state ik for k=1,…,m-1. For example, D1 is empty and D2={i11,…,i1n1}.
One can obtainπs,πs,qs,qst,qts(s,t=i1,i2,…,im) from the sojourn and hitting time PDFs at state i1, provided that the transitions between ik and its descendants in Dk for any k(=2,3,…,m-1) are all known or have been identified.Figure 2
Schematic plot of a subtree.i,i11,…,i1n1 are leaves and all children of state i2; i2,i21,…,i2n2 are all children of state i3; im is the root.Proof.
Firstly, one can obtainπi1,πi2,πi3,qi1=qi1,i2,qi2,qi3,qi2,i1,qi2,i3,qi3,i2 according to (ii) of Lemma 7.
Secondly,qi3,i4=qi3-qi3,i2-∑s=1n2qi3,is, and by Corollary 5, (17)c6=πi2qi2,i12qi2,i3qi3,i4qi4,i3qi3,i2+∑a1,a2∈D3∪i3∖i1qi2,a1qa1,a2qa2,a1qa1,i2,(18)c7=πi2qi2,i12qi2,i3qi3,i4qi4+qi3+qi2qi4,i3qi3,i2+∑a1,a2,a3∈D3∪i3∖i1qi2,a1qa1,a2qa3qa2,a1qa1,i2.Obviously, only the bold part is unknown in (17). Thus, one can determine qi4,i3 by (17). Then, only the bold part is unknown in (18), and qi4 can be determined by (18). Furthermore, πi4=πi3qi3,i4/qi4,i3.
Finally, by induction, it is not difficult to verify thatπs,qs,qst,qts(s,t=i5,i6,…,im) can be identified by the subsequent c8,c9,…,c2m-2,c2m-1.
The proof is completed.Remark 9.
The above conclusion is true by observation atis for any s=i1,i2,…,in1 provided that the transitions between i2 and its other descendants are all known or have been identified.Lemmas7 and 8 show that if a state j in a tree has n children and the transitions between states j and n-1 of the n children as well as the descendants of such n-1 children are all known or have been identified, then the transitions between state j, the nth child (say i), and the parent can be identified by the PDFs of sojourn and hitting time at the nth child (i.e., state i).


## 3.2. Main Results on Trees

Recall the statement in the Introduction; it is trivial to identify the TRM of an underlying Markov chain provided that every state of this chain is observed. People hope that the number of states observed is as few as possible. But there is no strict criterion for determining how many states are observed to use for a general model other than simplicity and ease of solution. However, there is no doubt that it is also of questionable significance to finish it if the number is more than half of the whole chain. Thus, we impose a mild restriction on the number of observed states such that it is smaller than or equal to half of the whole chain.First of all, a solution is first provided to complete the binary tree, in which all interior nodes have two children and all leaves have the same depth or same level.Theorem 10.
If the initial distribution of a Markov chain on a complete binary tree is the equilibrium distribution, then this tree can be identified by the PDFs of the sojourn time and hitting time for all leaves.Proof.
Consider a complete binary tree with a depth ofh; it has 2h leaves at the last level h and has 2h-1 nonleaf nodes (including one root).
Now, let us use mathematical induction to prove these facts as follows.
Step  1.We prove the case with 2 levels. For the convenience of expression, let 1–4 be the leaf from the left to the right at the last level, 5-6 be the node from the left to the right at the former level, and 7 be the root (see Figure 3). Let πi be the corresponding equilibrium distribution for state i for i=1,2,…. Firstly, according to Lemma 6, one can obtain π1,…,π4, and q1=q15, q2=q25, q3=q36, and q4=q46 by observation at states 1–4. Secondly, (i) of Lemma 7 implies that q5, q6, q51, q52, q63, and q64 can be solved. Thus, one has q57=q5-q51-q52 and q67=q6-q63-q64.
By observation at state1 (resp., state 3), according to Corollary 5, one has c4=π5(q51)2[q52+q52q25+q57q75] (resp., c4=π6(q63)2[q62+q64q46+q67q76]) and c5=π5(q51)2[q52q2q25+q52q25q5+q57q75q5+q57q7q75]. Finally, one gets q75 (resp. q76) and q7 by (ii) of Lemma 7. Those complete the proof of 2 levels.
Step  2.We suppose that this claim is true for any complete binary tree with k(≥2) levels. For a complete binary tree with k+1 levels, we then show it is correct as follows. At this point, a complete binary tree with k levels can be viewed as a left or right child. This means that all transition rates in two complete binary trees with k levels can be identified by observation at all leaves between 1 and 2h+1.
For conciseness of notation, letLk (resp. Lk-1) be a subtree belonging to the left child in the complete binary tree with k+1 (resp., k) levels, and let 0-(k+1) be the number of the leftmost nodes at each level from the bottom to the top in such complete binary tree with k+1 levels.
Firstly, by observation at state0, according to Corollary 5, one has(19)c2k+1=π1q102∑a1,…,ak-1≠0∈Lkq1a1qa1a2⋯qak-2ak-1qak-1qak-1ak-2⋯qa2a1qa11=π1q102∑a1,…,ak-1≠0∈Lk-1q1a1qa1a2⋯qak-2ak-1qak-1qak-1ak-2⋯qa2a1qa11+π1q102q12q23⋯qk-1,kqkqk-1,k-2⋯q32q21.By inductive assumptions, there is only one unknown qk in (19). Thus, qk can be determined. Again by inductive assumptions, one can obtain qk,k+1=qk-qk,k-1-qk,s (where s denotes the right child of the node k).
Analagous to the above, one can getqk+1,k by(20)c2k+2=π1q102∑a1,…,ak≠0∈Lkq1a1qa1a2⋯qak-1akqakak-1⋯qa2a1qa11=π1q102∑a1,…,ak≠0∈Lk-1q1a1qa1a2⋯qak-1akqakak-1+π1q102q12q23⋯qk,k+1qk+1,k⋯q32q21.Thus, qk+1,k can be determined by (20).
Those imply that all transition rates from the left subtree (for the tree withk+1 levels) can be identified by observations at the first 2k-1 leaves.
Secondly, one can identify the rest (i.e., right part) of the tree withk+1 levels by duplicate method of the left part.
These have proved that the conclusions of induction are true for a complete binary tree withk+1 levels.
As a matter of fact, this theorem can also be proved simply by Lemma8.Figure 3
Schematic plot of a complete binary tree with two levels.1 and 2 are leaves and two children of state 5; 3 and 4 are leaves and two children of state 6; state 7 is the root.Remark 11.
This proof shows the corresponding algorithm to determine all transition rates. The solution by observation at all leaves is satisfied by the mild restriction on the number of observed states, although the number of leaves is bigger than the number of nonleaf nodes by one. Because it also can be identified by observation at any2h-1 of those 2h leaves, for example, without loss of generality, assume that 1–3 are observable for a tree in Figure 3; one can obtain q1=q15,q51,q2=q25,q52,q5,q57,q7,q75,π1,π2,π5,π7 by observations at 1 and 2 and q3=q36,q63,q6,π3,π6 by observations at 3 and then obtain q76,q67,q6 by observation at 1 or 2; thus, q64=q6-q67-q63, π4=1-π1-π2-π3-π5-π6-π7, and q46=π6q64/π4. If the number of all leaves is less than that of all nonleaf nodes for a tree, such as a tree in which many nodes have only one child, then this solution is very valid. These assertions are valid to n-tree later.One can carry this line of argument a bit further to obtain the following result.Theorem 12.
If the initial distribution of a Markov chain onn-tree is the equilibrium distribution, then this tree can be identified by the PDFs of the sojourn time and hitting time for all leaves.One may proceed as previously explained to obtain a more general conclusion for the tree.Theorem 13.
If the initial distribution of a Markov chain on a tree is the equilibrium distribution, then this tree can be identified by the PDFs of the sojourn time and hitting time for all leaves.Theoretically, the transition rates about statei in a tree can be calculated by PDFS at any leaf from the descendants. However, the one from the shortest path should be optimal to minimize the error propagation.Furthermore, identification by observation at leaves is just one of the solutions for Markov chains on trees. There are also other solutions for particular trees; for example, the number of leaves is bigger than the number of nonleaf nodes by one.


## 3.3. Solutions to Special Trees

In this subsection, Double-Star Graph, Banana Tree, and Firecracker Tree, as representatives of trees, will be addressed for demonstration to solutions of specific trees.


### 3.3.1. Double-Star Graph

Consider a Double-Star Graph Markov chain{Xt;t≥0} (see Figure 4), where the two central states O1 and O2 are observable states. The transition rate matrix is given as follows: (21)Q=q0q01q02⋯q0,M-1q0,M00⋯0q10q10⋯0000⋯0q200q2⋯0000⋯0⋮⋮⋮⋱⋮⋮⋮⋮⋱⋮qM-1,000⋯qM-1000⋯0qM,000⋯0qMqM,M+1qM,M+2⋯qM,N000⋯0qM+1,MqM+10⋯0000⋯0qM+2,M0qM+2⋯0⋮⋮⋮⋱⋮⋮⋮⋮⋱⋮000⋯0qN,M00⋯qN.One can observe the two central states 0=O1∈O1 and M=O2∈O2.Figure 4
Schematic plot of Markov chain on a Double-Star Graph.For the conciseness of notation, we denotei=Ci(i=1,…,M-1), j=Cj(j=M+1,…,N), and 0=O1, M=O2. Thus, the state space is simple for S={0,1,…,M-1,M,M+1,…,N} and the transition rates qij are nonzero only for i∈0,M or j∈0,M. Thus, one intends to derive qi0, q0i for all i=1,…,M-1 and qjM, qMj for all j=M+1,…,N, as well as q0M, qM0. We set (22)π0=1+q0MqM0+∑i=1M-1q0iqi0+∑j=M+1NqMjqjM-1,πi=π0q0iqi0,1≤i≤M-1;πj=π0q0MqMjqjMqM0,M+1≤j≤N;πM=π0q0MqM0.Then, {π0,…,πM-1,πM,πM+1,…,πN} is the equilibrium distribution and the reversibility in (1) is satisfied.From now on, we investigate the algorithm of how to identify such chain.Firstly, we observe state0 and let σ(0) be its sojourn time. It follows from Corollary 2 that(23)q0=1Eσ0,π0=c10Eσ0.Secondly, we observe the state M and let σ(M) be its sojourn time. It follows from Corollary 2 that(24)qM=1EσM,πM=c1MEσM.Finally, we observe the two states 0 and M, that is, O={0,M}  (C=S-O). Let τ(0,M) (resp., σ(0,M)) be the hitting time (resp., sojourn time) of O. According to Theorem 1, one can get the following lemma.Lemma 14.
The PDF of the hitting timeτ(0,M) is, for t>0, as follows: (25)fτt=∑i=1M-1γiexp⁡-αit+∑j=M+1Nγjexp⁡-αjt,where(26)αi=qi0=qi,1≤i≤M-1;αj=qjM=qj,M+1≤j≤N;γi=π01-π0+πMq0i,1≤i≤M-1;γj=πM1-π0+πMqMj,M+1≤j≤N.Proof.
Here,C={1,…,M-1,M+1,…,N}. So,(27)Qcc=q10⋯000⋯00q2⋯000⋯0⋮⋮⋱⋮⋮⋮⋱⋮00⋯qM-100⋯000⋯0qM+10⋯000⋯00qM+2⋯0⋮⋮⋱⋮⋮⋮⋱⋮00⋯000⋯qN.According to the proof of Theorem 1, -αi=-qi(1≤i≠M≤N) are all real eigenvalues of Qcc, and(28)Pτ0,M>t=∑i≠0,Mπi1-π0+πM∑j≠0,Mpijct=11-π0+πM∑i=1M-1πiexp⁡-αit+∑j=M+1Nπjexp⁡-αjt.Performing the differential calculation in (28), by reversibility,(29)γi=πiαi1-π0+πM=πiqi01-π0+πM=π01-π0+πMq0i,1≤i≤M-1;γj=πjαj1-π0+πM=πjqjM1-π0+πM=πM1-π0+πMqMj,M+1≤j≤N.This completes the proof.The following theorem is an immediate consequence of Lemma14.Theorem 15.
If the initial distribution of the Markov chain with Double-Star Graph in Figure4 is the equilibrium distribution, then it can be identified by the PDFs of the sojourn time and hitting time for the two central states O1 and O2.Proof.
Firstly,q0,π0 and qM,πM can be obtained by (23) and (24). Secondly, according to Lemma 14, qi0(1≤i≤M-1) and qjM(M+1≤j≤N) can be obtained by the first two assertions of (26), because all αi and γi are known from the PDF in Lemma 14 by observation of states 0 and M. Finally, q0i(1≤i≤M-1) and qMj(M+1≤j≤N) can be followed by the final two assertions of (26).Note that this proof shows the corresponding algorithm to determine all transition rates of such Double-Star Graph chain. In the course of calculation, one can easily derive real roots from comparatively accurate PDFs.


### 3.3.2. Banana Tree Graph

An (n,k)-banana tree, say Bn,k, as defined by Chen et al. [23], is a graph obtained by connecting one leaf of each of n copies of a k-star graph with a single root vertex that is distinct from all the stars. Thus, there are n(k-2) leaves, 2n nodes, and 1 root. This is one of the regular trees.Consider a Markov chain{Xt;t≥0} with Banana Tree Graph Bn,k (see Figure 5).Figure 5
Schematic plot of banana trees (adapted from Wolfram MathWorld).Fork=2 or k=3, it is degenerated into the special case of Star-Branch Graph.Fork=4, there are two leaves for each k-star graph. It is implied that the number 2n of all leaves is less than 1, compared with 2n+1 of all nonleaf nodes. So, observation at all leaves is valid. According to Theorem 13, a normal solution is as follows.Theorem 16.
If the initial distribution of a Markov chain with Banana Tree GraphBn,k(k≤4) is the equilibrium distribution, then it can be identified by the PDFs of the sojourn time and hitting time for all leaves.Fork≥5, the number of all leaves is bigger than that of nonleaf nodes. An optional solution is as follows.Theorem 17.
If the initial distribution of a Markov chain with Banana Tree GraphBn,k(k≥5) is the equilibrium distribution, then it can be identified by the PDFs of the sojourn time and hitting time for the root state and all node states, that is, all nonleaf states.Proof.
For ease of exposition, suppose thatr is the root (see the previous introduction of banana tree in this subsection) of this tree and that o is the central state, l is the leaf, and s are the others at each k-star graph, respectively. Firstly, the corresponding qr, πr, qo, πo, qs, and πs can be obtained by each nonleaf state. Secondly, according to the proof of Double-Star Graph, all ql=qlo, qol can be obtained by observation at all nonleaf states, because their Qcc is similar to that of observation at {O1,O2} for Double-Star Graph. Finally, for each k-star graph, qos=qo-∑l‍qol, qso=πoqos/πs, qsr=qs-qso, and qrs=πsqsr/πr.


### 3.3.3. Firecracker Graph

An (n,k)- firecracker, say Fn,k, is a graph obtained by the concatenation of n  k-stars by linking one leaf from each [23].A Markov chain{Xt;t≥0} with Firecracker Graph Fn,k (see Figure 6) is provided.Figure 6
Schematic plot of firecracker graphs (adapted from Wolfram MathWorld).Fork=2 or k=3, it is degenerated into the special tree which is similar, but not completely equivalent, to a Star-Branch Graph.Fork≤4, there are two leaves for each k-star graph. It is implied that the number 2n of all leaves is identical to that of all nonleaf nodes. So, observation at all leaves is valid. According to Theorem 13, a normal solution for k≤4 is as follows.Theorem 18.
If the initial distribution of a Markov chain with Firecracker GraphFn,k(k≤4) is the equilibrium distribution, then it can be identified by the PDFs of the sojourn time and hitting time for all leaves.Fork≥5, the number of all leaves is bigger than that of nonleaf nodes. Following the technique of proof in Theorem 17, it is easy to verify such optional solution.Theorem 19.
If the initial distribution of a Markov chain with Firecracker GraphFn,k(k≥5) is the equilibrium distribution, then it can be identified by the PDFs of the sojourn time and hitting time for all nonleaf states.


## 3.3.1. Double-Star Graph

Consider a Double-Star Graph Markov chain{Xt;t≥0} (see Figure 4), where the two central states O1 and O2 are observable states. The transition rate matrix is given as follows: (21)Q=q0q01q02⋯q0,M-1q0,M00⋯0q10q10⋯0000⋯0q200q2⋯0000⋯0⋮⋮⋮⋱⋮⋮⋮⋮⋱⋮qM-1,000⋯qM-1000⋯0qM,000⋯0qMqM,M+1qM,M+2⋯qM,N000⋯0qM+1,MqM+10⋯0000⋯0qM+2,M0qM+2⋯0⋮⋮⋮⋱⋮⋮⋮⋮⋱⋮000⋯0qN,M00⋯qN.One can observe the two central states 0=O1∈O1 and M=O2∈O2.Figure 4
Schematic plot of Markov chain on a Double-Star Graph.For the conciseness of notation, we denotei=Ci(i=1,…,M-1), j=Cj(j=M+1,…,N), and 0=O1, M=O2. Thus, the state space is simple for S={0,1,…,M-1,M,M+1,…,N} and the transition rates qij are nonzero only for i∈0,M or j∈0,M. Thus, one intends to derive qi0, q0i for all i=1,…,M-1 and qjM, qMj for all j=M+1,…,N, as well as q0M, qM0. We set (22)π0=1+q0MqM0+∑i=1M-1q0iqi0+∑j=M+1NqMjqjM-1,πi=π0q0iqi0,1≤i≤M-1;πj=π0q0MqMjqjMqM0,M+1≤j≤N;πM=π0q0MqM0.Then, {π0,…,πM-1,πM,πM+1,…,πN} is the equilibrium distribution and the reversibility in (1) is satisfied.From now on, we investigate the algorithm of how to identify such chain.Firstly, we observe state0 and let σ(0) be its sojourn time. It follows from Corollary 2 that(23)q0=1Eσ0,π0=c10Eσ0.Secondly, we observe the state M and let σ(M) be its sojourn time. It follows from Corollary 2 that(24)qM=1EσM,πM=c1MEσM.Finally, we observe the two states 0 and M, that is, O={0,M}  (C=S-O). Let τ(0,M) (resp., σ(0,M)) be the hitting time (resp., sojourn time) of O. According to Theorem 1, one can get the following lemma.Lemma 14.
The PDF of the hitting timeτ(0,M) is, for t>0, as follows: (25)fτt=∑i=1M-1γiexp⁡-αit+∑j=M+1Nγjexp⁡-αjt,where(26)αi=qi0=qi,1≤i≤M-1;αj=qjM=qj,M+1≤j≤N;γi=π01-π0+πMq0i,1≤i≤M-1;γj=πM1-π0+πMqMj,M+1≤j≤N.Proof.
Here,C={1,…,M-1,M+1,…,N}. So,(27)Qcc=q10⋯000⋯00q2⋯000⋯0⋮⋮⋱⋮⋮⋮⋱⋮00⋯qM-100⋯000⋯0qM+10⋯000⋯00qM+2⋯0⋮⋮⋱⋮⋮⋮⋱⋮00⋯000⋯qN.According to the proof of Theorem 1, -αi=-qi(1≤i≠M≤N) are all real eigenvalues of Qcc, and(28)Pτ0,M>t=∑i≠0,Mπi1-π0+πM∑j≠0,Mpijct=11-π0+πM∑i=1M-1πiexp⁡-αit+∑j=M+1Nπjexp⁡-αjt.Performing the differential calculation in (28), by reversibility,(29)γi=πiαi1-π0+πM=πiqi01-π0+πM=π01-π0+πMq0i,1≤i≤M-1;γj=πjαj1-π0+πM=πjqjM1-π0+πM=πM1-π0+πMqMj,M+1≤j≤N.This completes the proof.The following theorem is an immediate consequence of Lemma14.Theorem 15.
If the initial distribution of the Markov chain with Double-Star Graph in Figure4 is the equilibrium distribution, then it can be identified by the PDFs of the sojourn time and hitting time for the two central states O1 and O2.Proof.
Firstly,q0,π0 and qM,πM can be obtained by (23) and (24). Secondly, according to Lemma 14, qi0(1≤i≤M-1) and qjM(M+1≤j≤N) can be obtained by the first two assertions of (26), because all αi and γi are known from the PDF in Lemma 14 by observation of states 0 and M. Finally, q0i(1≤i≤M-1) and qMj(M+1≤j≤N) can be followed by the final two assertions of (26).Note that this proof shows the corresponding algorithm to determine all transition rates of such Double-Star Graph chain. In the course of calculation, one can easily derive real roots from comparatively accurate PDFs.


## 3.3.2. Banana Tree Graph

An (n,k)-banana tree, say Bn,k, as defined by Chen et al. [23], is a graph obtained by connecting one leaf of each of n copies of a k-star graph with a single root vertex that is distinct from all the stars. Thus, there are n(k-2) leaves, 2n nodes, and 1 root. This is one of the regular trees.Consider a Markov chain{Xt;t≥0} with Banana Tree Graph Bn,k (see Figure 5).Figure 5
Schematic plot of banana trees (adapted from Wolfram MathWorld).Fork=2 or k=3, it is degenerated into the special case of Star-Branch Graph.Fork=4, there are two leaves for each k-star graph. It is implied that the number 2n of all leaves is less than 1, compared with 2n+1 of all nonleaf nodes. So, observation at all leaves is valid. According to Theorem 13, a normal solution is as follows.Theorem 16.
If the initial distribution of a Markov chain with Banana Tree GraphBn,k(k≤4) is the equilibrium distribution, then it can be identified by the PDFs of the sojourn time and hitting time for all leaves.Fork≥5, the number of all leaves is bigger than that of nonleaf nodes. An optional solution is as follows.Theorem 17.
If the initial distribution of a Markov chain with Banana Tree GraphBn,k(k≥5) is the equilibrium distribution, then it can be identified by the PDFs of the sojourn time and hitting time for the root state and all node states, that is, all nonleaf states.Proof.
For ease of exposition, suppose thatr is the root (see the previous introduction of banana tree in this subsection) of this tree and that o is the central state, l is the leaf, and s are the others at each k-star graph, respectively. Firstly, the corresponding qr, πr, qo, πo, qs, and πs can be obtained by each nonleaf state. Secondly, according to the proof of Double-Star Graph, all ql=qlo, qol can be obtained by observation at all nonleaf states, because their Qcc is similar to that of observation at {O1,O2} for Double-Star Graph. Finally, for each k-star graph, qos=qo-∑l‍qol, qso=πoqos/πs, qsr=qs-qso, and qrs=πsqsr/πr.


## 3.3.3. Firecracker Graph

An (n,k)- firecracker, say Fn,k, is a graph obtained by the concatenation of n  k-stars by linking one leaf from each [23].A Markov chain{Xt;t≥0} with Firecracker Graph Fn,k (see Figure 6) is provided.Figure 6
Schematic plot of firecracker graphs (adapted from Wolfram MathWorld).Fork=2 or k=3, it is degenerated into the special tree which is similar, but not completely equivalent, to a Star-Branch Graph.Fork≤4, there are two leaves for each k-star graph. It is implied that the number 2n of all leaves is identical to that of all nonleaf nodes. So, observation at all leaves is valid. According to Theorem 13, a normal solution for k≤4 is as follows.Theorem 18.
If the initial distribution of a Markov chain with Firecracker GraphFn,k(k≤4) is the equilibrium distribution, then it can be identified by the PDFs of the sojourn time and hitting time for all leaves.Fork≥5, the number of all leaves is bigger than that of nonleaf nodes. Following the technique of proof in Theorem 17, it is easy to verify such optional solution.Theorem 19.
If the initial distribution of a Markov chain with Firecracker GraphFn,k(k≥5) is the equilibrium distribution, then it can be identified by the PDFs of the sojourn time and hitting time for all nonleaf states.


## 3.4. Numerical Example

To demonstrate how to apply our algorithms to real data, we present a numerical example here. As we mentioned before, we focus on the final step and then we omit the preprocessing of data. Thus, the data we have is the observed PDFs of sojourn time and hitting time at each leaf. Based upon these data, we could find all the transition rates of this tree.Example 1.
The model of a Markov chain is a binary tree in Figure3 with the true transition rates matrix Q=(qij)S×S given by(30)Q=-1000010000-2500250000-3000300000-15015051500-500300030500-1002000009060-150.We can divide the calculation into two steps: fitting sojourn time and hitting time histogram and transition rates estimation.Step 1 (sojourn time and hitting time histogram estimate).
Suppose that we have obtained the PDFs by fitting (simulating) as follows:(31)fτ1t=0.002032e-186.015025t+0.002801e-107.093861t+0.031748e-43.239654t+0.530183e-0.537764t+0.121303e-9.103660t+0.000006e-24.010036tt≥0,(32)fτ2t=0.018133e-185.792813t+0.023965e-106.751426t+1.024495e-1.089438t+0.265559e-8.032879t+0.669767e-30.000000t+0.091104e-23.333445tt≥0,(33)fτ3t=0.098146e-185.213916t+1.004750e-98.503674t+0.063878e-43.082231t+2.304378e-2.701274t+0.960962e-7.138694t+0.001383e-13.360211tt≥0,(34)fτ4t=0.425895e-185.406369t+3.907008e-101.419933t+0.117730e-43.639996t+2.473349e-3.548045t+3.456848e-18.354848t+0.897366e-12.630809tt≥0,(35)fσ1t=25e-25t,fσ2t=10e-10t,fσ3t=15e-50t,fσ4t=30e-50tt≥0,where fσ(i)(t) (resp., fτ(i)(t)) is the PDF of sojourn time (resp., hitting time) at the state i for i=1,2,3,4.Step 2 (transition rate calculations).
Firstly, by (35) and (10), we have(36)q1=q15=10,q2=q25=25,q3=q36=30,q4=q46=15.For state 1, let (37)α1=186.015025,α2=107.093861,α3=43.239654,α4=0.537764,α5=9.103660,α6=24.010036,γ1=0.002032,γ2=0.002801,γ3=0.031748,γ4=0.530183,γ5=0.121303,γ6=0.000006.Because d1(1)=∑i=16γi=0.688073, hence π1=d1(1)/q1+d1(1)=0.064378, 1-π1=0.935622. Since (38)dn1=∑i=16γiαin-1,cn1=1-π1dn1=0.935622dn,we have (39)c11=0.643777,c21=3.218884,c31=160.944206,c41=17945.278970.Similarly, we can get for states 2, 3, and 4, respectively, (40)π2=0.077253,π3=0.128755,π4=0.429185,c12=1.931330,c22=28.969957,c32=1448.497854,c42=152092.274678,c13=3.862661,c23=115.879828,c33=11587.982833,c43=1384763.948498,c14=6.437768,c24=321.888412,c34=32188.841202,c44=3894849.785408.Thus, we can obtain by the algorithm (proof) of Theorem 10 that(41)q51=c21c11=5.000000,q63=c23c13=29.999999,q52=c22c12=15.000000,q64=c24c14=50.000000,q5=c31c21=50.000000,q6=c33c23=100.000000,π5=c112c21=0.128755,π6=c132c23=0.128755,q57=q5-q51-q52=30.000000,q67=q6-q63-q64=20.000000,q75=c41/c21-q52q25-q52c31/c21-c21/c11-q52=90.000007,q76=c43/c23-q64q46-q62c33/c23-c23/c13-q64=59.999999,π7=1-∑i=16πi=0.042919.Thus, the TRM of {Xt:t≥0} is identified as follows:(42)Q=-1000010000-2500250000-3000300000-15015051500-500300029.999999500-99.99999920000090.00000759.999999-150.000006.Comparing matrix (42) with the original Q-matrix (30), it is not difficult to find that our approach is very efficient under the condition that we obtain an accurate PDF of the hitting time and sojourn time at each leaf.Note that ifQ is symmetric, then the corresponding algorithms are also valid. As a matter of fact, the calculation can be more concise due to the identical equilibrium distributions. In addition, it also can be identified by observations at any three states of four leaves as stated in Remark 11 of Theorem 10.


## 4. Discussion

In the current paper, we have focused on the statistical identification of Markov chains on trees. As stated earlier, all of them are identified only by the derivative constraints. For example, a complete binary tree is identified by observations at all leaves (see Theorem10). Many of them are from current applications and others are still not (e.g., in ion channels). However, it is necessary for the theoretical point of view to be extended to the more general one-tree model. It is mentioned that the states of each subset observed should be distinguishable on the experimental recording of applications.In the future, we might shed light on the statistical identification of reversible Markov chains with cyclic graphs, as another important class analogous to trees such as Tadpole Graph, Pan Graph, and even the more general one-Markov chain. Once reversible Markov chains with cyclic graphs are solved, our approach is then feasible to most of the reversible Markov chains, except those with very complicated network architectures. Hence, the work further opens up the possibility of carrying out the statistical identification for general Markov chains with reversibility.



---

*Source: 2036248-2018-03-28.xml*