Regenerativity of Viterbi process for pairwise Markov models

For hidden Markov models one of the most popular estimates of the hidden chain is the Viterbi path -- the path maximising the posterior probability. We consider a more general setting, called the pairwise Markov model (PMM), where the joint process consisting of finite-state hidden process and observation process is assumed to be a Markov chain. It has been recently proven that under some conditions the Viterbi path of the PMM can almost surely be extended to infinity, thereby defining the infinite Viterbi decoding of the observation sequence, called the Viterbi process. This was done by constructing a block of observations, called a barrier, which ensures that the Viterbi path goes trough a given state whenever this block occurs in the observation sequence. In this paper we prove that the joint process consisting of Viterbi process and PMM is regenerative. The proof involves a delicate construction of regeneration times which coincide with the occurrences of barriers. As one possible application of our theory, some results on the asymptotics of the Viterbi training algorithm are derived.

1 Introduction and preliminaries 1

.1 Introduction
We consider a Markov chain Z = {Z k } k≥1 with product state space X × Y, where Y is a finite set (state space) and X is an arbitrary separable metric space (observation space). Thus, the process Z decomposes as Z = (X, Y ), where X = {X k } k≥1 and Y = {Y k } k≥1 are random processes taking values in X and Y, respectively. The process X is identified as an observation process and the process Y , sometimes called the regime, models the observations-driving hidden state sequence. Therefore our general model contains many well-known stochastic models as a special case: hidden Markov models (HMM), Markov switching models, hidden Markov models with dependent noise and many more. The segmentation or path estimation problem consists of estimating the realization of (Y 1 , . . . , Y n ) given a realization x 1:n of (X 1 , . . . , X n ). A standard estimate is any path v 1:n ∈ Y n having maximum posterior probability: v 1:n = arg max y1:n P (Y 1:n = y 1:n |X 1:n = x 1:n ).
Any such path is called Viterbi path and we are interested in the behaviour of v 1:n as n grows. The study of asymptotics of Viterbi path is complicated by the fact that adding one more observation, x n+1 can change the whole path, and so it is not clear, whether there exists a limiting infinite Viterbi path.
It has been recently proven [28] that under some conditions the infinite Viterbi path exists for almost every realization x 1:∞ of X, allowing to define an infinite Viterbi decoding of X, called the Viterbi process. This was done trough construction of barriers. A barrier is a fixed-sized block in the observations x 1:n that fixes the Viterbi path up to itself: for every continuation of x 1:n , the Viterbi path up to the barrier Also p(z 1 ) = p(x 1 , y 1 ) denotes the initial distribution density of Z with respect to measure µ 1 × c, where µ 1 is some σ-finite measure on B(X ). Thus the joint density of Z 1:n is p(z 1:n ) = p(z 1 )p(z 2:n |z 1 ). For every n ≥ 2 and i, j ∈ Y we also denote p ij (x 1:n ) = max y1:n : y1=i,yn=j n k=2 q(x k , y k |x k−1 , y k−1 ), x 1:n ∈ X n .
Density functions f j are also called the emission densities.
If p(y 2 |x 1 , y 1 ) doesn't depend on x 1 , and p(x 2 |y 2 , x 1 , y 1 ) doesn't depend on y 1 , then following [4] we call Z a Markov switching model. Thus HMM's constitute a sub-class of Markov switching models. In the case of Markov switching model, denoting f j (x|x ) = p(x 2 = x|y 2 = j, x 1 = x ), the transition kernel density becomes q(x, j|x , i) = p ij f j (x|x ).
It is easy to confirm that in case of Markov switching model (and therefore also in case of HMM) Y is a homogeneous Markov chain with transition matrix (p ij ) [33]. Most PMM's used in practice fall into the class of Markov switching models. Figure 1 depicts the directed dependence graph of HMM, Markov switching model and the general PMM.
Throughout this paper we write P z (A) = P (A|Z 1 = z) for any event A and E z [S] = E[S|Z 1 = z] for any random variable S.

