The markovchain Package: A Package for Easily Handling ...

1 The markovchain Package : A Package for Easily HandlingDiscrete markov Chains inRGiorgio Alfredo Spedicato, Tae Seung Kang, Sai Bhargav Yalamanchi, Deepak Yadav, Ignacio Cord onAbstractThemarkovchainpackage aims to fill a gap within theRframework providing S4classes and methods for Easily Handling discrete time markov chains, homogeneous andsimple inhomogeneous ones as well as continuous time markov chains. The S4 classesfor Handling and analysing discrete and continuous time markov chains are presented, aswell as functions and method for performing probabilistic and statistical analysis. Finally,some examples in which the Package s functions are applied to Economics, Finance andNatural Sciences topics are : discrete time markov chains, continuous time markov chains, transition matrices,communicating classes, periodicity, first passage time, stationary IntroductionMarkov chains represent a class of stochastic processes of great interest for the wide spectrumof practical applications.

2 In particular, discrete time markov chains(DTMC) permit to modelthe transition probabilities between discrete states by the aid of with models that are based on markov chains: msm(Jackson 2011) handles Multi-State Models for panel data. mcmcR(Geyer and Johnson 2013) implements Monte Carlo markov chain approach. hmm(Himmelmann and 2010) fits hidden markov models with covari-ates. mstatefits Multi-State Models based on markov chains for survival analysis (de Wreede,Fiocco, and Putter 2011).Nevertheless, theRstatistical environment (R Core Team 2013) seems to lack a simple packagethat coherently defines S4 classes for discrete markov chains and allows to perform probabilis-tic analysis, statistical inference and applications. For the sake of completeness,markovchainis the second Package specifically dedicated to DTMC analysis, beingDTMCPack(Nichol-son 2013) the first one. Notwithstanding,markovchainpackage (Spedicato 2017) aims tooffer more flexibility in Handling DTMC than other existing solutions, providing S4 classesfor both homogeneous and non-homogeneous markov chains as well as methods suited toperform statistical and probabilistic depends on the followingRpackages:expm(Goulet, Dutang,Maechler, Firth, Shapira, Stadelmann, and 2013)2markovchainpackage: discrete markov chains inRto perform efficient matrices powers;igraph(Csardi and Nepusz 2006) to perform pretty plot-ting ofmarkovchainobjects andmatlab(Roebuck 2011), that contains functions for matrixmanagement and calculations that emulate those withinMATLAB environment.

3 Moreover,other scientific softwares provide functions specifically designed to analyze DTMC, asMath-ematica9 (Wolfram Research 2013b).The paper is structured as follows: Section2briefly reviews mathematics and definitions re-garding DTMC, Section3discusses how to handle and manage markov chain objects withinthe Package , Section4and Section5show how to perform probabilistic and statistical mod-elling, while Section6presents some applied examples from various fields analyzed by meansof Review of core mathematical General DefinitionsA DTMC is a sequence of random variablesX1, X2, .. , Xn, ..characterized by the Markovproperty (also known as memoryless property, see Equation1). The markov property statesthat the distribution of the forthcoming stateXn+1depends only on the current stateXnand doesn t depend on the previous onesXn 1, Xn 2, .. , r(Xn+1=xn+1|X1=x1, X2=x2,.., Xn=xn) =P r(Xn+1=xn+1|Xn=xn).(1)The set of possible statesS={s1, s2, .., sr}ofXncan be finite or countable and it is namedthe state space of the chain moves from one state to another (this change is named either transition or step )and the probabilitypijto move from statesito statesjin one step is named transitionprobability:pij=P r(X1=sj|X0=si).

4 (2)The probability of moving from stateitojinnsteps is denoted byp(n)ij=P r(Xn=sj|X0=si).A DTMC is called time-homogeneous if the property shown in Equation3holds. Timehomogeneity implies no change in the underlying transition probabilities as time goes r(Xn+1=sj|Xn=si) =P r(Xn=sj|Xn 1=si).(3)If the markov chain is time-homogeneous, thenpij=P r(Xk+1=sj|Xk=si) andp(n)ij=P r(Xn+k=sj|Xk=si), wherek > probability distribution of transitions from one state to another canbe represented intoa transition matrixP= (pij)i,j, where each element of position (i, j) represents the transitionprobabilitypij. , ifr= 3 the transition matrixPis shown in Equation4P= p11p12p13p21p22p23p31p32p33 .(4) Spedicato, Kang, Yalamanchi, D. Yadav, I. Cord on3 The distribution over the states can be written in the form of a stochastic row vectorx(theterm stochastic means thatPixi= 1, xi 0): , if the current state ofxiss2,x= (0 1 0).As a consequence, the relation betweenx(1)andx(0)isx(1)=x(0)Pand, recursively, we getx(2)=x(0)P2andx(n)=x(0)Pn, n > are explained in most theory books on stochastic processes, seeBr emaud(1999) andDobrow(2016) for example.

5 Valuable references online available are:Konstantopoulos(2009),Snell(1999) andBard(2000). Properties and classification of statesA statesjis said accessible from statesi(writtensi sj) if a system starting in statesihasa positive probability to reach the statesjat a certain point, , n >0 :pnij>0. If bothsi sjandsj si, thensiandsjare said to communicating class is defined to be a set of states that DTMC can becomposed by one or more communicating classes. If the DTMC is composed byonly onecommunicating class ( , if all states in the chain communicate), then it is said communicating class is said to be closed if no states outside of the class can be reachedfrom any state inside 1,siis defined as absorbing state: an absorbing state corresponds to a closed com-municating class composed by one state canonical form of a DTMC transition matrix is a matrix having a blockform, where theclosed communicating classes are shown at the beginning of the diagonal statesihas periodkiif any return to statesimust occur in multiplies ofkisteps, that iski=gcd{n:P r(Xn=si|X0=si)>0}, wheregcdis the greatest common divisor.

