Characterizing the Aperiodicity of Irreducible Markov Chains by Using P Systems

Characterizing the Aperiodicity of Irreducible Markov Chains by Using P Systems M´onica Cardona1, M. Angels Colomer1, Mario J. P´erez-Jim´enez2 1Dpt. of Mathematics, University of Lleida Av. Alcalde Rovira Roure, 191. 25198 LLeida, Spain {mcardona,colomer}@matematica.udl.es 2Research Group on Natural Computing Dpt. of Computer Science and Artificial Intelligence University of Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain [email protected] Summary. It is well known that any irreducible and aperiodic Markov chain has exactly one stationary distribution, and for any arbitrary initial distribution, the sequence of distributions at time nconverges to the stationary distribution, that is, the Markov chain is approaching equilibrium as n→ ∞. In this paper, a characterization of the aperiodicity in existential terms of some state is given. At the same time, a P system with external output is associated with any irreducible Markov chain. The designed system provides the aperiodicity of that Markov chain and spends a polynomial amount of resources with respect to the size of the input. A formal verification of this solution is presented and a comparative analysis with respect to another known solution is described. 1 Introduction A discrete-time Markov chain is a stochastic process such that the past time is irrelevant to predict the future, given knowledge of the present time. That is, given the present time, the future does not depend on the past time: the result of each event depends only on the result of the previous event. In order to study the evolution in time of a Markov chain as well as the existence of the stationary distribution, it is suitable to classify its states. This classification depends on the path structure of the chain. One of the central issues in Markov Theory is the study of the asymptotic behavior of Markov chains. It is well known that for any irreducible and aperiodic Markov chain: (a) there exists at least one stationary distribution (that is, a probability distribution on the state space which is an invariant for the transition 82 M. Cardona et al. matrix associated with the chain), and (b) for any initial distribution, µ(0) and for any stationary distribution πfor the Markov chain, the sequence (µ(n))n∈Nconverges to πin total variation as n→ ∞ (that is, the Markov chain is approaching equilibrium as n→ ∞). In the paper [2], a classification of states of a finite and homogeneous Markov chain is provided by using P systems. Moreover, the period was calculated for recurrent classes. The design of the P systems was inspired in properties used in classic algorithms that deal with the problem of the classification. Especially, this solution allows us to decide whether an irreducible Markov chain is aperiodic or not. The main goal of this paper is to design a P system associated with an irreducible Markov chain which provides an answer to the aperiodicity of the chain. If the answer is negative, then the system provides the period of the chain. The solution presented is based on a characterization of the aperiodicity in existential terms of some state and a natural number, and it is semi–uniform, in the sense that for each Markov chain, a P system associated with it is constructed. Besides, the solution spends a polynomial amount of resources in the sense of the computational complexity theory in Membrane Computing. The solution presented in the paper improves the solution obtained in [2], because less computational resources are used. The paper is organized as follows. In the following section, we recall some basic notions and results that we use in the paper. In Section 3, a P system associated with an irreducible Markov chain is designed in order to study the periodicity of that class. Section 4 shows a formal verification of the designed P system. In Section 5, the solution presented is compared with another solution obtained from [2]. Finally some conclusions are presented. 2 Preliminaries A discrete Markov chain is a sequence {Xt|t∈N}of random variables whose values are called states, that verifies the following property: P(Xt+1 =j/X0=i0, X1=i1,...,Xt=it) = P(Xt+1 =j/Xt=it) Without loss of generality, we can suppose that the state space is the set of nonnegative integers. The value of variable Xtis interpreted as the state of the process at instant t. In this paper we work with Markov chains having a finite state space S={s1,...,sk}. A discrete Markov chain is characterized by the transition probability pij(t) = P(Xt=sj/Xt−1=si),∀t≥1 where pij(t) provides the transition from state sito state sjat time t−1. The matrix of transition probabilities Characterizing the Aperiodicity of Irreducible Markov Chains 83 P(t) = (pij(t))1≤i,j≤k is a stochastic matrix, that is, is nonnegative for all tand the sum of each arrow is equal to 1, Pk j=1 pij(t) = 1. We say that the chain is time homogeneous or stationary if pij(t) = pij for each tand it verifies the Kolmogorov-Chapman equation: p(1) ij =pij, p(2) ij = k X l=1 pilplj , . . . , p(n) ij = k X l=1 pilp(n−1) lj , where p(n) ij is the transition probability of state sito state sjat time n. We denote the initial distribution by means of the vector µ(0) = (µ(0) 1,...,µ(0) k) = (P(X0=s1), P(X0=s2),...,P(X0=sk)) and the distribution of the Markov chain at time nis µ(n)= (µ(n) 1,...,µ(n) k) = (P(Xn=s1), P(Xn=s2),...,P(Xn=sk)) Then, µ(n)=µ(0) ·P(n), where P= (pij) is the transition matrix of the homogeneous Markov chain. Next, we introduce some concepts and results related to the states of a homogeneous Markov chain. We say that a state sjcommunicates with another state si(and we denote it by si→sj), if there exists a natural number n > 0 such that p(n) ij >0 (that is, if the chain has a positive probability of ever reaching sjwhen we start from si. We say that the states siand sjintercommunicate (and we denote it by si↔sj) if si→sjand sj→si. In the finite state space S={s1,...,sk}of a Markov chain, the relation ↔ is an equivalence relation and we can consider the corresponding quotient set {s1,...,sk}/↔whose elements are the classes of equivalence by ↔. A Markov chain with state space S={s1,...,sk}is said to be irreducible if there exists only one class of equivalence by ↔; that is, if for all si, sj∈Ewe have si↔sj. Otherwise, the chain is said to be reducible. We say that a state siis recurrent or essential if for each natural number m and for each state sjverifying p(m) ij >0 there exists a natural number nsuch that p(n) ji >0. Otherwise, the state is said to be transient. A recurrent class is the equivalence class determined by a recurrent state. It is easy to prove that from a recurrent state, only recurrent states belonging to the same class are reachable. Arecurrence time of siis a natural number n > 0 such that p(n) ii >0. The period of a state siis defined as d(i) = g.c.d. {n≥1|p(n) ii >0}, that is, it is the greatest common divisor of the recurrence times associated with it. All states belonging to the same class have the same period. Then, we can define the period of a class of a given Markov chain in a natural manner: it is the period of any state of the class (see [3] and [4] for more details). 84 M. Cardona et al. Definition 1. A Markov chain is said to be aperiodic if all its states are aperiodic; that is, their periods are equal to 1. Otherwise, the chain is said to be periodic. Next, we provide a method to compute the period of a recurrent class and a characterization of the periodicity of a class. Theorem 1. Let A={s1,...,sr}be a recurrent class. The period of Ais d=g.c.d. {n|p(n) ii >0; 1 ≤i, n ≤r}. That is, the period of Ais the greatest common divisor of all times of recurrences of the states of that class, smaller than or equal to r. Proof. By definition, given a state si(1 ≤i≤r) its period is d(i) = g.c.d. {n≥1|p(n) ii >0}. As all states have the same period d, we have d=d(1) = d(2) = ...=d(r) = g.c.d. {n≥1|p(n) ii >0; 1 ≤i≤r}. Let d′=g.c.d.{n|p(n) ii >0; 1 ≤i, n ≤r}. Let us see that d=d′. For that, we will check that any trajectory from a state si∈Ato itself, with the length bigger than r, is the composition of trajectories with length smaller than or equal to r between the same states. Let n > r be a time of recurrence associated with a state si∈A, that is, p(n) ii >0. There exists a state si0such that p(n) ii ≥p(n′) ii0·p(n0) i0i0·p(n′′ ) i0i>0, being n=n′+n0+n′′. Thus, n0and n′+n′′ are also times of recurrence. If n0> r or n′+n′′ > r, then we repeat the process until we obtain a decomposition p(n) ii ≥p(n′) ii0·p(n0) i0i0·p(n1) i1i1. . . p(nr) irir·p(n′′ ) iri>0 with 1 ≤i1,...,ir≤r,n=n′+n1+...+nr+n′′ verifying n′+n′′ ≤rand n1,...,nr≤r. Finally, let us notice that substituting p(n) ii , with n > k, by a suitable sequence of p(m) ii , with m≤k, the g.c.d. is the same. ¤ Lemma 1. Let A={a1,··· , ar}be a set of natural numbers. Let us suppose g.c.d. {a1,··· , ar}= 1. Let us denote by A+the set of all positive linear combinations λ1a1+··· , λrar, with λi∈Z+,1≤i≤r. Then, there exists a natural number Nsuch that n∈A+for all n≥N. Proof. See, e.g., the appendix of [1] ¤ Next, we characterize the aperiodicity of a recurrent class of a finite Markov chain through the existence of a state sjreachable from each state si. Characterizing the Aperiodicity of Irreducible Markov Chains 85 Theorem 2. Let {Xt|t∈N}be a Markov chain with state space S={s1,...,sk} and transition matrix P= (pij). (1) If {Xt|t∈N}is aperiodic, then there exists a natural number Nsuch that p(n) ii >0, for all i(1 ≤i≤k)and all n≥N. (2) If {Xt|t∈N}is irreducible and aperiodic, then there exists a natural number Msuch that p(n) ij >0, for all i, j (1 ≤i, j ≤k)and all n≥M. Proof. See, e.g., Chapter 4 from [3] ¤ Theorem 3. Let A={s1, . . . , sr}be a recurrent class of a finite Markov chain. The following are equivalent: (1) Class Ais aperiodic. (2) There exists a state sj∈Aand a natural number m0∈Nsuch that p(m0) ij >0 for all state si∈A. Proof. Let us suppose that class Ais aperiodic. Then all states in Ahave the same period d= 1. From Theorem 2 there exists a natural number Nsuch that p(n) ii >0, for all i(1 ≤i≤r) and all n≥N. Given j(1 ≤j≤r), we define ni(j) = min{n|p(n) ij >0}, for each si∈A,n(j) = max{n1(j), . . . , nr(j)}, and m0=N+n(j). Let us see that p(m0) ij >0, for each i(1 ≤i≤r). We have p(m0) ij ≥p(ni(j)) ij p(m0−ni(j)) jj >0 because of p(ni(j)) ij >0 by definition of ni(j), and p(m0−ni(j)) jj >0 by Theorem 2. Conversely, let us suppose that there exists m0≥1 and a state sj∈Asuch that ∀si∈Awe have p(m0) ij >0. In particular, p(m0) jj >0 so m0is a recurrence time. On the one hand, if dis the period of the class, then m0is a multiple of d. On the other hand, if si∈Ais a state such that pji >0, then 0 < p(m0) ij pji ≤p(m0+1) ii , so m0+ 1 is a multiple of d. Hence, d= 1. ¤ 3 A P System Associated with an Irreducible Markov Chain The goal of this paper is to study the aperiodicity of an irreducible Markov chain with state space S={s1,...,sk},k≥2, by using P systems. In the affirmative case, the answer of the system is Y ES, on the contrary, the system sends an object encoding the period of the class to the environment. 3.1 The Design of the P System Let Pk= (pij)1≤i,j≤kbe a Boolean matrix associated with a class with a finite and homogeneous Markov chain of order ksuch that pij = 1 if the transition from sito sjis possible, and pij = 0 otherwise; that is, Pkis the adjacency matrix of the directed graph associated with the recurrent class. 86 M. Cardona et al. The solution presented in this paper is a semi–uniform one in the following sense: we give a family Π={Π(Pk)|k∈N}, associating with Pka P system with external output, such that: •There exists a deterministic Turing machine working in polynomial time which constructs the system Π(Pk) from Pk. •The output of the P system Π(Pk) provides the classification of the recurrent class of the Markov chain as well as the period of the states. We associate with the matrix Pkthe P system of degree 4 with external output, Π(Pk) = (Γ(Pk), µ(Pk),M1,M2,M3,M4, R) defined as follows: •Working alphabet: Γ(Pk) = {sij, tij, τij |1≤i, j ≤k} ∪ {sijr |1≤i, j, r ≤k} ∪ {Tr|0≤r≤k} ∪ {βl|0≤l≤k−1} ∪ {bi|1≤i≤k} ∪ {pr|1≤r≤k} ∪ {ci, di|0≤i≤α} ∪ {yes, Y ES, σ, } where α= 3k+⌈k 2⌉. In the working alphabet the objects: –sii represents (at the initial configuration) the state siof the chain. –tij and τij represent the elements pij of the Boolean matrix associated with the transition matrix of the Markov chain. –sijr represents the existence of a path of length rfrom the state sito state sj. –Trand prrepresent the existence of a recurrence time equal to rin different configurations. –τij represents that the state sjis reachable from state si. •Membrane structure: µ(Pk) = [ [ [ [ ]1]2]3]4. •Initial multisets: M1={tpij ij |1≤i, j ≤k} ∪ {β0} M2={sii |1≤i≤k} M3={bi|1≤i≤k} ∪ {d0} M4=∅ •The set Rof evolution rules consists of the following rules: r1(ij)≡[tij →τij tk ij]1,1≤i, j ≤k r2(i)≡[βi→βi+1]1,0≤i≤k−2 r3≡[βk−1]1→ck 0 r4(rij)≡[crsijτpj1 j1. . . τpjk jk ]2→[spj1 i1. . . spjk ik cγj r+1]2spj1 i1r+1 . . . spjk ikr+1Tpji r+1, 1≤i, j ≤k, 0≤r≤α−1, γj=Pk l=1 pjl Characterizing the Aperiodicity of Irreducible Markov Chains 87 r5≡[σ]2→σ r6(jr)≡[s1jr . . . skjr]3→[σ]2yes, 1≤j≤k, 1≤r≤α r7(r)≡[Trbr→pr]3,1≤r≤k r8(il)≡[pipi+l→pipl]3,1≤i≤k, 1≤l≤k−i r9(i)≡[p2 i→pi]3,1≤i≤k r10(i)≡[di→di+1]3,0≤i≤α−1 r11(r)≡[dαpr]3→pr[ ]3,2≤r≤k r12 ≡[dαp1]3→yes[ ]3 r13 ≡[yes]4→Y ES[ ]4 r14(r)≡[pr]4→pr[ ]4,1≤r≤k 3.2 An Overview of Computations Initially, membrane 1 contains objects tij that codify the elements pij of the Boolean matrix associated with the transition matrix of the Markov chain, together with the counter β0. This counter allows us to dissolve membrane 1 at a certain instant. Membrane 2 contains initially objects sii that codify the states si of the chain. Membrane 3 contains objects bithat will be used in order to avoid that repeated recurrence times smaller than or equal to kappear. The counter d in membrane 2 will be used to trigger the answer at the suitable instant. The design of the P system Π(Pk) implements a process that is structured by stages. The first one consists of ksteps which allow the production of sufficiently many new copies τij of objects tij . This is done by applying rules of type r1and r2in membrane 1 at k−1 first steps and applying at step krule r3that dissolves membrane 1. At the second stage, all paths between states with length at most k, as well as recurrence times smaller than or equal to k, are generated. This stage starts at step k+ 1 and it spends at most ksteps. First, rules of type r4are applied producing objects sijr in membrane 3 that codify the existence of a path with length rfrom state sito state sj, as well as the objects Trcodifying the existence of a recurrence time equal to r. Simultaneously, it is checked if there exists a state sjand a natural number m0such that p(m0) ij >0, for all states si. In that case, an object σis produced in membrane 2 and the system expels an object Y ES to the environment. The third stage is only applied if an object Y ES has not been expelled to the environment. At this stage, the period of the class is computed and it takes k+⌈k 2⌉steps. By applying rules of type r7, objects prencoding recurrence times smaller than or equal to k, are obtained. Such recurrence times are different from each other. By applying rules of types r8and r9, the greatest common divisor of 88 M. Cardona et al. these times is computed. If the period of the class is equal to 1, then the system sends an object Y ES to the environment, otherwise, the system expels an object pnthat encodes the period of the class to the environment. 4 Formal Verification Given a computation Cof the P system Π(Pk), for each m∈Nwe denote by Cmthe configuration of the system obtained after the execution of msteps. For each label l∈ {1,2,3}, we denote by Cm(l) the multiset of objects contained in membrane lin the configuration Cm. Besides, we denote by Cm(env) the content of the environment of the system in the configuration Cm. Proposition 1. (First stage) We have the following: (1) For each m,1≤m≤k−1, we denote ψm= 1 + k+k2+... +km= (km+1 −1)/(k−1). Then Cm(1) = {βmtkm·pij ij τψm−1·pij ij }. (2) Ck(2) = {ck 0, sii, τψk−1·pij ij , t(kk)·pij ij |1≤i, j ≤k} Proof. (1) By induction on m. Let us see the result for m= 1. First, we notice that rule r2(0) is applicable to configuration C0, so β1∈ C1(1). Rule r1(ij) is applicable to configuration C0if and only if pij = 1. Hence, C1(1) = {β1tk·pij ij τpij ij }. Let mbe such that 1 ≤m < k −1 and Cm(1) = {βmtkm·pij ij τψm−1·pij ij }. Then, rule r2(m) is applicable to configuration Cm, so βm+1 ∈ Cm+1(1). Rule r1(ij) is applicable to configuration Cmif and only if pij = 1. Hence, Cm+1(1) = {βm+1 tkm·k·pij ij τ(ψm−1+km)·pij ij }. (2) From (1), we have Ck−1(1) = {βk−1tkk−1·pij ij τψk−2·pij ij }. Next, rule r1(ij) produces kobjects tij and an object τij for each object tij ∈ Ck−1(1). Moreover, rule r3produces kcopies of c0dissolving membrane 1. ¤ Remark: Let us notice that condition τij ∈ Cr(1), 1 ≤r≤k−1, means that state sjis reachable from state si. Lemma 2. For each i, j, r (1 ≤i, j, r ≤k)we have the following: •The sum of the multiplicities of objects s1j. . . skj in Ck+r(2) is, at most, kr. •There exists, at most, kr+1 objects crin Ck+r(2). •τ(ψk−1−ψr−1)·pij ij ∈ Ck+r(2). Characterizing the Aperiodicity of Irreducible Markov Chains 89 Proof. By induction on r. Let us suppose that r= 1, Let i, j be such that 1 ≤i, j ≤k. From (2) in Proposition 1 we have Ck(2) = {ck 0, sii, τψk−1·pij ij } ⊆ Ck(2). Then, rules r4(0,1,1),...,r4(0, k, k) must be applied. If pij = 1, then an object sij (resp. an object τij ) is produced (resp. is consumed) by the application of rule r4(0, i, i) (besides, these objects can only be spent/produced by the application of that rules). Hence, the sum of multiplicities of objects s1j,...,skj will be p1j+...+pkj ≤k, there exists at most k2objects c1in Ck+1(2), and τ(ψk−1−1) ij ∈ Ck+1(2). Let r≥1, r < k, and let us suppose that the result holds for r. Let i, j be such that 1 ≤i, j ≤k. By the induction hypothesis the sum of the multiplicities of objects s1i,...,ski in Ck+r(2) is, at most, kr, there exists, at most, kr+1 objects crin Ck+r(2), and τ(ψk−1−ψr−1)·pij ij ∈ Ck+r(2). For each i(1 ≤i≤k) the rules r4(r1i),...,r4(rki) will be applied to configuration Ck+r(2) at most krtimes, so at most krobjects τij will be spent and kr·kobjects cr+1 will be produced. Then, there exists at most kr+2 objects cr+1 in Ck+r+1(2), and τ(ψk−1−ψr−1−kr)·pij ij ∈ Ck+r+1(2). Moreover, each object siq (1 ≤q≤k) produces, at most, an object sij in Ck+r+1(2). Hence, the sum of multiplicities of s1j,...,skj in Ck+r+1(2) will be, at most, kr+...+kr=k·kr=kr+1.¤ Proposition 2. (Second stage) For each i, j, r (1 ≤i, j, r ≤k)we have: (1) Objects sij and crbelong to Ck+r(2) if and only if there exists a trajectory from state sito state sjwith a length r. (2) A state sof the Markov chain has a recurrence time rif and only if Tr∈ Ck+r(3). Proof. (1) By induction on r. Let us suppose that r= 1. If sij , c1∈ Ck+1(2), then rule r4(0, i, i) must be applied by using objects c0, sii, τij ∈ Ck(2). Then, pij = 1, otherwise pij = 0 ⇒ τij /∈ Ck(2) (from Proposition 1). Let i0, j0(1 ≤i0, j0≤k) and let us suppose that there exists a trajectory from state si0to state sj0with a length 1. Then, pi0j0= 1. From Proposition 1 we deduce that Ck(2) = {ck 0, sii, τψk−1·pij ij , t(kk)·pij ij |1≤i, j ≤k}, so for each i(1 ≤i≤k) rule r4(0ii) is applied once to configuration Ck(2). Then, {c1, si0j0} ⊆ Ck+1(2). Let r≥1, r < k, and let us suppose that the result holds for r. Let i, j (1 ≤ i, j ≤k) be such that sij , cr+1 ∈ Ck+r+1(2). On the one hand, rule r4(ril) has been applied, at least once, to configuration Ck+rby using objects cr, sil, τlj (for some l, 1 ≤l≤k). So, plj = 1. On the other hand, cr, sil ∈ Ck+r(2). Then, by induction hypothesis we deduce that there exists a trajectory with a length rfrom state sito state sl. Hence, there exists a trajectory with the length r+ 1 from state sito state sj.