Infinite Viterbi path
The segmentation problem in general consists of guessing or estimating the unobserved realization of process Y 1:n -the true path -given the realization x 1:n of the observation process X 1:n . Since the true path cannot be exactly known, the segmentation procedure merely consists of finding the path that in some sense is the best approximation. Probably the most popular estimate is the path with maximum posterior probability. This path will be denoted with v(x 1:n ) and also with v 1:n , when x 1:n is assumed to be fixed: v 1:n = v(x 1:n ) = arg max y1:n p(y 1:n , x 1:n ) = arg max y1:n P (Y 1:n = y 1:n |X 1:n = x 1:n ).
Typically v 1:n is called Viterbi or MAP path (also Viterbi or MAP alignment). It can be found by a dynamic programming algorithm called Viterbi algorithm [34]. Clearly v 1:n might not be unique. For more detailed discussion about the segmentation problem and the properties of different estimates, we refer to [30,21,38,23,24]. Although these papers deal with HMM's only, the general theory applies for any model including PMM's.
To study the statistical properties of Viterbi path-based inferences, one has to know the long-run or typical behaviour of random vectors v(X 1:n ). As argued in [29], behaviour of v(X 1:n ) is not trivial since . . . . . . . If this happens again and again, then the first element of v(x 1:n ) keeps changing as n grows and there is not such thing as limiting Viterbi path. On the other hand, it could be intuitively claimed that sometimes there is a positive probability to observe x 1:n such that regardless of the value of the (n + 1) th observation (provided n is sufficiently large), the paths v(x 1:n ) and v(x 1:n+1 ) agree on first u elements, where u < n. If this is true, then no matter what happens in the future, the first u elements of the paths remain constant. Provided there is an increasing unbounded sequence u i (u < u 1 < u 2 < . . .) such that the path up to u i remains constant, one can define limiting or infinite Viterbi path. Let us formalize the idea. In the following definition v(x 1:n ) is a Viterbi path and v(x 1:n ) 1:t are the first t elements of the n-elemental vector v(x 1:n ).
Hence v 1:∞ is the infinite Viterbi path of x 1:∞ if for any t, the first t elements of v 1:∞ are the first t elements of a Viterbi path v(x 1:n ) for all n big enough (n ≥ m(t)). In other words, for every n big enough, there exists at least one Viterbi path so that v(x 1:n ) 1:t = v 1:t . For the definition of infinite Viterbi path in the case Y is infinite, see [6,28].
As we shall see, for many PMM's the infinite Viterbi path exists for almost every realization of X. However, it is possible to construct a model where almost no realization has an infinite Viterbi path (see [28,Example 1.1]).
Nodes Suppose now x 1:∞ is such that infinite Viterbi path exists. It means that for every time t, there exists time m(t) ≥ t such that the first t elements of v(x 1:n ) are fixed as soon as n ≥ m. Note that if m(t) is such a time, then m(t) + 1 is such a time too. Theoretically, the time m might depend on the whole sequence x 1:∞ . This means that after observing the sequence x 1:m , it is not yet clear, whether the first t elements of Viterbi path are now fixed (for any continuation of x 1:m ) or not. In practice, one would not like to wait infinitely long, instead one prefers to realize that the time m(t) is arrived right after observing x 1:m . In this case, the (random) time m(t) is the stopping time with respect to the observation process. In particular, it means the following: for every possible continuation x m+1:n of x 1:m , the Viterbi path at time t passes the state v t , let that state be i. This requirement is fulfilled, when the following holds: for every two states j, k ∈ Y where δ 1 (y) = p(x 1 , y 1 = y), δ t (y) = max y1:t : yt=y p(x 1:t , y 1:t ), t ≥ 2.
and p ij (·) is defined in (1). Indeed, there might be several states satisfying (3), but the ties can always be broken in favour of the state i, so that whenever n ≥ m, there is at least one Viterbi path v(x 1:n ) that passes the state i at time t. Therefore, if at time t, there is a state i satisfying (3), then m is the time m(t) required in (2) and it depends on x 1:m only.
Definition 1.2. Let x 1:m be a vector of observations. If inequalities (3) hold for any pair of states j and k, then the time t is called an i-node of order r = m − t. Time t is called a strong i-node of order r, if it is an i-node of order r, and the inequality (3) is strict for any j and k = i for which the left side of the inequality is positive. We call t a node of order r if for some i, it is an i-node of order r = m − t.
In [36] the concept of node is used under the name "coalescence point" to describe a memory-efficient modification of the Viterbi algorithm. Our theory justifies the use of such algorithm and could be used to derive bounds on its memory complexity.
Barriers Whether a time t is a node of order r or not depends, in general, on the sequence x 1:t+r . Sometimes, however, there is some small block of observations that guarantees the existence of a node regardless of the other observations. Let us illustrate this by an example.
Then δ t (i)q(x t+1 , y t+1 |x t , i) = max We thus have that t is an i-node of order 1, because for every pair j, k ∈ Y Whether (4) holds or not, depends on triplet (x t−1 , x t , x t+1 ). In case of Markov switching model, (4) is And in a more special case of HMM, (4) is equivalent to The inequalities (5) have very clear meaning -when the observation x t has relatively big probability of being emitted from state i (in comparison of being emitted from any other state), then regardless of the observations before or after x t , time t is a node. On the other hand, for many models, there are no such x t possible, so (5) is rather an exception than a rule. Suppose now that an i-barrier of order r occurs in x 1:∞ infinitely often. By definition of a barrier, there must exist infinitely many i-nodes of order r in x 1:∞ , let these nodes be u 1 < u 2 < · · · . Let m ≥ u 2 + r. There must exist a Viterbi path v(x 1:m ) passing state i at time u 1 . There also exists a Viterbi path passing i at time u 2 . If v(x 1:m ) is unique, then the path passes i at both times, but if Viterbi path is not unique and u 1 and u 2 are too close to each other, then there might not be possible to break ties in favour of i at u 1 and u 2 simultaneously (see [28,Example 1.4]). This problem does not occur, if the nodes are strong or if u 2 ≥ u 1 + r. Indeed, since u 1 is an i-node of order r, then by definition of r-order node, between times u 1 and u 1 + r + 1, the ties can be broken so that whatever state the Viterbi path passes at time u 2 , it passes i at time u 1 . Thus, if the locations of nodes u 1 < u 2 < · · · are such that u k ≥ u k−1 + r for all k ≥ 2, it is possible to construct the infinite Viterbi path so that it passes the state i at every time u k . In what follows, when the nodes u k and u k−1 are such that u k ≥ u k−1 + r, then the nodes are called separated. Of course, there is no loss of generality in assuming that the nodes u 1 < u 2 < · · · are separated, because from any non-separated sequence of nodes it is possible to pick a separated subsequence. Another approach is to enlarge the barriers so that two barriers cannot overlap and, therefore, are separated. This is the way barriers are defined in [27].
Piecewise construction of infinite Viterbi path Having infinitely many separated nodes u 1 < u 2 < · · · or order r, it is possible to construct the infinite Viterbi path piecewise. Indeed, we know that for every n ≥ u k + r, there is a Viterbi path v 1:n = v(x 1:n ) such that v uj = i, j = 1, . . . , k. Because of that property and by optimality principle clearly the piece v uj−1:uj depends on the observations x uj−1:uj , only. Therefore v 1:∞ can be constructed in the following way: first use the observations x 1:u1 to find the first piece v 1:u1 as follows: v 1:u1 = arg max y1:u 1 : yu 1 =i p(x 1:u1 , y 1:u1 ).
Then use x u1:u2 to find the second piece v u1:u2 as follows: v u1:u2 = arg max yu 1 :u 2 : yu 1 =yu 2 =i p(x u1:u2 , y u1:u2 ), and so on. Finally use x u k :n to find the last piece v u k :n as follows: v u k :n = arg max yu k :n : yu k =i p(x u k :n , y u k :n ).
The last piece v u k :n might change as n grows, but the rest of the Viterbi path is now fixed. Thus, if x 1:∞ contains infinitely many nodes, the whole infinite path can be constructed piecewise. If the nodes u k are strong (not necessarily separated) then regardless of tie-breaking scheme v(x 1:n ) u k = i for all k ≥ 1 and n ≥ u k +r. Therefore the piecewise construction detailed above is in that case achieved when the Viterbi estimation is done by a lexicographic * tie-breaking scheme induced by some ordering on Y. Furthermore, under lexicographic ordering, each piece in the piecewise construction is also found by lexicographic ordering. The latter observation will be crucial to our proof of regenerativity.
If the nodes u k are not strong, then the lexicographic ordering may fail to produce the piecewise construction. However from practice point of view the lexicographic ordering is clearly advantageous, since it can easily be implemented via Viterbi algorithm. For that reason we will from now on almost exclusively focus on strong nodes and strong barriers. Fortunately, this does not seem to impose any significant restrictions.