6 Ifki= 1the statesiis said to be aperiodic, else ifki>1 the statesiis periodic with periodki. Looselyspeaking,siis periodic if it can only return to itself after a fixed number of transitionski>1(or multiple ofki), else it is statessiandsjbelong to the same communicating class, then they have the same a consequence, each of the states of an irreducible DTMC share the same periodicity. Thisperiodicity is also considered the DTMC periodicity. It is possible to classify states accordingto their periodicity. LetTx xis the number of periods to go back to statexknowing thatthe chain starts inx. A statexis recurrent ifP(Tx x<+ ) = 1 (equivalentlyP(Tx x= + ) = 0). Inaddition:1. A statexis null recurrent if in additionE(Tx x) = + .2. A statexis positive recurrent if in additionE(Tx x)<+ .3. A statexis absorbing if in additionP(Tx x= 1) = 1. A statexis transient ifP(Tx x<+ )<1 (equivalentlyP(Tx x= + )>0).It is possible to analyze the timing to reach a certain state.

7 The first passage time (or hittingtime) from statesito statesjis the numberTijof steps taken by the chain until it arrivesfor the first time to statesj, given thatX0=si. The probability distribution ofTijis defined4markovchainpackage: discrete markov chains inRby Equation5hij(n)=P r(Tij=n) =P r(Xn=sj, Xn 16=sj, .. , X16=sj|X0=si)(5)and can be found recursively using Equation6, given thathij(n)= (n)=Xk S {sj}pikhkj(n 1).(6)A commonly used quantity related tohis its average value, themean first passage time(also expected hitting time), namely hij=Pn= n h(n) in the definition of the first passage time we letsi=sj, we obtain the first recurrence timeTi= inf{n 1 :Xn=si|X0=si}. We could also ask ourselves which is themean recurrencetime, an average of the mean first recurrence times:ri= Xk=1k P(Ti=k)Revisiting the definition of recurrence and transience: a statesiis said to be recurrent if it isvisited infinitely often, ,P r(Ti<+ |X0=si) = 1. On the opposite,siis called transientif there is a positive probability that the chain will never returntosi, ,P r(Ti= + |X0=si)> a time homogeneous markov chain with transition matrixP, a stationary distributionzis a stochastic row vector such thatz=z P, where 0 zj 1 jandPjzj= a DTMC{Xn}is irreducible and aperiodic, then it has a limit distribution andthis distri-bution is stationary.

8 As a consequence, ifPis thek ktransition matrix of the chain andz= (z1, .., zk) is the unique eigenvector ofPsuch thatPki=1zi= 1, then we getlimn Pn=Z,(7)whereZis the matrix having all rows equal toz. The stationary distribution of{Xn}isrepresented matrixAis called primitive if all of its entries are strictly positive, andwe write itA >0. Ifthe transition matrixPfor a DTMC has some primitive power, it existsm >0 :Pm>0,then the DTMC is said to be regular. In fact being regular is equivalent to being irreducibleand aperiodic. All regular DTMCs are irreducible. The counterpart isnot two absorbing statessA(source) andsB(sink), thecommittor probabilityq(AB)jis theprobability that a process starting in statesiis absorbed in statesB(rather thansA) (No e,Sch utte, Vanden-Eijnden, Reich, and Weikl 2009). It can be computed viaq(AB)j=Xk A,BPjkq(AB)kwithq(AB)A= 0 andq(AB)B= 1(8) Spedicato, Kang, Yalamanchi, D. Yadav, I. Cord on5 Note we can also define the hitting probability fromitojas the probability of ever reachingthe statejif our initial state isi:hi,j=P r(Tij< ) = Xn=0h(n)ij(9)In a DTMC with finite set of states, we know that a transient state communicates at leastwith one recurrent state.

9 If the chain starts in a transient element, once it hits a recurrentstate, it is going to be caught in its recurrent state, and we cannot expect it would go backto the initial state. Given a transient stateiwe can define theabsorption probabilityto therecurrent statejas the probability that the first recurrent state that the markov chainvisits(and therefore gets absorbed by its recurrent class) isj,f ij. We can also define themeanabsorption timeas the mean number of steps the transient stateiwould take until it hits anyrecurrent state, A short exampleConsider the following numerical example. Suppose we have a DTMC with a set of 3 possiblestatesS={s1, s2, s3}. Let the transition matrix be:P= .(10)InP,p11= is the probability thatX1=s1given that we observedX0=s1is , and is easy to see that the chain is irreducible since all the states communicate (it is madeby one communicating class only).Suppose that the current state of the chain isX0=s2, ,x(0)= (010), then the probabilitydistribution of states after 1 and 2 steps can be computed as shown in Equations (11) and(12).

10 X(1)= (0 1 0) = ( ).(11)x(n)=x(n 1)P ( ) = ( ).(12)If we were interested in the probability of being in the states3in the second step, thenP r(X2=s3|X0=s2) = : discrete markov chains inR3. The structure of the Creating markovchain objectsThe Package is loaded within theRcommand line as follows:R> library(" markovchain ")Loading required Package : matlabAttaching Package : matlab The following object is masked from Package :stats :reshapeThe following objects are masked from Package :utils :find, fixThe following object is masked from Package :base :sumThemarkovchainandmarkovchainListS4 classes (Chambers 2008) are defined within themarkovchainpackage as displayed:Class " markovchain " [ Package " markovchain "]Slots:Name: states byrow transitionMatrix nameClass: character logical matrix characterClass "markovchainList" [ Package " markovchain "]Slots:Name: markovchains nameClass.