ijcccv4n3Draft.pdf Int. J. of Computers, Communications & Control, ISSN 1841-9836, E-ISSN 1841-9844 Vol. IV (2009), No. 3, pp. 291-300 P Systems Computing the Period of Irreducible Markov Chains Mónica Cardona-Roca, M. Ángels Colomer-Cugat, Agustín Riscos-Núñez, Miquel Rius-Font Mónica Cardona-Roca, M. Ángels Colomer-Cugat Dpt. of Mathematics, University of Lleida Av. Alcalde Rovira Roure, 191. 25198 Lleida, Spain E-mail: {mcardona, colomer}@matematica.udl.es Agustín Riscos-Núñez Research Group on Natural Computing Dpt. of Computer Science and Artificial Intelligence University of Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain E-mail: ariscosn@us.es Miquel Rius-Font Department of Applied Mathematics IV Universitat Politécnica de Catalunya Edifici C3, Despatx 016, Av. del Canal Olímpic, s/n, 08860 Castelldefels, Spain E-mail: mrius@ma4.upc.edu Received: April 5, 2009 Accepted: May 30, 2009 Abstract: It is well known that any irreducible and aperiodic Markov chain has exactly one stationary distribution, and for any arbitrary initial distribution, the se- quence of distributions at time n converges 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 irre- ducible 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 in- put. A comparative analysis with respect to another known solution is described. Keywords: Markov chain, P Sytems, Membrane Computing 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 station- ary distribution (that is, a probability distribution on the state space which is an invariant for the transition matrix associated with the chain), and (b) for any initial distribution, µ () and for any stationary distri- bution π for the Markov chain, the sequence (µ (n))n∈NNN converges to π in total variation as n → ∞ (that is, the Markov chain is approaching equilibrium as n → ∞). Copyright c© 2006-2009 by CCC Publications 292 Mónica Cardona-Roca, M. Ángels Colomer-Cugat, Agustín Riscos-Núñez, Miquel Rius-Font In 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 con- structed in order to study the periodicity of that class. In Section 4, the solution presented is compared with another solution given in [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+ = j/X = i, X = i, . . . , Xt = it ) = P(Xt+ = j/Xt = it ). Without loss of generality, we can suppose that the state space is the set of nonnegative integers. The value of variable Xt is interpreted as the state of the process at instant t. In this paper we work with Markov chains having a finite state space S = {s, . . . , sk}. A discrete Markov chain is characterized by the transition probability pi j(t) = P(Xt = s j/Xt− = si), ∀t ≥ , where pi j(t) provides the transition from state si to state s j at time t − . The matrix of transition probabilities P(t) = (pi j(t))≤i, j≤k , is a stochastic matrix, that is, is nonnegative for all t and the sum of each row is equal to 1, ∑k j= pi j(t) = . We say that the chain is time homogeneous or stationary if pi j(t) = pi j for each t and it verifies the Kolmogorov-Chapman equation: p () i j = pi j, p () i j = k∑ l= pil pl j, . . . , p (n) i j = k∑ l= pil p (n−) l j , where p (n) i j is the transition probability of state si to state s j at time n. We denote the initial distribution by means of the vector µ () = (µ () , . . . , µ () k ) = (P(X = s), P(X = s), . . . , P(X = sk)), and the distribution of the Markov chain at time n is µ (n) = (µ (n) , . . . , µ (n) k ) = (P(Xn = s), P(Xn = s), . . . , P(Xn = sk)). P Systems Computing the Period of Irreducible Markov Chains 293 Then, µ (n) = µ () · P(n), where P = (pi j) 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 s j communicates with another state si (and we denote it by si → s j), if there exists a natural number n >  such that p (n) i j >  (that is, if the chain has a positive probability of ever reaching s j when we start from si. We say that the states si and s j intercommunicate (and we denote it by si ↔ s j) if si → s j and s j → si. In the finite state space S = {s, . . . , sk} of a Markov chain, the relation ↔ is an equivalence relation and we can consider the corresponding quotient set {s, . . . , sk}/ ↔ whose elements are the classes of equivalence by ↔. A Markov chain with state space S = {s, . . . , sk} is said to be irreducible if there exists only equiva- lence class with respect to ↔; that is, if for all si, s j ∈ E we have si ↔ s j. Otherwise, the chain is said to be reducible. We say that a state si is recurrent or essential if for each natural number m and for each state s j verifying p (m) i j >  there exists a natural number n such that p (n) ji > . 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. A recurrence time of si is a natural number n >  such that p (n) ii > . The period of a state si is defined as d(i) = g.c.d. {n ≥  | p (n) ii > }, 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). 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 2. Let A = {s, . . . , sr} be a recurrent class. The period of A is d = g.c.d. {n | p (n) ii > ;  ≤ i, n ≤ r}. Proof. As all states have the same period d, we have d = d() = d() = . . . = d(r) = g.c.d. {n ≥  | p (n) ii > ;  ≤ i ≤ r}. Let d ′ = g.c.d.{n| p (n) ii > ;  ≤ i, n ≤ r}. Let us see that d = d ′. For that, let n > r be a time of recurrence associated with a state si ∈ A, that is, p (n) ii > . There exists a state si such that p (n) ii ≥ p (n′) ii · p (n) ii · p (n′′) ii > , where n = n′ + n + n ′′. Thus, n and n ′ + n′′ are also times of recurrence. If n > r or n ′ + n′′ > r, then we repeat the process until we obtain a decomposition p (n) ii ≥ p (n′) ii · p (n) ii · p (n) ii . . . p (nt ) it it · p (n′′) it i > , with  ≤ i, . . . , it ≤ r, n = n ′ + n + . . . + nt + n ′′ verifying n′ + n′′ ≤ r and n, . . . , nt ≤ r. Finally, let us notice that substituting p (n) ii , with n > r, by a suitable sequence of p (m) ii , with m ≤ r, the g.c.d. is the same. Lemma 3. Let A = {a,··· , ar} be a set of natural numbers. Let us suppose g.c.d. {a,··· , ar} = . Let us denote by A+ the set of all positive linear combinations λa + ··· + λrar, with λi ∈ Z +,  ≤ i ≤ r. Then, there exists a natural number N such that n ∈ A+ for all n ≥ N. 294 Mónica Cardona-Roca, M. Ángels Colomer-Cugat, Agustín Riscos-Núñez, Miquel Rius-Font Proof. See, e.g., the appendix of [1] Next, we characterize the aperiodicity of a recurrent class of a finite Markov chain through the exis- tence of a state s j reachable from each state si. Theorem 4. Let {Xt | t ∈ N} be a Markov chain with state space S = {s, . . . , sk} and transition matrix P = (pi j). (1) If {Xt | t ∈ N} is aperiodic, then there exists a natural number N such that p (n) ii > , for all i ( ≤ i ≤ k) and all n ≥ N. (2) If {Xt | t ∈ N} is irreducible and aperiodic, then there exists a natural number M such that p (n) i j > , for all i, j ( ≤ i, j ≤ k) and all n ≥ M. Proof. See, e.g., Chapter 4 from [3] Theorem 5. Let A = {s, . . . , sr} be a recurrent class of a finite Markov chain. The following are equiv- alent: (1) Class A is aperiodic. (2) There exists a state s j ∈ A and a natural number m ∈ N such that p (m) i j >  for all state si ∈ A. Proof. Let us suppose that class A is aperiodic. Then all states in A have the same period d = . From Theorem 4 there exists a natural number N such that p (n) ii > , for all i ( ≤ i ≤ r) and all n ≥ N. Given j ( ≤ j ≤ r), we define ni( j) = min{n | p (n) i j > }, for each si ∈ A, n( j) = max{n( j), . . . , nr( j)}, and m = N + n( j). Let us see that p (m) i j > , for each i ( ≤ i ≤ r). We have p (m) i j ≥ p (ni( j)) i j p (m−ni( j)) j j >  because of p (ni( j)) i j >  by definition of ni( j), and p (m−ni( j)) j j >  by Theorem 4. Conversely, let us suppose that there exists m ≥  and a state s j ∈ A such that ∀ si ∈ A we have p (m) i j > . In particular, p (m) j j >  so m is a recurrence time. On the one hand, if d is the period of the class, then m is a multiple of d. On the other hand, if si ∈ A is a state such that p ji > , then  < p (m) i j p ji ≤ p (m+) ii , so m +  is a multiple of d. Hence, d = . 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 = {s, . . . , sk}, k ≥ , 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 = (pi j)≤i, j≤k be a Boolean matrix associated with a class with a finite and homogeneous Markov chain of order k such that pi j =  if the transition from si to s j is possible, and pi j =  otherwise; that is, Pk is the adjacency matrix of the directed graph associated with the recurrent class. The solution presented in this paper is a semi–uniform one in the following sense: we give a family ΠΠΠ = {Π (Pk) | k ∈ NNN}, associating with Pk a P system with external output, such that (a) there exists a deterministic Turing machine working in polynomial time which constructs the system Π (Pk) from Pk; and (b) 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 Pk the P system of degree 4 with external output, P Systems Computing the Period of Irreducible Markov Chains 295 Π (Pk) = (Γ (Pk), µ(Pk), M, M, M, M, R) defined as follows: • Working alphabet: Γ (Pk) = {si j, ti j, τi j |  ≤ i, j ≤ k} ∪ {si jr |  ≤ i, j, r ≤ k} ∪ {Tr |  ≤ r ≤ k} ∪ {βl |  ≤ l ≤ k − } ∪ {bi, pi |  ≤ i ≤ k} ∪ {ci, di |  ≤ i ≤ α} ∪ {yes,Y ES, σ } where α = k + ⌈ k  ⌉. • Membrane structure: µ(Pk) = [ [ [ [ ] ] ]]. • Initial multisets: M = {t pi j i j |  ≤ i, j ≤ k} ∪ {β}; M = {sii |  ≤ i ≤ k} M = {bi |  ≤ i ≤ k} ∪ {d}; M = /0 • The set R of evolution rules consists of the following rules: r = [ti j → τi jt k i j],  ≤ i, j ≤ k r = [βi → βi+],  ≤ i ≤ k −  r = [βk−] → c k  r = [crsi jτ p j j . . . τ p jk jk ] → [s p j i . . . s p jk ik c γ j r+]s p j ir+ . . . s p jk ikr+T p ji r+,  ≤ i, j ≤ k,  ≤ r ≤ α − , γ j = ∑k l= p jl r = [σ ] → σ r = [s jr . . . sk jr] → [σ ] yes,  ≤ j ≤ k,  ≤ r ≤ α r = [Trbr → pr],  ≤ r ≤ k r = [pi pi+l → pi pl ],  ≤ i ≤ k,  ≤ l ≤ k − i r = [p  i → pi],  ≤ i ≤ k r = [di → di+],  ≤ i ≤ α −  r = [dα pr] → pr[ ],  ≤ r ≤ k r = [dα p] → yes[ ] r = [yes] → Y ES[ ] r = [pr] → pr[ ],  ≤ r ≤ k 3.2 An Overview of Computations Initially, membrane 1 contains objects ti j that codify the elements pi j of the Boolean matrix associ- ated with the transition matrix of the Markov chain, together with the counter β. 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 bi that will be used in order to avoid that repeated recurrence times smaller than or equal to k appear. 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 k steps which allow the production of sufficiently many new copies τi j of objects ti j. This is done by applying rules of type r and r in membrane 1 at k −  first steps and applying at step k rule r that dissolves membrane 1. 296 Mónica Cardona-Roca, M. Ángels Colomer-Cugat, Agustín Riscos-Núñez, Miquel Rius-Font 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 +  and it spends at most k steps. First, rules of type r are applied producing objects si jr in membrane 3 that codify the existence of a path with length r from state si to state s j, as well as the objects Tr codifying the existence of a recurrence time equal to r. Simultaneously, it is checked if there exists a state s j and a natural number m such that p (m) i j > , 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  ⌉ steps. By applying rules of type r, objects pr encoding recurrence times smaller than or equal to k, are obtained. Such recurrence times are different from each other. By applying rules of types r and r, the greatest common divisor of these times is computed. If the period of the class is equal to , then the system sends an object Y ES to the environment, otherwise, the system expels an object pn that encodes the period of the class to the environment. 4 Results and Discussions In [2] a P system was constructed which allows us to classify the states of a Markov chain. Thus, that P system can be adapted to characterize the aperiodicity of such a chain. Specifically, if Pk = (pi j)≤i, j≤k is the Boolean matrix associated with the states of a recurrent class of a finite and homogeneous Markov chain of order k, then we define the system Π ′(Pk) = (Γ ′(Pk), µ ′(Pk), M ′ , M ′ , M ′ , M ′ , R ′, ρ ′), as follows: • Working alphabet: Γ ′(Pk) = {A, Ri, ti j |  ≤ i, j ≤ k} ∪ {cr |  ≤ r ≤ k + } ∪ {ti jur |  ≤ i, j, u ≤ k,  ≤ r ≤ k} ∪ {βi |  ≤ i ≤ γ + } ∪ {si jr |  ≤ i, j ≤ k,  ≤ r ≤ k} ∪ {di |  ≤ i ≤ (k − )} where γ = k +  + ⌈lgk⌉ + (k−)(k+)  . • Membrane structure: µ ′(Pk) = [ [ [ [ ] ] ] ]. • Initial multisets: M′ = /0; M ′  = {β}; M ′  = {c}; M ′  = {sii t pi j (k−) i j |  ≤ i, j ≤ k}. • The set R of evolution rules consists of the following rules: – Rules in the skin membrane labeled by 1: r = {dp → (Rp, out) |  < p ≤ k} r = {d → (A, out)} – Rules in the membrane labeled by 2: r = {βi → βi+ |  ≤ i ≤ γ} ∪ {βγ+ → λ }. r = {d  j → d j |  ≤ j ≤ k} r = {d jd j+l → d jdl |  ≤ j ≤ k,  ≤ j + l ≤ k} P Systems Computing the Period of Irreducible Markov Chains 297 – Rules in the membrane labeled by 3: r = {ti jur → (ti j su j(r+), in) | pi j = , u 6= j,  ≤ i, j, u ≤ k,  ≤ r < (k − )} r = {ti ju(k−) → (ti j, in) | pi j = , u 6= j,  ≤ i, j, u ≤ k} r = {ti j jr → (ti j, in) dr+ | pi j = ,  ≤ i, j ≤ k,  ≤ r < (k − )} r = {ti j j(k−) → (ti j, in) | pi j = ,  ≤ i, j ≤ k} r = {cr → cr+ |  ≤ r ≤ (k − ) + } ∪ {c(k−)+ → λ } – Rules in the membrane labeled by 4: r = {suirt pi i . . .t pik ik → (t pi iur . . .t pik ikur, out) |  ≤ u, i ≤ k,  ≤ r ≤ (k − )}. • There is only a priority relation in the membrane labeled by 2: {r > r}. In order to study the efficiency of the P system Π (Pk) constructed in this work, we will compare the results with those obtained by the P system Π ′(Pk) described above. For that purpose, a comparative analysis of the computational resources required in both P systems is given first. Secondly, an analysis of the times of execution obtained on designed simulators for both P systems with some case studies is presented. 4.1 Computational Resources Required The resources required initially to construct the systems Π (Pk) and Π ′(Pk), and the number of steps taken by the systems, are the following: Π (Pk) Π ′(Pk) Size of the alphabet Θ (k) Θ (k) Initial number of membranes 4 4 Sum of the sizes of initial multisets Θ (k) Θ (k) Number of rules Θ (k) Θ (k) Maximal length of a rule Θ (k) Θ (k) Number of priority relations 0 Θ (k) Number of steps Θ (k) Θ (k) In the previous table, let us notice that the amount of resources requested by Π (Pk) is smaller than the ones requested by Π ′(Pk). Indeed, the size of the alphabet and the number of rules pass from power 3 to power 4, and the system Π (Pk) has no priority relation. The number of steps is of the same asymptotic order. 4.2 Case Studies We have realized a simulator for each system Π (Pk) and Π ′(Pk). These simulators have been written in C++ language and they have been executed on a Pentium 4 computer with 512 Mb RAM and 3.20 GHz. In both simulators objects ti j have been represented by means of arrays of dimension 2; objects si j have been represented by vectors of dimension 2 and recurrent times have been represented by one- dimensional vectors. The simulator of the system Π (Pk) generates the trajectories with a length at most k + ⌈k/⌉ in a sequential way, keeping the times of recurrence smaller than or equal to k. If assertion () in Theorem 5 is fulfilled, the simulator halts displaying the time of execution and the aperiodicity of the Markov chain. Otherwise the simulator computes the g.c.d. of the recurrence times obtained where all of them are different. 298 Mónica Cardona-Roca, M. Ángels Colomer-Cugat, Agustín Riscos-Núñez, Miquel Rius-Font Similarly, a simulator for the system Π ′(Pk) has been implemented. The main difference with respect to the previously mentioned one is that it can keep more than a copy of the times of recurrence. All trajectories of the Markov chain with a length smaller than or equal to (k − ) and their recurrence time are computed. Then the g.c.d. of these times is obtained. When the Markov chain is aperiodic, the P system Π (Pk) can finish before all trajectories with a length k + ⌈k/⌉ are computed. In case it is necessary to calculate the period, bearing in mind that all recurrence times are different, system Π (Pk) is faster than Π ′(Pk) in computing the g.c.d. of these times. When the Markov chain is periodic the length of the trajectories computed by Π (Pk) are longer than those computed by Π ′(Pk). Nonetheless, in order to compute the period, recurrence times used in Π (Pk) are all different. The simulators designed have been executed on eight recurrent Markov chains with 100 states. Four of these Markov chains are periodic and the others are aperiodic. Table 1 shows the values equal to 1 of the adjacency matrix of the graph associated with the recurrent Markov chains. The execution times are described in Table 2. Example 1 pi,i+ =   ≤ i ≤  p, =  2 pi,i+ =   ≤ i ≤  pi, =   ≤ i ≤  3 p j+i, j+i+ =   ≤ i ≤   ≤ j ≤  p j, j− =   ≤ j ≤  p j+, j+ =   ≤ j ≤  p, =  4 p j+i, j+i+ =   ≤ i ≤   ≤ j ≤  p j, j− =   ≤ j ≤  p j+, j+ =   ≤ j ≤  p, =  p, =  5 p j+i, j+i+ =   ≤ i ≤   ≤ j ≤  p j, j− =   ≤ j ≤  p j+, j+ =   ≤ j ≤  p, =  p, =  6 p j+i, j+i+ =   ≤ i ≤   ≤ j ≤  p j, j− =   ≤ j ≤  p j+, j+ =   ≤ j ≤  p, =  7 pi,i+ =   ≤ i ≤  pi+,i =   ≤ i ≤  p+i,+i =   ≤ i ≤  8 pi,i+ =   ≤ i ≤  pi+,i =   ≤ i ≤  p+i,+i =   ≤ i ≤  p, =  Table 1. Adjacency values of the examples 5 Conclusions Markov chains have applications in different fields such as physics, economics, biology, statistics, so- cial sciences, etc. In these applications it is important to know whether the Markov chain associated with the process is convergent or not. When the Markov chain is aperiodic, the transition matrix converges and the process becomes stable. In other cases, the process does not reach an equilibrium. In this work, a characterization of the aperiodicity of a Markov chain has been given in terms of the P Systems Computing the Period of Irreducible Markov Chains 299 Example period Π ′(Pk) Π (Pk) 1 100 0 0 2 1 146 0 3 10 0 0 4 1 122 35 5 1 1 2 6 5 11 20 7 2 381 169 8 1 1101 104 Table 2. Observed run times existence of a state reachable from any other state. Based on this property, a computational P system has been constructed that allows us to know whether the Markov chain is aperiodic and calculate its period if not. In [2], every finite and homogeneous Markov chain has associated a P system that provides a clas- sification of its recurrent classes. That P system can be adapted to study the aperiodicity of a Markov chain and then its period can be calculated. The solution presented in this work improves the solution derived from the P system described in [2]. For that purpose, simulators have been constructed for these P systems and the respective times of execution on eight examples have been analyzed. For the computational study of the aperiodicity of a Markov chain it would be interesting to design new P systems that incorporate additional features such as electrical charges, active membranes, etc. and that improve quantitatively the amount of computational resources used. Acknowledgement The authors wish to thank Mario J. Pérez-Jiménez for his advices, suggestions and constant help. Among the numerous virtues of this excellent professor, we would like to highlight his enviable capacity of work and his great human quality. As it is usually said, behind a great man there is a great woman and so we cannot end theses line without expressing our gratitude to Queta for her immense patience with all of us. The third author acknowledges the support of the project TIN2006–13425 of the Ministerio de Ed- ucación y Ciencia of Spain, cofinanced by FEDER funds, and the support of the Project of Excellence with Investigador de Reconocida Valía of the Junta de Andalucía, grant P08-TIC-04200. Bibliography [1] P. Brémaud: Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues. Springer, New York, 1998. [2] M. Cardona, M.A. Colomer, M.J. Pérez–Jiménez, A. Zaragoza: Classifying states of a finite Markov chains with membrane computing. Lecture Notes in Computer Science. Springer,Vol 4361, pp. 266- 278, 2006. [3] O. Häggstöm: Finite Markov Chains and Algorithmic Applications. London Mathematical Society, Cambridge University Press, Cambridge, 2003. [4] R. Nelson: Probability, Stochastic Processes, and Queing Theory. Springer, New York, 1995. 300 Mónica Cardona-Roca, M. Ángels Colomer-Cugat, Agustín Riscos-Núñez, Miquel Rius-Font Mónica Cardona-Roca received his degree in Mathematics in 2000, from the Barcelona University. He is associate professor at the Department of Mathematics of the University of Lleida where he has been teaching for eight years. Here main research areas are natural computing and membrane computing. She has co-authored two books in mathematics. She has co-authored 5 papers on international journals in natural computing. She has co-authored 3 papers in statistics published in proceedings of Spanish conferences. M. Ángels Colomer-Cugat received his degree in Engineer Agronomist from the UPC (Politecnic Universitiy of Catalonia) and doctor degree in mathematics in 1996 from the UPC. Currently, she is titular professor of Statistics and Operative Investigation where she has been teaching for more than twenty five years. In the current moment she is the head of the emergent Research Group on Models of membrane computation applied to ecosystems. She has published seven books on statistics and quality control. She has published twelve scientifics papers in international journals. Her main research area are models of computation with membranes applied to the ecology and biology processes. Hers first researches were centred on the stocastics models, concretely Markov chain applied to natural processes where she has some works. Agustín Riscos-Núñez got his Master degree in Mathematics in 2000, and then his PhD degree on 2004. Currently he is an associate professor at the Department of Computer Science and Artificial Intelligence in the University of Sevilla (Spain). He is a member of the Research Group on Natural Computing in the same University, and his main research interests within the membrane computing area are complexity theory, models for biological processes, and computer simulation. He has co-authored about 30 papers on international journals in the last years, and he has also participated in 15 conferences and workshops. Miquel Rius-Font received his bachelor degree in Mathematics form the Universitat Autónoma de Barcelona and his doctor degree in mathematics from University of Barcelona. He is currently teach- ing mathematics at Catalonian Techology University and his research area is graph theory and natural computing. His interest involves isoperimetric problems as well as graph labeling problems.