Viterbi process
The notion of infinite Viterbi path of a fixed realization x 1:∞ naturally carries over to an infinite Viterbi path of X, called the Viterbi process. Formally, this process is defined as follows.
is not an infinite Viterbi path of X} is contained in a set of zero probability measure.
If there exists a barrier set X * ⊂ X M consisting of i-barriers of fixed order and satisfying P (X ∈ X * i.o.) = 1, where then the Viterbi process can be constructed by applying the piecewise construction detailed above to the process X. Having infinitely many barriers not only ensures the existence of the Viterbi process, but -as we shall see briefly -will also provide a rather straightforward route to proving that the Viterbi process is regenerative. As follows we state two theorems which ensure the existence of Viterbi process. The first one only concerns HMM while the latter applies to any PMM.
Recall that in case of HMM f i are the emission densities with respect to measure µ. Denote The conditions for the HMM-theorem are the following.
and the sub-stochastic matrix P C = (p ij ) i,j∈C is primitive in the sense that P R C consists of only positive elements for some positive integer R.
Note that condition (HMM2) only depends on transition matrix P = (p ij ) and the probability laws induced by densities f i . Also, this condition is not very restrictive. It is fulfilled when P consists of only positive elements. It is also fulfilled when P is primitive and there exists some µ-positive set such that f i are positive on that set. Theorem 1.4 is not the only result in literature guaranteeing the existence of Viterbi process for HMM, but it is the latest and has the most general conditions (cf. [3,2,27,20]).
In order to state the PMM-theorem we need introduce some general state Markov chain terminol- [32,Prop. 4.2.2.]) a maximal irreducibility measure ψ in the sense that for any other irreducibility measure ϕ the measure ψ dominates ϕ , ψ ϕ . The symbol ψ will be reserved to denote the maximal irreducibility measure of For ψ-irreducible Z, the point z is reachable if and only if it belongs to the support of ψ [32, Lemma 6.1.4]. Since we have equipped space Z with product topology τ × 2 Y , where τ denotes the topology induced by the metrics of X , the above-stated definition of reachable point is in fact equivalent to the following: For any n ≥ 2 define For any set A consisting of vectors of length n we adopt the following notation: Hence Observe The conditions for the PMM-theorem are the following.
(PMM1) For any N ≥ 1 there exist 1 < n 1 < . . . < n 2N , an open set B ⊂ X n 2N , and > 0 such that denoting n 0 = 1 we have for all k = 1, . . . , 2N and all x ∈ B (n k−1 ,n k ) where either inequalities (7) or (8) could be non-strict. We assume that and B (1) are independent of N , and that there exists a compact set K, which is independent of N , such that is the same for every x ∈ E and satisfies the following property: (i, j) ∈ Y + for every i ∈ Y + (1) and j ∈ Y + (2) . Furthermore, we assume that there exists a reachable point in E (1) × Y + (1) . For discussion on conditions (PMM1) and (PMM2) and applications of Theorem 1.2 to specific models we refer the reader to [28].

Regenerativity
For any sequence u = (u k ) k≥1 and a sequence of times [19,37] (in the classic sense), if there exists a sequence of random times S = {S k } k≥1 , 1 ≤ S 1 < S 2 < . . ., called regeneration times, such that for each n ≥ 1 Let from now on V = {V k } k≥1 denote the Viterbi process, whenever it exists, obtained by a lexicographic tie-breaking scheme. The main goal of the present paper is to prove that under some conditions the joint process (Z, V ) = {(Z k , V k )} k≥1 is regenerative. Regenerativity of a general state space Markov chain is typically proved by applying the so-called splitting method [19,37]. If the regeneration times of Z obtained by the splitting method are also strong nodes, then (Z, V ) is regenerative as well. This is the idea behind our main regeneration theorem below. The theorem is proven under assumptions (R1)-(R3), where (R1) ensures the existence of an appropriate barrier set, (R2) ensures that the splitting method can be applied to obtain suitable regeneration times for Z and (R3) guarantees that the inter-regeneration times have finite expectation.
For any A ∈ B(Z) let τ A denote the number of time-steps for Z to reach A after time 1: (R1) There exists a set X * ⊂ X M satisfying the following conditions: (ii) there exist state i 0 ∈ Y, such that for every z ∈ Z There exists a probability measure ν on B(Z) and β ∈ (0, 1) such that ν(Z 1 ) = 1 and Theorem 2.1. If (R1) and (R2) hold, then (i) X * satisfies P (X ∈ X * i.o.) = 1 and hence the Viterbi process V is well-defined; If also (R3) holds, then the inter-regeneration times have finite mean.
Proof. Construction of regeneration times. Denote By (R2) we have that Q(z, ·) are probability measures. Hence for all z ∈ Z 0 the measure P (z, ·) is a mixture of measures ν and Q(z, ·): We now apply the standard splitting technique to construct regeneration times for Markov chain Z. We define a homogeneous Markov chain , and whenever W 1 k ∈ Z 0 we flip a coin: with probability 1 − β we take W 2 k = 0 and generate W 1 k+1 according to Q(W 1 k , ·) and with probability β we take W 2 k = 1 and generate W 1 k+1 according to ν (independently of W 1 k ). The initial distribution of W is defined by Since S 1 k − 1 are stopping times for W and W S 1 k −1 ∈ Z 0 × {1}, we have by strong Markov property that S 1 k are regeneration times for W and therefore also for Z def = {W 1 k } k≥1 . In fact, for every k ≥ 1, {Z S 1 k +u } u≥0 is a Markov chain with initial distribution ν and transition kernel P (z, A).
, where ∨ denotes maximum, and let Times S 2 k (l) are regeneration times for Z (since S 1 k are regeneration times), with {Z S 2 k (l)+u } u≥0 being a Markov chain with initial distribution ν and transition kernel P (z, A) for each k ≥ 1. But this time we always have some separation between regeneration times: Define where I denotes the indicator function and Z is as defined in (R1)(ii). Since b ≥ M − r − 1, then (10) implies that {I k (l)} k≥2 are i.i.d. sequences. We will show that there exists l * such that Denote J 1 = min n | Z n−M +r+2:n ∈ Z , J k = min n > J k−1 | Z n−M +r+2:n ∈ Z , k ≥ 2.
By (R1)(ii) every J k is almost surely finite. Denote {U k } k≥1 = {W 2 J k } k≥1 and note that {U k } k≥1 is i.i.d. sequence with P (U 1 = 1) = β. Indeed, fix k ≥ 1 and consider the homogeneous Markov chain Since J k is stopping time for that Markov chain, we have by strong Markov property for every z ∈ Z 0 Since Z J k ∈ Z 0 by definition of J k , then P (U k = 1) = β. Furthermore, by strong Markov property U k depends on U 1:k−1 only through (Z J k , W 2 J k −1 ). But, as we saw, U k is independent of (Z J k , W 2 J k −1 ) and therefore also of which implies that l * satisfying (11) indeed exists.

Take now
Note that by (11) S 3 k are almost surely finite. Again, S 3 k − 1 are stopping times for W and W S 3 k −1 ∈ Z 0 × {1}, so it follows from strong Markov property and (10) that S 3 k are regeneration times for Z, with {Z S 3 k +u } u≥0 being a Markov chain with initial distribution ν and transition kernel P (z, A) for each k ≥ 1. Also, by construction S 3 k satisfies X S 3 Note that by (R1)(iv) and the assumption ν(Z 1 ) = 1 of (R2) S k are almost surely finite. We will now show S k are regeneration times for W . Let and let N (k) be such that S 3 N (k) = S k . Hence N (k) = n if and only if n−1 l=1 H l = k − 1 and H n = 1. Also note that by (10) S k − S k−1 ≥ r + 1. We can express the conditional distribution of W S k :S k +u , u ≥ 1, given past history: n +u ∈ A|H n = 1) · I(N (k) = n) = P (W S 3 1 :S 3 1 +u ∈ A|H 1 = 1). Here the first equality follows because σ(W 1:S k −1 , S 1:k ) = σ(W 1:S k −1 ); the second equality can be easily confirmed using the fact that B ∩ {N (k) = n} ∈ σ(W 1:S 3 n −1 , H n ) for every B ∈ σ(W 1:S k −1 ) and n ≥ 1; the third equality follows from the fact that W 1:S 3 n −1 is independent of (W S 3 n :S 3 n +u , H n ) (recall that S 3 n is a regeneration time); the fourth equality follows from the fact that {N (k) = n} ⊂ {H n = 1}. That S k are regeneration times for W easily follows. Also, we have X S k −M +r+1:S k +r ∈ X * for all k ≥ 1 by construction and by the assumption X * = X * (1,M −r−1) × X * (M −r,M ) ((R1)(iii)). Therefore P (X ∈ X * i.o.) = 1. Also by (R1)(i) S k are strong 1-nodes, and so by piecewise construction with lexicographic tie-breaking inside each piece the process {(Z k , V k )} k≥1 is regenerative as claimed.
Inter-regeneration times have finite mean. We will now show that where ∧ denotes minimum. Indeed, note that for any k ≥ 1 and z ∈ Z 0 Therefore, for every z ∈ Z 0 , This implies (12).
Next, we will show that E[S 1 2 − S 1 1 ] < ∞. Denote Here we used the fact that {N ≥ k} ∈ σ(W 1:S 1 1 −1+T k−1 ) for second equality, that S 1 1 − 1 + T k−1 is a stopping time for W and strong Markov property for third equality, and (12) for the inequality. Thus we have Since N has a geometric distribution, then c 0 Recall the sequence n 1 < . . . < n N and set B ⊂ X n N of (PMM1). A set A ∈ B(Z) is called regular when Z is ψ-irreducible, if for all B satisfying ψ(B) > 0, sup z∈A E z [τ B ] < ∞. When conditions of Theorem 1.2 hold, then regularity of (B (n N −1) × Y) is sufficient for (R1)-(R3) to hold: Lemma 2.1. If the following conditions are fulfilled, then (R1)-(R3) hold: µ is strictly positive, function (x , x ) → q(x, j|x , i) is lower semi-continuous and bounded for all i, j ∈ Y, Z is Harris recurrent, (PMM1) holds with set (B (n N −1) × Y) being regular, and (PMM2) holds.
Proof. We omit some of the technical details from the proof since they largely concern the specific construction of the barrier set given in [28]. By Theorem 1.2 there exists barrier set X * ⊂ X M consisting of strong 1-barriers of order r ∈ {1, . . . , M − 2}. Using the lower semi-continuity assumption, this barrier set can be constructed so that it satisfies (R1) with some i 0 ∈ Y and i 1 = 1. Furthermore, denoting B = B (n N −1,n N ) , we may with no loss of generality assume that q(x, 1|x , i 0 ) > 0 for all (x , x) ∈ B . There exists 0 > 0 such that set is non-empty. Since B is open, then by the lower semi-continuity assumption (13) is also open, so there exist open balls B 0 , B 1 ⊂ X such that B 0 × B 1 is contained in (13).
By construction of X * (see [28] for details) we may with no loss of generality assume that X * Then for all x ∈ B 0 Proof. Since (R1)(ii) implies that P z (Z k ∈ Z 0 i.o.) = 1 for every z ∈ Z, then for every z ∈ Z there exists k(z) ≥ 2 such that P z (Z k(z) ∈ Z 0 ) > 0. Also note that by (R2) It follows that Z must be ν-irreducible. That Z is Harris recurrent now follows from [32, Prop. 9.1.7(ii)] and that Z is positive follows from (R3) and [32, Th. 11.0.1].

Hidden Markov model
We consider some simple examples of applications of Theorem 2.1 to specific models. For HMM no additional conditions than those of barrier construction theorem 1.1 are needed for (R1)-(R3) to hold. Proof. The assumptions of the statement guarantee the existence of the barrier set X * ⊂ X M consisting of strong 1-barriers with fixed order r for some labelling of Y. Furthermore, it follows from the construction of X * that (R1) holds with i 1 = 1 and i 0 = arg max i p i1 -see [28] for details. Recall that f j denote the emission densities with respect to measure µ. For j ∈ Y denote P j (A) = A f j (x) µ(dx). The barrier set X * is constructed in such a way that P 1 (X * (M −r) ) > 0 -see [28]. For any A ∈ B(Z) and j ∈ Y we write [32,Prop. 8.3.7]). It is not difficult to show that in case of HMM with irreducible Y every set in B(Z) is regular and so (R3) holds.

Discrete X
Consider the case where X is discrete (finite or countable) and Z is an irreducible and positive recurrent Markov chain with (discrete) state space Z ⊂ X × Y. Here the state-space refers to the set of possible values of Z. Note that Z can be a proper subset X × Y. Recall the definition of Y + (·) (6). We assume that the transition kernel q(z|z ) is defined on Z and so (i, x 1 ) ∈ Z for every i ∈ Y + (x 1:q ) (1) . Lemma 3.2. Let X be discrete and let Z be an irreducible and positive recurrent Markov chain with the state-space Z ⊂ X × Y. Then the following conditions ensure that (R1)-(R3) hold.

it holds
where either inequalities (14) or inequalities (15) could be non-strict.
Proof. It is shown in [28] that the conditions of the statement imply (PMM1)-(PMM2) with B (n N −1) = {x * n−1 } and B (n N ) = {x * n }. Since Z is positive recurrent on Z then with no loss of generality we may assume that all finite sets in B(Z) are regular. The statement now follows from Lemma 2.1.

Linear Markov switching model
Let X = R d for some d ≥ 1 and for each state i ∈ Y let {ξ k (i)} k≥2 be an i.i.d. sequence of random variables on X with ξ 2 (i) having density h i with respect to Lebesgue measure on R d . We consider the "linear Markov switching model", where X is defined recursively by Here F (i) are some d × d matrices, Y = {Y k } k≥1 is a Markov chain with transition matrix (p ij ), X 1 is some random variable on X , and random variables {ξ k (i)} k≥2, i∈Y are assumed to be independent and independent of X 1 and Y . Recall that for Markov switching model, the transition density expresses as q(x, j|x , i) = p ij f j (x|x ). For the current model measure µ is Lebesgue measure on R d and f j (x|x ) = h j (x − F (j)x ). When F (i) are zero-matrices, then the linear Markov switching model simply becomes HMM with h i being the emission densities. When d = 1, we obtain the "switching linear autoregression of order 1". The switching linear autoregressions are popular in econometric modelling, see e.g. [14,15,16,13].
In what follows, for any x ∈ X and r > 0 let B(x, r) denote an open ball in X with respect to 2-norm with center point x and radius r > 0. The conditions for (PMM2) are given by (i) There exists set C ⊂ Y and r > 0 such that the following two conditions are satisfied: 1. for x ∈ B(0, r), h i (x) > 0 if and only if i ∈ C; 2. the sub-stochastic matrix P C = (p ij ) i,j∈C is primitive, i.e. there exists R ≥ 1 such that matrix P R C has only positive elements.
Conditions (i) and (ii) are not very restrictive. For example, when all the elements of P = (p ij ) are positive, then (i) is fulfilled if densities h i are either positive around 0 or zero around 0 and there exists at least one j ∈ Y such that h j is positive around 0. If densities h i are all positive around 0, then (i) is fulfilled when P is primitive with C = Y. If h i are positive everywhere and Y is irreducible, then all points in Z are reachable and so (ii) trivially holds.
For x ∈ X we denote with x 1 the 1-norm of x, and for a d × d matrix A we denote with A 1 the 1-norm of matrix A, that is A 1 is the maximum absolute column sum of A. The following lemma addresses Harris recurrence of Z and regularity of sets in B(Z). This can be proved analogously to Lemma 4.3 in [28] by using [32,Th. 11.3.11] instead of [32, Th. 9.1.8].
Lemma 3.5. Let Z be the linear Markov switching model. If the following conditions are fulfilled, then Z is Harris recurrent and every compact set in B(Z) is regular: (i) Z is ψ-irreducible and support of ψ has non-empty interior; (iii) max i∈Y j∈Y p ij F (j) 1 < 1. (i) Matrix P = (p ij ) is primitive, i.e. there exists R such that P R consists of only positive elements.
(ii) It holds p 11 = max i∈Y p i1 .
(iii) Matrix I d − F (1), where I d denotes the identity matrix of dimension d, is non-singular, and for all i ∈ Y and j ∈ Y \ {1} Proof. It is shown in [28] that under given conditions the assumptions of Lemmas 3.3, 3.4 and 3.5 are fulfilled. The statement now follows from Lemma 2.1.

Asymptotics of Viterbi training: regeneration-based analysis
Regenerative property of (Z, V ) has numerous potential theoretical applications ranging from SLLN's and CLT's to proving the existence of asymptotic risks. In this section we look at one such application, namely regeneration-based analysis of the Viterbi training algorithm.
Convergence of empirical measures Firstly, let us state a general SLLN that provides a theoretical basis for several regeneration-based inferences, including the ones in the present section. The proof of the theorem is a rather straightforward application of the regenerative property of (Z, V ) and is given in Appendix A. An analogous result for HMM was proven in [29]. Let V n 1:n denote, the Viterbi path of X 1:n , i.e. V n 1:n = v(X 1:n ). Here the tie-breaking scheme is assumed lexicographic as above. Whenever (R1)-(R3) hold, let {S k } k≥1 denote the regeneration times of (Z, V ), as constructed in the proof of Theorem 2.1. Then In what follows, we study empirical measures where I A denotes the indicator function on A. Also define measure From Theorem 4.1 it follows that P n ⇒ P ∞ a.s., where ⇒ stands for the weak convergence of measures: then g is P ∞ -integrable, and g dP n − → n g dP ∞ , a.s.

Proof.
Denote It follows from Theorem 4.1 that g dP n − → n I(g), a.s.
-just take f ((x 1 , y 1 , v 1 ), (x 2 , y 2 , v 2 )) = g((x 1 , v 1 ), (x 2 , v 2 )). To prove (18), we need to show that I(g) = g dP ∞ . This follows by the standard machinery of measure theory: if g is a simple function, then the equality I(g) = g dP ∞ follows by definition of P ∞ . For non-negative measurable g take a monotone convergent sequence of simple functions g m g and use Monotone Convergence Theorem to see that the equality I(g) = g dP ∞ holds also in the limit. For arbitrary g we have by (17) that I(g + ) < ∞ and I(g − ) < ∞, and hence I(g) = g dP ∞ follows.
The weak convergence now follows from the standard theory of weak convergence of probability measures, see e.g. proof of [9,Th. 11.4.1].
Note that when (R1)-(R3) hold, then there exists γ such that where I denotes the indicator function. Indeed, this follows directly from Theorem 4.1, by taking The limit γ is simply the asymptotic pairwise misclassification rate of the Viterbi estimation. For any pair of measures ν and ν on common σ-field, we denote with ν − ν the total variation distance of measures ν and ν : where supremum is taken over all measurable A. Recall (Lemma 2.2) that when (R1)-(R3) hold, then the transition kernel of Z admits an invariant probability measure π. Let P π denote the probability measure with respect to the stationary initial distribution π. The following result is useful for our purposes.
Proof. Note that by Theorem 4.1 Similarly, denoting where η is a probability measure defined by

Now we have for every A ∈ B(Z) ⊗ B(Z)
and so by (19) By Lemma 2.2 (R1)-(R3) imply that Z is Harris recurrent and positive. To prove the statement, it suffices to show that η = P π (Z 1:2 ∈ ·). From the ergodic theorem for aperiodic and positive Harris Markov chains [32,Th. 13.3.3.] it follows that for all A, B ∈ B(Z) it holds Thus applying Dominated Convergence Theorem to (20) Viterbi training The empirical measures P n are central in many Viterbi-inferences based applications. In this section we look at one of such applications, namely Viterbi training.
For any application of PMM one needs to estimate the parameters of the model. The standard go-to method of parameter estimation in case of Markov switching models is the EM-algorithm, also known as Baum-Welch or forward-backward algorithm [4,1,34,14]. In practice the EM-algorithm is often replaced with the Viterbi training algorithm (VT) [35,17,31] (also known as segmental K-means algorithm [10,18] and classification EM in the mixture case [5,11]) due to its ease of implementation and significantly smaller computational cost. However, compared to the EM-algorithm, VT can sometimes lead to sub-optimal results. It could be argued that the closer the Viterbi path is to the real path, the better VT performs. Thus VT is expected to work well when the dimension of observation space X is relatively high compared to the number of hidden states, since the Viterbi path is in that case -in ‡ See [32] for the definition of aperiodicity of general state ψ-irreducible Markov chain. some sense -probably very similar to the real hidden path. By the same logic, replacing a HMM with a more general PMM (for instance the linear Markov switching model) can improve the accuracy of the Viterbi path estimation and therefore also that of VT. We will see that asymptotic analysis of VT is made possible by the convergence of empirical measures P n and, therefore, by regenerativity of (Z, V ).
We start by formulation of VT for PMM's. We assume that transition densities q(z|z ) are known up to a parametrization q(z|z ) = q(z|z ; θ), where θ is the unknown "true" parameter vector belonging to parameter space Θ ⊂ R d , d ≥ 1. For any parameter vector θ ∈ Θ denote with v(x 1:n ; θ ) the Viterbi path of x 1:n obtained by using the parameters θ . Hence v(x 1:n ) = v(x 1:n ; θ). Viterbi training is a method of estimating the unknown parameters using the following algorithm.
As a special case, we can consider the Markov switching model defined by transition kernel density p ij f j (x|x ; α j ), where θ = (p ij , α j ) i,j∈Y is the unknown parameter vector. Then (as one can see by applying Lagrange multipliers method) the estimates of l+1 p ij of p ij at the 3rd step of Viterbi training algorithm can simply be calculated by Then also l+1 α j , the estimates of α j at the 3rd step of Viterbi training algorithm, can be calculated separately by where A j is the parameter space corresponding to α j . Recall that Markov switching model also includes HMM in which case f j (x|x ; α j ) is independent of x . Assume for now that (R1)-(R3) hold and Z is aperiodic. In the light of Theorem 4.1 we may want to seek the answer to the following question: what is the output of the 3rd step of the Viterbi training algorithm if the input is the correct parameter θ? Ideally, we would like to see that that the output is in that case close to the input: θ = l θ ≈ l+1 θ. This is called the fixed point property. Write q(θ ) for (z , z) → q(z|z ; θ ). Assuming that q(θ ) is positive everywhere on Z 2 and ln q(θ ) satisfies (17) we have by Corollary 4.1 that ln q(θ ) dP n (· ; X 1:n , θ) − → n ln q(θ ) dP ∞ , a.s. This gives hope that at least under some conditions arg max θ ∈Θ ln q(θ ) dP n (· ; X 1:n , θ) − → n arg max θ ∈Θ ln q(θ ) dP ∞ , a.s.
In [22] an analogous convergence is proved under certain conditions. Although [22] deals with HMM's only, we believe that the same idea can be applied to PMM as well to obtain the convergence (21). Denote Assuming that (21) holds and that the sample size n is sufficiently large, the fixed point property holds when θ * ≈ θ. It is not difficult to confirm that P ∞ has a density with respect to measure (µ×c)×(µ×c), where c denotes counting measure on 2 Y . Let p (z , z) denote this density. Writing d(z , z) in place of (µ × c) × (µ × c)(d(z , z)) we have It is not difficult to confirm that the invariant measure π has a density with respect to measure µ × cdenote this density with p π . Assuming that ln p (z , z) and (z , z) → ln p π (z ) are both P ∞ -integrable, we have Defining measure Q θ by we can see that (22) minimizes the Kullback-Leibler divergence of P ∞ from Q θ . If the Viterbi path is perfect estimate of the hidden path, i.e. V ≡ Y , then by Proposition 4.1 P ∞ = P π (Z 1:2 ∈ ·) = Q θ . The Kullback-Leibler divergence of Q θ from Q θ is minimal when θ = θ, implying that the fixed point property θ * ≈ θ indeed holds when the Viterbi path is perfect, at least under appropriate identifiability conditions. In practice however the Viterbi path is almost never perfect and so whether θ * ≈ θ holds or not depends on how closely P ∞ resembles P π (Z 1:2 ∈ ·). If the pairwise misclassification rate γ is small, then by Proposition 4.1 P ∞ − P π (Z 1:2 ∈ ·) ≤ γ, and so the fixed point property is in that case expected to hold. If P ∞ is not close to P π (Z 1:2 ∈ ·), we can correct the estimation error at the 3rd step of the VT by taking the estimate l+1 θ to be l+1 θ = θ − θ * (θ) + arg max θ ∈Θ ln q(z|z ; θ ) P n (d(z , z); X 1:n , l θ).
In case of HMM this modified version of the VT has been called the adjusted Viterbi training (AV) [29,26,22]. AV ensures that the fixed point property holds simply by virtue of convergence (21). The simulations in [26,22] show how the fixed point property significantly improves the accuracy of the estimator so that AV outperforms VT and is comparable to EM-algorithm. The key component of AV is the map θ → θ * (θ). This map is generally not known analytically and should therefore be estimated by simulations. The estimation takes some time and effort but could be worthwhile if a single model is to be applied repeatedly.
It remains to show that the second term on the right side of (23) converges to